比赛地址:https://codeforc.es/contest/1698/
这一场比赛是我没有参加的一场,忘记了是什么原因了,但是我还是回过头来补了一下题。
自己单独A了三道,感觉有点简单,后悔没做了┭┮﹏┭┮,804的直接打了12000多的rank,一个题没做出来,这波血亏。
这套题感觉前三道都挺简单的。
A题:异或运算的题,没错,又是这个。不过这次我A出来了。大意是从数组a中找到一个数,令其余所有数的异或等于这个数,数据很小,可以直接暴力。
code:
#include<bits/stdc++.h> using namespace std; int main() { int t; vector<int> v; cin>>t; while(t--) { v.clear(); int x,n; scanf("%d",&n); while(n--) { scanf("%d",&x); v.push_back(x); } int ans = 0; for(int i=0;i<v.size();i++) { ans = 0; for(int j=0;j<v.size();j++) { if(i!=j) ans = ans^v[j]; } if(ans == v[i]) { printf("%d\n",ans); break; } } } }B题:大意就是输入一个k,在数组a中可以让连续k个数的值+1。让我们求出经过操作后(不限次数),我们可以得到多少a[i]>a[i-1]+a[i+1]。
这个题就是一个规律题。我们考虑k是1和不是1的情况,如果k是1,那么无疑我们可以得到一个最多数量的。我们可以将插空的数全部调整到很高的数。通过计算,我们得出奇数时ans = n/2偶数时 ans=n/2-1。然后就是k为>1的数,不难看出,我们无法增加任意一组符合条件的数,所以,其ans还是原来符合条件的那些数,可以n暴力。
code:
#include<bits/stdc++.h> using namespace std; const int maxt = 2*1e5+10; int a[maxt]; int main() { int t; cin>>t; while(t--) { memset(a,0,sizeof a); int n,k,ans=0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); if(k==1) { if(n%2==1) ans = n/2; else ans = n/2-1; cout<<ans<<endl; }else { for(int i=2;i<n;i++) { if(a[i]>a[i-1]+a[i+1]) ans++; } cout<<ans<<endl; } } }
C题:有些难度,但是感觉还好。大意就是给我们一个数组a,让我们看看是否每个三元组相加的数都可以在这个数组中找到。这里我用了我以前最常用的分析问题的方法,就是先分析复杂度,在计算暴力的复杂度,如果相差不大,那么考虑简化,如果相加过大,考虑用逆向思维找技巧。这个方法感觉可以用在很多数论题中。
如果暴力,我们可以n^3logn 解决,即暴力三层,然后set查找。 比我们预计的nlogn要多n^2。于是,我们考虑直接去寻找不符合条件的情况,也就是说我们不应该列举那么多符合情况的。我们考虑到,如果存在三个正数,那么令最高的正数加上两个正数一定不存在,所以可以pass。同理可得三个负数也是一样的。想到这里,这个题就解决了一大半了。剩下就是考虑0,如果不存在0,那么我们只有枚举三个数来计算。如果存在1个0,那么我们需要多考虑到枚举两个数相加然后加上0,也就是两个数相加,如果存在三个0,我们还需要额外考虑一个数。当然,一个数一定存在。
因为先前3个正数3个负数的思路我们缩小了数据范围,所以可以直接暴力。这里需要拿出0来单独确定情况就是怕0太多,导致tle。
code:
#include<bits/stdc++.h> using namespace std; const int maxt = 2*1e5+10; int a[maxt]; set<int>se; bool cmp(int a,int b) { return a>b; }; int main() { //限制 nlogn 或 n //暴力 n^3logn 需要简化 n^2 //如果要获取所有的三元组,其复杂程度本身超过限制。考虑从另一个角度入手,想办法让一个三元组不符合条件。 //过程性猜想:如果有三个整数,那么一定pass,因为最大的那个整数加上两个整数一定不存在 //如果存在三个负数,情况也是如此,所以se.size()应该要小于等于5(含有0) //这个时候暴力,可以只暴力出5个不相同的数,这就非常nice 了 int t; cin>>t; while(t--) { memset(a,0,sizeof a); se.clear(); int n,zheng=0,fu=0,ling=0; scanf("%d",&n); int j=1,x;; for(int i=1;i<=n;i++) { scanf("%d",&x); if(x>0) a[j++]=x,zheng++; if(x<0) a[j++]=x,fu++; if(x==0) ling++; se.insert(x); } if(zheng>=3||fu>=3) printf("NO\n"); else { int sign = 0; for(int i=1;i<j;i++) for(int k=1;k<j;k++) for(int m=1;m<j;m++) if(i!=k&&i!=m&&k!=m&&se.count(a[i]+a[k]+a[m])==0) { sign = 1; goto xy; } if(ling>0)//如果存在零,那么我们考虑两个数相加和三个数相加的情况 { for(int i=1;i<j;i++) for(int k=1;k<j;k++) if(i!=k&&se.count(a[i]+a[k])==0) { sign = 1; goto xy; } } xy: if(sign == 1) printf("NO\n"); else printf("YES\n"); } } }