傳送門
\(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]<d[i])cmax(mx,d[i]);printf("%d\n",mx);
}\(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<bits/stdc++.h>
#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 fd(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<class T>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<bits/stdc++.h>
#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 fd(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'<<' '<<x<<' '<<y<<endl;fflush(stdout);return read();}
const int inf=1e9;
int a,b,c,d,t,x,y,xx,yy;
int main(){
// freopen("testdata.in","r",stdin);int T=read();while(T--){a=print(0,0),b=print(0,inf),c=print(inf,inf),d=print(inf,0);if(0ll+b+c<inf)t=print(b+1,inf);else t=print((0ll+inf+b-c)>>1,inf);yy=0ll+inf-t,xx=0ll+(inf<<1)-c-yy;y=0ll+xx-inf+d,x=0ll+a-y;cout<<'A'<<' '<<x<<' '<<y<<' '<<xx<<' '<<yy<<endl;fflush(stdout);read();}return 0;
}\(GUESSRT\)
最優策略應該是先排除最后一個不管，前面一直\(12121212...\)，最后一個必選\(1\)
證明的話……我瞎猜的一個結論你叫我證明……
順便注意如果剛開始\(n>k\)要先進行一次\(2\)操作令\(n\leq k\)
upd:去看了看官方題解，這個似乎應該反過來說，也就是如果只剩一個選\(1\)，前面一直按照\(21212121\)的順序，因為\(21\)的概率顯然比\(11\)要大
//minamoto
#include<bits/stdc++.h>
#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 fd(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<bits/stdc++.h>
#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 fd(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<n;++i)u=read(),v=read(),Add(u,v),Add(v,u);dfs(1,0);if(sum[1]==x)upd(res,f[1][0]);if(sum[1]==0)upd(res,f[1][1]);printf("%d\n",res);return 0;
}\(MAXTAX\)
縮點之后跑個\(dp\)就可以了
關于同一個聯通塊內，我們可以先\(sort\)一下，然后枚舉有\(i\)個人會因為稅款太高而愉悅，那么能收到的最大稅款就是\((cnt-i)\times b_{i+1}\)
記得要求的是最大值，計算過程中不需要取模
清零的時候我忘了\(long\ long\)占\(8\)個字節然后計算的時候算錯了orz
//minamoto
#include<bits/stdc++.h>
#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 fd(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<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>inline bool cmax(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;
}
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<int>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<s&&(v=to[u][i]);++i)if(!dfn[v])tarjan(v),cmin(low[u],low[v]);else if(!col[v])cmin(low[u],dfn[v]);if(low[u]==dfn[u])for(++cnt,st[top+1]=0;st[top+1]!=u;--top)col[st[top]]=cnt,nod[cnt].pb(a[st[top]]);
}
int n,m,k;
void clr(){fp(i,1,n)vector<int>().swap(to[i]);fp(i,1,cnt)vector<int>().swap(nod[i]);memset(col,0,(n+1)<<2),memset(dfn,0,(n+1)<<2);memset(deg,0,(cnt+1)<<2),memset(head,0,(cnt+1)<<2);tot=cnt=top=tim=0;
}
void solve(){int h=1,t=0,u;++cnt;fp(i,1,cnt-1){add(i,cnt),++deg[cnt];if(!deg[i])q[++t]=i;memset(f[i],0,(k+1)<<3);}memset(f[cnt],0,(k+1)<<3);while(h<=t){u=q[h++],sort(nod[u].begin(),nod[u].end());fp(j,0,k)tmp[j]=f[u][j];for(R int i=0,s=nod[u].size();i<s;++i)fp(j,0,k-i)cmax(tmp[i+j],f[u][j]+1ll*(s-i)*nod[u][i]);go(u){fp(j,0,k)cmax(f[v][j],tmp[j]);if(!--deg[v])q[++t]=v;}}
}
int main(){
// freopen("testdata.in","r",stdin);for(int T=read();T;--T){n=read(),m=read(),k=read();fp(i,1,n)a[i]=read();for(R int i=1,u,v;i<=m;++i)u=read(),v=read(),to[u].pb(v);fp(i,1,n)if(!dfn[i])tarjan(i);fp(u,1,n)for(R int i=0,s=to[u].size(),v;i<s&&(v=to[u][i]);++i)if(col[u]!=col[v])add(col[u],col[v]),++deg[col[v]];solve();res=0;fp(i,0,k)cmax(res,f[cnt][i]);printf("%lld\n",res%P);clr();}return 0;
}\(TRDST\)
我怎么又把點分給忘了→_→
首先在每一個點處是可以二分答案的，那么我們現在的問題轉化為求到它的距離大于\(mid\)的點數，也可以轉化為數到它的距離小于等于\(mid\)的點數
到某個頂點距離小于等于\(k\)的點數……這就是個點分樹的經典應用了，我覺得代碼比我講得清楚所以建議自行看代碼理解
//minamoto
#include<bits/stdc++.h>
#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 fd(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<class T>inline bool cmax(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 C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;while(z[++Z]=x%10+48,x/=10);while(sr[++C]=z[Z],--Z);sr[++C]=' ';
}
const int N=1e5+5,M=3e6+5;
inline int min(R int x,R int y){return x<y?x:y;}
int pool[M],*pp=pool;
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;}
struct Eg{int sz,nx,d,sgn,*c;}E[M];int Head[N],tc;
int sz[N],mx[N],dep[N],fa[N],q[N],vis[N],size,rt;
int n,a[N];
void findrt(int u,int fa){sz[u]=1,mx[u]=0;go(u)if(v!=fa&&!vis[v])findrt(v,u),sz[u]+=sz[v],cmax(mx[u],sz[v]);cmax(mx[u],size-sz[u]);if(mx[u]<mx[rt])rt=u;
}
void dfs(int u,int sgn,int d){int h=1,t=0;q[++t]=u,dep[u]=d,fa[u]=0;while(h<=t){u=q[h++],++pp[dep[u]];go(u)if(!vis[v]&&v!=fa[u])q[++t]=v,dep[v]=dep[u]+1,fa[v]=u;}int len=dep[q[t]];fp(i,1,t)u=q[i],E[++tc]={len,Head[u],dep[u],sgn,pp},Head[u]=tc;fp(i,1,len)pp[i]+=pp[i-1];pp+=len+1;
}
void solve(int u){vis[u]=1,dfs(u,1,0);int s=size;go(u)if(!vis[v]){dfs(v,-1,1);rt=0,size=sz[v]>sz[u]?s-sz[u]:sz[v],findrt(v,0);solve(rt);}
}
int calc(int d,int u){int res=0;for(R int i=Head[u];i;i=E[i].nx)if(d>=E[i].d)res+=E[i].c[min(d-E[i].d,E[i].sz)]*E[i].sgn;return n-res;
}
int main(){
// freopen("testdata.in","r",stdin);n=read();fp(i,1,n)a[i]=read();for(R int i=1,u,v;i<n;++i)u=read(),v=read(),add(u,v),add(v,u);mx[0]=n+1,rt=0,size=n,findrt(1,0),solve(rt);int l,r,mid,ans;fp(i,1,n){l=0,r=n-1;while(l<=r)mid=(l+r)>>1,(calc(mid,i)>=a[i])?(ans=mid,l=mid+1):r=mid-1;print(ans);}return Ot(),0;
}
