Codeforces Round #757 (Div. 2)

• 贪心

#include 
#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();
}

• 贪心+排序

#include 
#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();
}