【codeforces】Codeforces Round #371 (Div. 2)

B

题目大意

给你长度为n的数列a，问能否通过指定一个x，对序列中的一部分数字进行+x或-x的操作，使得序列中的所有数字相等

---

脑洞法？ QAQ 没有证明，就是感觉这个最终数字有三种情况 1、最终数字为max( ai ) 2、最终数字为min( ai ) 3、最终数字是max( ai ) + min( ai ) >> 1 没有证明就是感觉……

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int MAXN = 100000 + 5; int n; int num[MAXN]; bool to_fox() { int to = num[1] + num[n] >> 1; int x = num[n] - to; for(int i = 1;i <= n;i ++) if(abs(num[i] - to) != x && num[i] != to) return false; return true; } bool to_two() { for(int i = 1;i <= n;i ++) if(num[i] != num[1] && num[i] != num[n]) return false; return true; } int main() { scanf("%d",&n); for(int i = 1;i <= n;i ++) scanf("%d",&num[i]); sort(num + 1,num + n + 1); if(!to_fox() && !to_two()) puts("NO"); else puts("YES"); return 0; }

C

题目大意

维护一个可重集，实现三种操作 1、+ ai 向集合中加入 ai 2、- ai 删除一个 ai 3、？ ai 问奇偶性符合 ai 的有多少个，1代表奇数，0代表偶数 //如果位数不够就补0

---

嘛…… 审题难度很大2333333 最初的想法是维护一个数组， num[i][j] 是 10i 那一位上的奇偶性为j的有多少个 A:

3 +11 +22 ?10

…… 额好吧 来一棵trie树

嘛好长时间不打trie了手生了…… 注意的事情嘛……

gets不带清空的 比如gets了一个123456789 然后又gets了一个2333 那么数组成了 2333\06789 恩恩就为这个WA了一大会……

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cctype> using namespace std; const int MAXN = 10000000 + 5; const int LOG = 18; int n; int tree[MAXN][2]; int sz; void scanf(char &c) { c = getchar(); while(isspace(c)) c = getchar(); return; } int root = 0; int tag[MAXN]; void insert(char num[]) { int x = root; for(int i = 0;i <= LOG;i ++) { if(!tree[x][num[i]]) tree[x][num[i]] = ++sz; x = tree[x][num[i]]; } tag[x] ++; return; } void del(char num[]) { int x = root; for(int i = 0;i <= LOG;i ++) x = tree[x][num[i]]; tag[x] --; return; } int ask(char num[]) { int x = root; for(int i = 0;i <= LOG;i ++) x = tree[x][num[i]]; return tag[x]; } char q; char num[30]; int main() { scanf("%d",&n); while(n --) { scanf(q); memset(num,0,sizeof(num)); getchar(); gets(num); int l = strlen(num); for(int i = 0;i + i < l;i ++) swap(num[i],num[l - i - 1]); for(int i = 0;i <= LOG;i ++) num[i] %= 2; switch(q) { case '+': insert(num); break; case '-': del(num); break; case '?': printf("%d\n",ask(num)); break; } } return 0; }