http://codeforces.com/gym/101196/attachments
A題
B題
題意：一群人玩桌上足球(>4人)，分成黑白兩隊，每隊有進攻和防守兩名玩家，如果有一方失敗則失敗方的防守坐到等候席的結尾、進攻被流放到防守區再上來一個人作為進攻方。而勝利方則是攻防對換。問上場時間最長的有哪些隊伍？打印隊伍的最初狀態的姓名（先打印進攻方后打印防守方）。
思路：首先把所有玩家放入隊列中，然后求出在場上時間最長的隊伍是在第幾輪比賽時入場的放入數組中。然后依次模擬比賽，當模擬到數組中的輪數時就打印此時的隊伍狀態。
1 #include <iostream> 2 #include<bits/stdc++.h> 3 #include<string> 4 using namespace std; 5 string p[12],s,ss; 6 queue<string>que; 7 string now[2][2]; 8 int a[1005]; 9 int main() 10 { 11 int n; 12 while(cin>>n) 13 { 14 while(!que.empty()) 15 que.pop(); 16 for(int i=1; i<=n; i++) 17 { 18 cin>>s; 19 que.push(s); 20 } 21 cin>>s; 22 int len=s.length(); 23 int maxn=0; 24 int t=0; 25 for(int i=0; i<len;) 26 { 27 int k=i+1,num=0; 28 while(s[k]==s[i]) 29 { 30 num++; 31 k++; 32 } 33 if(maxn<num) 34 { 35 maxn=num; 36 t=0; 37 a[t++]=i; 38 } 39 else if(maxn==num) 40 { 41 a[t++]=i; 42 } 43 i=k; 44 } 45 int p=t; 46 for(int i=0; i<2; i++) 47 for(int j=0; j<2; j++) 48 { 49 now[j][i]=que.front(); 50 que.pop(); 51 } 52 t=0; 53 for(int i=0; i<len; i++) 54 { 55 //cout<<now[0][0]<<" "<<now[0][1]<<endl; 56 //cout<<now[1][0]<<" "<<now[1][1]<<endl; 57 if(s[i]=='W') 58 { 59 ss=now[0][0]; 60 now[0][0]=now[0][1]; 61 now[0][1]=ss; 62 que.push(now[1][1]); 63 now[1][1]=now[1][0]; 64 now[1][0]=que.front(); 65 que.pop(); 66 } 67 else if(s[i]=='B') 68 { 69 ss=now[1][0]; 70 now[1][0]=now[1][1]; 71 now[1][1]=ss; 72 que.push(now[0][1]); 73 now[0][1]=now[0][0]; 74 now[0][0]=que.front(); 75 //cout<<que.front()<<endl; 76 que.pop(); 77 } 78 if(i==a[t]&&t<p) 79 { 80 if(i==0) 81 { 82 if(s[i]=='W') 83 { 84 cout<<now[0][1]<<" "<<now[0][0]<<endl; 85 } 86 else 87 { 88 cout<<now[1][1]<<" "<<now[1][0]<<endl; 89 } 90 t++; 91 } 92 else 93 { 94 if(s[i]=='W') 95 { 96 cout<<now[0][0]<<" "<<now[0][1]<<endl; 97 } 98 else 99 { 100 cout<<now[1][0]<<" "<<now[1][1]<<endl; 101 } 102 t++; 103 } 104 } 105 } 106 107 } 108 return 0; 109 }
C題
題意：給你兩組字符串，一組是加密之后的字符串，一組是加密的前len個密文，從len+1開始密文為原文從第一個，len+2的密文為原文第二個，以此類推，問原文是什么？
思路：前len個原文字符是（s[i]-key[i]+26）%26,后面的是（s[i]-ans[i-len]+26）%26,跑一遍就能得到結果ans了
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 char ch[1005],ans[1005],tmp[1005]; 6 7 int main() 8 { 9 10 while(scanf("%s",ch)!=-1) 11 { 12 scanf("%s",tmp); 13 int len1=strlen(ch); 14 int len2=strlen(tmp); 15 for(int i=0;i<len2;i++) 16 { 17 ans[i]=(ch[i]-tmp[i]+26)%26+'A'; 18 } 19 for(int i=len2;i<len1;i++) 20 { 21 ans[i]=(ch[i]-ans[i-len2]+26)%26+'A'; 22 } 23 ans[len1]='\0'; 24 printf("%s\n",ans); 25 26 } 27 return 0; 28 }
D題
E題
題意：問一個字符串多個相同的子串組成，將相同子串變成一個單字符M，變完之后的字符串長度加上子串的長度的最小值是多少？
思路：由于所給字符串較短，直接暴力求解。求長度為從1~len/2的所有子串，然后依次于主串進行匹配，更新的最小結果即可。
1 #include <iostream> 2 #include<bits/stdc++.h> 3 #include<string> 4 using namespace std; 5 string s; 6 string c[105][105]; 7 map<string,int > mp; 8 int main() 9 { 10 while(cin>>s) 11 { 12 int len=s.size(); 13 int ans=len; 14 for(int i=1; i<len; i++) 15 { 16 for(int j=0; j<len-i; j++) 17 { 18 string ch=s.substr(j,i); 19 int tmp=0; 20 for(int k=0;k<=len-i;) 21 { 22 string p=s.substr(k,i); 23 if(p==ch) 24 { 25 tmp++; 26 k=k+i; 27 } 28 else 29 k++; 30 } 31 if(ans>len-tmp*(ch.size()-1)+ch.size()) 32 ans=len-tmp*(ch.size()-1)+ch.size(); 33 } 34 } 35 cout<<ans<<endl; 36 } 37 return 0; 38 }
F題
G題
H題
題意：給兩個凸多邊形的邊界，問這兩個凸多邊形有多少個點只包含在A內部，又有多少個點包含在B的內部，還有多少個點包含在A和B的內部（不含邊界點）。
思路：從A點開始進行搜索邊界，并在標記數組vis1中進行記錄，同理對B進行處理記錄在vis2中，然后對vis1和vis2的外圍進行標記覆蓋，最后取得圖上的字符是點的vis1或vis2為0的結果。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <set> 10 #include <stack> 11 #include <map> 12 using namespace std; 13 const int maxn = 105; 14 int vis[maxn][maxn]; 15 int vis1[maxn][maxn]; 16 int vis2[maxn][maxn]; 17 char a[maxn][maxn]; 18 int n,m; 19 int dx[] = {0,0,1,-1,}; 20 int dy[] = {1,-1,0,0,}; 21 void colorA(int i,int j,int clo); 22 void dfsA(int i,int j,int dir,int clo); 23 void colorB(int i,int j,int clo); 24 void dfsB(int i,int j,int dir,int clo); 25 void dfs(int i,int j,int clo,int vis[105][105]) 26 { 27 for(int k=0;k<4;k++) 28 { 29 int tx = i+dx[k]; 30 int ty = j+dy[k]; 31 if(vis[tx][ty]) 32 continue; 33 if(tx<0 || ty<0 || tx>n+1 || ty>m+1) 34 continue; 35 vis[tx][ty] = clo; 36 dfs(tx,ty,clo,vis); 37 } 38 } 39 bool checkA(int i,int j) 40 { 41 if(i<0||j<0||i>n||j>m) 42 return false; 43 if(vis1[i][j]==1) 44 return false; 45 return a[i][j]=='X'||a[i][j]=='A'; 46 } 47 bool checkB(int i,int j) 48 { 49 if(i<0||j<0 || i>n+1 || j>m+1) 50 return false; 51 if(vis2[i][j]==2) 52 return false; 53 return a[i][j]=='X'||a[i][j]=='B'; 54 } 55 void colorA(int i,int j,int clo) 56 { 57 if(checkA(i,j+1)) 58 dfsA(i,j+1,0,clo); 59 else if(checkA(i,j-1)) 60 dfsA(i,j-1,1,clo); 61 else if(checkA(i+1,j)) 62 dfsA(i+1,j,2,clo); 63 else if(checkA(i-1,j)) 64 dfsA(i-1,j,3,clo); 65 } 66 void colorB(int i,int j,int clo) 67 { 68 if(checkB(i,j+1)) 69 dfsB(i,j+1,0,clo); 70 else if(checkB(i,j-1)) 71 dfsB(i,j-1,1,clo); 72 else if(checkB(i+1,j)) 73 dfsB(i+1,j,2,clo); 74 else if(checkB(i-1,j)) 75 dfsB(i-1,j,3,clo); 76 } 77 void dfsA(int i,int j,int dir,int clo) 78 { 79 vis1[i][j] = clo; 80 if(checkA(i+dx[dir],j+dy[dir])) 81 dfsA(i+dx[dir],j+dy[dir],dir,clo); 82 else 83 colorA(i,j,clo); 84 } 85 void dfsB(int i,int j,int dir,int clo) 86 { 87 vis2[i][j] = clo; 88 if(checkB(i+dx[dir],j+dy[dir])) 89 dfsB(i+dx[dir],j+dy[dir],dir,clo); 90 else 91 colorB(i,j,clo); 92 } 93 int main() 94 { 95 memset(vis,0,sizeof(vis)); 96 memset(vis1,0,sizeof(vis1)); 97 memset(vis2,0,sizeof(vis2)); 98 scanf("%d %d",&n,&m); 99 for(int i=0;i<=n;i++) 100 a[n+1][i] = a[i][m+1] = a[0][i] = a[i][0] = '.'; 101 for(int i=1;i<=n;i++) 102 scanf("%s",a[i]+1); 103 int ax,ay,bx,by; 104 for(int i=0;i<=n;i++) 105 { 106 for(int j=0;j<=m;j++) 107 { 108 if(a[i][j]=='A') 109 ax=i,ay=j; 110 if(a[i][j]=='B') 111 bx=i,by=j; 112 } 113 } 114 colorA(ax,ay,1); 115 colorB(bx,by,2); 116 vis1[0][0] = 6; 117 vis2[0][0] = 6; 118 dfs(0,0,6,vis1); 119 dfs(0,0,6,vis2); 120 for(int i=0;i<=n;i++) 121 { 122 for(int j=0;j<=m;j++) 123 { 124 if(vis1[i][j]==0 && a[i][j]=='.') 125 vis1[i][j] = 3; 126 if(vis2[i][j]==0 && a[i][j]=='.') 127 vis2[i][j] = 4; 128 } 129 } 130 // for(int i=0;i<=n;i++) 131 // { 132 // for(int j=0;j<=m;j++) 133 // printf("%d ",vis1[i][j]); 134 // puts(""); 135 // } 136 // puts(""); 137 // for(int i=0;i<=n;i++) 138 // { 139 // for(int j=0;j<=m;j++) 140 // printf("%d ",vis2[i][j]); 141 // puts(""); 142 // } 143 int ans1 = 0,ans2 = 0,ans3 = 0; 144 for(int i=0;i<=n;i++) 145 { 146 for(int j=0;j<=m;j++) 147 { 148 if(vis1[i][j]==3&&a[i][j]=='.') 149 ans1++; 150 if(vis2[i][j]==4&&a[i][j]=='.') 151 ans2++; 152 if(vis1[i][j]==3&&vis2[i][j]==4&&a[i][j]=='.') 153 ans3++; 154 } 155 } 156 printf("%d %d %d\n",ans1-ans3,ans2-ans3,ans3); 157 return 0; 158 }
I題
J題
?
安裝apache2并支持php7.0)
