T1 题意简述：

 

Description

被污染的灰灰草原上有羊和狼。有N只动物围成一圈，每只动物是羊或狼。

该游戏从其中的一只动物开始，报出[1,K]区间的整数，若上一只动物报出的数是x，下一只动物可以报[x+1,x+K]区间的整数，游戏按顺时针方向进行。每只动物报的数字都不能超过M。若一只动物报了M这个数，它所在的种族就输了。问以第i只动物为游戏的开始，最后哪种动物会赢？

Input

第一行输入三个正整数N，M，K。

接下来一行N个正整数，分别表示N只动物的种类，以顺时针的方向给出。0代表羊，1代表狼。

Output

一行输出N个整数，表示若从第i只动物开始，赢的动物的种类。同上，0代表羊，1代表狼。

Data Constraint

对于60%的数据，1 ≤ N, M, K ≤ 500。

对于100%的数据，1 ≤ N, M, K ≤ 5000。

 

   解题思路：乍一看这道题是博弈论，然后它就是博弈论。

             看到博弈论想什么呢？SG函数...

             然而这道题并不是用SG函数...

             凉凉。

             正解：dp。dp[i][j]表示第i只动物如果报j，有没有必胜策略。

             逆推。初始条件即为dp[1~n][m]=0。

             考虑a[i]=a[i+1](即：此动物与后一只动物种群相等)

             若dp[i+1][j+1~j+k]中有至少一项为真(即：此动物报j可以递推到下一只动物的必胜局面)

             那么dp[i][j]=1(即：此动物报j也为必胜局面)

             a[i]!=a[i+1]同理。

             若dp[i+1][j+1~j+k]中没有一项为真(即：此动物报j可以递推到下一只动物的必败局面)

             那么dp[i][j]=1(即：此动物报j为必胜局面)

             由于n^3无法在时限内跑过，考虑优化。前缀和优化可省掉一维。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,m,k,dp[5010][5010],sum[5010],a[5010];int main(){ freopen("vode.in","r",stdin); freopen("vode.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int j=m-1;j;j--) { for(int i=n;i;i--) { if(a[i]==a[i%n+1]&&sum[i]) dp[i][j]=1; else if(a[i]!=a[i%n+1]&&!sum[i]) dp[i][j]=1; sum[i]+=dp[i%n+1][j]; if(j+k<=m) sum[i]-=dp[i%n+1][j+k]; } sum[n]+=dp[1][j]; }// for(int j=m-1;j;j--)// {// for(int i=n;i;i--)// {// if(a[i]==a[i%n+1])// {// int tmp=0;// for(int l=j+1;l<=min(j+k,m);l++)// tmp+=dp[i%n+1][l];// if(tmp) dp[i][j]=1;// }// else// {// int tmp=0;// for(int l=j+1;l<=min(j+k,m);l++)// tmp+=dp[i%n+1][l];// if(!tmp) dp[i][j]=1;// }// }// } for(int i=1;i<=n;i++) { int flag=0; for(int j=1;j<=k;j++) if(dp[i][j]){printf("%d ",a[i]);flag=1;break;} if(!flag) printf("%d ",a[i]^1); } return 0;}
          
         
        
       
      
     

 

---

 

T2 题意简述：

 

Description

有一副n*m的地图，有n*m块地，每块是下列四种中的一种：

墙：用#表示，墙有4个面，分别是前面，后面，左面，右面。

起点：用C表示，为主角的起点，是一片空地。

终点：用F表示，为主角的目的地，是一片空地。

空地：用 . 表示。

其中除了墙不能穿过，其他地方都能走。

 

主角有以下3种操作：

1.移动到相邻的前后左右的地方，花费一个单位时间。

2.向前后左右其中一个方向发射子弹，子弹沿直线穿过，打在最近的一堵墙的一面，然后墙的这面就会形成一个开口通往秘密通道。同一时间最多只能有两个开口，若出现有3个开口，出现时间最早的开口会立即消失。该操作不用时间。

3.可以从一个与开口相邻的空地跳进去，进入秘密通道，从另外一个开口正对的空地跳出来。这个过程花费一个单位时间。

地图四周都是墙，问主角最少用多少时间从C走到F。C和F

只会出现一次。

Input

第一行输入两个正整数n，m。

接下来n行，每行m个字符描述地图。

Output

输出1个整数，表示最短时间完成路途。如果无解输出nemoguce

Data Constraint

对于50%的数据，4≤ n,m≤ 15。

对于100%的数据，4≤ n,m≤ 500。

 

   解题思路：大水题...

             若当前点是路，则向四周连边。

             若当前点是路且靠墙，则向不靠墙的一侧最远处连边。

             跑一遍SPFA或者dijkstra都可以。

             好像没什么不对？70分会告诉你代码错了。

             漏了哪里呢？漏掉了不靠墙的路。

             注意，走到不靠墙的路时，可以先向四周发射传送门，然后再走到传送门处。

             因此，还要加上不靠墙的路向四周最远处连边，边权为离墙最近的道路距离+1。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define INF 0x3f3f3f3fusing namespace std;char s[501];int n,m,a[501][501],head[250001],vis[250001],dis[250001],cnt,S,T;struct uio{ int nxt,to,val;}edge[4000001];void add(int x,int y,int z){ edge[++cnt].nxt=head[x]; edge[cnt].to=y; edge[cnt].val=z; head[x]=cnt;}void spfa(){ memset(dis,0x3f,sizeof(dis)); queue
            
              que; while(!que.empty()) que.pop(); vis[S]=1; dis[S]=0; que.push(S); while(!que.empty()) { int x=que.front(); vis[x]=0; que.pop(); for(int i=head[x];i;i=edge[i].nxt) { int y=edge[i].to; if(dis[y]>dis[x]+edge[i].val) { dis[y]=dis[x]+edge[i].val; if(!vis[y]) que.push(y),vis[y]=1; } } }}int main(){ freopen("portal.in","r",stdin); freopen("portal.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",s+1); for(int j=1;j<=m;j++) { if(s[j]!='#') a[i][j]=1; if(s[j]=='C') S=(i-1)*m+j; if(s[j]=='F') T=(i-1)*m+j; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(!a[i][j]) continue; int x=(i-1)*m+j; if(a[i+1][j]) add(x,x+m,1); if(a[i-1][j]) add(x,x-m,1); if(a[i][j+1]) add(x,x+1,1); if(a[i][j-1]) add(x,x-1,1); int k1=0; while(a[i+k1+1][j]) k1++; int k2=0; while(a[i-k2-1][j]) k2++; int k3=0; while(a[i][j+k3+1]) k3++; int k4=0; while(a[i][j-k4-1]) k4++; int k=min(k1,min(k2,min(k3,k4))); if(k1!=0) add(x,x+k1*m,k+1); if(k2!=0) add(x,x-k2*m,k+1); if(k3!=0) add(x,x+k3,k+1); if(k4!=0) add(x,x-k4,k+1); } spfa(); if(dis[T]==INF) printf("nemoguce\n"); else printf("%d\n",dis[T]); return 0;}
            
           
          
         
        
       
      
     

 

---

 

T3 题意简述：

 

Description

有n个城市，标号为1到n，修建道路花费m天，第i天时，若gcd(a,b)=m-i+1，则标号为a的城市和标号为b的城市会建好一条直接相连的道路，有多次询问，每次询问某两座城市最早什么时候能连通。

Input

第一行输入三个正整数n,m,q，其中q表示询问个数。

接下来q行，每行两个正整数x，y，表示询问城市x和城市y最早什么时候连通。

Output

输出q行，每行一个正整数，表示最早连通的天数

Data Constraint

对于40%的数据，n≤ 1000，q<=100000

对于100%的数据，1 ≤ n,q≤ 100000,1<=m<=q

 

   解题思路：并查集/CDQ分治。

             这里给出并查集做法。

             考虑对每一组加边进行一组并查集操作。

             每次操作对儿子赋予一个权值，m-i+1。

             答案即为x到y的最短路径上的最大值。

             由于要求最大值，故不能进行路径压缩，只能按秩合并。

             感谢ErkkiErkko大佬及Menteur_Hxy大佬的帮助。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define INF 0x3f3f3f3fusing namespace std;int n,m,ask,fa[100001],siz[100001],val[100001],dep[100001];int find(int x){ if(x==fa[x]) return x; dep[x]=dep[fa[x]]+1; return find(fa[x]);}void add(int x,int y,int z){ int xx=find(x); int yy=find(y); if(xx!=yy) { if(siz[xx]>siz[yy]) fa[yy]=xx,siz[xx]=max(siz[xx],siz[yy]+1),val[yy]=z; else fa[xx]=yy,siz[yy]=max(siz[yy],siz[xx]+1),val[xx]=z; }}int query(int x,int y){ int ansx=0,ansy=0; if(dep[x]
           
            dep[y]) ansx=max(ansx,val[x]),x=fa[x]; while(x!=y) { ansx=max(ansx,val[x]),x=fa[x]; ansy=max(ansy,val[y]),y=fa[y]; } return max(ansx,ansy);}int main(){ freopen("pictionary.in","r",stdin); freopen("pictionary.out","w",stdout); scanf("%d%d%d",&n,&m,&ask); for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1; for(int i=m;i;i--) for(int j=2*i;j<=n;j+=i) add(j-i,j,m-i+1); for(int i=1;i<=ask;i++) { int u,v; scanf("%d%d",&u,&v); printf("%d\n",query(u,v)); } return 0;}