太菜了连\(D\)都做不出来没有小裙子\(QAQ\)

\(A\)

暴力把所有的数对都算出来，然后\(sort\)一下就行了

const int N=505;int a[N],st[N*N],top,n,k;ll res;int main(){    scanf("%d%d",&n,&k);    fp(i,1,n)scanf("%d",&a[i]);    fp(i,1,n)fp(j,i+1,n)st[++top]=a[i]+a[j];    sort(st+1,st+1+top);    fd(i,top,top-k+1)res+=st[i];    printf("%lld\n",res);    return 0;}

\(B\)

我们从左到右一列一列考虑，如果该列上下都没有，放一个黑的就够了（具体放在上下无所谓，反正都是一个），如果这一列有，那么和上一个有黑的列进行比较，如果它们上同有或下同有就不用管了，否则必须多放一个。具体可以画个图

//minamoto#include
    
     #define R register#define ll long long#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=1e5+5;int mp[5][N];int n,res;inline int calc(R int i){return mp[1][i]|(mp[2][i]<<1);}int main(){    scanf("%d",&n);    fp(i,1,n)scanf("%d",&mp[1][i]);    fp(i,1,n)scanf("%d",&mp[2][i]);    int bg=n,ed=1;    fp(i,1,n)if(mp[1][i]||mp[2][i]){bg=i;break;}    fd(i,n,1)if(mp[1][i]||mp[2][i]){ed=i;break;}    if(bg==ed)return puts("0"),0;    int las=calc(bg);    fp(i,bg+1,ed)if(!mp[1][i]&&!mp[2][i])++res;    else{        if((calc(i)&las)==0)++res,mp[1][i]=mp[2][i]=1;        las=calc(i);    }    printf("%d\n",res);    return 0;}
        
       
      
     
    

\(C\)

设子序列中元素个数为\(s\)，那么这个子序列中每个元素会被计算\(2^{s-1}\)次，那么就是要求\(m|sum\times 2^{s-1}\)（\(sum\)表示子序列元素和）

如果没有\(2^{s-1}\)，那么可以直接跑个暴力背包计算方案数。如果有\(2^{s-1}\)，我们发现有贡献的\(s\)最多只有\(O(\log m)\)个，那么我们开\(O(\log m)\)个背包就好了，每加一个数就令\(m/=2\)

//minamoto#include
    
     #define R register#define ll long long#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=5005,P=1e9+7;inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int f[21][N],g[21][N],st[21],a[N],top,n,m,res;int main(){    scanf("%d%d",&n,&m);    fp(i,1,n)scanf("%d",&a[i]);    st[++top]=m;for(R int k=m;k&1^1;st[++top]=k>>1,k>>=1);    fp(i,1,n){        fp(k,1,top)fp(s,0,st[k]-1)g[k][s]=f[k][s];        upd(g[1][a[i]%m],1);        fp(k,1,top-1)fp(s,0,st[k]-1)upd(g[k+1][(s+a[i])%st[k+1]],f[k][s]);        fp(s,0,st[top]-1)upd(g[top][(s+a[i])%st[top]],f[top][s]);        fp(k,1,top)fp(s,0,st[k]-1)f[k][s]=g[k][s];    }    fp(k,1,top)upd(res,f[k][0]);    printf("%d\n",res);    return 0;}
        
       
      
     
    

\(D\)

我错了我以后再也不看到\(lxl\)就想到分块了……

首先如果它是个单点修改可以直接线段树维护线性基，然而它是个区间修改我就不会做了……比赛结束之后看了看\(rqy\)的代码发现把原数组给差分一下，区间修改就可以变成两个单点修改了。根据线性代数芝士原来的线性基和差分之后的线性基是等价的。注意一下边界条件就行了

关于为啥边界条件这样处理是对的可以感性理解一下……

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int K=-1,Z=0;inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}void print(R int x){    if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++K]=z[Z],--Z);sr[++K]='\n';}const int N=50005,L=31;struct node;typedef node* ptr;struct node{    ptr lc,rc;int v[L];    inline void init(R int x){        int k=0;        fp(i,0,L-1){            v[i]=0;            if(x>>i&1)k=i;        }        v[k]=x;    }    void merge(ptr s,ptr t){        if(s!=this)memcpy(v,s->v,124);        int k=0;        fp(i,0,L-1)if(k=t->v[i]){            fd(j,i,0)if(k>>j&1){                if(!v[j]){v[j]=k;break;}                k^=v[j];            }        }    }    inline int calc(R int x){        fd(i,L-1,0)if(x>>i&1^1)x^=v[i];        return x;    }    inline void upd(){merge(lc,rc);}}pool[N<<2],*rt,*now,*pp=pool;int A[N],c[N],n,m,l,r,op,x;inline void upd(R int x,R int y){for(;x<=n;x+=x&-x)c[x]^=y;}inline int ask(R int x){R int res=0;for(;x;x-=x&-x)res^=c[x];return res;}void build(ptr &p,int l,int r){    p=pp++;    if(l==r)return p->init(A[l]),void();    int mid=(l+r)>>1;    build(p->lc,l,mid),build(p->rc,mid+1,r);    p->upd();}void update(ptr p,int l,int r,int x){    if(l==r)return p->init(A[x]),void();    int mid=(l+r)>>1;    x<=mid?update(p->lc,l,mid,x):update(p->rc,mid+1,r,x);    p->upd();}void query(ptr p,int l,int r,int ql,int qr){    if(ql<=l&&qr>=r)return now->merge(now,p),void();    int mid=(l+r)>>1;    if(ql<=mid)query(p->lc,l,mid,ql,qr);    if(qr>mid)query(p->rc,mid+1,r,ql,qr);}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read(),now=pp++;    fp(i,1,n)A[i]=read();    fd(i,n,1)A[i]^=A[i-1];    fp(i,1,n){        c[i]^=A[i];        if(i+(i&-i)<=n)c[i+(i&-i)]^=c[i];    }    build(rt,1,n);    while(m--){        op=read(),l=read(),r=read(),x=read();        if(op==1){            upd(l,x),upd(++r,x);            A[l]^=x,update(rt,1,n,l);            if(r<=n)A[r]^=x,update(rt,1,n,r);        }else{            now->init(ask(l));            if(l
         
          calc(x)); } } return Ot(),0;}
         
        
       
      
     
    

剩下两题先咕了……