首页 > 代码库 > Codeforces Round #368 (Div. 2)
Codeforces Round #368 (Div. 2)
A. Brain‘s Photos
题目大意：根据照片里的颜色判断一下是黑白照片还是彩照吧。水题
1 #include <cstdio> 2 int main() 3 { 4 int n,m; 5 char ch; 6 bool flag = false; 7 scanf("%d%d",&n,&m); 8 for(int i = 0; i < n; i++) 9 {10 for(int j = 0; j < m; j++)11 {12 getchar();13 scanf("%c",&ch);14 if(ch ==‘C‘ || ch ==‘M‘ || ch ==‘Y‘)15 flag = true;16 }17 }18 if(flag)19 printf("#Color\n");20 else21 printf("#Black&White\n");22 return 0;23 }
B. Bakery
题目大意：有k个储存点，在n-k个点中，找一个离他们最近的。
1 #include <cstdio> 2 #include <cstring> 3 const int INF = 0x3f3f3f3f; 4 const int maxn = 1e5 + 5; 5 struct _ 6 { 7 int u,v,l; 8 }edge[maxn]; 9 int a[maxn];10 int main()11 {12 int n,m,k,u,v,l;13 scanf("%d%d%d", &n, &m, &k);14 for(int i = 0; i < m; i++)15 {16 scanf("%d%d%d", &u, &v, &l);17 edge[i].u = u, edge[i].v = v, edge[i].l = l;18 }19 memset(a,0,sizeof(a));20 int x;21 for(int i = 0; i < k; i++)22 scanf("%d",&x), a[x] = 1;23 int ans = INF;24 for(int i = 0; i < m; i++)25 {26 _ e = edge[i];27 if(a[e.u] != a[e.v] && e.l < ans)28 {29 ans = e.l;30 }31 }32 if(ans == INF)33 printf("-1\n");34 else35 printf("%d\n", ans);36 return 0;37 }
C. Pythagorean Triples（勾股数构造）
题目大意：给你一个数，构造勾股数。
若m是奇整数，则m,(m^2-1)/2及(m^2+1)/2便是勾股数。不是奇数的时候，就要小小考虑一下哦。还有别漏了特判。
1 #include <cstdio> 2 typedef long long LL; 3 int main() 4 { 5 LL n; 6 while(~scanf("%I64d", &n)) 7 { 8 if(n == 1 || n == 2) {printf("-1\n");continue;} 9 if(n % 2 == 1)10 {11 printf("%I64d %I64d\n", (n * n - 1) / 2, (n * n + 1) / 2);12 }13 else14 {15 LL t = n;16 while(t % 2 == 0) t /= 2;17 if(t == 1) 18 LL temp = n / 2;19 else 20 printf("%I64d %I64d\n", (t * t - 1) / 2 * (n / t), (t * t + 1) / 2 * (n / t) ) ;21 }22 }23 return 0;24 }
解法二：
（1）n<=2，无解
（2）n为偶数 k - r = 2;k + r = n ^ 2 / 2; 解得k = n ^ 2 / 4 + 1, r = n ^ 2 / 4 - 1;
（3）n为奇数 k - r = 1;k + r = n ^ 2; 解得k = (n ^ 2 + 1) / 2, r = (n ^ 2 - 1) / 2;
D. Persistent Bookcase
题目大意：详见题目吧，各种数字代表各种操作。比较特殊的一点是会，返回到之前某次操作的之前。
离线处理+dfs
把每次操作看做一个点，和前一次操作的点相连。
这个dfs超级重要，画个图你就能明白了。
1 for(int i = 0;i < vec[v].size(); i++)2 {3 dfs(vec[v][i]);4 }
1 #include <cstdio> 2 #include <vector> 3 using namespace std; 4 const int maxn = 1e5 + 5; 5 int n, m, q; 6 int type[maxn], ans[maxn], x[maxn], y[maxn], ma[1005][1005]; 7 int cnt; 8 vector<int>vec[maxn]; 9 10 void dfs(int v)11 {12 if(type[v] == 1 && ma[x[v]][y[v]] == 0) cnt++, ma[x[v]][y[v]] = 1;13 else if(type[v] == 2 && ma[x[v]][y[v]] == 1) cnt--, ma[x[v]][y[v]] = 0;14 else if(type[v] == 3)15 {16 for(int i = 0 ; i < m; i++)17 {18 if(ma[x[v]][i] == 1) cnt--, ma[x[v]][i] = 0;19 else cnt++, ma[x[v]][i] = 1;20 }21 }22 23 ans[v] = cnt;24 25 for(int i = 0;i < vec[v].size(); i++)26 {27 dfs(vec[v][i]);28 }29 30 if(type[v] == 1) cnt--, ma[x[v]][y[v]] = 0;31 else if(type[v] == 2) cnt++, ma[x[v]][y[v]] = 1;32 33 34 35 }36 else if(type[v] == 3)37 {38 for(int i = 0;i < m ;i++)39 {40 if(ma[x[v]][i] == 0) cnt++, ma[x[v]][i] = 1;41 else if(ma[x[v]][i] == 1) cnt--, ma[x[v]][i] = 0;42 }43 }44 }45 46 int main()47 {48 scanf("%d%d%d", &n, &m, &q);49 for(int i = 1; i <= q; i++)50 {51 scanf("%d%d", &type[i], &x[i]);52 if(type[i] <= 2) scanf("%d", &y[i]);53 if(type[i] == 4) vec[x[i]].push_back(i);54 else vec[i-1].push_back(i);55 }56 cnt = 0;57 dfs(0);58 for(int i = 1; i <= q; i++)59 printf("%d\n", ans[i]);60 61 return 0;62 }
E. Garlands
Codeforces Round #368 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。