- 贪心
#includeB. Divan and a New Project 分析:#define int long long using namespace std; const int N=1e6+5; int a[N]; void solve() { int n,l,r,k; cin>>n>>l>>r>>k; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); int ans=0; for(int i=1;i<=n;i++) { if(a[i]>=l && a[i]<=r && a[i]<=k) { ans++; k-=a[i]; } } cout<>T; while(T--) solve(); }
- 贪心+排序
#includeC. Divan and bitwise operations 分析:#define int long long using namespace std; const int N=1e6+5; struct node { int a,id; bool operator < (const node &b) { return a>b.a; } }e[N]; int ans[N]; void solve() { int n; cin>>n; for(int i=1;i<=n;i++) { ans[i]=0; cin>>e[i].a; e[i].id=i; } sort(e+1,e+1+n); int tot=0,sum=0; for(int i=1;i+1<=n;i+=2) { ans[e[i].id]=++tot; ans[e[i+1].id]=-tot; sum+=2*(tot)*(e[i].a+e[i+1].a); } if(n&1) { ans[e[n].id]=++tot; sum+=2*(tot)*(e[n].a); } cout< T; while(T--) solve(); }
-
组合数学+亦或的一个性质
-
最后要输出的是所有 子序列亦或和 的和
-
现单独考虑最低位的贡献情况
子序列的个数为 2 n 2^n 2n 个,假设 n n n 个数中有 k k k 个数的最低位为 1
那么最低为的贡献情况为:
2 0 ( C k 1 + C k 3 + C k 5 + . . . ) ∗ 2 n − k = 1 ∗ 2 k − 1 ∗ 2 n − k = 2 n − 1 2^{0}(C_{k}^1+C_{k}^3+C_{k}^5+...)*2^{n-k}=1*2^{k-1}*2^{n-k}=2^{n-1} 20(Ck1+Ck3+Ck5+...)∗2n−k=1∗2k−1∗2n−k=2n−1 -
故只要某一位有 1 ,就会有贡献
-
a n s = ( x 1 ∣ x 2 ∣ . . . ∣ x m ) ∗ 2 n − 1 ans=(x_1|x_2|...|x_m)*2^{n-1} ans=(x1∣x2∣...∣xm)∗2n−1
#include#define int long long using namespace std; const int mo=1e9+7; int ksm(int a,int b,int p=mo) { int ans=1; while(b) { if(b&1) ans=ans*a%p; a=a*a%p; b>>=1; } return ans; } void solve() { int n,m; cin>>n>>m; int ans=0; for(int i=1;i<=m;i++) { int l,r,x; cin>>l>>r>>x; ans|=x; } ans%=mo; ans=ans*ksm(2,n-1)%mo; cout<>T; while(T--) solve(); }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)