目录
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;
}
