A - Brain's Photos
CodeForces - 707A
题意：判断是不是彩色
题解：判断是否含有除 B W G 以外的英文字母即可
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e4+7; int main() { int n,m; scanf("%d %d",&n,&m); int flag = 1; getchar(); for (int i=0;i<n;i++) { string s; getline(cin,s); for(int i=0;i<s.size();i++) if(s[i] != 'B' && s[i] != 'W' && s[i] != ' ' && s[i] != 'G') flag = 0; // cout<<s<<endl; } if(flag) puts("#Black&White"); else puts("#Color"); }
B - Bakery
CodeForces - 707B
题意：n个城市，m条边，k个城市里有进货点。Masha要选一个没有进货点的城市开店，要选一个最近的有商店的城市进货，输出她进货时所用的最小路程。
题解：进货点和商店相邻最优然后对每个进货点扫一次就行
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e5+7; int u[maxn]; int v[maxn]; int l[maxn]; map<int,int>mp; int main() { int n,m,k; scanf("%d %d %d",&n,&m,&k); for(int i=0;i<m;i++) { scanf("%d %d %d",&u[i],&v[i],&l[i]); } int no; for(int i=0;i<k;i++) { scanf("%d",&no); mp[no] = 1; } int ans = INF; for(int i=0;i<m;i++) { if(mp[u[i]] + mp[v[i]] == 1) ans = min(ans,l[i]); } printf("%d ",ans == INF ? -1 : ans); }
C - Pythagorean Triples
CodeForces - 707C
题意：给出一条变，要求你给出另外两条构成直角三角形
题解：a2 + b2 = c2 可得 a2 = (c + b) * (c - b)。如果给的a为奇数的话，那么使得c - b = 1,c + b = a即可。如果a为偶数的话使得 c - b = 2,c + b = a * a / 2即可，化简即可。注意特殊样例 a <= 2
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; const int maxn = 1e4+7; int main() { ll n,c,b; while(~scanf("%lld",&n)) { if (n <= 2) puts("-1"); else if (n % 2 == 0) { c = n * n / 4 + 1; b = c - 2; printf("%lld %lld ", b, c); } else { c = (n * n + 1) / 2; b = c - 1; printf("%lld %lld ", b, c); } } }
D - Persistent Bookcase（DFS树）
CodeForces - 707D
题意：
有一个书架，书架有n层（分别编号为1…n），每层能放m本书（分别编号为1…m），有q次操作(分别编号为1…q）：
1 i j：在第i层第j位放一本书（如果这个位置没有书）
2 i j ：在第i层第j位取走一本书（如果这个位置有书）
3 i:翻转第i行（无书变有书，有书变无书）
4 k:回退到第k个操作后的状态，若k=0则为清空
输出每次操作后书架上有几本书。
题解：妙啊，用book的二维数组模拟书架，按照顺序建树，操作1 2 3 显然都是在上一步的基础上进行的，只需要直接向前一步连接就行，操作4就是直接连向那个顶点，之后dfs遍历这棵树，同时更新每一个节点的数目即可。妙啊 ！
样例：
19 16 14
3 10
3 8
3 3
2 5 3
1 7 15
4 0
2 11 2
1 16 3
1 16 3
3 13
1 13 3
4 9
1 5 11
3 1
按照操作的顺序得：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> using namespace std; #define ll long long const int maxn = 1e5 + 10; const int INF = 0x3f3f3f3f; struct node{ int type,i,j; int ans; }q[maxn]; bool book[1005][1005]; vector<int>g[maxn]; int n,m,query; void dfs(int t,int cur){ q[t].ans = cur; for(int i=0;i<g[t].size();i++){ int next = g[t][i]; if(q[next].type == 1){ if(book[q[next].i][q[next].j]) dfs(next,cur); else { book[q[next].i][q[next].j] = true; dfs(next,cur + 1); book[q[next].i][q[next].j] = false; } } else if(q[next].type == 2){ if(!book[q[next].i][q[next].j]) dfs(next,cur); else{ book[q[next].i][q[next].j] = false; dfs(next,cur - 1); book[q[next].i][q[next].j] = true; } } else if(q[next].type == 3){ int tot = 0; for(int j=1;j<=m;j++){ if(book[q[next].i][j]){ book[q[next].i][j] = false; tot--; } else{ book[q[next].i][j] = true; tot++; } } dfs(next,cur + tot); for(int j=1;j<=m;j++) book[q[next].i][j] = !book[q[next].i][j]; } else{ dfs(next,cur); } } } int main() { memset(book,false,sizeof book); q[0].ans = 0; scanf("%d %d %d",&n,&m,&query); for(int i=1;i<=query;i++){ scanf("%d",&q[i].type); if(q[i].type <= 2){ g[i-1].push_back(i); scanf("%d %d",&q[i].i,&q[i].j); } else if(q[i].type == 3){ g[i-1].push_back(i); scanf("%d",&q[i].i); } else{ scanf("%d",&q[i].i); g[q[i].i].push_back(i); } } dfs(0,0); for(int i=1;i<=query;i++) printf("%d ",q[i].ans); }
E - Garlands
CodeForces - 707E
题意：一个n * m矩阵，k条链(1 <= n,m,k <= 2000)，每条链绑定着一些灯泡，每个灯泡亮着时有权值，灭掉的时候权值为0。一个链条控制其上所有灯泡的亮灭。有两种操作，SWITCH i：按第i条链的开关，开变关，关变开。ASK x1,y1,x2,y2，查询以x1,y1为左上，x2,y2为右下的矩阵的权值。ASK最多2000次
题解：2000 * 2000 的数据可以使用二维的树状数组，主要是链的保证状态，当状态改变的时候如果关变开明显是加上顶点值，反之减去。在计算矩形的所有顶点值的和时候容斥一下面积就好了
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<stack> #define INF 0x3f3f3f3f #define lowbit(x) (x&(-x)) using namespace std; typedef long long LL; const int MAXN = 2e3 + 10; const int MOD = 1e9 + 7; int n,m,k; LL c[MAXN][MAXN]; struct node { int len,x,y; LL w; }Q[MAXN][MAXN]; int isOn[MAXN * MAXN],last[MAXN * MAXN]; void init() { memset(c,0,sizeof c); for(int i = 1; i <= n * n; i++) isOn[i] = last[i] = 1; } void add(int x,int y,LL val) { for(int i = x; i <= n; i += lowbit(i)) for(int j = y;j <= m; j += lowbit(j)) c[i][j] += val; } LL ask(int x,int y) { LL ans = 0; for(int i = x; i > 0; i -= lowbit(i)) for(int j = y; j > 0;j -= lowbit(j)) ans += c[i][j]; return ans; } LL all(int x1,int y1,int x2,int y2) { LL ans = ask(x2,y2) - ask(x2,y1 - 1) - ask(x1 - 1,y2) + ask(x1 - 1,y1 - 1); return ans; } int main() { scanf("%d %d %d",&n,&m,&k); init(); for(int i = 1; i <= k; i++) { scanf("%d",&Q[i][0].len); for(int j = 1; j <= Q[i][0].len; j++) { scanf("%d %d %lld",&Q[i][j].x,&Q[i][j].y,&Q[i][j].w); add(Q[i][j].x,Q[i][j].y,Q[i][j].w); } } int query; scanf("%d",&query); char str[50]; while(query--) { scanf("%s",str); if(str[0] == 'A') { for(int i = 1; i <= k; i++) { if(last[i] != isOn[i])//last和isOn不相同保证了这条链被动过 { for(int j = 1; j <= Q[i][0].len; j++) { if(isOn[i]) add(Q[i][j].x,Q[i][j].y,Q[i][j].w);//isOn为1代表原先为0，那么这条链上的每一个点都要加上权值 else add(Q[i][j].x,Q[i][j].y,-Q[i][j].w);//如果isOn为0代表这条链是关闭的，这条链上的每一个点都减去权值 } last[i] = isOn[i]; //将该条链的状态保证，以至于下次改变状态的时候可以知道和原先的状态是不一样的 } } int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); printf("%lld ",all(x1,y1,x2,y2)); } else { int tk; scanf("%d",&tk); isOn[tk] ^= 1; //改变这条链的现有的状态 } } return 0; }