2018-01-31
题目链接：http://codeforces.com/contest/776
官方题解：http://codeforces.com/blog/entry/50622
【A】水题，按照题意即可
#include#include #include using namespace std;const int maxn = 100;int main(){ string names[2], temp; int flag; cin >> names[0] >> names[1]; cout << names[0] << " " << names[1] << endl; int n; cin >> n; while(n--){ cin >> temp; if(temp==names[0]){ flag=0; } else { flag=1; } cin >> names[flag]; cout << names[0] << " " << names[1] << endl; } return 0;}
【B】思维题，应该仔细分析题目
题意：给从2开始连续的一组数2， 3 ， 4 ， 5 ........，如果 i 是 j 的质因数，则 i 与 j 的颜色不同，问给所有的数涂上色最少要几种，并求涂 色情况
思路：总共只需要2种色，一种涂质数，一种涂其他的数
分情况讨论一下即可得出上述结论。
问题转化为求质数
当是需要注意 n=1 或 n=2时情况特殊（只需要一种颜色）
【C】
自己写的线段树，预感会超时，但还是试了提交。。。。
/*题意：求区间和为 K 次方 的区间数目 线段树遍历所有区间 再判断 超时 */#include#include #include typedef long long LL;using namespace std;const int maxn = 400000;LL sum[maxn];int n, k;//int maxindex = -10;int ql, qr;void built(int root, int L, int R){ if(L==R){ scanf("%I64d", &sum[root]); ///test// cout << "i==" << root << sum[root] << endl; // if(root>maxindex) maxindex = root; return; } int m = (L+R)/2; built(root*2,L, m); built(root*2+1, m+1, R); sum[root] = sum[root*2] + sum[root*2+1];} LL query(int root, int L, int R){ if(ql<=L && R<=qr){ return sum[root]; } int m = (L+R)/2; LL ans = 0; if(ql<=m) ans += query(root*2, L, m); if(qr>m) ans += query(root*2+1, m+1, R); return ans;}int main(){ scanf("%d%d", &n, &k); built(1, 1, n); // ///test// for(int i=1;i<=maxindex;++i){// cout << i << "===" << sum[i] << endl; // } LL temp; int ans = 0; for(int i=1;i<=n;++i){ for(int j=i;j<=n;++j){ ql = i, qr = j; temp = query(1, 1, n); // ///test// cout << "i=" << i << " j=" << j << " " << temp << endl; if(temp==0) continue; while(temp%k==0){ temp/=k; } if(temp==1) ans++; } } printf("%d", ans); return 0;}
看别人的思路后写的，巧妙利用了 k ,将遍历所有区间改为便利 k 的幂的所有情况
/*【题意】 求有多少个符合要求的区间，使得区间和为 power(k,x) 其中 1<=|k|<=10 【题解】 求 sum(R) - sum(L) = power(k, x)因为power(k, x)的个数很少转化为 sum(R)-power(k, x) = sum(L)初始answer = 0 对于前缀和sum(i) 遍历所有的power(k, x)，求sum(i)-power(k,x) 如果存在 j < i 有 sum(j) == sum(i) - power(k, x) ，则 answer++ */#include#include #include
【D】这道题解法多样
（1）自己刚开始想时用了高斯消元法
对于每一个门，可以建立一个方程，设xi 为第i个开关，解方程组，看有无整数解
但是只停留在了思想上，没有去编程实现
（2）网上大部分是用并查集做的
我的理解如下：
首先 无论操作开关多少次 都可以等价为 1 次 或 0 次
因此每个 开关有两种操作， 对于每一个开关我们需要选一种操作，然后构成一个操作集合，最终使得所有门为开。
我们用dsu[i] 表示每个操作, dsu[i] 表示操作开关 i 0 次 , dsu[i + m]表示操作开关 i 1次
运用并查集选出一个操作集合，使得所有的门最终状态为开
之后在检测操作集合是否符合要求 : dsu[ i ] 和 dsu[ i + m ] 不能在同一个集合里
#include#include #include using namespace std;const int maxn = 200010;vector door[maxn]; //door[i][0] door[i][1] 分别存储控制门的两个开关 int status[maxn]; //门的初始状态 int dsu[2*maxn]; //并查集 int find(int u){ return dsu[u] = dsu[u]==u ? u : find(dsu[u]);}void un(int u, int v){ int x = find(u); int y = find(v); dsu[y] = x; //并查集此处容易写错，注意 }int main(){ int n, m; scanf("%d%d", &n, &m); for(int i=1;i<=n;++i) scanf("%d", &status[i]); for(int i=1;i<=m;++i) { int x; cin >> x; while(x--){ int d; scanf("%d", &d); door[d].push_back(i); } } for(int i=0;i<=2*maxn;++i) dsu[i] = i;//并查集初始化 //遍历门的初始状态 for(int i=1;i<=n;++i){//test cout << "x==" << door[i][0] << " y==" << door[i][1] << endl; if(status[i]){ //门开：控制该门两个开关的操作必须相同 un( door[i][0] , door[i][1] ); un( door[i][0] + m, door[i][1]+m ); } else{ //门关 ： 控制该门两个开关的操作必须不同 un( door[i][0] , door[i][1]+m ); un( door[i][0]+m , door[i][1] ); }//// //test//// for(int i=1;i<=2*m;++i) printf("%d ", dsu[i]);//// cout << endl; } for(int i=1;i<=m;++i){ if( find(i) == find(i+m) ){ printf("NO"); return 0; } } printf("YES"); return 0;}
（3）官方答案是 将题目 抽象为图论模型， 然后 dfs 染色
（4）还有用 2-SAT