arc135C

时间：2023-05-29

题目
题意: 给定数组a，可以执行任意次操作。选定数组中任意一个数a[i]，令整个数组均执行^a[i].执行完操作后数组a的最大和。
思路: 可以证明不执行操作和执行操作1次包含了所有情况。

时间复杂度: O(nlogn)
代码:

// Problem: C - XOR to All// Contest: AtCoder - AtCoder Regular Contest 135// URL: https://atcoder.jp/contests/arc135/tasks/arc135_c// Memory Limit: 1024 MB// Time Limit: 2000 ms// // Powered by CP Editor (https://cpeditor.org)#include#include#include#include#include#include#include#include #include #include#include#include#include#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)#define fir(i,a,b) for(int i=a;i<=b;++i) #define mem(a,x) memset(a,x,sizeof(a))#define p_ priority_queue// round() 四舍五入 ceil() 向上取整 floor() 向下取整// lower_bound(a.begin(),a.end(),tmp,greater()) 第一个小于等于的// #define int long long //QAQusing namespace std;typedef complex CP;typedef pair PII;typedef long long ll;// typedef __int128 it;const double pi = acos(-1.0);const int INF = 0x3f3f3f3f;const ll inf = 1e18;const int N = 3e5+10;const int M = 1e6+10;const int mod = 1e9+7;const double eps = 1e-6;inline int lowbit(int x){ return x&(-x);}templatevoid write(T x){ if(x<0) { putchar('-'); x=-x; } if(x>9) { write(x/10); } putchar(x%10+'0');}template void read(T &x){ x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();} while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;}int n,m,k,T;int a[N];int cnt[N][2]; //0、1ll ans = 0;void solve(){ read(n); for(int i=1;i<=n;++i) { read(a[i]); ans += a[i]; for(int j=0;j<30;++j) { if(a[i]>>j&1) cnt[j][1]++; else cnt[j][0]++; } } for(int i=1;i<=n;++i) { ll res = 0; for(int j=0;j<30;++j) { if(a[i]>>j&1) res += 1ll*cnt[j][0]*(1<>T; // read(T); while(T--) { solve(); } return 0;}

上一篇：论文笔记WeaklySupervisedDeepDetectionNetworks

下一篇：linux-ubuntu20.04+cuda11.0.2（显卡3060Ti）+cudnn11.0+anaconda+pytorch（GPU）+pycharm史上最详细教程（持续更新ing）