2018年全国多校算法寒假训练营练习比赛(第五场)比赛题目题解

xiaoxiao2021-02-28  7

这场比赛中的题目考察线段树/树状数组知识的居多。线段树学习:线段树讲解

这场比赛数据不严谨,自己觉得难、当时没做出的题目,比赛后发现别人根本没用什么东西,

都是暴力过的。

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; }
转载请注明原文地址: https://www.6miu.com/read-2000191.html

最新回复(0)