题目来自ecna2017
C题：DRM Messages
首先把字符串从中间分成两半，A代表0，以此类推。计算两段字符串的字母所带表的数字之和sum1,sum2，然后把第一段中的所有字母依次往后移sum2，第二段所有字母依次往后移sum1。然后求出第二段所有字母分别 所代表的数字num[]。把第一段中的所有字母相应往后移num[]个，最后得到答案
直接模拟
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 string s; 5 int a[15005],b[15005]; 6 int main() 7 { 8 cin>>s; 9 int len=s.size(); 10 int a1=0,a2=0; 11 for(int i=0;i<len/2;i++) 12 a1+=(s[i]-'A'); 13 for(int i=len/2;i<len;i++) 14 a2+=(s[i]-'A'); 15 for(int i=0;i<len/2;i++) 16 a[i]=((s[i]-'A')+a1)%26; 17 for(int i=len/2;i<len;i++) 18 b[i-len/2]=((s[i]-'A')+a2)%26; 19 for(int i=0;i<len/2;i++) 20 a[i]=(a[i]+b[i])%26; 21 string ans=""; 22 for(int i=0;i<len/2;i++) 23 ans+=(a[i]+'A'); 24 cout<<ans<<endl; 25 return 0; 26 }
D题：Game of Throwns
n个人围成一圈，按顺时针编号0~n-1。有k次传递操作，在k次操作中有两种传递方式：1、按照顺时针往后传递x个位置 2、undo m 即按照逆时针返回m次。求最后在哪个位置
用栈来存储已经传递过的人的编号
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 struct node 5 { 6 int id,num; 7 }mp[200]; 8 string s; 9 int n,k; 10 int a[200]; 11 int fun(string t) 12 { 13 int ans=0; 14 if(t[0]=='-') 15 { 16 for(int i=1;i<t.size();i++) 17 ans=ans*10+(t[i]-'0'); 18 ans=-ans; 19 } 20 else 21 { 22 for(int i=0;i<t.size();i++) 23 ans=ans*10+(t[i]-'0'); 24 } 25 return ans; 26 } 27 stack<int>q; 28 int main() 29 { 30 cin>>n>>k; 31 for(int i=0;i<k;i++) 32 { 33 cin>>s; 34 if(s[0]=='u') 35 { 36 mp[i].id=2; 37 cin>>mp[i].num; 38 } 39 else 40 { 41 mp[i].id=1; 42 mp[i].num=fun(s); 43 } 44 } 45 int now=0; 46 q.push(now); 47 for(int i=0;i<k;i++) 48 { 49 if(mp[i].id==1) 50 { 51 now+=mp[i].num; 52 while(now<0) 53 { 54 now+=3000*n; 55 } 56 now%=n; 57 q.push(now); 58 } 59 else 60 { 61 for(int j=0;j<mp[i].num;j++) 62 q.pop(); 63 now=q.top(); 64 } 65 } 66 cout<<now<<endl; 67 return 0; 68 }
E题：Is-A? Has-A? Who Knowz-A?
只要有路径上有一个has-a，两者的关系就是has-a
is-a是路径上都是is-a
对每个字符串进行bfs。vis[][][0]表示is-a的关系，vis[][][1]表示has-a的关系
注意map的使用，可以很方便的把字符串转化成数字
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 int n,m; 5 map<string,int>mp; 6 bool vis[1005][1005][2],is[1005][1005],has[1005][1005]; 7 string s1,s2,s3; 8 int num=0; 9 void fun1(string s) 10 { 11 if(mp.count(s)) return ; 12 else mp[s]=num++; 13 return ; 14 } 15 void bfs(int x) 16 { 17 queue< pair<int,int> >q; 18 vis[x][x][0]=1; 19 q.push({x,0}); 20 while(!q.empty()) 21 { 22 pair<int,int> tmp=q.front();q.pop(); 23 for(int i=0;i<num;i++) 24 { 25 if(is[tmp.first][i]&&!vis[x][i][tmp.second]) 26 { 27 vis[x][i][tmp.second]=1; 28 q.push({i,tmp.second}); 29 } 30 if(has[tmp.first][i]&&!vis[x][i][1]) 31 { 32 vis[x][i][1]=1; 33 q.push({i,1}); 34 } 35 } 36 } 37 } 38 int main() 39 { 40 cin>>n>>m; 41 while(n--) 42 { 43 cin>>s1>>s2>>s3; 44 fun1(s1);fun1(s3); 45 if(s2[0]=='i') is[mp[s1]][mp[s3]]=1; 46 else has[mp[s1]][mp[s3]]=1; 47 48 } 49 for(int i=0;i<num;i++) 50 bfs(i); 51 for(int i=1;i<=m;i++) 52 { 53 cin>>s1>>s2>>s3; 54 if(s2[0]=='i') 55 { 56 if(vis[mp[s1]][mp[s3]][0]) 57 cout<<"Query "<<i<<": true"<<endl; 58 else 59 cout<<"Query "<<i<<": false"<<endl; 60 } 61 else 62 { 63 if(vis[mp[s1]][mp[s3]][1]) 64 cout<<"Query "<<i<<": true"<<endl; 65 else 66 cout<<"Query "<<i<<": false"<<endl; 67 } 68 } 69 return 0; 70 }
F题：Keeping On Track
输入n条路径，删除其中任意一个节点，使得剩余的节点中两个不能到达的节点对数最大，在这个基础上，添加一条路径，使得不能到达的节点对数最小
1 #include <iostream> 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 const ll maxn=10050; 6 int n,critical=-1,maxpair=-1; 7 int head[maxn],tot; 8 bool vis[maxn]; 9 struct node 10 { 11 int u,v,nextt; 12 }edge[10050*2]; 13 void addedge(int u,int v) 14 { 15 edge[++tot].u=u; 16 edge[tot].v=v; 17 edge[tot].nextt=head[u]; 18 head[u]=tot; 19 } 20 int dfs(int u) 21 { 22 int v,ans=1; 23 vis[u]=1; 24 for(int i=head[u];i;i=edge[i].nextt) 25 { 26 v=edge[i].v; 27 if(!vis[v]) 28 { 29 ans+=dfs(v); 30 } 31 } 32 return ans; 33 } 34 int dfs2(int u) 35 { 36 int v,ans=0,son=0; 37 vis[u]=1; 38 for(int i=head[u];i;i=edge[i].nextt) 39 { 40 v=edge[i].v; 41 if(!vis[v]) 42 { 43 int tmp=dfs2(v); 44 ans+=tmp*(n-tmp); 45 son+=tmp; 46 } 47 } 48 ans+=(n-son)*son; 49 ans/=2; 50 if(ans>maxpair) 51 { 52 maxpair=ans; 53 critical=u; 54 } 55 return son+1; 56 } 57 int main() 58 { 59 int u,v; 60 scanf("%d",&n); 61 for(int i=1;i<=n;i++) 62 { 63 scanf("%d %d",&u,&v); 64 addedge(u,v); 65 addedge(v,u); 66 } 67 dfs2(0); 68 memset(vis,0,sizeof(vis)); 69 vis[critical]=1; 70 int fir=0,sec=0; 71 for(int i=head[critical];i;i=edge[i].nextt) 72 { 73 v=edge[i].v; 74 if(!vis[v]) 75 { 76 int tmp=dfs(v); 77 if(tmp>fir) 78 { 79 sec=fir; 80 fir=tmp; 81 } 82 else if(tmp>sec) 83 { 84 sec=tmp; 85 } 86 } 87 } 88 printf("%d %d ",maxpair,maxpair-fir*sec); 89 return 0; 90 }
G题：A Question of Ingestion
dp
直接贴上队友代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 int dp[105][105][2]; 4 int main() 5 { 6 int n,maxp; 7 scanf("%d%d",&n,&maxp); 8 int a[105]; 9 for(int i=1; i<=n; i++) 10 scanf("%d",&a[i]); 11 int ap[105]; 12 ap[1] = maxp; 13 for(int i=2; i<=n; i++) 14 ap[i] = ap[i-1]*2/3; 15 for(int i=1; i<=n; i++) 16 { 17 dp[i][1][1]=min(a[i],ap[1]); 18 if(i>2) 19 { 20 for(int j=0;j<=i-3;j++) 21 { 22 dp[i][1][1]=max(dp[i][1][1],dp[i-3][j][1]+min(a[i],ap[1])); 23 dp[i][1][1]=max(dp[i][1][1],dp[i-3][j][0]+min(a[i],ap[1])); 24 } 25 } 26 if(i>1) 27 { 28 for(int j=0; j<=i-2; j++) 29 { 30 dp[i][0][0]=max(dp[i][0][0],dp[i-2][j][0]); 31 dp[i][0][0]=max(dp[i][0][0],dp[i-2][j][1]); 32 } 33 } 34 for(int j=1; j<=i; j++) 35 { 36 dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-1][1]+min(a[i],ap[j])); 37 dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][1]); 38 if(i>1) 39 { 40 dp[i][j][1]=max(dp[i][j][1],dp[i-2][j][1]+min(a[i],ap[j])); 41 } 42 } 43 } 44 int ans=0; 45 for(int i=1; i<=n; i++) 46 { 47 for(int j=1; j<=i; j++) 48 { 49 for(int k=0; k<2; k++) 50 { 51 ans=max(ans,dp[i][j][k]); 52 } 53 } 54 } 55 printf("%d ",ans); 56 return 0; 57 }
H题：Sheba’s Amoebas
求有多少个loop
直接bfs
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 char Map[105][105]; 6 7 int dx[8]={0,0,-1,1,-1,1,1,-1}; 8 int dy[8]={1,-1,0,0,1,1,-1,-1}; 9 int n,m; 10 int vis[105][105]; 11 void f(int x,int y) 12 { 13 int nowx; 14 int nowy; 15 for(int i=0;i<8;i++) 16 { 17 nowx = x+dx[i]; 18 nowy = y+dy[i]; 19 if(nowx>=0&&nowx<n&&nowy>=0&&nowy<m&&vis[nowx][nowy]==0&&Map[nowx][nowy]=='#') 20 { 21 vis[nowx][nowy] = 1; 22 Map[nowx][nowy] = '.'; 23 f(nowx,nowy); 24 } 25 } 26 } 27 int main() 28 { 29 memset(vis,0,sizeof(vis)); 30 scanf("%d%d",&n,&m); 31 for(int i=0;i<n;i++) 32 scanf("%s",Map[i]); 33 int ans = 0; 34 for(int i=0;i<n;i++) 35 { 36 for(int j=0;j<m;j++) 37 { 38 if(Map[i][j]=='#'&&vis[i][j]==0) 39 { 40 vis[i][j] = 1; 41 ans++; 42 f(i,j); 43 } 44 } 45 } 46 cout<<ans<<endl; 47 }
I题：Twenty Four, Again
暴力枚举四个数的组合方式，然后分别枚举三种运算符号，还有括号。看每种情况能不能形成24，最后维护一个最小值
代码尚未完成
J题：Workout for a Dumbbell
有一个人想在10台健身器材上来回运动三次，对于每一台器材他有一个运动时间，和一个休息时间。但是没台器材上都会有一个人在重复运动，他们也有相应的运动时间和休息时间。求这个人第三次在10号器材上运动完的时间是多少
这个直接模拟就行了
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 long long use[15],rec[15],u[15],r[15],t[15]; 5 int main() 6 { 7 for(int i=1; i<=10; i++) 8 cin>>use[i]>>rec[i]; 9 for(int i=1; i<=10; i++) 10 cin>>u[i]>>r[i]>>t[i]; 11 int ans=0; 12 for(int j=1; j<=3; j++) 13 { 14 for(int i=1; i<=10; i++) 15 { 16 if(t[i]>ans) 17 { 18 t[i]=max(ans+use[i],t[i]); 19 ans+=(use[i]+rec[i]); 20 21 } 22 else if(t[i]==ans) 23 { 24 t[i]=ans+u[i]+max(use[i],r[i]); 25 ans+=(u[i]+use[i]+rec[i]); 26 } 27 else 28 { 29 int tmp=(ans-t[i])%(u[i]+r[i]); 30 if(tmp<u[i]) 31 { 32 t[i]=ans+u[i]-tmp+max(use[i],r[i]); 33 ans+=(u[i]-tmp+use[i]+rec[i]); 34 } 35 else 36 { 37 t[i]=ans+max(use[i],u[i]+r[i]-tmp); 38 ans+=(use[i]+rec[i]); 39 } 40 } 41 } 42 } 43 cout <<ans-rec[10]<< endl; 44 return 0; 45 }