额，考完期末考结束周之前家里突发急事，赶回安徽，然后又接到集训的通知，结果回来路上发烧40°C+航班取消两次，要死要活地赶到eg。。。（然而期末考还是不（ling）出（ren）意（xin）外（xi）的炸了）
新题库小视野好评~ ps:文内题目持续做&&更新
1.【xsy2336】【CF471D】MUH and Cube Walls KMP+乱搞差值
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int l1,l2,ans=0,s1[200001],s2[200001],nxt[200001]; void kmp(){ nxt[0]=-1; for(int i=1,j=0;i<l1;i++){ for(j=nxt[i-1];j!=-1&&s1[i]!=s1[j+1];j=nxt[j]); if(s1[i]==s1[j+1])j++; nxt[i]=j; } for(int i=0,j=-1;i<l2;i++){ for(;j!=-1&&s2[i]!=s1[j+1];j=nxt[j]); if(s1[j+1]==s2[i])j++; if(j==l1-1){ ans++; } } } int main(){ scanf("%d%d",&l2,&l1); for(int i=0;i<l2;i++){ scanf("%d",&s2[i]); } for(int i=0;i<l1;i++){ scanf("%d",&s1[i]); } if(l1==1){ printf("%d",l2); return 0; } l1--; l2--; for(int i=0;i<l1;i++){ s1[i]=s1[i+1]-s1[i]; } for(int i=0;i<l2;i++){ s2[i]=s2[i+1]-s2[i]; } kmp(); printf("%d",ans); return 0; }2.【xsy2338】【bzoj1355】Radio Transmission （并不是KMP）fail数组应用
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,ans,nxt[1000001]; char s[1000001]; int main(){ scanf("%d%s",&n,s); nxt[0]=-1; for(int i=1,j=0;i<n;i++){ for(j=nxt[i-1];j!=-1&&s[i]!=s[j+1];j=nxt[j]); if(s[i]==s[j+1])j++; nxt[i]=j; } ans=n-1; while(nxt[ans])ans--; printf("%d",ans); return 0; }3.【xsy2349】【bzoj1355】[Baltic2009]Bazinga （也不是KMP）strstr大法好
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; char st[2001][2001]; bool check[2001]; int n,T,ans; int main(){ scanf("%d",&T); for(int t=1;t<=T;t++){ memset(check,0,sizeof(check)); ans=-1; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",st[i]); for(int j=i-1;j>=1;j--){ if(check[j])continue; else if(strstr(st[i],st[j])==NULL){ ans=i; break; } else check[j]=true; } } printf("Case #%d: %d\n",t,ans); } return 0; }1.【xsy2335】【NOI2014】动物园 2.【xsy2337】【CF494B】Obsessive String
1.【xsy2339】[Balkan2007]Toponyms trie+dfs
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; struct t_node{ int nxt; char data; }trie[12000001]; int n,tot=0,head[12000001],anss[12000001]; ll ans; char st[10000001]; void ins(char st[]){ int now=0,len=strlen(st); for(int i=0;i<len;i++){ int tmp; for(tmp=head[now];trie[tmp].data!=st[i]&&tmp!=-1;tmp=trie[tmp].nxt); if(tmp==-1){ trie[tmp=++tot].data=st[i]; trie[tmp].nxt=head[now]; head[now]=tmp; } now=tmp; anss[now]++; ans=max(ans,(ll)(i+1)*anss[now]); } } int main(){ memset(head,-1,sizeof(head)); scanf("%d\n",&n); for(int i=1;i<=n;i++){ gets(st); ins(st); } printf("%lld",ans); return 0; }2.【xsy2340】【POJ3764】The xor-longest Path trie+xor
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; struct edge{ int v,w,next; }a[400001]; int n,u,v,w,ans=0,tot=0,tot1=0,num[400001],head[400001],trie[2][4000001]; bool check[400001]; void add(int u,int v,int w){ a[++tot].v=v; a[tot].w=w; a[tot].next=head[u]; head[u]=tot; } void dfs(int u,int x){ num[u]=x; check[u]=true; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ if(!check[a[tmp].v])dfs(a[tmp].v,a[tmp].w^x); } } void ins(int x){ int now=0; bool f; for(int i=30;i>=0;i--){ f=x&(1<<i); if(trie[f][now])now=trie[f][now]; else{ trie[f][now]=++tot1; now=tot1; } } } int query(int x){ int maxn=0,now=0; bool f; for(int i=30;i>=0;i--){ f=x&(1<<i); if(trie[!f][now]){ now=trie[!f][now]; maxn+=(1<<i); }else now=trie[f][now]; } return maxn; } int main(){ memset(head,-1,sizeof(head)); memset(check,0,sizeof(check)); memset(trie,0,sizeof(trie)); scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(1,0); ins(num[1]); for(int i=2;i<=n;i++){ ans=max(ans,query(num[i])); ins(num[i]); } printf("%d",ans); return 0; }3.【xsy2342】【bzoj4260】REBXOR trie+xor
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,ans,tot=0,now=0,s[4000001],lf[4000001],rt[4000001],trie[2][10000001]; void add(int x){ int now=0; bool f; for(int i=1<<30;i>0;i/=2){ f=i&x; if(trie[f][now])now=trie[f][now]; else{ trie[f][now]=++tot; now=tot; } } } int query(int x){ int now=0,ans=0; bool f; for(int i=1<<30;i>0;i/=2){ f=!(i&x); if(trie[f][now]){ ans+=i; now=trie[f][now]; }else now=trie[!f][now]; } return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&s[i]); } add(0); for(int i=1;i<=n;i++){ now^=s[i]; add(now); lf[i]=max(lf[i-1],query(now)); } memset(trie,0,sizeof(trie)); now=tot=0; add(0); for(int i=n;i>=1;i--){ now^=s[i]; add(now); rt[i]=max(rt[i+1],query(now)); } for(int i=0;i<=n;i++){ ans=max(ans,lf[i]+rt[i+1]); } printf("%d",ans); return 0; }1.【xsy2341】异或之 2.【xsy2343】【SCOI2016】背单词
1.【xsy2436】[CF487B]Strip 然而并不是线段树
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,s,l,ans=1,maxn,minn,a[100001]; int main(){ scanf("%d%d%d",&n,&s,&l); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } minn=maxn=a[1]; for(int i=2;i<=n;i++){ if(abs(minn-a[i])>s||abs(maxn-a[i])>s){ maxn=minn=a[i]; ans++; }else{ maxn=max(maxn,a[i]); minn=min(minn,a[i]); } } if(ans*l<=n)printf("%d",ans); else printf("-1"); return 0; }2.【xsy2437】[CF373C]计算袋鼠是愉快的 然而也不是线段树
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,ans=0,a[500001]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } sort(a+1,a+n+1); ans=n; for(int i=n/2;i>0;i--){ if(a[ans]>=a[i]*2)ans--; } printf("%d",ans); return 0; }太多了不写了
0.模板。。。 1.【xsy2346】Prefixes and Suffixes
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int l2,tot=0,nxt[100001],ans[100001]; bool check[100001]; char t[100001]; void getnext(){ int a=0,p; nxt[0]=l2; for(int i=1,j=-1;i<l2;i++,j--){ if(j<0||i+nxt[i-a]>=p){ if(j<0){ p=i; j=0; } while(p<l2&&t[p]==t[j]){ p++; j++; } nxt[i]=j; a=i; }else nxt[i]=nxt[i-a]; } } int main(){ memset(nxt,0,sizeof(nxt)); memset(ans,0,sizeof(ans)); memset(check,0,sizeof(check)); scanf("%s",t); l2=strlen(t); getnext(); for(int i=0;i<l2;i++){ if(i+nxt[i]==l2){ check[nxt[i]]=true; tot++; } ans[nxt[i]]++; } for(int i=l2-1;i>=1;i--){ ans[i]+=ans[i+1]; } printf("%d\n",tot); for(int i=1;i<=l2;i++){ if(check[i])printf("%d %d\n",i,ans[i]); } return 0; }2.【xsy2347】Tavas and Malekas
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define modHA 1000000007 using namespace std; int n,m,tot,s[1000001],nxt[1000001],l2; long long ans=1; char t[1000001]; void getnext(){ int a=0,p; nxt[0]=l2; for(int i=1,j=-1;i<l2;i++,j--){ if(j<0||i+nxt[i-a]>=p){ if(j<0){ p=i; j=0; } while(p<l2&&t[p]==t[j]){ p++; j++; } nxt[i]=j; a=i; }else nxt[i]=nxt[i-a]; } } int main(){ scanf("%d%d",&n,&m); if(m==0){ for(int i=1;i<=n;i++)ans=(ans*26)%modHA; printf("%lld",ans); return 0; } scanf("%s",t); l2=strlen(t); for(int i=1;i<=m;i++){ scanf("%d",&s[i]); } getnext(); for(int i=1;i<m;i++){ if(s[i]+l2<s[i+1])continue; if(nxt[s[i+1]-s[i]]!=l2-s[i+1]+s[i]){ printf("0"); return 0; } } tot=s[1]-1; for(int i=1;i<m;i++){ if(s[i]+l2<s[i+1])tot+=s[i+1]-s[i]-l2; } if(s[m]+l2-1<n)tot+=n-s[m]-l2+1; for(int i=1;i<=tot;i++)ans=(ans*26)%modHA; printf("%lld",ans); return 0; }1.【xsy2348】Revolving Digits
0.模板。。。 1.【xsy2356】最长回文 就是模板啊。。。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; char s[100001]; int manacher(char s[]){ int maxn=0,p[200001],mx=0,id=0,len=strlen(s); char st[200001]; st[0]='$'; for(int i=0;i<len;i++){ st[i*2+1]='#'; st[(i+1)*2]=s[i]; } st[len*2+1]='#'; for(int i=0;i<2*len;i++){ if(i<mx)p[i]=min(p[id*2-i],mx-i); else p[i]=1; while(st[i-p[i]]==st[i+p[i]])p[i]++; if(i+p[i]>mx){ mx=i+p[i]; id=i; } maxn=max(maxn,p[i]-1); } return maxn; } int main(){ while(scanf("%s",s)!=EOF) printf("%d\n",manacher(s)); return 0; }2.【xsy2357】吉哥系列故事——完美队形II 还是模板啊。。。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int t,n,a[100001]; int m(int len){ int p[200001],st[200001],mx=0,id=0,maxn=0; memset(p,0,sizeof(p)); st[0]=-2; for(int i=1;i<=len;i++){ st[i*2-1]=-1; st[i*2]=a[i]; } st[len*2+1]=-1; for(int i=1;i<=len*2+1;i++){ if(i<mx)p[i]=min(mx-i,p[id*2-i]); else p[i]=1; while(st[i+p[i]]==st[i-p[i]]&&st[i-p[i]]<=st[i-p[i]+2])p[i]++; if(i+p[i]>mx){ mx=i+p[i]; id=i; } maxn=max(maxn,p[i]-1); } return maxn; } int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } printf("%d\n",m(n)); } return 0; }3.【xsy2359】[POI2010] Antisymmetry
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n; char s[500001]; long long manacher(){ int p[2000001],mx=0,id=0,st[2000001],len=n; long long maxn=0; st[0]=-1; for(int i=1;i<=len;i++){ st[i*2-1]=s[i]-'0'; st[i*2]=138; } len=len*2-1; //st[len]=138; for(int i=2;i<=len;i+=2){ if(i<mx)p[i]=min(p[id*2-i],mx-i); else p[i]=1; while(i+p[i]<=len&&i-p[i]>0&&(st[i-p[i]]!=st[i+p[i]]||st[i-p[i]]==138))p[i]++; if(i+p[i]>mx){ mx=i+p[i]; id=i; } maxn+=p[i]>>1; } return maxn; } int main(){ scanf("%d%s",&n,s+1); printf("%lld",manacher()); return 0; }1.【xsy2358】Interestring 2.【xsy2360】[CF17E] Palisection
1.【xsy1998】Xorequ
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define modHA 1000000007LL using namespace std; typedef long long ll; struct sq{ ll s[3][3]; void init(){ memset(s,0,sizeof(s)); s[0][0]=s[0][1]=s[1][0]=1; } }; ll t,n,num[101],f[2][101]; ll _cal(int x,int y,bool ch){ ll ans=0,ss=ch?num[x]:1; if(x==0)return 1; if(!ch&&f[y][x]!=-1)return f[y][x]; for(int i=0;i<=ss;i++){ if(i==0||y==0){ ans+=_cal(x-1,i,ch&&(i==ss)); } } if(!ch){ f[y][x]=ans; } return ans; } ll cal(ll s){ int len=0; while(s){ num[++len]=s&1; s>>=1; } return _cal(len,0,true); } sq _mul(sq a,sq b){ sq c; memset(c.s,0,sizeof(c.s)); for(int i=0;i<=1;i++){ for(int j=0;j<=1;j++){ for(int k=0;k<=1;k++){ c.s[i][j]=(c.s[i][j]+a.s[i][k]*b.s[k][j])%modHA; } } } return c; } sq fast_pow(sq a,ll s){ sq tmp; memset(tmp.s,0,sizeof(tmp.s)); tmp.s[0][0]=tmp.s[1][1]=1; for(;s;s/=2){ if(s&1)tmp=_mul(tmp,a); a=_mul(a,a); } return tmp; } ll squ_mul(){ sq a,b; a.init(); memset(b.s,0,sizeof(b.s)); b.s[0][0]=1; a=fast_pow(a,n+1); a=_mul(a,b); return a.s[0][0]; } int main(){ scanf("%lld",&t); while(t--){ memset(f,-1,sizeof(f)); scanf("%lld",&n); printf("%lld\n%lld\n",cal(n)-1,squ_mul()); } return 0; }2.【xsy1999】[ZJOI2010] 数字计数
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; ll a,b,c=1,ans[10],f[13]; void cal(ll s,int ch){ ll tmp=1,k=10,tt,sum; for(;k<s;tmp++,k*=10){ for(int j=0;j<=9;j++)ans[j]+=f[tmp-1]*9*ch; for(int j=1;j<=9;j++)ans[j]+=k/10*ch; } k/=10; tt=k; tmp--; while(tt<s){ while(tt+k<=s){ sum=tt/k; while(sum){ ans[sum%10]+=k*ch; sum/=10; } for(int j=0;j<=9;j++){ ans[j]+=f[tmp]*ch; } tt+=k; } k/=10; tmp--; } } int main(){ memset(ans,0,sizeof(ans)); scanf("%lld%lld",&a,&b); f[1]=1; for(int i=2;i<=12;i++){ f[i]=f[i-1]*10+(c=c*10); } cal(b+1,1); cal(a,-1); for(int i=0;i<=9;i++){ printf("%lld ",ans[i]); } return 0; }3.【xsy2000】[SCOI2009] windy数
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; ll a,b,tot=0LL,f[101][101],num[12]; ll cal(ll s){ memset(num,0,sizeof(num)); if(s==0)return 0; ll ans=0LL; tot=0LL; while(s){ num[++tot]=s%10; s/=10; } for(int i=1;i<num[tot];i++){ ans+=f[tot][i]; } for(int i=tot-1;i>0;i--){ for(int j=1;j<=9;j++){ ans+=f[i][j]; } } for(int i=tot-1;i>0;i--){ for(int j=0;j<num[i];j++){ if(abs(num[i+1]-j)>=2){ ans+=f[i][j]; } } if(abs(num[i+1]-num[i])<2)break; } return ans; } int main(){ memset(f,0,sizeof(f)); scanf("%lld%lld",&a,&b); for(int i=0;i<=9;i++){ f[1][i]=1; } for(int i=2;i<=10;i++){ for(int j=0;j<=9;j++){ for(int k=0;k<=9;k++){ if(abs(j-k)>=2){ f[i][j]+=f[i-1][k]; } } } } printf("%lld",cal(b+1)-cal(a)); return 0; }4.【xsy2001】[POJ3208] Apocalypse Someday
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; const int w[4][10]={{0,0,0,0,0,0,0,0,0,0},{3,3,3,3,3,3,0,3,3,3},{3,3,3,3,3,3,1,3,3,3},{3,3,3,3,3,3,2,3,3,3}}; ll n,t,tot,sum,f[201][4]; int main(){ scanf("%d",&t); f[0][0]=1; for(int i=1;i<=12;i++){ f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])*9; f[i][1]=f[i-1][0]; f[i][2]=f[i-1][1]; f[i][3]=f[i-1][2]+f[i-1][3]*10; } while(t--){ tot=0; sum=3; scanf("%d",&n); while(f[tot][3]<n)tot++; while(tot){ ll s=0,now; for(int i=0;i<=9;i++){ now=0; for(int j=3;j>=w[sum][i];j--){ now+=f[tot-1][j]; } if(s+now>=n){ printf("%d",i); sum=w[sum][i]; break; } s+=now; } n-=s; tot--; } printf("\n"); } return 0; }太多了不写了
1.【xsy1961】[NOIP2016] 换教室 就这题调了我3h。。。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,m,v,e,u,vv,w,c[2001],d[2001],sp[2001][2001]; double k[2000001],f[2001][2001][2],tt,ans; int main(){ memset(sp,0x3f,sizeof(sp)); scanf("%d%d%d%d",&n,&m,&v,&e); for(int i=1;i<=n;i++){ scanf("%d",&c[i]); } for(int i=1;i<=n;i++){ scanf("%d",&d[i]); } for(int i=1;i<=n;i++){ scanf("%lf",&k[i]); } for(int i=0;i<=v;i++){ sp[i][i]=0; } for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ f[i][j][0]=1e16; f[i][j][1]=1e16; } } f[1][0][0]=f[1][1][1]=0; for(int i=1;i<=e;i++){ scanf("%d%d%d",&u,&vv,&w); if(u==vv){ continue; } sp[u][vv]=min(sp[u][vv],w); sp[vv][u]=sp[u][vv]; } for(int kk=1;kk<=v;kk++){ for(int i=1;i<=v;i++){ for(int j=1;j<=v;j++){ sp[i][j]=min(sp[i][kk]+sp[kk][j],sp[i][j]); } } } for(int i=2;i<=n;i++){ f[i][0][0]=f[i-1][0][0]+sp[c[i-1]][c[i]]; for(int j=1;j<=min(m,i);j++){ f[i][j][0]=min(f[i-1][j][0]+sp[c[i-1]][c[i]],f[i-1][j][1]+sp[c[i-1]][c[i]]*(1.0-k[i-1])+sp[d[i-1]][c[i]]*k[i-1]); f[i][j][1]=f[i-1][j-1][0]+sp[c[i-1]][c[i]]*(1.0-k[i])+sp[c[i-1]][d[i]]*k[i]; tt=f[i-1][j-1][1]+sp[c[i-1]][c[i]]*(1.0-k[i-1])*(1.0-k[i])+sp[d[i-1]][c[i]]*k[i-1]*(1.0-k[i])+sp[c[i-1]][d[i]]*(1.0-k[i-1])*k[i]+sp[d[i-1]][d[i]]*k[i-1]*k[i]; f[i][j][1]=min(f[i][j][1],tt); } } ans=f[n][0][0]; for(int i=1;i<=m;i++){ ans=min(ans,min(f[n][i][1],f[n][i][0])); } printf("%.2lf",ans); return 0; }2.【xsy1962】OSU!
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n; double s,f1[100001],f2[100001],f3[100001]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lf",&s); f1[i]=(f1[i-1]+1)*s; f2[i]=(f2[i-1]+f1[i-1]*2+1)*s; f3[i]=f3[i-1]+(3*(f1[i-1]+f2[i-1])+1)*s; } printf("%.1lf",f3[n]); return 0; }3.【xsy1963】概率充电器
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; struct edge{ int v,next; double w; }a[1000001]; int n,u,v,w,tot=0,head[1000001]; double ans=0,f[500001],s[500001]; void add(int u,int v,double w){ a[++tot].v=v; a[tot].w=w; a[tot].next=head[u]; head[u]=tot; } void dfs(int u,int fa){ int v; double w; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ v=a[tmp].v; w=a[tmp].w; if(v!=fa){ s[u]=s[u]+s[v]*w-s[u]*s[v]*w; dfs(v,u); } } } void dp(int u,int fa){ int v; double w,a1,a2; ans+=f[u]; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ v=a[tmp].v; w=a[tmp].w; if(v!=fa){ a1=(double)1.0-s[v]*w; if(fabs((double)a1-0)<1e-6)f[v]=1.0; else{ a2=(double)(f[u]-s[v]*w)/a1; f[v]=s[v]+a2*w-s[v]*a2*w; } dp(v,u); } } } int main(){ memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,(double)w/100); add(v,u,(double)w/100); } for(int i=1;i<=n;i++){ scanf("%lf",&s[i]); s[i]=(double)s[i]/100; } dfs(1,0); f[1]=s[1]; dp(1,0); printf("%.6lf",ans); return 0; }4.【xsy1964】守卫者的挑战
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; struct dclyz{ int a; double p; }a[201]; int n,m,l,s; double ans=0,f[201][201][201]; bool cmp(dclyz a,dclyz b){ return a.a>b.a; } int main(){ scanf("%d%d%d",&n,&l,&m); for(int i=1;i<=n;i++){ scanf("%lf",&a[i].p); a[i].p=(double)a[i].p/(double)100; } for(int i=1;i<=n;i++){ scanf("%d",&a[i].a); } sort(a+1,a+n+1,cmp); f[0][0][min(n,m)]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ for(int k=0;k<=n;k++){ f[i][j-1][k]+=f[i-1][j-1][k]*(1-a[i].p); if((s=k+a[i].a)<0)continue; s=min(s,n); f[i][j][s]+=f[i-1][j-1][k]*a[i].p; } } } for(int i=l;i<=n;i++){ for(int j=0;j<=n;j++){ ans+=f[n][i][j]; } } printf("%.6lf",ans); return 0; }太多了不写了
1.【xsy2408】[CF337D]邪恶古籍
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; struct edge{ int v,next; }a[500001]; int n,m,d,u,v,tot=0,ans=0,head[100001],f1[100001],f2[100001]; void add(int u,int v){ a[++tot].v=v; a[tot].next=head[u]; head[u]=tot; } void dfs(int u,int fa){ for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; if(v!=fa){ dfs(v,u); if(f1[v]!=-1){ f1[u]=max(f1[u],f1[v]+1); } } } } void dfs_(int u,int fa){ int a1=-1,a2=-1; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; if(v!=fa){ if(f2[u]!=-1){ f2[v]=max(f2[v],f2[u]+1); } if(f1[v]!=-1){ if(f1[v]>a1){ a2=a1; a1=f1[v]; }else if(f1[v]>a2){ a2=f1[v]; } } } } for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; if(v!=fa){ if(a1!=-1&&a2!=-1&&f1[v]==a1){ f2[v]=max(f2[v],a2+2); } if(f1[v]<a1){ f2[v]=max(f2[v],a1+2); } dfs_(v,u); } } } int main(){ memset(head,-1,sizeof(head)); memset(f1,-1,sizeof(f1)); memset(f2,-1,sizeof(f2)); scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=m;i++){ scanf("%d",&u); f1[u]=f2[u]=0; } for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1,0); dfs_(1,0); for(int i=1;i<=n;i++){ if(max(f1[i],f2[i])<=d)ans++; } printf("%d",ans); return 0; }2.【xsy2409】[CF697D]Puzzles
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; struct edge{ int v,next; }a[500001]; int n,u,tot=0,s[100001],head[100001]; double f[100001]; void add(int u,int v){ a[++tot].v=v; a[tot].next=head[u]; head[u]=tot; } void dfs(int u){ s[u]=1; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; dfs(v); s[u]+=s[v]; } } void dfs_(int u){ for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; f[v]=(double)((double)(s[u]-s[v]-1)*0.5+f[u]+1.000); dfs_(v); } } int main(){ memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=2;i<=n;i++){ scanf("%d",&u); add(u,i); } dfs(1); f[1]=1.000; dfs_(1); for(int i=1;i<=n;i++){ printf("%.2lf ",f[i]); } return 0; }3.【xsy2410】[CF486D]有效集合
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define modHA 1000000007LL using namespace std; struct edge{ int v,next; }a[500001]; int d,n,u,v,tot=0,num[100001],head[100001]; long long ans=0ll,f[100001]; void add(int u,int v){ a[++tot].v=v; a[tot].next=head[u]; head[u]=tot; } void dfs(int u,int fa,int rt){ f[u]=1; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; if(v!=fa&&!(num[v]>num[rt]||num[rt]-num[v]>d)&&!(num[v]==num[rt]&&v<rt)){ dfs(v,u,rt); f[u]=f[u]*(f[v]+1)%modHA; } } } int main(){ memset(head,-1,sizeof(head)); scanf("%d%d",&d,&n); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); } for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(int i=1;i<=n;i++){ dfs(i,0,i); ans=(ans+f[i])%modHA; } printf("%lld",ans); return 0; }4.【xsy2411】[CF161D]Distance in Tree
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; struct edge{ int v,next; }a[500001]; int n,k,u,v,tot=0,ans=0,f[50001][501],head[100001]; void add(int u,int v){ a[++tot].v=v; a[tot].next=head[u]; head[u]=tot; } void dfs(int u,int fa){ f[u][0]=1; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; if(v!=fa){ dfs(v,u); for(int i=0;i<k;i++){ ans+=f[u][i]*f[v][k-i-1]; } for(int i=1;i<=k;i++){ f[u][i]+=f[v][i-1]; } } } } int main(){ memset(head,-1,sizeof(head)); scanf("%d%d",&n,&k); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1,0); printf("%d",ans); return 0; }1.【xsy2117】摩尔庄园 2.【xsy2407】[CF708C]Centroids
0.模板（LCA）。。。 1.【xsy2018】[NOIP2013] 货车运输
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; struct edge{ int u,v,w; }a[1000001]; struct ed{ int v,w,next; }e[1000001]; int n,m,q,u,v,w,tot=0,p[16],dep[100001],fa[100001],f[10001][16],minn[10001][16],head[100001]; bool cmp(edge a,edge b){ return a.w>b.w; } int ff(int u){ return u==fa[u]?u:fa[u]=ff(fa[u]); } void add(int u,int v,int w){ e[++tot].v=v; e[tot].w=w; e[tot].next=head[u]; head[u]=tot; } void mst_k(){ sort(a+1,a+m+1,cmp); for(int i=1;i<=m;i++){ int x1=ff(a[i].u),x2=ff(a[i].v); if(x1!=x2){ add(a[i].u,a[i].v,a[i].w); add(a[i].v,a[i].u,a[i].w); fa[x1]=x2; } } } void cal_dep(int u){ dep[u]=dep[f[u][0]]+1; for(int i=1;p[i]<=n;i++){ f[u][i]=f[f[u][i-1]][i-1]; minn[u][i]=min(minn[u][i-1],minn[f[u][i-1]][i-1]); } for(int tmp=head[u];tmp!=-1;tmp=e[tmp].next){ int v=e[tmp].v; if(v!=f[u][0]){ f[v][0]=u; minn[v][0]=e[tmp].w; cal_dep(v); } } } int lca(int u,int v){ if(dep[u]<dep[v]){ swap(u,v); } for(int i=14;i>=0;i--){ if(p[i]<=dep[u]-dep[v])u=f[u][i]; } if(u==v)return u; for(int i=14;i>=0;i--){ if(f[u][i]!=f[v][i]){ u=f[u][i]; v=f[v][i]; } } return f[u][0]; } int query(int u,int v,int l){ int ans=0x7f7f7f7f; for(int i=14;i>=0;i--){ if(p[i]<=dep[u]-dep[l]){ ans=min(ans,minn[u][i]); u=f[u][i]; } } for(int i=14;i>=0;i--){ if(p[i]<=dep[v]-dep[l]){ ans=min(ans,minn[v][i]); v=f[v][i]; } } return ans; } int main(){ memset(head,-1,sizeof(head)); memset(minn,0x7f,sizeof(minn)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); } p[0]=1; for(int i=1;i<=14;i++){ p[i]=p[i-1]*2; } for(int i=1;i<=n;i++){ fa[i]=i; } mst_k(); dep[1]=1; f[1][0]=0; cal_dep(1); scanf("%d",&q); for(int i=1;i<=q;i++){ scanf("%d%d",&u,&v); int u1=ff(u),v1=ff(v); if(u1!=v1){ printf("-1\n"); continue; } printf("%d\n",query(u,v,lca(u,v))); } return 0; }2.【xsy2413】[JLOI2012]树
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int n,s,u,v,ans=0,num[100001],fa[100001]; int main(){ scanf("%d%d",&n,&s); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); } for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); fa[v]=u; } for(int i=1;i<=n;i++){ u=i; v=0; while(v<=s&&u!=0){ v+=num[u]; u=fa[u]; if(v==s)ans++; } } printf("%d",ans); return 0; }太多了不写了
1.【xsy2428】[Cqoi2010]内部白点
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define lowbit(n) (n&-n) using namespace std; struct node{ int x,y; }a[100001]; struct link{ int x,y,k,r; }s[1000001]; int n,ans,tot=0,h[100001],tree[400001]; bool cmp(node a,node b){ return a.x==b.x?a.y<b.y:a.x<b.x; } bool cmp_(node a,node b){ return a.y==b.y?a.x<b.x:a.y<b.y; } bool _cmp_(link a,link b){ return a.y==b.y?a.k<b.k:a.y<b.y; } void add(int u,int val){ for(;u<=n;u+=lowbit(u)){ tree[u]+=val; } } int query(int u){ int ans=0; for(;u>0;u-=lowbit(u)){ ans+=tree[u]; } return ans; } int ff(int u){ int l=1,r=n,mid; while(l<=r){ mid=(l+r)/2; if(h[mid]<u)l=mid+1; else if(h[mid]>u)r=mid; else return mid; } } void ins(bool ch,int l,int r,int ss){ if(!ch){ s[++tot].x=ff(l); s[tot].y=ss; s[tot].r=ff(r); s[tot].k=0; }else{ s[++tot].x=ff(ss); s[tot].y=l; s[tot].k=1; s[++tot].x=ff(ss); s[tot].y=r; s[tot].k=-1; } } int main(){ memset(tree,0,sizeof(tree)); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].x,&a[i].y); h[i]=a[i].x; } sort(h+1,h+n+1); sort(a+1,a+n+1,cmp); for(int i=2;i<=n;i++){ if(a[i].x==a[i-1].x){ ins(true,a[i-1].y,a[i].y,a[i].x); } } sort(a+1,a+n+1,cmp_); for(int i=2;i<=n;i++){ if(a[i].y==a[i-1].y){ ins(false,a[i-1].x,a[i].x,a[i].y); } } sort(s+1,s+tot+1,_cmp_); for(int i=1;i<=tot;i++){ if(s[i].k==0){ ans+=query(s[i].r-1)-query(s[i].x); }else{ add(s[i].x,s[i].k); } } printf("%d",ans+n); return 0; }2.【xsy2429】isn
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define lowbit(n) (n&-n) #define modHA 1000000007 typedef long long ll; using namespace std; ll n,ans=0,a[2001],b[2001],tree[2001][2001],f[2001][2001],dc[2001],p[2001]; void add(ll u,ll v,ll val){ for(;v<=n;v+=lowbit(v)){ tree[u][v]=(tree[u][v]+val)%modHA; } } ll query(ll u,ll v){ int ans=0; for(;v>0;v-=lowbit(v)){ ans=(ans+tree[u][v])%modHA; } return ans%modHA; } int main(){ memset(dc,0,sizeof(dc)); scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); b[i]=a[i]; } p[0]=1; for(int i=1;i<=n;i++){ p[i]=(p[i-1]*i)%modHA; } sort(b+1,b+n+1); for(int i=1;i<=n;i++){ a[i]=lower_bound(b+1,b+n+1,a[i])-b; } add(0,1,1); for(int i=1;i<=n;i++){ for(int j=i;j>=1;j--){ f[i][j]=query(j-1,a[i])%modHA; add(j,a[i],f[i][j]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dc[i]=(dc[i]+f[j][i])%modHA; } } for(int i=1;i<=n;i++){ ans=(((ans+dc[i]*p[n-i])%modHA-dc[i+1]*p[n-i-1]%modHA*(i+1)%modHA)%modHA+modHA)%modHA; } printf("%lld",ans); return 0; }3.【xsy2430】[cf341D]Iahub and Xors
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define lowbit(n) (n&-n) typedef long long ll; using namespace std; ll n,m,a,b,c,d,e,f,ans=0,tree[2][2][1001][1001]; void add(ll u,ll v,ll val){ int uu=u&1,vv=v&1; for(;u<=n;u+=lowbit(u)){ for(;v<=n;v+=lowbit(v)){ tree[uu][vv][u][v]^=val; } } } int query(ll u,ll v){ int uu=u&1,vv=v&1,ans=0; for(;u>0;u-=lowbit(u)){ for(;v>0;v-=lowbit(v)){ ans^=tree[uu][vv][u][v]; } } return ans; } int main(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++){ scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e); if(a==1){ ans=query(d,e); if(b>1)ans^=query(b-1,e); if(c>1)ans^=query(d,c-1); if(b>1&&c>1)ans^=query(b-1,c-1); printf("%lld\n",ans); }else{ scanf("%lld",&f); add(d+1,e+1,f); add(b,e+1,f); add(d+1,c,f); add(b,c,f); } } return 0; }4.【xsy2431】[cf597C]子序列
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define lowbit(n) (n&-n) using namespace std; typedef long long ll; ll n,k,a[100001],tree[100001][21]; void add(ll u,ll v,ll val){ for(;u<=n+1;u+=lowbit(u)){ tree[u][v]+=val; } } ll query(ll u,ll v){ ll ans=0; for(;u>0;u-=lowbit(u)){ ans+=tree[u][v]; } return ans; } int main(){ memset(tree,0,sizeof(tree)); scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } add(1,0,1); for(int i=1;i<=n;i++){ for(int j=1;j<=k+1;j++){ add(a[i]+1,j,query(a[i],j-1)); } } printf("%lld",query(n+1,k+1)); return 0; }1.【xsy2432】[BZOJ2819] Nim 2.【xsy2433】[BZOJ3155]Preprefix sum
1.【xsy1129】flow 树剖求链+线段树优化建图+最大流最小割
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> using namespace std; struct node{ int f,v,k,p; }aa[100001]; struct edge_dinic{ int v,w,op,next; }a[5000001]; struct edge_tree{ int v,next; }a1[100001]; int n,tot=0,tot1=0,sum=0,vs,vt,tim=0,ans=0,siz[100001],dfn[100001],top[100001],dep[100001],son[100001],tree[100001],nm1[100001],lv[1000001],head[1000001],head1[1000001]; void add(int u,int v){ a1[++tot1].v=v; a1[tot1].next=head1[u]; head1[u]=tot1; } void add1(int u,int v,int w){ a[++tot].v=v; a[tot].w=w; a[tot].op=tot+1; a[tot].next=head[u]; head[u]=tot; a[++tot].v=u; a[tot].w=0; a[tot].op=tot-1; a[tot].next=head[v]; head[v]=tot; } void dfs(int u){ siz[u]=1; son[u]=0; for(int tmp=head1[u];tmp!=-1;tmp=a1[tmp].next){ int v=a1[tmp].v; if(v!=aa[u].f){ dep[v]=dep[u]+1; dfs(v); siz[u]+=siz[v]; if(siz[v]>siz[son[u]])son[u]=v; } } } void dfs_(int u,int top_){ dfn[u]=++tim; nm1[tim]=u; top[u]=top_; if(son[u]){ dfs_(son[u],top_); } for(int tmp=head1[u];tmp!=-1;tmp=a1[tmp].next){ int v=a1[tmp].v; if(v!=aa[u].f&&v!=son[u]){ dfs_(v,v); } } } void build(int l,int r,int u){ sum=max(sum,u); if(l==r){ tree[nm1[l]]=u; return; } int mid=(l+r)/2; build(l,mid,u*2); build(mid+1,r,u*2+1); add1(u,u*2,0x7f7f7f7f); add1(u,u*2+1,0x7f7f7f7f); } void query(int l,int r,int u,int L,int R,int val){ if(L<=l&&r<=R){ add1(val,u,0x7f7f7f7f); return; } int mid=(l+r)/2; if(L<=mid)query(l,mid,u*2,L,R,val); if(R>mid)query(mid+1,r,u*2+1,L,R,val); } void work(int x,int y){ int cnt=y; y=aa[y].f; while(true){ int depth=dep[y]-dep[top[y]]+1; if(depth<x){ x-=depth; query(1,n,1,dfn[top[y]],dfn[y],cnt+sum); y=aa[top[y]].f; }else{ query(1,n,1,dfn[y]-x+1,dfn[y],cnt+sum); break; } } } bool bfs(){ queue<int>q; memset(lv,0,sizeof(lv)); lv[vs]=1; q.push(vs); while(!q.empty()){ int u=q.front(); q.pop(); for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; if(a[tmp].w!=0&&lv[v]==0){ lv[v]=lv[u]+1; if(v==vt)return true; q.push(v); } } } return false; } int dfs__(int u,int l){ int anss=0; if(u==vt||!l)return l; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v,flow; if(lv[v]==lv[u]+1){ flow=dfs__(v,min(l,a[tmp].w)); anss+=flow; l-=flow; a[tmp].w-=flow; a[a[tmp].op].w+=flow; if(!l)break; } } if(anss==0)lv[u]=0; return anss; } int main(){ memset(head1,-1,sizeof(head1)); memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d%d%d",&aa[i].f,&aa[i].v,&aa[i].k,&aa[i].p); if(aa[i].f){ add(i,aa[i].f); add(aa[i].f,i); } } dep[1]=0; dfs(1); dfs_(1,1); build(1,n,1); vs=0; vt=n+sum+1; for(int i=1;i<=n;i++){ if(aa[i].v>=0){ add1(vs,tree[i],aa[i].v); ans+=aa[i].v; }else{ add1(tree[i],vt,-aa[i].v); } add1(tree[i],sum+i,aa[i].p); if(aa[i].k)work(aa[i].k,i); } while(bfs())ans-=dfs__(vs,0x7f7f7f7f); printf("%d",ans); return 0; }2.【xsy2147】[ZJOI2008] 树的统计
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> using namespace std; struct edge{ int v,next; }a[1000001]; struct tree_node{ int s,mx; }tree[1000001]; int n,u,v,q,tot=0,tim=0,head[1000001],son[1000001],fa[1000001],w[1000001],dfn[1000001],dep[1000001],siz[1000001],top[1000001],nm[1000001]; char ord[10]; void add(int u,int v){ a[++tot].v=v; a[tot].next=head[u]; head[u]=tot; } void dfs(int u){ siz[u]=1; for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; if(v!=fa[u]){ dep[v]=dep[u]+1; fa[v]=u; dfs(v); siz[u]+=siz[v]; if(siz[v]>siz[son[u]])son[u]=v; } } } void dfs_(int u,int f){ dfn[u]=++tim; top[u]=f; if(son[u]==0)return; dfs_(son[u],f); for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){ int v=a[tmp].v; if(v!=fa[u]&&v!=son[u]){ dfs_(v,v); } } } void updata(int l,int r,int u,int s,int val){ if(l==r){ tree[u].mx=val; tree[u].s=val; return; } int mid=(l+r)/2; if(s<=mid)updata(l,mid,u*2,s,val); else updata(mid+1,r,u*2+1,s,val); tree[u].s=tree[u*2].s+tree[u*2+1].s; tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx); } int qmax(int l,int r,int u,int L,int R){ if(L<=l&&r<=R){ return tree[u].mx; } int mid=(l+r)/2,ans=-0x7f7f7f7f; if(L<=mid)ans=max(ans,qmax(l,mid,u*2,L,R)); if(R>mid)ans=max(ans,qmax(mid+1,r,u*2+1,L,R)); return ans; } int q_max(int u,int v){ int ans=-0x7f7f7f7f; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]])swap(u,v); ans=max(ans,qmax(1,n,1,dfn[top[u]],dfn[u])); u=fa[top[u]]; } if(dfn[u]>dfn[v])swap(u,v); ans=max(ans,qmax(1,n,1,dfn[u],dfn[v])); return ans; } int qsum(int l,int r,int u,int L,int R){ if(L<=l&&r<=R){ return tree[u].s; } int mid=(l+r)/2,ans=0; if(L<=mid)ans+=qsum(l,mid,u*2,L,R); if(R>mid)ans+=qsum(mid+1,r,u*2+1,L,R); return ans; } int q_sum(int u,int v){ int ans=0; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]])swap(u,v); ans+=qsum(1,n,1,dfn[top[u]],dfn[u]); u=fa[top[u]]; } if(dfn[u]>dfn[v])swap(u,v); ans+=qsum(1,n,1,dfn[u],dfn[v]); return ans; } int main(){ memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(int i=1;i<=n;i++){ scanf("%d",&w[i]); } for(int i=1;i<=n*4;i++){ tree[i].mx=-0x7f7f7f7f; } dep[1]=1; fa[1]=0; dfs(1); dfs_(1,1); for(int i=1;i<=n;i++){ updata(1,n,1,dfn[i],w[i]); } scanf("%d",&q); for(int i=1;i<=q;i++){ scanf("%s%d%d",ord,&u,&v); if(ord[0]=='C'){ updata(1,n,1,dfn[u],v); }else if(ord[0]=='Q'&&ord[1]=='M'){ printf("%d\n",q_max(u,v)); }else{ printf("%d\n",q_sum(u,v)); } } return 0; }太多了不写了
这几天集训其实很腐（CS+看Seed-D+每天2h农药），加上自己晚来一天，总是感觉做的题很少，又追不上同学的速度。。。（代码一些也是抄solution||网上的，感觉自己要AFO了）
