CodeforcesRound882(Div.2)

目录

A. The Man who became a God 

题目分析:

B. Hamon Odyssey

题目分析:

C. Vampiric Powers, anyone?

题目分析: 

---

A. The Man who became a God 

题目分析:

n个人分成k组，每一组的力量都是这样的，那么如果分成k组那么就会有k-1个力量不被统计，将力量总和减去前k-1个最大的力量就是最小的结果

#include<bits/stdc++.h> #pragma GCC optimize("Ofast") #define INF 0x3f3f3f3f #define IOS ios::sync_with_stdio(false);cin.tie(0); #define int long long #define pb push_back #define vct vector #define checkbit __builtin_popcount #define gcd __gcd #define use int T;cin>>T;while(T--) template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; } template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; } #define lowbit(x) (x&(-x)) #define yes cout<<"YES"<<endl #define no cout<<"NO"<<endl using namespace std; typedef pair<int,int>pii; const int N =105; int a[N],sb[N]; bool cmp(int a,int b){ return a>b; } signed main() {IOS use{ int n,k;cin>>n>>k;cin>>a[1]; for(int i=2;i<=n;i++){ cin>>a[i]; sb[i-1]=abs(a[i]-a[i-1]); } sort(sb+1,sb+n,cmp);int sum=0; for(int i=k;i<n;i++){ sum+=sb[i]; }cout<<sum<<endl; } return 0; } B. Hamon Odyssey

 

题目分析:

将数组分组，每个组内进行按位与运算，若想让每个组的结果加和最小，最多可以分几个组

按位与运算，是一个单调递减的过程，如果一个数字的某一位为0，那么无论多少数该位为1 ，结果都为0，对于题目来说，我们需要尽可能的将一个组的结果变为零，也即让所有的0尽可能的发挥作用，故，如果当前数按位与为零之后，将其分为一组.

#include<bits/stdc++.h> #pragma GCC optimize("Ofast") #define INF 0x3f3f3f3f #define IOS ios::sync_with_stdio(false);cin.tie(0); #define int long long #define pb push_back #define vct vector #define checkbit __builtin_popcount #define gcd __gcd #define use int T;cin>>T;while(T--) template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; } template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; } #define lowbit(x) (x&(-x)) #define yes cout<<"YES"<<endl #define no cout<<"NO"<<endl using namespace std; typedef pair<int,int>pii; const int N =2e5+7; signed main() {IOS use{ int fi=0,ans=0,x,n;cin>>n; for(int i=1;i<=n;i++){ cin>>x; if(fi==0)fi=x,ans++; fi&=x; } if(!fi)ans++; cout<<max(1ll,ans-1)<<endl; } return 0; } C. Vampiric Powers, anyone?

题目分析: 

给一个数组，可以在数组的末尾加上从~的异或和，求出数组最大的数可能是多少。

已知可以将~的异或和(qwq)提取出来，那么从1~-1的异或和(awa)就可以通过AllXOR^qwq=awa;

我们可以利用前缀和的思想，存下前项的异或和，我们可以通过XOR前面的异或和来获得各个小区间的异或和，最终遍历取最大值即可;

#include<bits/stdc++.h> #pragma GCC optimize("Ofast") #define INF 0x3f3f3f3f #define IOS ios::sync_with_stdio(false);cin.tie(0); #define int long long #define pb push_back #define vct vector #define checkbit __builtin_popcount #define gcd __gcd #define use int T;cin>>T;while(T--) #define LEN length() #define all(a) a.begin(),a.end() template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; } template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; } #define lowbit(x) (x&(-x)) #define yes cout<<"YES"<<endl #define no cout<<"NO"<<endl using namespace std; typedef pair<int,int>pii; signed main() {IOS use{ int n;cin>>n; vector<int> a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; a[i]^=a[i-1]; } vct<bool>st((1<<8|1),0); st[0]=1; int ans=0; for(int i=1;i<=n;i++) { for(int j=0;j<(1<<8);j++) { if(st[j]) ans=max(ans,j^a[i]); } st[a[i]]=1; } cout<<ans<<endl; } return 0; }