首页 > 代码库 > Codeforces Round #396 (Div. 2)
Codeforces Round #396 (Div. 2)
AB都是大水题。
C题，题意稍微有点晦涩。但是还是一个比较简单的dp（虽然我不是独立的做出来的= =）。感觉我dp掌握的不是很好啊；看到这题突然想起前几天碰到的一题：不考虑顺序的整数划分问题。C题代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 #include <string> 6 using namespace std; 7 const int N = 1000 + 5; 8 typedef long long ll; 9 const int mod = 1e9 + 7; 10 11 int n; 12 char s[N]; 13 int a[30]; 14 int dp[N]; 15 int minn[N]; 16 17 int main() 18 { 19 cin >> n; 20 scanf("%s",s+1); 21 for(int i=1;i<=26;i++) scanf("%d",a+i); 22 dp[0] = 1; 23 int maxx = 0; 24 for(int i=1;i<=n;i++) minn[i] = 1111; 25 for(int i=1;i<=n;i++) 26 { 27 int temp = 1111; 28 for(int j=i;j>=1;j--) 29 { 30 int now = s[j] - ‘a‘ + 1; 31 temp = min(temp, a[now]); 32 if(temp >= i-j+1) 33 { 34 dp[i] = (dp[i] + dp[j-1]) % mod; 35 minn[i] = min(minn[i], minn[j-1] + 1); 36 maxx = max(maxx, i-j+1); 37 } 38 else break; 39 } 40 } 41 cout << dp[n] << endl; 42 cout << maxx << endl; 43 cout << minn[n] << endl; 44 return 0; 45 }
D题，是个带权并查集。我记得去年寒假的时候写过这种题目，然后就一直没接触过了= =。近几天稍微复习一下这个专题好了。代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 #include <string> 6 #include <map> 7 #include <vector> 8 #include <set> 9 using namespace std; 10 const int N = 100000 + 5; 11 typedef long long ll; 12 const int mod = 1e9 + 7; 13 typedef pair<int,int> pii; 14 15 int n,m,q; 16 int root[N],rnk[N]; 17 map<string,int> M; 18 void init() 19 { 20 for(int i=1;i<=n;i++) root[i] = i, rnk[i] = 0; 21 } 22 int find(int x) 23 { 24 if(x == root[x]) return x; 25 int y = root[x]; 26 root[x] = find(root[x]); 27 rnk[x] = (rnk[x] + rnk[y]) % 2; 28 return root[x]; 29 } 30 bool connect(int x,int y,int op) 31 { 32 int rx = find(x); 33 int ry = find(y); 34 if(rx != ry) 35 { 36 root[ry] = rx; 37 rnk[ry] = (op + rnk[x] - rnk[y] + 2) % 2; 38 } 39 else 40 { 41 int temp = (rnk[x] - rnk[y] + 2) % 2; 42 if(temp != op) return false; 43 } 44 return true; 45 } 46 47 int main() 48 { 49 cin >> n >> m >> q; 50 for(int i=1;i<=n;i++) 51 { 52 string s; 53 cin >> s; 54 M[s] = i; 55 } 56 init(); 57 while(m--) 58 { 59 int op; 60 string x,y; 61 cin >> op >> x >> y; 62 puts(connect(M[x],M[y],op-1) ? "YES" : "NO"); 63 } 64 while(q--) 65 { 66 string x,y; 67 cin >> x >> y; 68 int rx = find(M[x]); 69 int ry = find(M[y]); 70 if(rx != ry) puts("3"); 71 else printf("%d\n",(rnk[M[x]]-rnk[M[y]]+2) % 2 + 1); 72 } 73 return 0; 74 }
E题还是比较有意思的。具体做法是在dfs的时候二进制下把各个位置的已经出现过的1和0记录下来，然后直接做贡献即可。具体见代码：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <iostream> 5 #include <string> 6 #include <map> 7 #include <vector> 8 #include <set> 9 using namespace std; 10 const int N = 100000 + 5; 11 typedef long long ll; 12 const int mod = 1e9 + 7; 13 typedef pair<int,int> pii; 14 15 int n; 16 vector<int> G[N]; 17 int a[N]; 18 int cnt[N][30][2]; 19 ll dfs(int u,int fa) 20 { 21 ll ans = 0; 22 for(int i=0;i<22;i++) 23 { 24 cnt[u][i][(a[u] & (1<<i)) != 0]++; 25 ans += (1LL<<i) * cnt[u][i][1]; 26 } 27 for(int now=0;now<G[u].size();now++) 28 { 29 int v = G[u][now]; 30 if(v == fa) continue; 31 ans += dfs(v,u); 32 for(int i=0;i<22;i++) 33 { 34 for(int j=0;j<2;j++) 35 { 36 ans += (1LL<<i) * cnt[u][i][j] * cnt[v][i][j^1]; 37 } 38 for(int j=0;j<2;j++) 39 { 40 cnt[u][i][j] += cnt[v][i][j ^ ((a[u] & (1<<i))) != 0]; 41 } 42 } 43 } 44 return ans; 45 } 46 47 int main() 48 { 49 cin >> n; 50 for(int i=1;i<=n;i++) scanf("%d",a+i); 51 for(int i=1;i<n;i++) 52 { 53 int x,y; 54 scanf("%d%d",&x,&y); 55 G[x].push_back(y); 56 G[y].push_back(x); 57 } 58 cout << dfs(1,-1) << endl; 59 return 0; 60 }
Codeforces Round #396 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。