这场比赛中的题目考察线段树/树状数组知识的居多。线段树学习：线段树讲解
这场比赛数据不严谨，自己觉得难、当时没做出的题目，比赛后发现别人根本没用什么东西，
都是暴力过的。
A-逆序数
/******************************************************************************************************* Date 2018/2/25 Author Wen Yaxin 解题思路：求解逆序数方法很多，可以用线段树去求解，可以用归并排序去做， 如果数据规模不大，甚至可以直接暴力。在此用线段树求解逆序数。线段树的 节点代表的区间用来维护该区间内有多少个数，对于题目给出的数，逆序插入 线段树内，当要把num插入线段树前，寻找已经插入到线段树中的数有多少是小于 num的，则查询【0，num-1】区间内存在多少个数字即可。将查询到的结果一一 累加到答案上。需要注意的问题是，按照题目的范围，如果给出十万个数字，并且 从大到小给出，则最后答案的范围会超int类型，所以解题时候数据类型需要用 long long 变量含义： sum:sum是线段树的节点需要维护的值，即该区间中存在多少数字。 arr:用来逆序存储题目给出的数据。 方法含义： push_up:更新当前节点的值。 build:构建线段树 Insert:将元素插入到线段树内 query:查询某个区间内存在多少个数字 ***************************************************************************************************/ #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define lchild left,mid,root<<1 #define rchild mid+1,right,root<<1|1 using namespace std; const int maxn = 100000+5; long long sum[maxn*4]; int arr[maxn]; void push_up(int root) { sum[root] = sum[root<<1] + sum[root<<1|1]; } void build(int left,int right,int root) { sum[root] = 0; if(left == right) { return; } int mid = (left+right)/2; build(lchild); build(rchild); } void Insert(int pos,int left,int right,int root) { if(left == right) { sum[root]++; //注意这里是++,因为某个数可能出现多次。 return; } int mid = (left+right)/2; if(pos <= mid) Insert(pos,lchild); else Insert(pos,rchild); push_up(root); } long long query(int L,int R,int left,int right,int root) { if(L<=left && right<=R) { return sum[root]; } int ans = 0; int mid = (left+right)>>1; if(L<=mid) ans += query(L,R,lchild); if(R>mid) ans += query(L,R,rchild); return ans; } int main() { int n,Max; long long ans; while(~scanf("%d",&n)) { ans = 0; Max = 0; for(int i = n-1; i >= 0; i--) { scanf("%d",&arr[i]); if(arr[i]>Max) { Max = arr[i]; } } build(0,Max,1); for(int i = 0; i < n; i++) { if(arr[i] != 0) { ans += query(0,arr[i]-1,0,Max,1); } Insert(arr[i],0,Max,1); } printf("%lld\n",ans); } return 0; }B-Big Water Problem
/******************************************************************************************* Date 2018/2/25 Author Wen Yaxin 解题思路：线段树单点更新，区间查询，裸的线段树题目。 变量含义： sum:维护区间的和 方法含义： push_up:更新当前节点的值。 build:构建线段树 update:完成将某个位置的数加上一个数字 query:查询区间和值 ********************************************************************************************/ #include <iostream> #include <stdio.h> #include <string.h> #define lchild left,mid,root<<1 #define rchild mid+1,right,root<<1|1 using namespace std; const int maxn = 1e6+2; int sum[maxn<<2]; void push_up(int root) { sum[root] = sum[root<<1] + sum[root<<1|1]; } void build(int left,int right,int root) { sum[root] = 0; if(left == right) { scanf("%d",&sum[root]); return; } int mid = (left+right)/2; build(lchild); build(rchild); push_up(root); } void update(int pos,int value,int left,int right,int root) { if(left == right) { sum[root] += value; return; } int mid = (left+right)/2; if(pos <= mid) update(pos,value,lchild); else update(pos,value,rchild); push_up(root); } int query(int L,int R,int left,int right,int root) { if(L<=left && right<=R) { return sum[root]; } int mid = (left+right)/2; int ans = 0; if(L<=mid) ans += query(L,R,lchild); if(R>mid) ans += query(L,R,rchild); return ans; } int main() { int n,m,f,x,y; while(~scanf("%d%d",&n,&m)) { build(1,n,1); while(m--) { scanf("%d%d%d",&f,&x,&y); if(f == 1) { update(x,y,1,n,1); } else { printf("%d\n",query(x,y,1,n,1)); } } } return 0; }C-字符串的问题
/*************************************************************** Date 2018/2/25 Author Wen Yaxin 解题思路：比赛时候没有写，比赛完发现用暴力枚举，使用 C++中string的函数就能过。 变量含义： str:题目所给字符串 prefix:前缀 suffix:后缀 mid:中间的字符串 **********************************************************************/ #include <iostream> #include <stdio.h> #include <string> using namespace std; int main() { string str,prefix,suffix,mid; cin>>str; string ans = "Just a legend"; int len = str.length(); if(len < 3) { cout<<ans<<endl; } else { int index = 1; mid = str.substr(1,len-2); while(index < len) { prefix = str.substr(0,index); suffix = str.substr(len-index,len-1); if(prefix == suffix) { if((int)mid.find(prefix) != -1) { ans = prefix; } } index++; } cout<<ans<<endl; } return 0; }D-集合问题
/*********************************************************************************************** Date 2018/2/25 Author Wen Yaxin 解题思路：对于一个元素，只有两种情况，要么属于A集合，要么属于B集合。 如果都不满足，则无解。因此枚举每个元素对其考虑归属问题。 1.用一个数组保存题目给出的原数列，因为输出答案的时候需要进行对应情况的输出。 2.用一个数组对原数列进行排序。由于数列可能出现数字重复。 3.对于以排序的数列，对其去重，即每个数字只保存一次，并在用一个数组对应记录其出现的次数 4.枚举元素，对于元素x，首先判断其是否归属于B，则对b-x，在数组中进行二分查找，只要能找到 就说明数列中有元素可以匹配，如果查找到的是自己，则元素x全属于B集合，查找到的是其他元素， 则要取两个数字的最少数量。该元素剩余的数量，在考虑是否属于集合A。 5.在此过程中，只用记录一下一个元素，假设其为N个，N个中有几个属于集合B。 6.根据题目给出的数列，在存储单次数字的数组进行二分查找。 误区：之前做的时候思路还是有点偏差，同样的思路，开始的时候，我认为只有数字为偶数个 的时候，才可能有解。并且如果元素自己和自己匹配，采用错误的思想，认为两个相同的元素 算成两个数字匹配在一起。事实上自己和自己匹配，只要自身属于某个集合，单个元素就是合法 的。因此，奇数个数字也可能匹配。 比如： 3 2 3 1 1 1 答案： YES 0 0 0 变量含义： num[i]:num[i]用来记录某个数字出现的次数 arr1:用来存储去重后的数列。 arr2:用来存储题目给出的原数列 sortedArr:开始和arr2一样，但是该数组用来排序使用 inSetB:记录某元素有多少个属于集合B。 方法含义： binarySearch:对某元素进行二分查找。 **********************************************************************************************/ #include <iostream> #include <stdio.h> #include <string> #include <algorithm> #include <string.h> using namespace std; const int maxn = 1e5+10; int num[maxn]; int arr1[maxn]; int arr2[maxn]; int sortedArr[maxn]; int inSetB[maxn]; int binarySearch(int value,int left,int right) { int mid; while(left <= right) { mid = (left+right)/2; if(arr1[mid] == value) { return mid; } else if(arr1[mid] > value) { right = mid - 1; } else { left = mid + 1; } } return -1; } int main() { int n,a,b,cnt,pos; while(~scanf("%d%d%d",&n,&a,&b)) { for(int i = 0; i < n; i++) { scanf("%d",&arr2[i]); sortedArr[i] = arr2[i]; } sort(sortedArr,sortedArr+n); //对数组进行排序 memset(num,0,sizeof(num)); //对数字出重并存储该数字出现的次数。 int pre = sortedArr[0]; num[0] = 1; arr1[0] = pre; cnt = 0; for(int i = 1; i < n; i++) { if(sortedArr[i] != pre) { cnt++; pre = sortedArr[i]; arr1[cnt] = pre; } num[cnt]++; } memset(inSetB,0,sizeof(inSetB)); int index = 0,x,Min; //枚举每个元素，判断其归属。 bool flag = true; while(index <= cnt) { //先考虑是否可以归属于集合B if(num[index]) { x = b - arr1[index]; pos = binarySearch(x,0,cnt); //arr1[index]不可能属于集合B if(pos != -1) { if(index == pos) { //考虑与它匹配的是其自己 inSetB[index] = num[index]; num[index] = 0; } else { //和其他数匹配 Min = min(num[index],num[pos]); inSetB[index] += Min; inSetB[pos] += Min; num[index] -= Min; num[pos] -= Min; } } } //然后考虑剩余的属于A if(num[index]) { x = a - arr1[index]; pos = binarySearch(x,0,cnt); if(pos != -1) { if(index == pos) { num[index] = 0; } else { Min = min(num[index],num[pos]); num[index] -= Min; num[pos] -= Min; } } } //处理过的元素必须完全在数组中找到匹配，处理过后未匹配的个数应该是0 if(num[index]) { flag = false; break; } index++; } if(flag) { printf("YES\n"); pos = binarySearch(arr2[0],0,cnt); if(inSetB[pos]) { printf("1"); inSetB[pos]--; } else { printf("0"); } for(int i = 1; i < n; i++) { pos = binarySearch(arr2[i],0,cnt); if(inSetB[pos]) { printf(" 1"); inSetB[pos]--; } else { printf(" 0"); } } printf("\n"); } else { printf("NO\n"); } } return 0; }E-情人节的电灯泡
/*************************************************************** Date 2018/2/25 Author Wen Yaxin 解题思路：题目数据弱了，暴力也能过。按照题目数据范围计算，暴力在一秒时间 内极限情况是不能过的。但是正确保险的做法是用二维的树状数组。 **********************************************************************/ #include <iostream> #include <stdio.h> using namespace std; const int maxn = 1003; int arr[maxn][maxn]; int main() { int n,m,op,x1,y1,x2,y2; while(~scanf("%d%d",&n,&m)) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { scanf("%d",&arr[i][j]); } } while(m--) { scanf("%d",&op); if(op == 1) { scanf("%d%d",&x1,&y1); arr[x1][y1] = !arr[x1][y1]; } else { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); int ans = 0; for(int i = x1; i <= x2; i++) { for(int j = y1; j <= y2; j++) { if(arr[i][j]) ans++; } } printf("%d\n",ans); } } } return 0; }F-The Biggest Water Problem
/**************************************************************************** Date 2018/2/25 Author Wen Yaxin 解题思路：考察数位分离。 方法含义： fun:对n进行数位分离，并算出数位加和。 **************************************************************************/ #include <iostream> #include <stdio.h> #include <string.h> using namespace std; int fun(int n) { int ans = 0; while(n) { ans += n; n = n/10; } return ans; } int main() { int n; while(~scanf("%d",&n)) { while(n >= 10) { n = fun(n); } printf("%d\n",n); } return 0; }G-送分啦-QAQ
/******************************************************************************** Date 2018/2/25 Author Wen Yaxin 解题思路：简单博弈题，通过分析，可以知道这个博弈 和斐波那契数列相关。斐波那契数列从2，3，开始往后 推到，如果n是斐波那契数，则小傻子赢，否则小仙女赢。 方法含义： fun:求以斐波那契数列并制成表 binarySearch:在斐波那契而数列中进行二分查找操作。 ********************************************************************************/ #include <iostream> #include <stdio.h> using namespace std; long long f[100]; void fun() { f[0] = 2; f[1] = 3; for(int i = 2; i < 40; i++) { f[i] = f[i-1] + f[i-2]; } } int binarySearch(int n) { int low,high,mid; low = 0; high = 39; while(low<=high) { mid = (low+high)/2; if(f[mid] == n){ return mid; } else if(f[mid]>n) { high = mid-1; } else { low = mid+1; } } return -1; } int main() { fun(); int n; while(~scanf("%d",&n)) { int temp = binarySearch(n); if(temp == -1) { printf("Xian\n"); } else { printf("Sha\n"); } } return 0; }H-Tree Recovery
/*************************************************************** Date 2018/2/25 Author Wen Yaxin 解题思路：线段树基础题，区间更新，区间查询。 变量含义： sum:区间和值。 lazy:区间懒惰标记 方法含义： push_up:更新当前节点值。 push_down:下推标记 build:构建线段树 update:在某个区间上的值都加上一个数 query:查询区间和值 **********************************************************************/ #include <iostream> #include <stdio.h> #define lchild left,mid,root<<1 #define rchild mid+1,right,root<<1|1 using namespace std; const int maxn = 1e6+10; int sum[maxn<<2]; int lazy[maxn<<2]; void push_up(int root) { sum[root] = sum[root<<1] + sum[root<<1|1]; } void push_down(int root,int left,int right) { //说明该节点有标记 int mid = (left+right)/2; if(lazy[root]>0) { //求左区间的长度 int leftLen = mid-left+1; //求右区间的长度 int rightLen = right-mid; sum[root<<1] += leftLen*lazy[root]; //更新右区间和值 sum[root<<1|1] += rightLen*lazy[root]; //下推标记到左区间 lazy[root<<1] += lazy[root]; //下推标记到右区间 lazy[root<<1|1] += lazy[root]; //当前节点标记下推完毕，恢复成无标记状态 lazy[root] = 0; } } void build(int left,int right,int root) { sum[root] = 0; lazy[root] = 0; if(left == right) { scanf("%d",&sum[root]); return; } int mid = (left+right)/2; build(lchild); build(rchild); push_up(root); } void update(int L,int R,int add,int left,int right,int root) { if(L<=left && right<=R) { sum[root] += (right-left+1)*add; lazy[root] += add; return; } push_down(root,left,right); int mid = (left+right)/2; if(L<=mid) update(L,R,add,lchild); if(R>mid) update(L,R,add,rchild); push_up(root); } int query(int L,int R,int left,int right,int root) { if(L<=left && right<=R) { return sum[root]; } push_down(root,left,right); int mid = (left+right)/2; int ans = 0; if(L<=mid) ans += query(L,R,lchild); if(R>mid) ans += query(L,R,rchild); return ans; } int main() { int N,M,a,b,c; char op; while(~scanf("%d%d",&N,&M)) { build(1,N,1); while(M--) { scanf(" %c",&op); if(op == 'C') { scanf("%d%d%d",&a,&b,&c); update(a,b,c,1,N,1); } else { scanf("%d%d",&a,&b); printf("%d\n",query(a,b,1,N,1)); } } } return 0; }