A. Parity Game
problem：
在一个01串中。可以去掉最前面的一个字符；可以在后面加一个字符，若该串有奇数个‘1’则末尾加字符‘1’否则加‘0’。
问能否把a串变为b串。
think：
如果偶数个‘1’则‘0’可以在结尾任意加。又因为前面随便去掉，所以可以在想要的位置去掉前面的‘1’然后结尾加‘1’。所以偶数(n)个‘1’的串可以变成任意‘1’的个数为(<=n)的串。
如果奇数个‘1’。后面加一个‘1’就变成了上一种情况。所以奇数个'1'的串可以变成任意‘1’的个数为(<=n+1)的串。
B.
Fish Weight
problem：
Alice有n个东西，Bob有m个东西。每个东西的大小排序为[1,
k]中的一个整数。只是大小定性排序，具体多少不一定。问Alice能不能比Bob多。think：
从大往小比较，遇到Alice的比Bob的大，那就把Alice的无限变大，所以就是可能。否则就假装他俩一样大，继续比较。必到最后谁最先没了谁就输了。
code：
int main(){ int n, m, k; scanf("%d%d%d", &n, &m, &k); for(int i=0; i<n; i++){ scanf("%d", &a[i]); } for(int i=0; i<m; i++){ scanf("%d", &b[i]); } sort(a, a+n); sort(b, b+m); bool ok = false; for(int i=n-1, j=m-1; i>=0 && j>=0; i--, j--){ if(a[i]>b[j]){ ok = true; break; } else if(j==0 && i!=0){ ok = true; break; } else if(i==0){ ok = false; break; } } if(ok) puts("YES"); else puts("NO"); return 0; }
C. Splitting the Uniqueness
problem：
给出一个长度为n的s非负数序列，里面每个数字都不一样，能否有两个长度为n的非负数序列a和b，a[i]+b[i]=s[i]，且有不少于2/3的数字都不一样。
think：
请注意：s本身是每个元素都不一样的。排序后从后后2/3个，从0开始给a一个给b一个。如：“0 1 a b c d” 把“a b c d”变成“0 b 1 d-1”和“a 0 c-1 1”。因为d 比b至少大2，所以d-1>b. 因为是后2/3所以b>k(k为需要变化的个数的一半减1，在这里，需要变化的个数为4，一半为2，减1为1)
code：
struct point { int s, id; }p[N]; int a[N], b[N]; bool cmp(point x, point y){ return x.s<y.s; } int main(){ int n; scanf("%d", &n); for(int i=0; i<n; i++){ scanf("%d", &p[i].s); p[i].id = i; } int m = n-(n+2)/3; sort(p, p+n, cmp); for(int i=n-m, j=0; i<n; i++, j++){ int id = p[i].id; if(j&1){ b[id] = j/2; a[id] = p[i].s-j/2; } else{ a[id] = j/2; b[id] = p[i].s-j/2; } } for(int i=0; i<n-m; i++){ int id = p[i].id; a[id] = 0; b[id] = p[i].s; } puts("YES"); for(int i=0; i<n; i++) printf("%d ", a[i]); puts(""); for(int i=0; i<n; i++) printf("%d ", b[i]); puts(""); return 0; }
D.
Color the Carpet
problem：
给出一张n*m的图表，用不多于k种颜色涂色，使其满足图表中3/4的等于不等于关系。
think：
共有n*(m-1)+m*(n-1)个关系。我们把这个分为两部分n*(m-1)和m*(n-1)。若多的那一部分满足所有关系，少的那一部分满足一半以上的关系，就是可以了。假设n<m,即让n*(m-1)全部满足，就是让同一行的关系都满足。如果只有两个颜色，那么当这一行满足条件时，看与上一行的关系满足的是否过半，若不过半，那么这一行全部换颜色，这样与上一行的关系满足一半以上并且行内依然全部满足。(n>m的话同理)所以颜色两个就够了，当然，要特判k==1的时候。
code：
char a[N][N], b[N][N], c[N][N]; bool ans[N][N]; int main(){ int n, m, k; scanf("%d%d%d", &n, &m, &k); for(int i=0; i<n; i++){ scanf("%s", a[i]); if(i<n-1) scanf("%s", b[i]); } if(k==1){ int t=0; for(int i=0; i<n; i++){ for(int j=0; j<m-1; j++) t+=(a[i][j]=='E'?1:0); if(i==n-1) break; for(int j=0; j<m; j++) t+=(b[i][j]=='E'?1:0); } if(t*4>=3*(n*(m-1)+m*(n-1))){ puts("YES"); for(int i=0; i<n; i++){ printf("1"); for(int j=1; j<m; j++) printf(" 1"); puts(""); } } else puts("NO"); return 0; } if(m>=n){ for(int i=0; i<n; i++){ ans[i][0] = 0; for(int j=1; j<m; j++) ans[i][j] = ans[i][j-1]^(a[i][j-1]=='N'); int t=0; if(i==0) continue; for(int j=0; j<m; j++) t+=((ans[i-1][j]^(b[i-1][j]=='N'))==ans[i][j])?1:0; if(t*2<m){ for(int j=0; j<m; j++) ans[i][j] = !ans[i][j]; } } } else{ for(int j=0; j<m; j++){ ans[0][j] = 0; for(int i=1; i<n; i++) ans[i][j] = ans[i-1][j]^(b[i-1][j]=='N'); int t=0; if(j==0) continue; for(int i=0; i<n; i++){ t+=((ans[i][j-1]^(a[i][j-1]=='N'))==ans[i][j])?1:0; } if(t*2<n){ for(int i=0; i<n; i++) ans[i][j] = !ans[i][j]; } } } puts("YES"); for(int i=0; i<n; i++){ printf("%c", "12"[ans[i][0]]); for(int j=1; j<m; j++) printf(" %c", "12"[ans[i][j]]); puts(""); } return 0; }
E.
Mystic Carvings
problem：
一个圆上依次有1~2*n的数字。每个数字都有且只有另一个数字与他相连。选出三条线，使得每条线的两端之间隔的最少点(只包括被选择的6个点)的个数相等。
think:
六个点三条边有以下五种可能：
(用PPT画的图不好看。。)明显只有第1个和第4个可以。用间接法求。
令a，b为一条线的两个端点且a<b。令x为两端点都在(a, b)之间的线的个数。令y为另一侧的线的个数。令z为与之相交的线的个数。那么上图第三个就是x*y. 上图第二个和第五个就是z*(x+y),但是这里算重复了，最后/2. 求x可以用树状数组来维护。知道x了，则z=b-a-1-x*2.
又x+y+z+1=n.code：
const int N = 200009; int a[N], b[N], c[N], p[N]; int n, m; inline int lowbit(int f){ return f&(-f); } int sum(int f){ int ans = 0; for(int i=f; i>0; i-=lowbit(i)){ ans += c[i]; } return ans; } void add(int f, int g){ for(int i=f; i<=m; i+=lowbit(i)){ c[i] += g; } } int main(){ scanf("%d", &n); m = n*2; for(int i=1; i<=n; i++){ scanf("%d%d", &a[i], &b[i]); p[ a[i] ] = b[i]; p[ b[i] ] = a[i]; } long long a1 = 0; long long a2 = 0; for(int i=1; i<=m; i++){ if(p[i]>i) continue; int x = sum(i)-sum(p[i]-1); int z = i-p[i]-1-x*2; add(p[i], 1); long long y = n-1-x-z; a1 += z*(x+y); a2 += x*y; } long long nn = n; long long aa = nn*(nn-1)*(nn-2)/6; cout<<aa-a1/2-a2<<endl; return 0; }