\(TRDST\)

\(HMAPPY2\)

咕

话说这题居然卡\(scanf\)的么？？？

int T;cin>>T;while(T--){    cin>>n>>a>>b>>k;    puts(n/a+n/b-n/(a*b/__gcd(a,b))*2>=k?"Win":"Lose");}

\(CHEFING\)

咕咕

int T;scanf("%d",&T);while(T--){    scanf("%d",&n),res=0;    fp(i,0,25)flag[i]=1;    while(n--){        scanf("%s",s+1);        fp(i,0,25)cnt[i]=0;        fp(i,1,strlen(s+1))cnt[s[i]-'a']=1;        fp(i,0,25)flag[i]&=cnt[i];    }    fp(i,0,25)res+=flag[i];    printf("%d\n",res);}

\(DEPCHEF\)

咕咕咕

int T;scanf("%d",&T);while(T--){    scanf("%d",&n),mx=-1;    fp(i,1,n)scanf("%d",&a[i]);a[0]=a[n],a[n+1]=a[1];    fp(i,1,n)scanf("%d",&d[i]);d[0]=d[n],d[n+1]=d[1];    fp(i,1,n)if(a[i-1]+a[i+1]

\(MAGICJAR\)

咕咕咕咕

int T;scanf("%d",&T);while(T--){    scanf("%d",&n),res=0;    fp(i,1,n)scanf("%d",&a[i]),res+=a[i]-1;    printf("%lld\n",res+1);}

\(ARTBALAN\)

发现只与字母出现次数有关。枚举一下最后剩下\(k\)个字母，那么每种字母要剩\(n/k\)个，如果不选代价是\(cnt_i\)，选了代价是\(|cnt_i-n/k|\)，先假设全选，再找出\(|cnt_i-n/k|-cnt_i\)最小的\(k\)个加上就是了

//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 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;}int read(char *s){    R int len=0;R char ch;while(((ch=getc())>'Z'||ch<'A'));    for(s[++len]=ch;(ch=getc())>='A'&&ch<='Z';s[++len]=ch);    return s[len+1]='\0',len;}const int N=1e6+5;char s[N];int cnt[35],a[35],res,tmp,n;inline int abs(R int x){return x<0?-x:x;}int main(){//  freopen("testdata.in","r",stdin);    for(int T=read();T;--T){        n=read(s),res=n+1;        memset(cnt,0,104);        fp(i,1,n)++cnt[s[i]-'A'];        fp(k,1,26)if(n%k==0){            tmp=0;            fp(i,0,25)tmp+=cnt[i],a[i]=abs(n/k-cnt[i])-cnt[i];            sort(a,a+26);            fp(i,0,k-1)tmp+=a[i];            cmin(res,tmp>>1);        }        printf("%d\n",res);    }    return 0;}
      
     
    

\(MANRECT\)

先询问\((0,0)\)，可以求出矩形左下角所在的那条副对角线，同理询问\((0,inf),(inf,inf),(inf,0)\)，然后再求出左上角的对角线和右上角的对角线的交点横坐标\(x\)（有可能不是整数，那么下取整），此时询问\((x,inf)\)，得到的必然是矩形上边界离\(y=inf\)这条直线的距离，然后就求出矩形右上角的\(y\)坐标了，剩下的代入方程就可以了

话说为啥用\(scanf\)和\(printf\)会\(T\)啊？？？

//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)using namespace std;int read(){    R int res,f=1;R char ch;    while((ch=getchar())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getchar())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}inline int print(R int x,R int y){cout<<'Q'<<' '<
      
       <<' '<
       
        <
        
         >1,inf);        yy=0ll+inf-t,xx=0ll+(inf<<1)-c-yy;        y=0ll+xx-inf+d,x=0ll+a-y;        cout<<'A'<<' '<
         
          <<' '<
          
           <<' '<
           
            <<' '<
            
             <
            
           
          
         
        
       
      
     
    

\(GUESSRT\)

最优策略应该是先排除最后一个不管，前面一直\(12121212...\)，最后一个必选\(1\)

证明的话……我瞎猜的一个结论你叫我证明……

顺便注意如果刚开始\(n>k\)要先进行一次\(2\)操作令\(n\leq k\)

upd:去看了看官方题解，这个似乎应该反过来说，也就是如果只剩一个选\(1\)，前面一直按照\(21212121\)的顺序，因为\(21\)的概率显然比\(11\)要大

//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)using namespace std;int read(){    R int res,f=1;R char ch;    while((ch=getchar())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getchar())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=6e4+5,P=1e9+7;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 ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}int n,m,k,res,tmp,inv[N];int main(){//  freopen("testdata.in","r",stdin);    inv[0]=inv[1]=1;fp(i,2,N-1)inv[i]=mul(P-P/i,inv[P%i]);    for(int T=read();T;--T){        n=read(),k=read(),m=read();        if(m==1){printf("%d\n",inv[n]);continue;}        if(n>k)--m,n=(n-1)%k+1;        tmp=ksm(mul(n-1,inv[n]),(m+1)>>1);        res=add(P+1-tmp,(m&1^1)?mul(tmp,inv[n+k]):0);        printf("%d\n",res);    }    return 0;}
     
    

\(CHORCKIT\)

咕咕咕咕咕咕咕咕咕

\(challenge\)不写了

\(XDCOMP\)

首先对于一个子树，只有它的异或和为\(x\)或\(0\)才有分割成功的可能

我们记\(f_{u,0/1}\)表示对于\(u\)这棵子树，已经割掉的边为偶数/奇数的方案数，转移的时候，如果当前这条边不割，那么直接转移就是。只有当\(sum_v\)（其中\(sum\)表示子树异或和）为\(0\)且\(v\)的子树里割掉的边为奇数条，或者\(sum_v\)为\(x\)且\(v\)的子树里割掉的边为偶数条，这一条边才允许被割掉。最后记得判一下整棵树的异或和

//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)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;}const int N=1e5+5,P=1e9+7;inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:x;}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 ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}struct eg{int v,nx;}e[N<<1];int head[N],tot;inline void Add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}int f[N][2],g[N][2],sum[N],n,x,res;void dfs(int u,int fa){    f[u][0]=1,f[u][1]=0;    go(u)if(v!=fa){        dfs(v,u),sum[u]^=sum[v];        g[u][0]=g[u][1]=0;        if(sum[v]==x){            upd(g[u][1],mul(f[u][0],f[v][0])),            upd(g[u][0],mul(f[u][1],f[v][0]));        }        if(sum[v]==0){            upd(g[u][1],mul(f[u][1],f[v][1])),            upd(g[u][0],mul(f[u][0],f[v][1]));        }        upd(g[u][0],mul(f[u][0],f[v][0])),        upd(g[u][0],mul(f[u][1],f[v][1])),        upd(g[u][1],mul(f[u][0],f[v][1])),        upd(g[u][1],mul(f[u][1],f[v][0]));        f[u][0]=g[u][0],f[u][1]=g[u][1];    }}int main(){//  freopen("testdata.in","r",stdin);    n=read(),x=read();    fp(i,1,n)sum[i]=read();    for(R int i=1,u,v;i
     
    

\(MAXTAX\)

缩点之后跑个\(dp\)就可以了

关于同一个联通块内，我们可以先\(sort\)一下，然后枚举有\(i\)个人会因为税款太高而愉悦，那么能收到的最大税款就是\((cnt-i)\times b_{i+1}\)

记得要求的是最大值，计算过程中不需要取模

清零的时候我忘了\(long\ long\)占\(8\)个字节然后计算的时候算错了orz

//minamoto#include
    
     #define R register#define pb push_back#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 cmin(T&a,const T&b){return a>b?a=b,1:0;}template
       
        inline bool cmax(T&a,const T&b){return a
        
         '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=2e5+5,M=5e5+5,P=1e9+21;struct eg{int v,nx;}e[M];int head[N],tot;inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}vector
         
          to[N],nod[N];int col[N],dfn[N],low[N],st[N],deg[N],top,cnt,tim;int q[N],a[N];ll f[N][205],tmp[205],res;void tarjan(int u){ dfn[u]=low[u]=++tim,st[++top]=u; for(R int i=0,s=to[u].size(),v;i