9.10
40+0+60=100 rank 16 T1 裸的exgcd，然而不会求解的个数了，用解析几何搞的，考试时一堆问题都没调出来。。。 T2树形dp，f[i][j]表示i这颗子树里选j个黑点的最大收益，像背包一样转移就好了，考试打的暴力，还tm翻车了(#include#include #include #include #include #define LL long longusing namespace std;LL exgcd(LL a,LL b,LL &x,LL &y){ if(b==0){ x=1;y=0; return a; } LL g=exgcd(b,a%b,x,y); LL t=x; x=y; y=t-(a/b)*x; return g;}int main(){ //freopen("fuction.in","r",stdin); //freopen("fuction.out","w",stdout); LL a,b,c,d,x,y,ans,numx,numy,T; scanf("%lld",&T); while(T--){ scanf("%lld%lld%lld",&a,&b,&c); if(a==0&&b==0){ printf("0\n"); continue; } if(a==0){ if((c%b==0)&&(c/b>0)) printf("ZenMeZheMeDuo\n"); else printf("0\n"); continue; } if(b==0){ if((c%a==0)&&((c/a>0))) printf("ZenMeZheMeDuo\n"); else printf("0\n"); continue; } if(a<0||b<0){a=-a;b=-b;c=-c;} LL d=exgcd(a,b,x,y); if(c%d!=0){ printf("0\n"); continue; } if(a*b<0){ printf("ZenMeZheMeDuo\n"); continue; } x=x*(c/d);y=y*(c/d); if(x<=0&&y<=0){ printf("0\n"); continue; } if(x<=0&&y>0){ numy=(y-1)/(a/d)+1; if(x==0)numx=1; else numx=(-x)/(b/d)+1; ans=numy-numx; if(ans<0)ans=0; if(ans>65535) printf("ZenMeZheMeDuo\n"); else printf("%lld\n",ans); continue; } if(y<=0&&x>0){ numx=(x-1)/(b/d)+1; if(y==0) numy=1; else numy=(-y)/(a/d)+1; ans=numx-numy; if(ans<0)ans=0; if(ans>65535) printf("ZenMeZheMeDuo\n"); else printf("%lld\n",ans); continue; } if(x>0&&y>0){ numx=(x-1)/(b/d)+1; numy=(y-1)/(a/d)+1; ans=numx+numy-1; if(ans<0)ans=0; if(ans>65535) printf("ZenMeZheMeDuo\n"); else printf("%lld\n",ans); continue; } } return 0;}
T2
#include#include #include #include #include #define N 2050using namespace std;int e=1,head[N];struct edge{ int u,v,w,next;}ed[2*N];void add(int u,int v,int w){ ed[e].u=u;ed[e].v=v;ed[e].w=w; ed[e].next=head[u];head[u]=e++;}int n,m;int size[N],fa[N];long long f[N][N];void dfs(int x){ size[x]++; for(int i=head[x];i;i=ed[i].next){ int v=ed[i].v; if(v==fa[x])continue; fa[v]=x; dfs(v); size[x]+=size[v]; for(int j=min(size[x],m);j>=0;j--){ int minn=max(0,max(j-size[x]+size[v],size[v]-n+m)); for(int k=minn;k<=min(size[v],min(m,j));k++){ long long tmp=(long long)(k*(m-k)+(size[v]-k)*((n-m)-(size[v]-k))); f[x][j]=max(f[x][j],f[x][j-k]+f[v][k]+(ed[i].w*tmp)); } } }}int main(){ scanf("%d%d",&n,&m); int u,v,w; for(int i=1;i
9.14
70+70+15=155 rank1 T1 欧拉路，去掉的至少有一个自环或者两条边有公共点(欧拉路需要保证整个图只有0或2个有奇数条连边)需要判边是否连通！最后手贱还扔了10分…… T2 下底分块的思想 我们要求一个最大的d，满足 ∑i=1n(⌈ai/d⌉∗d−ai)≤k
设 C=k+∑ni=1ai 则 ∑ni=1⌈ai/d⌉≤⌊C/d⌋ 易证等式左边随d增加单调不增，所以按右边分块，可能作为答案的是所有块的右端点，考试打了好多特判骗了70 T3 神奇的dp….dp[i][j]表示一棵i-超级树，同时有j条点不重复的路径存在的方案数 枚举左子树和右子树的路径条数l、r，记num=dp[i][l]*dp[i][r]， 什么也不做 dp[i+1][l+r]+=num 根自己作为一条新路径 dp[i+1][l+r+1]+=num 根连接到左子树（或右子树）的某条路径上 dp[i+1][l+r]+=2*num*(l+r) 根连接左子树和右子树的各一条路径 dp[i+1][l+r-1]+=2*num*l*r 根连接左子树（或右子树）的两条路径 dp[i+1][l+r-1]+=num*(l*(l-1)+r*(r- 1)) 注意这里的路径都是有向的！ T1 #include#include #include #include #include using namespace std;long long ans,in[100005],tot,n,m;int fa[100005];bool vis[100005];int find(int x){ if(x==fa[x])return x; return fa[x]=find(fa[x]);}int main(){ scanf("%lld%lld",&n,&m); int u,v,fu,fv; for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); vis[u]=1;vis[v]=1; if(u!=v){ in[u]++;in[v]++; fu=find(u);fv=find(v); if(fu!=fv)fa[fv]=fu; } else tot++; } for(int i=1;i<=n;i++)if(vis[i]){fu=find(i);break;} for(int i=1;i<=n;i++)if(vis[i]&&find(i)!=fu){ printf("0\n");return 0;} for(int i=1;i<=n;i++) ans+=in[i]*(in[i]-1)/2; ans+=tot*(m-tot); ans+=tot*(tot-1)/2; printf("%lld\n",ans); return 0;}
T2
#include#include #include #include #include #define LL long long#define N 105using namespace std;int n;LL m,a[N],tot; bool check(LL x){ LL cnt=0,top=tot/x; for(int i=1;i<=n;++i){ cnt+=((a[i]-1)/x)+1; if(cnt>top)return 0; }return 1;}int main(){ scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); tot+=a[i]; } tot+=m; for(LL d=tot;d>=1;--d){ if(check(d)){ printf("%lld\n",d);return 0;} d=(tot/(tot/d+1))+1; } return 0;}
T3
#include#include #include #include #include #define LL long long#define N 302using namespace std;int n;LL f[N][N],num,mod;int main(){ scanf("%d%lld",&n,&mod); f[1][0]=1; f[1][1]=1; for(int i=1;i
9.16
100+100+40=240 rank3 T1 贪心找能剩下的最多的 T2 ans=Cn2∗n T3 竟然是区间dp，二维树状数组也可以水！想到回文那一串东西无法自拔，关键是我什么都不会……看了就要学，不学不要看。。。。 f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+[i~j是回文串] T1#include#include #include #include #include #define N 100005#define LL long longusing namespace std;struct data{LL a,b,c;}d[N];bool cmpc(data a,data b){ return a.c>b.c;}LL n,tot,ans;LL read(){ LL a=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){a=a*10+ch-'0';ch=getchar();} return a;}int T;int main(){ scanf("%d",&T); while(T--){ tot=0; ans=0; n=read(); for(int i=1;i<=n;i++){ d[i].a=read(); d[i].b=read(); d[i].c=d[i].b-d[i].a; } sort(d+1,d+n+1,cmpc); for(int i=1;i<=n;i++){ if(tot>=d[i].b)tot-=d[i].a; else{ans+=d[i].b-tot;tot=d[i].c;} } printf("%lld\n",ans); } return 0;}
T2
#include#include #include #include #include #define LL long long#define N 1000005#define mod 1000000007using namespace std;LL fac[2*N],n,T,ans;LL qp(LL a,LL b){ LL ff=1; while(b){ if(b&1)ff=ff*a%mod; a=a*a%mod;b>>=1; } return ff;}LL C(LL x,LL y){ if(!y||y==x)return 1; return ((fac[x]*qp(fac[y],mod-2))%mod*qp(fac[x-y],mod-2))%mod;}int main(){ fac[1]=1; for(int i=2;i<=2000000;i++)fac[i]=(fac[i-1]*i)%mod; scanf("%lld",&T); while(T--){ scanf("%lld",&n); printf("%lld\n",C(2*n,n)); } return 0;}
T3
#include#include #include #include #include #define N 5005using namespace std;char s[N];int len,f[N][N],g[N][N];int read(){ int a=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){a=a*10+(ch^48);ch=getchar();} return a;}int main(){ scanf("%s",s+1); len=strlen(s+1); for(int i=1;i<=len;++i){ g[i][i]=1; for(int j=1;;++j){ if(i+j>len||j>=i) break; if(s[i+j]==s[i-j])g[i-j][i+j]=1; else break; } } for(int i=1;i<=len;++i){ for(int j=1;;++j){ if(i+j>len||j>i) break; if(s[i+j]==s[i-j+1])g[i-j+1][i+j]=1; else break; } } for(int i=1;i<=len;i++)f[i][i]=1; for(int l=2;l<=len;l++){ for(int i=1;i<=len-l+1;i++){ int j=i+l-1; f[i][j]=f[i][j-1]+f[i+1][j]-f[i+1][j-1]+g[i][j]; } } int l,r,T=read(); while(T--){ l=read();r=read(); printf("%d\n",f[l][r]); } return 0;}