T1 神奇的幻方  就只是一道模拟题 水水水

#include
      
       #include
       
        #include
        
         using namespace std;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int map[55][55],x[2507],y[2507],n;int main(){    n=read();    map[1][(n+1)/2]=1;    x[1]=1; y[1]=(n+1)/2;    for(int i=2;i<=n*n;i++){        int nx=x[i-1],ny=y[i-1];        if(nx==1&&ny
        
       
      

T2 信息传递

这道题呢 搞一波tarjan缩点 最小的环就是答案了哇 不过一个点自成一环的不能算

#include
      
       #include
       
        #include
        
         using namespace std;const int M=250007;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int n,ans=M;int top,st[M],book[M];int low[M],dfn[M],sum;int first[M],cnt;struct node{
    int to,next;}e[2*M];void ins(int a,int b){sum++; e[sum].to=b; e[sum].next=first[a]; first[a]=sum;}void dfs(int x){    dfn[x]=low[x]=++sum;    st[++top]=x;     book[x]=1;    for(int i=first[x];i;i=e[i].next){        int now=e[i].to;        if(!dfn[now]){            dfs(now);            low[x]=min(low[x],low[now]);        }        if(book[now]) low[x]=min(low[x],dfn[now]);    }    if(low[x]==dfn[x]){        int sum=1;        book[x]=0;        while(st[top]!=x){            int now=st[top--];            book[now]=0;            sum++;        }        top--;        if(sum>1) ans=min(ans,sum);    }}int main(){    int x;    n=read();    for(int i=1;i<=n;i++) x=read(),ins(i,x);    for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);    printf("%d\n",ans);    return 0;}
        
       
      

T3 斗地主

很佩服写这道题的人 我比较懒所以就跳了...23333

 好的跑回来补题了 其实这道题没有想象中那么恶心

考虑到如果没有顺子出牌次数应该是一定的

所以dfs枚举顺子的怎么打 然后就算一波答案就好啦 

orz vijos的一百个测试数据

#include
      
       #include
       
        #include
        
         #define LL long longusing namespace std;const int inf=0x3f3f3f3f;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int T,n,x,ans;int num[15],sum[15];int calc(){    int cnt=0,f=0; memset(sum,0,sizeof(sum));    for(int i=0;i<=13;i++) sum[num[i]]++;    if(num[0]==2) f=1;    while(sum[4]&&sum[2]>=2) cnt++,f=0,sum[4]--,sum[2]-=2;    while(sum[4]&&sum[1]>=2) cnt++,sum[4]--,sum[1]-=2;    while(sum[4]&&sum[2]) cnt++,f=0,sum[4]--,sum[2]--;    if(f) cnt++,sum[2]--;    while(sum[3]&&sum[2]) cnt++,sum[3]--,sum[2]--;    while(sum[3]&&sum[1]) cnt++,sum[3]--,sum[1]--;    return cnt+sum[1]+sum[2]+sum[3]+sum[4];}void dfs(int step){    if(step>=ans) return ;    ans=min(ans,step+calc());    for(int i=2;i<=13;i++){        int now=i;        while(num[now]>=3) now++;        if(now-i>=2){            for(int j=i+1;j
         
          =2) now++;        if(now-i>=3){            for(int j=i+2;j
          
           =5){            for(int j=i+4;j
          
         
        
       
      

 

T4 跳石头   这就是道简单的二分

#include
      
       #include
       
        #include
        
         using namespace std;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int s[50007],n,m,v;int l,r,k,old;int pd(int w){    int ans=0,sum=0;    for(int i=1;i<=n;i++)    {        if(s[i]-sum<=w) ans++;        else    sum=s[i];    }    return ans<=m;}int main(){    v=read(); n=read(); m=read();    l=0; r=v+1;    for(int i=1;i<=n;i++) s[i]=read();    n++; s[n]=v;    while(l<=r){        int mid=(l+r)>>1;        if(pd(mid)) l=mid+1;        else r=mid-1;    }    printf("%d\n",l);    return 0;}
        
       
      

T5 子串 这道题就是个DP 自己讲得不好 推荐个博客吧

#include
      
       #include
       
         #include
        
         using namespace std;const int M=1507,mod=1000000007;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int n,m,cnt,now,last=1;char a[M],b[M];int f[2][M][M],s[2][M][M];int main(){    n=read(); m=read(); cnt=read(); //printf("[%d %d %d]\n",n,m,cnt);    scanf("%s %s",a+1,b+1); //printf("%s %s",a+1,b+1);    s[0][0][0]=s[1][0][0]=1;    for(int i=1;i<=n;i++){        now^=1; last^=1;        for(int j=1;j<=m;j++){            if(a[i]==b[j]) for(int k=1;k<=cnt;k++)             f[now][j][k]=(f[last][j-1][k]+s[last][j-1][k-1])%mod,s[now][j][k]=(s[last][j][k]+f[now][j][k])%mod;            else for(int k=1;k<=cnt;k++)             f[now][j][k]=0,s[now][j][k]=s[last][j][k];        }    }    printf("%d\n",s[n%2][m][cnt]);    return 0;}
        
       
      

T6 运输计划  

 这是道lca加二分 果然自己还是太弱了没写出来 看了波题解才懂的 orzzsn

我感觉吧 sum处理的时候就像是打标记一样所以sum【l【i】】++，sum【r【i】】++，sum【lca【i】-=2； 就是把l【i】到r【i】的路径打一波标记好处理 2333

具体看思诺大爷的题解吧 orz

#include
      
       #include
       
        #include
        
         using namespace std;const int M=350007;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
    if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int l[M],r[M],lca[M],dis[M],deep[M],f[M][25],sum[M],v[M],T[M],vis[M];int n,m,x,y,w;int cnt,first[M];struct node{
    int to,next,w;}e[2*M];void ins(int a,int b,int w){cnt++; e[cnt].to=b; e[cnt].w=w; e[cnt].next=first[a]; first[a]=cnt;}void insert(int a,int b,int w){ins(a,b,w); ins(b,a,w);}void dfs(int x){    vis[x]=1;    for(int i=1;(1<
         
          <=deep[x];i++) f[x][i]=f[f[x][i-1]][i-1];    for(int i=first[x];i;i=e[i].next){        int now=e[i].to;        if(!vis[now]){            deep[now]=deep[x]+1;            v[now]=e[i].w;            dis[now]=dis[x]+v[now];            f[now][0]=x;            dfs(now);        }    }}int find(int x,int y){    if(deep[x]
          
           =0;i--)     if((1<
           
            <=deep[x]&&f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0];}void push_sum(int x){ for(int i=first[x];i;i=e[i].next){ int now=e[i].to; if(now!=f[x][0]) push_sum(now),sum[x]+=sum[now]; }}int check(int mid){ int cnt=0,cmax=0; for(int i=1;i<=n;i++) sum[i]=0; for(int i=1;i<=m;i++) if(T[i]>mid){ cnt++; cmax=max(cmax,T[i]-mid); sum[l[i]]++; sum[r[i]]++; sum[lca[i]]-=2; } push_sum(1); for(int i=1;i<=n;i++) if(sum[i]==cnt&&v[i]>=cmax) return 1; return 0;}int main(){ n=read(); m=read(); for(int i=1;i
            
             >1; if(check(mid)) R=mid-1; else L=mid+1; } printf("%d\n",L); return 0;}