BZOJ2709
二分+最短路,主要是精度问题,可以根据我的程序调整精度.
#include#include #include #include #include #include using namespace std; typedef double f2; int head[10010],next[100010],end[100010],ind; f2 len[100010]; inline void reset(){ ind=0; memset(head,0,sizeof head); } inline void addedge(int a,int b,f2 l){ int q=++ind; end[q]=b; next[q]=head[a]; head[a]=q; len[q]=l; } bool map[110][110]; char s[110]; int lab[110][110],id; static const int dx[]={-1,1,0,0}; static const int dy[]={0,0,-1,1}; f2 d[10010]; queue q; bool inq[10010]; inline void spfa(int s){ int i,j; for(i=1;i<=id;++i) d[i]=1e10; d[s]=0; inq[s]=1; q.push(s); while(!q.empty()){ i=q.front(); q.pop(); inq[i]=0; for(j=head[i];j;j=next[j]){ if(d[end[j]]>d[i]+len[j]){ d[end[j]]=d[i]+len[j]; if(!inq[end[j]]){ inq[end[j]]=1; q.push(end[j]); } } } } } bool inrange(int x,int l,int r){ return x>=l&&x;<=r; } int main(){ int T; cin>>T; f2 L; int n,m,i,j,k; for(int Tcase=1;Tcase<=T;++Tcase){ scanf("%lf%d%d",&L;,&n;,&m;); int bx,by,ex,ey; memset(map,0,sizeof map); gets(s+1); for(i=1;i<=n;++i){ gets(s+1); for(j=1;j<=m;++j){ if(s[j]!='#') map[i][j]=1; if(s[j]=='S') bx=i,by=j; if(s[j]=='E') ex=i,ey=j; } } id=0; for(i=1;i<=n;++i) for(j=1;j<=m;++j) lab[i][j]=++id; f2 l=0,r=1000,mid; while(r-l>1e-10){ mid=(l+r)/2; reset(); for(i=1;i<=n;++i) for(j=1;j<=m;++j) if(map[i][j]) for(k=0;k<4;++k) if(inrange(i+dx[k],1,n)&&inrange;(j+dy[k],1,m)&↦[i+dx[k]][j+dy[k]]) addedge(lab[i][j],lab[i+dx[k]][j+dy[k]],(k==0||k==1)?mid:1); spfa(lab[bx][by]); if(d[lab[ex][ey]]
BZOJ2891
请参见弱省胡策Round2题解.
BZOJ2719
将所有坐标按照模3的余数分为九种类型,只考虑每种类型棋子的数目.
不难发现不跳过棋子的操作对于局面并不存在影响,然后跳过棋子的操作可以看做将两个棋子合并成一个.
于是搜索就行了.
需要注意一点:当当前棋盘上要合并到的位置已经满了,则不能进行这种合并.
#include#include #include #include #include #include using namespace std; typedef unsigned long long llu; struct State{ int d[3][3]; State(){ memset(d,0,sizeof d); } bool operator==(const State&B;)const{ for(int i=0;i<3;++i) for(int j=0;j<3;++j) if(d[i][j]!=B.d[i][j]) return 0; return 1; } inline llu hash(){ llu re=0,s=1; for(int i=0;i<3;++i) for(int j=0;j<3;++j) re+=s*d[i][j],s*=131; return re; } }; set s; bool ok[3][3][3][3][3][3]; struct Ope{ int x1,y1,x2,y2,x3,y3; Ope(){} Ope(int _x1,int _y1,int _x2,int _y2,int _x3,int _y3):x1(_x1),y1(_y1),x2(_x2),y2(_y2),x3(_x3),y3(_y3){} }O[1010]; int num; int n,m,x0,y0,K; int lim[3][3]; static const int dx[]={-1,-1,-1,0,0,1,1,1}; static const int dy[]={-1,0,1,-1,1,-1,0,1}; inline bool check(int x,int y){ return x>=1&&x;<=n&&y;>=1&&y;<=m; } inline void pre(){ num=0; memset(ok,0,sizeof ok); int x2,y2,x3,y3; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) for(int k=0;k<8;++k){ x2=i+dx[k],y2=j+dy[k]; x3=x2+dx[k],y3=y2+dy[k]; if(check(x2,y2)&✓(x3,y3)&&!ok[i%3][j%3][x2%3][y2%2][x3%3][y3%3]){ ok[i%3][j%3][x2%3][y2%2][x3%3][y3%3]=1; O[++num]=Ope(i%3,j%3,x2%3,y2%3,x3%3,y3%3); } } } State end; inline bool dfs(State&st;){ State tmp; if(st==end) return 1; int x1,y1,x2,y2,x3,y3; for(int i=1;i<=num;++i){ x1=O[i].x1,y1=O[i].y1; x2=O[i].x2,y2=O[i].y2; x3=O[i].x3,y3=O[i].y3; if(st.d[x1][y1]&&st.d;[x2][y2]&&st.d;[x3][y3] <=n;++i) for(j=1;j<=m;++j) ++lim[i%3][j%3]; State begin; while(K--){ scanf("%d%d",&x;,&y;); ++begin.d[x%3][y%3]; } for(i=0;i<3;++i) for(j=0;j<3;++j) end.d[i][j]=0; end.d[x0%3][y0%3]=1; pre(); s.clear(); s.insert(begin.hash()); if(dfs(begin)) puts("Yes"); else puts("No"); } return 0; }
BZOJ4103
虽然是傻逼题,但是多带一个log也是会TLE的.然而带不带log代码都一样长.
#include#include #include #include #include using namespace std; struct Node{ int d[2],s; }S[300010*32]; int cnt; int a[1010],b[300010],root[300010]; inline void insert(int&q;,int last,int dep,int x){ q=++cnt; S[q]=S[last]; ++S[q].s; if(dep<0) return; insert(S[q].d[(x>>dep)&1],S[last].d[(x>>dep)&1],dep-1,x); } int rootl[1010],rootr[1010]; int main(){ int n,m; scanf("%d%d",&n;,&m;); int i,j; for(i=1;i<=n;++i) scanf("%d",&a;[i]); for(i=1;i<=m;++i) scanf("%d",&b;[i]); for(i=1;i<=m;++i) insert(root[i],root[i-1],30,b[i]); int q,u,d,l,r,k; scanf("%d",&q;); while(q--){ scanf("%d%d%d%d%d",&u;,&d;,&l;,&r;,&k;); k=(d-u+1)*(r-l+1)+1-k; for(i=u;i<=d;++i) rootl[i]=root[l-1],rootr[i]=root[r]; int ans=0; for(i=30;i>=0;--i){ int ls=0; for(j=u;j<=d;++j) ls+=S[S[rootr[j]].d[(a[j]>>i)&1]].s-S[S[rootl[j]].d[(a[j]>>i)&1]].s; if(ls>=k){ for(j=u;j<=d;++j){ rootl[j]=S[rootl[j]].d[(a[j]>>i)&1]; rootr[j]=S[rootr[j]].d[(a[j]>>i)&1]; } } else{ k-=ls; ans+=1<<=d;++j){ rootl[j]=S[rootl[j]].d[1-((a[j]>>i)&1)]; rootr[j]=S[rootr[j]].d[1-((a[j]>>i)&1)]; } } } printf("%d\n",ans); } return 0; }
BZOJ3064
其实写这道题一开始我是拒绝的,但后来心血来潮了,于是就写了.
觉得这些操作都非常有道理.
同时必须要注意先下传历史标记,再下传当前标记.
具体的题解看18357的博客吧...
#include#include #include #include #include using namespace std; #define N 100010 #define inf 0x3f3f3f3f inline void maxi(int&x;,int y){ if(x >1; S[q].l=build(tl,mid); S[q].r=build(mid+1,tr); up(q); return q; } inline void Qadd(int q,int tl,int tr,int dl,int dr,int _ad){ down(q); if(dl<=tl&&tr;<=dr){ add(q,_ad); return; } int mid=(tl+tr)>>1; if(dr<=mid) Qadd(S[q].l,tl,mid,dl,dr,_ad); else if(dl>mid) Qadd(S[q].r,mid+1,tr,dl,dr,_ad); else{ Qadd(S[q].l,tl,mid,dl,mid,_ad); Qadd(S[q].r,mid+1,tr,mid+1,dr,_ad); } up(q); } inline void Qcover(int q,int tl,int tr,int dl,int dr,int _c){ down(q); if(dl<=tl&&tr;<=dr){ cover(q,_c); return; } int mid=(tl+tr)>>1; if(dr<=mid) Qcover(S[q].l,tl,mid,dl,dr,_c); else if(dl>mid) Qcover(S[q].r,mid+1,tr,dl,dr,_c); else{ Qcover(S[q].l,tl,mid,dl,mid,_c); Qcover(S[q].r,mid+1,tr,mid+1,dr,_c); } up(q); } inline int Qv(int q,int tl,int tr,int dl,int dr){ down(q); if(dl<=tl&&tr;<=dr) return S[q].v; int mid=(tl+tr)>>1; if(dr<=mid) return Qv(S[q].l,tl,mid,dl,dr); else if(dl>mid) return Qv(S[q].r,mid+1,tr,dl,dr); else return max(Qv(S[q].l,tl,mid,dl,mid),Qv(S[q].r,mid+1,tr,mid+1,dr)); } inline int Qhv(int q,int tl,int tr,int dl,int dr){ down(q); if(dl<=tl&&tr;<=dr) return S[q].hv; int mid=(tl+tr)>>1; if(dr<=mid) return Qhv(S[q].l,tl,mid,dl,dr); else if(dl>mid) return Qhv(S[q].r,mid+1,tr,dl,dr); else return max(Qhv(S[q].l,tl,mid,dl,mid),Qhv(S[q].r,mid+1,tr,mid+1,dr)); } int main(){ int n; scanf("%d",&n;); int i,j; for(i=1;i<=n;++i) scanf("%d",&a;[i]); build(1,n); int m,l,r,x; char q[10]; scanf("%d",&m;); while(m--){ scanf("%s%d%d",q,&l;,&r;); if(q[0]=='Q') printf("%d\n",Qv(1,1,n,l,r)); else if(q[0]=='A') printf("%d\n",Qhv(1,1,n,l,r)); else if(q[0]=='P'){ scanf("%d",&x;); Qadd(1,1,n,l,r,x); } else{ scanf("%d",&x;); Qcover(1,1,n,l,r,x); } } return 0; }
BZOJ2482
考虑如果我们已经有了所有以$i$为开头的区间的满足题意的子段和(而不是最大子段和),那我们如何求出所有开头为$i-1$的区间的子段和呢?
令$nxt[i]$表示$i$后面第一个与$i$的权值相同的位置,那我们只需把$(i-1,nxt[i-1]-1)$这段区间的答案加上$i-1$的权值即可.
我们可以考虑离线处理,将所有询问区间按照起点从大到小排序,然后依次从大到小添加左端点,添加完左端点后则回答所有左端点为当前左端点的询问区间的答案,答案显然就是这段区间答案的历史最大值.
至于为什么是这样,大家理性yy一下吧.
#include#include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define N 100010 int a[N],seq[N],sav[N],id; inline int getid(int x){ return lower_bound(sav+1,sav+id+1,x)-sav; } int nxt[N],last[N]; struct Node{ int l,r,hv,v,ad,had; }S[200010]; int cnt; inline void maxi(int&x;,int y){ if(x >1; S[q].l=build(tl,mid); S[q].r=build(mid+1,tr); return q; } inline void add(int x,int _ad){ maxi(S[x].hv,S[x].v+=_ad); maxi(S[x].had,S[x].ad+=_ad); } inline void h_add(int x,int _had){ maxi(S[x].hv,S[x].v+_had); maxi(S[x].had,S[x].ad+_had); } inline void down(int x){ if(S[x].l){ if(S[x].had!=0){ h_add(S[x].l,S[x].had); h_add(S[x].r,S[x].had); S[x].had=0; } if(S[x].ad!=0){ add(S[x].l,S[x].ad); add(S[x].r,S[x].ad); S[x].ad=0; } } } inline void up(int x){ if(S[x].l){ S[x].v=max(S[S[x].l].v,S[S[x].r].v); maxi(S[x].hv,max(S[S[x].l].hv,S[S[x].r].hv)); } } inline void Qadd(int q,int tl,int tr,int dl,int dr,int _ad){ down(q); if(dl<=tl&&tr;<=dr){ add(q,_ad); return; } int mid=(tl+tr)>>1; if(dr<=mid) Qadd(S[q].l,tl,mid,dl,dr,_ad); else if(dl>mid) Qadd(S[q].r,mid+1,tr,dl,dr,_ad); else{ Qadd(S[q].l,tl,mid,dl,mid,_ad); Qadd(S[q].r,mid+1,tr,mid+1,dr,_ad); } up(q); } inline int Qhv(int q,int tl,int tr,int dl,int dr){ down(q); if(dl<=tl&&tr;<=dr) return S[q].hv; int mid=(tl+tr)>>1; if(dr<=mid) return Qhv(S[q].l,tl,mid,dl,dr); else if(dl>mid) return Qhv(S[q].r,mid+1,tr,dl,dr); else return max(Qhv(S[q].l,tl,mid,dl,mid),Qhv(S[q].r,mid+1,tr,mid+1,dr)); } struct Interval{ int l,r,lab; Interval(){} Interval(int _l,int _r):l(_l),r(_r){} bool operator<(const Interval&B;)const{ return l>B.l; } }I[N]; int ans[N]; int main(){ //freopen("tt.in","r",stdin); int n; scanf("%d",&n;); int i,j; for(i=1;i<=n;++i) scanf("%d",&a;[i]),seq[i]=a[i]; sort(seq+1,seq+n+1); for(i=1;i<=n;){ for(j=i;j!=n&&seq;[j]==seq[j+1];++j); sav[++id]=seq[i]; i=j+1; } for(i=n;i>=1;--i){ int _id=getid(a[i]); nxt[i]=last[_id]==0?n+1:last[_id]; last[_id]=i; } int Q; scanf("%d",&Q;); for(i=1;i<=Q;++i){ scanf("%d%d",&I;[i].l,&I;[i].r); I[i].lab=i; } sort(I+1,I+Q+1); build(1,n); j=1; for(i=n;i>=1;--i){ Qadd(1,1,n,i,nxt[i]-1,a[i]); for(;j<=Q&&I;[j].l==i;++j) ans[I[j].lab]=Qhv(1,1,n,i,I[j].r); } for(i=1;i<=Q;++i) printf("%d\n",max(0,ans[i])); return 0; }
弱省胡策Round1 IHHH
令字符集大小为$|S|$,所有串的总长度为$\sum{L}$.
如果内存大一点的话,就可以直接fail树+主席树了,这样空间和时间是$O(\sum_{L}|S|+\sum{L}logn)$.
由于空间的常数有点大,这样就MLE了.
考虑把所有的询问拆分到$O(logn)$个线段树节点上,然后对于每个线段树节点,我们建立这个节点的所有串的ac自动机,然后对于这个节点上所有的询问暴力在上面走一遍.
这样每个串都会被建到$O(logn)$的ac自动机上,然后每个询问串都会被走$O(logn)$遍.
这样时间复杂度是$O(\sum{L}logn)$,但内存是线性的,于是很轻松就过了.
#include#include #include #include #include #include #define N 100010 #define L 500010 int s_begin[N],s_end[N],ends,t_begin[N],t_end[N],endt; char s[L],t[L],tmp[L]; struct Node{ int l,r; std::vector v; }S[N<<1]; int cnt; inline int build(int tl,int tr){ int q=++cnt; if(tl==tr) return q; int mid=(tl+tr)>>1; S[q].l=build(tl,mid); S[q].r=build(mid+1,tr); return q; } inline void cover(int q,int tl,int tr,int dl,int dr,int lab){ if(dl<=tl&&tr;<=dr){ S[q].v.push_back(lab); return; } int mid=(tl+tr)>>1; if(dr<=mid) cover(S[q].l,tl,mid,dl,dr,lab); else if(dl>mid) cover(S[q].r,mid+1,tr,dl,dr,lab); else{ cover(S[q].l,tl,mid,dl,mid,lab); cover(S[q].r,mid+1,tr,mid+1,dr,lab); } } int id,tranc[L][26],dep[L],fail[L]; inline void reset(){ id=0; memset(tranc[0],0,sizeof tranc[0]); } inline int newnode(){ int q=++id; for(int i=0;i<26;++i) tranc[q][i]=0; dep[q]=fail[q]=0; return q; } std::queue q; int ans[N]; inline void solve(int q,int tl,int tr){ if(S[q].v.size()){ reset(); for(int i=tl;i<=tr;++i){ int p=0; for(int j=s_begin[i];j<=s_end[i];++j){ if(!tranc[p][s[j]-'a']) tranc[p][s[j]-'a']=newnode(); p=tranc[p][s[j]-'a']; } dep[p]=s_end[i]-s_begin[i]+1; } int u,v,r; for(int i=0;i<26;++i) if(tranc[0][i]) ::q.push(tranc[0][i]); while(!::q.empty()){ u=::q.front(); ::q.pop(); for(int i=0;i<26;++i){ if(tranc[u][i]){ ::q.push(v=tranc[u][i]); for(r=fail[u];r&&!tranc[r][i];r=fail[r]); dep[v]=std::max(dep[v],dep[fail[v]=tranc[r][i]]); } else tranc[u][i]=tranc[fail[u]][i]; } } for(int i=0;i <=t_end[S[q].v[i]];++j) ans[S[q].v[i]]=std::max(ans[S[q].v[i]],dep[p=tranc[p][t[j]-'a']]); } } int mid=(tl+tr)>>1; if(tl!=tr){ solve(S[q].l,tl,mid); solve(S[q].r,mid+1,tr); } } int main(){ //freopen("tt.in","r",stdin); int n,q; scanf("%d%d",&n;,&q;); int i,j,len; for(i=1;i<=n;++i){ scanf("%s",tmp+1); len=strlen(tmp+1); s_begin[i]=ends+1; s_end[i]=ends+len; for(j=1;j<=len;++j) s[++ends]=tmp[j]; } build(1,n); int l,r; for(i=1;i<=q;++i){ scanf("%d%d%s",&l;,&r;,tmp+1); len=strlen(tmp+1); t_begin[i]=endt+1; t_end[i]=endt+len; for(j=1;j<=len;++j) t[++endt]=tmp[j]; cover(1,1,n,l,r,i); } solve(1,1,n); for(i=1;i<=q;++i) printf("%d\n",ans[i]); return 0; }
[20150607]A
题目大意:对于一个排列,权值为相邻两个元素的差的绝对值之和.给定$n$,并给出某些限制,限制形式为$A_{x}=y$,即排列的第$x$个元素是$y$.求所有$1-n$的且满足限制条件的排列的权值之和对$998244353$取模的余数.
思路:由于太懒就不写题解啦蛤蛤.
#include#include #include #include #include using namespace std; typedef long long ll; #define N 1000010 int d[N],ins[N],seq[N],id; ll pre[N]; int ds[N]; static const int mod=998244353; inline void inc(int&x;,int y){ if((x+=y)>=mod) x-=mod; } int fac[N]; int dist(int a,int b){ return a<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return x; } int main(){ int n; scanf("%d",&n;); int i,j; for(i=1;i<=n;++i){ d[i]=getint(); if(d[i]) ins[d[i]]=i; } for(i=1;i<=n;++i) if(!ins[i]){ seq[++id]=i; pre[id]=pre[id-1]+seq[id]; } seq[id+1]=n+1; for(fac[0]=i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%mod; if(id==n){ int ans=0; for(i=1;i < < < < <=n;++i) if(!d[i]) d[i]=seq[1]; int ans=0; for(i=1;i < < <=id;++i) inc(dsum,(((ll)(i-1)*seq[i]-pre[i-1])+(pre[id]-pre[i]-(ll)(id-i)*seq[i]))%mod); int ans=0; j=0; for(i=1;i<=n;++i){ if(ins[i]){ while(i>=seq[j+1]) ++j; ds[i]=(((ll)j*i-pre[j])+(pre[id]-pre[j]-(ll)(id-j)*i))%mod; } } for(i=1;i<=n;){ if(d[i]==0){ for(j=i+1;j<=n&&d;[j]==0;++j); i=j; } else{ for(j=i+1;j<=n&&d;[j]>0;++j); I[++num]=Interval(i,j-1); i=j; } } for(i=1;i<=num;++i){ for(j=I[i].l;j< <
[20150607]B
题目大意:定义一个数的权值为这个数的十进制表示的最长的等差子串的长度.现在问$[l,r]$区间内的权值和.
思路:典型的数位dp.我是这样做的:令$f[i][j][k][lp][ls]$表示长度为$i$,首位的数字为$j$,最长前缀等差子串的公差为$k$,最长前缀等差子串的长度为$lp$,最长等差子串的长度为$ls$的个数.
然后转移就随便了.
最后还是转化为前缀和相减,按位确定一下,也不是很难.
拍一下就行了.
#include#include #include #include #include #include using namespace std; typedef long long ll; ll f[14][10][22][14][14]; #define c(x) ((x)+10) inline int getans(ll x){ if(x==0) return 0; int stack[20]; int top=0; for(;x;x/=10) stack[++top]=x%10; int ans=1; for(int i=1;i <10;++j) for(k=-9;k<=10;++k) for(lp=1;lp<=i;++lp) for(ls=1;ls<=i;++ls) ans+=f[i][j][c(k)][lp][ls]*ls; for(i=top;i>=1;--i){ int ch=stack[i]; for(int _j=i==top?1:0;_j <10;++j) for(k=-9;k<=10;++k) for(lp=1;lp<=i-1;++lp) for(ls=1;ls<=i-1;++ls){ if(f[i-1][j][c(k)][lp][ls]){ int _lp=lp,_ls=ls,last=j,_k=k; for(int ins=i;ins<=top;++ins){ if(stack[ins]-last==_k){ ++_lp; } else{ _lp=2; _k=stack[ins]-last; } _ls=max(_ls,_lp); last=stack[ins]; } ans+=f[i-1][j][c(k)][lp][ls]*_ls; } } } stack[i]=ch; } for(long long c=max(1ll,x/10*10);c<=x;++c) ans+=getans(c); return ans; } int main(){ int i,j,k,lp,ls,g,np,ns; for(i=0;i<10;++i) f[1][i][c(10)][1][1]=1; for(i=1;i<13;++i) for(j=0;j<10;++j) for(k=-9;k<=10;++k) for(lp=1;lp<=i;++lp) for(ls=1;ls<=i;++ls) for(g=0;g<10;++g){ np=(j+k==g)?lp+1:2; ns=max(ls,np); f[i+1][g][c(g-j)][np][ns]+=f[i][j][c(k)][lp][ls]; } int T; cin>>T; ll L,R; while(T--){ cin>>L>>R; cout< <
[20150607]C
题目大意:(以下是原题面)
hzc有一个只包含大写字母的字符串 s. 他可以对这个字符串进行任意次的修改，允许的修改有：
1. 他可以添加下划线：('_') 到字符串的任意位置。
2. 他可以删除字符串里边的任意字符。
3. 他可以交换字符串的任意两个字符。
修改后的字符串，每一个字符的值为它的ASCII码值。
修改后的字符串必须满足如下条件：
1. 字符串的长度等于 n
2. 每个相同字母之间必须有至少 k 个字符的值比它们的值大。（下划线不当作字母）
计算hzc一共能得到多少不同的字符串？ 答案对1000003取模。
思路:注意到答案只与字母的数量有关.我们从小到大向最终的字符串中插入字母,令$f[i][j]$表示只考虑前$i$种字母,共插入了$j$个的方案数.那么我们显然应该枚举插入多少个当前的字母,假设我们要从$f[i-1][j]$转移到$f[i][j+g]$,那么方案数是多少呢?现在空着的位置还有$n-j$个,同时相邻的两个当前字母至少至少应该相隔$k$个空格,那么有$(g-1)\times{k}$个空格是不能用的,于是从剩下的空格中选择$g$个就行了,利用组合数算一算就行了.
那么从大到小为什么不能这样简单呢?
总之是不能像从小到大这样直接做的啦!
弱省胡策Round1 OVOO
一个状态就是一个合法的点集,权值即为所有点集里面的点的父亲边的权值和.
那么我们依然利用优先队列来维护,弹出一个状态的时候在队列中加入比这个状态大且最小的状态,这样做$k$次就行了.
要想比这个状态大一点点,我们首先可以考虑添加一个儿子,同时这个儿子父亲边的权值最小.
对于每个状态,我们维护一个堆,里面存的是所有接下来可以拓展的儿子,那么拓展下一个状态直接取堆顶就行喽.
然而比这个状态大一点点不一定就是拓展出一个新的儿子.
考虑这个状态的父亲状态,在这个父亲状态中我们取堆顶的左右儿子进行拓展不也是比这个状态大一点点嘛.
所以我们得到一个状态,首先拓展出一个添加最小儿子的状态,然后再添加一个将堆顶删除掉的状态.
(说不太明白,不过容易发现这样是对的
然后这些东西都用可持久化可并堆来维护.
#include#include #include #include #include #include using namespace std; #define N 100010 struct Node{ Node*l,*r; int v,lab,dist; Node():dist(0){} }mem[N*60],*P=mem,Tnull,*null=&Tnull; inline void copy(Node*&x;,Node*y){ if(y==null) x=null; else *x=*y; } inline Node*Newnode(){ P->l=P->r=null; P->dist=1; return P++; } inline Node*Merge(Node*x,Node*y){ Node*re=Newnode(); if(x==null||y==null) copy(re,x==null?y:x); else{ if(x->v>y->v) swap(x,y); copy(re,x); re->r=Merge(x->r,y); if(re->r->dist>re->l->dist) swap(re->l,re->r); re->dist=re->r->dist+1; } return re; } Node*Root[N]; int pa[N],v[N]; int head[N],next[N],end[N]; inline void addedge(int a,int b){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q++; } inline void dfs(int x){ Root[x]=null; for(int j=head[x];j;j=next[j]){ Node*tmp=Newnode(); tmp->v=v[end[j]]; tmp->lab=end[j]; tmp->dist=1; Root[x]=Merge(Root[x],tmp); } for(int j=head[x];j;j=next[j]) dfs(end[j]); } typedef long long ll; struct State{ Node*p; ll v; bool operator<(const State&B;)const{ return v+p->v>B.v+B.p->v; } }; priority_queue Q; int main(){ int n,K; scanf("%d%d",&n;,&K;); int i,j; for(i=2;i<=n;++i){ scanf("%d%d",&pa;[i],&v;[i]); addedge(pa[i],i); } dfs(1); State begin; begin.p=Root[1]; begin.v=0; Q.push(begin); ll ans=0; State tmp,nxt; for(int i=2;i<=K;++i){ if(Q.empty()) break; tmp=Q.top(); Q.pop(); ans=tmp.v+tmp.p->v; Node*next=Merge(tmp.p->l,tmp.p->r); if(next!=null){ nxt=tmp; nxt.p=next; Q.push(nxt); } next=Merge(next,Root[tmp.p->lab]); if(next!=null){ nxt=tmp; nxt.p=next; nxt.v+=tmp.p->v; Q.push(nxt); } } cout< <
弱省胡策Round4 Message
无脑分数规划+最大权闭合图,有点卡精度,比赛时inf设成了1e12是70分,后来改成了1e10就过了.
#include#include #include #include #include using namespace std; typedef double f2; #define eps 1e-10 #define inf 1e10 struct Solver{ static const int V=2010; static const int E=100010; int head[V],end[E],next[E],ind; f2 flow[E]; int d[V]; inline void reset(){ ind=0; memset(head,-1,sizeof head); } inline void addedge(int a,int b,f2 c){ int q=ind++; end[q]=b; next[q]=head[a]; head[a]=q; flow[q]=c; } inline void make(int a,int b,f2 c){ addedge(a,b,c); addedge(b,a,0); } inline bool bfs(int s,int t){ static int q[V]; memset(d,-1,sizeof d); d[s]=0; int fr=0,ta=0; q[ta++]=s; while(fr!=ta){ int i=q[fr++]; for(int j=head[i];j!=-1;j=next[j]) if(flow[j]>eps&&d;[end[j]]==-1){ d[end[j]]=d[i]+1; q[ta++]=end[j]; } } return d[t]!=-1; } inline f2 dinic(int p,int t,f2 Maxflow){ if(p==t) return Maxflow; f2 last=Maxflow; for(int j=head[p];j!=-1;j=next[j]){ if(flow[j]>eps&&d;[end[j]]==d[p]+1){ f2 to=dinic(end[j],t,flow[j]>last?last:flow[j]); if(to>eps){ flow[j]-=to; flow[j^1]+=to; if((last-=to) <=n;++i) scanf("%d",&c;[i]); int sigp=0; for(i=1;i<=m;++i){ scanf("%d%d%d",&a;[i],&b;[i],&p;[i]); sigp+=p[i]; } f2 L=0,R=1e6,mid; while(R-L>eps){ mid=(L+R)*.5; g.reset(); int s=0,t=n+m+1; for(i=1;i<=m;++i) g.make(s,n+i,p[i]); for(i=1;i<=n;++i) g.make(i,t,mid*c[i]); for(i=1;i<=m;++i){ g.make(n+i,a[i],inf); g.make(n+i,b[i],inf); } f2 res=g.Maxflow(s,t); if(sigp-res>0) L=mid; else R=mid; } printf("%.2lf",L+eps); return 0; }
弱省胡策Round4 Road
一个非常有用的事实:一个边双连通图必定是一个边双连通子图再加上条链组合成的.
一个点自己可以是一个边双连通子图,也可以看成一条链.
这样可以令$f_i$表示$i$这个集合内部的点组成一个双连通图的最小代价.
再令$g_{i,j,k}$表示$i$这个集合内部的点组成一条链,且两个端点分别是$j,k$的最小代价.
再预处理出$h1_{i,j},h2_{i,j}$分别表示点$j$到集合$i$的所有边的最小长度和次小长度.
然后再按照刚才说的状态随便转移一下就好了.
复杂度呢:我懒不想算了哈哈哈.
弱省胡策Round4 Express
原题大赛:BZOJ3302
暴力很好写,就是枚举把哪条边割断,然后两个部分分别求一下重心就行了.
然后现在我们知道树的高度很小,于是我们可以先做一些预处理,然后我们找出每个点子树权值和最大以及次大的儿子,这样找重心的时候$O(1)$就能知道走向哪个儿子了.
然后依然枚举割断那条边,但是不同的是这次我们直接$O(h)$就能找到重心,然后根据我们之前处理出的信息$O(1)$就能知道现在的代价.
所以这样做的复杂度$O(nh)$.
我的代码会被菊花卡超时,就不放了.
欧拉回路(通路)
最近随便搞了一下这个东西,稍微总结一下吧.
有向图:
存在欧拉回路当且仅当图连通并且所有点入度与出度相等.
存在欧拉通路当且仅当图连通并且所有点入度与出度相等或存在两个点入度-出度分别为-1和1,且剩下的点入度=出度.
无向图:
存在欧拉回路当且仅当图连通并且所有点度数为偶数.
存在欧拉通路当且仅当图连通并且所有点度数为偶数,或者存在两个点度数为奇数,剩下的点度数为偶数.
在判定了以上条件的情况下,就可以用一个简单的dfs找出一条欧拉回路(通路).
从一个合法的起点出发,然后每走一条边就将这条边删除,然后走完之后就把这条边入栈.
最后从栈顶到栈底就是一个合法的序列.
(但是现在依然没有非常理解...)
BZOJ2013
一开始看题目是觉得所有两块砖都满足上述的关系.
然后没过样例...
然后发现是只有相邻两块砖满足题目中说的关系!
于是就变成了逗逼题.
按照砖块长度从小到大排序,考虑前面所有的砖块都放好了,现在我们要插入最大的砖块,那么他作为下面的砖块肯定不会有影响(因为他最大),那么只需考虑他作为上面的砖块,也就是说他只能放在一些砖块的上面,而这个数目我们可以利用单调性扫出来,对于前面放的所有方案,我们都有这些放法,所以答案显然就是前面的答案乘上这个数目.
于是简单扫一遍.
时间$O(nlogn)$.
#include#include #include #include #include using namespace std; inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return x; } int A[1000010]; static const int mod=(1e9)+9; int main(){ int n=getint(),d=getint(); int i,j; for(i=1;i<=n;++i) A[i]=getint(); sort(A+1,A+n+1); j=n; A[0]=-1e9; int ans=1; for(i=n;i>=1;--i){ while(A[i]-A[j-1]<=d) --j; ans=(long long)ans*(i-j+1)%mod; } cout< <
BZOJ2386
显然将要求从小到大排序,则同一个分组的人是连续一段.
令$f_i$表示把前$i$个人进行分组,最多分成多少组.
然后利用前缀和优化一下就行了.
时间$O(nlogn)$.
#include#include #include #include #include using namespace std; #define inf 0x3f3f3f3f inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return x; } #define N 1000010 int a[N],f[N],g[N]; int main(){ int n=getint(); int i,j; for(i=1;i<=n;++i) a[i]=getint(); sort(a+1,a+n+1); for(i=1;i<=n;++i){ if(a[i]>i) f[i]=-inf; else f[i]=g[i-a[i]]+1; g[i]=max(g[i-1],f[i]); } cout< <
BZOJ3242
首先显然暴力算法是枚举删掉环上每条边,并求此时树的直径,并取最小值.这样是$O(n^2)$的.
我们只考虑环上的点,记录第$i$个点下面子树的最长延伸为$d_i$,从这个点到第$i$个点需要走的链的长度为$s_i$(由于删除了一条边,所以变环为链).那我们就需要找出一对$(i,j)$,使得$d_i+s_i-s_j+d_j=(d_i+s_i)+(d_j-s_j)$最大,所以我们分别维护这两个量的最大值即可,由于要求$i,j$不同,我们就维护这两个量的最大值以及次大值就行了.
于是这样就能做到$O(nlogn)$.
我一开始的方法非常麻烦,是因为我没有将式子拆开,因而考虑了很多点之间的位置关系,这样固定一个点,将信息都利用值来表示看起来就非常简单了.
由于我太懒就不写代码了.
BZOJ3648
考虑对于树的情况直接树分治就行了.
玛德我就暴力用树状数组$O(nlog^2n)$!
对于基环树,我们不妨拆掉一条环上的边变成一颗树,首先对于这棵树统计一下所有合法路径的数目;然后剩下的路径都固定的经过一条环上的边,直接拿主席树随便玩就行了.
BZOJ1768
考虑先枚举行,然后很容易处理出这一行最多往下延伸多少.然后我们需要排个序,然后枚举一遍.关键这样是$O(nmlogm)$,会超时.
窝们考虑相邻的两行,对于所有的元素,要么+1,要么变成0.这样就不用排序也能维护啦!
总时间复杂度$O(nm)$.
[UR8]A
我的思路比较傻逼,就是把整个图划分成一些黑白相间的块,然后就可以$O(1)$统计两个块之间的距离了.
于是在找这个块在哪里的时候带了一个log...
#include#include #include #include #include using namespace std; #define N 100010 int s[N]; int x[N],y[N],cntx,cnty; inline int getxid(int _x){ int d=upper_bound(x+1,x+cntx+1,_x)-x; return d-1; } inline int getyid(int _y){ int d=upper_bound(y+1,y+cnty+1,_y)-y; return d-1; } inline int getansx(int x1,int x2){ if(x1>x2) swap(x1,x2); return min(x2-x1,cntx-(x2-x1)-(cntx&1)); } inline int getansy(int y1,int y2){ if(y1>y2) swap(y1,y2); return min(y2-y1,cnty-(y2-y1)-(cnty&1)); } int main(){ //freopen("tt.in","r",stdin); int n,m; scanf("%d%d",&n;,&m;); int i,j; for(i=1;i<=n;++i) scanf("%d",&s;[i]); for(i=1;i<=n;){ for(j=i;j!=n&&s;[j]==s[j+1];++j); x[++cntx]=i; i=j+1; } x[cntx+1]=n+1; for(i=1;i<=m;++i) scanf("%d",&s;[i]); for(i=1;i<=m;){ for(j=i;j!=m&&s;[j]==s[j+1];++j); y[++cnty]=i; i=j+1; } y[cnty+1]=m+1; int q; scanf("%d",&q;); int x1,y1,x2,y2; while(q--){ scanf("%d%d%d%d",&x1;,&y1;,&x2;,&y2;); x1=getxid(x1),y1=getyid(y1); x2=getxid(x2),y2=getyid(y2); printf("%d\n",getansx(x1,x2)+getansy(y1,y2)); } return 0; }
[UR8]B
感觉好神一点不会,其实是简单题.
由于有$a,b,c\geq{0}$,所以对于$x_1\leq{x_2},y_1\leq{y_2}$,$(x1,y1)$什么时候都没有$(x2,y2)$优,就可以直接扔掉了.
所以对于每个线段树节点维护一个阶梯状序列就行了.
由于数据随机,这样的序列长度为$O(logn)$级别.
由于要打翻转标记,所以还要维护一个反的序列.
这样修改和询问都是$O(log^2n)$,直接暴力维护序列.
我们换一种方法,每个线段树节点都维护一个矩形框,这样修改只需$O(logn)$.
对于询问,窝现在有点难受,泥萌去看吉利的题解吧...
BZOJ3198
hash+容斥原理,我写的容斥是关于集合的,有点暴力...
#include#include #include #include #include using namespace std; #define N 100010 int a[N][6]; typedef unsigned long long llu; static const int seed=200019; struct Hashset{ static const int mod=13131; int head[mod],v[N],next[N],ind; llu f[N]; inline void reset(){ ind=0; memset(head,-1,sizeof head); } inline void insert(llu x){ int ins=x%mod; for(int j=head[ins];j!=-1;j=next[j]) if(f[j]==x){ ++v[j]; return; } f[ind]=x; v[ind]=1; next[ind]=head[ins]; head[ins]=ind++; } }M; long long f[1<<6],g[1<<6]; int main(){ int n,k; cin>>n>>k; int i,j; for(i=1;i<=n;++i) for(j=0;j<6;++j) scanf("%d",&a;[i][j]); for(int s=0;s<(1<<6);++s){ M.reset(); for(i=1;i<=n;++i){ llu p=0; for(j=0;j<6;++j) if((s>>j)&1) p=p*seed+a[i][j]; M.insert(p); } for(i=0;i <<6)-1;s>=0;--s){ g[s]=f[s]; for(int _s=s+1;_s<(1<<6);++_s) if((_s|s)==_s) g[s]-=g[_s]; int cnt=0; for(i=0;i<6;++i) if((s>>i)&1) ++cnt; if(cnt==k) ans+=g[s]; } cout< <
BZOJ2102
看起来和上面的那道题目没什么区别.
BZOJ2384
以前拿主席树暴力,现在由于主席树要被卡内存,于是学习了一下树状数组的方法.
话说我一直以为这个方法是数据弱才能卡过去的,其实不然,KMP算法是最坏$O(n)$的!
我们考虑一次匹配,会有一个指针$j$,如果匹配了$j++$,否则不断执行$j=next[j]$这个过程.
不妨设模式串长度为$n$,文本串长度为$m$,那么匹配的时候$j++$这个过程最多只会进行$m$次,而每执行一次$j=next[j]$这个过程$j$都会减少,并且$j$不能为负数,所以减少总量$\leq$增加总量$\leq{m}$.所以这两个过程都是$O(m)$级别的.
这个题目是求排名的匹配,那我们就把一个元素的"值"规定为这个元素比前面的区间中大的元素的个数,然后匹配的时候就比较一下这个值相不相等就行了.
我们用两个树状数组暴力维护当前合法区间的值,由于上述的复杂度证明,总时间为$O(mlogm)$.
具体的细节需要自己脑补一下...
(不知道怎么线性...)
#include#include #include #include #include #include using namespace std; #define N 1000010 int a[N],b[N],sav[N]; int A[N],B[N]; inline int ask(int A[],int x){ int re=0; for(;x;x-=x&-x) re+=A[x]; return re; } inline void modify(int A[],int x,int d){ for(;x<=1000000;x+=x&-x) A[x]+=d; } int pre[N]; inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return x; } int main(){ //freopen("tt.in","r",stdin); int n=getint(),m=getint(); int i,j; for(i=1;i<=n;++i){ a[getint()]=i; } for(i=1;i<=m;++i) sav[i]=b[i]=getint(); sort(sav+1,sav+m+1); for(i=1;i<=m;++i) b[i]=lower_bound(sav+1,sav+m+1,b[i])-sav; //modify(a[1],1); j=0; for(i=2;i<=n;++i){ int ins=i-j; while(1){ if(j==0) break; if(ask(A,a[j+1]-1)==ask(B,a[i]-1)) break; int _(pre[j]); while(j>_){ modify(B,a[ins++],-1); modify(A,a[j--],-1); } } if(ask(A,a[j+1]-1)==ask(B,a[i]-1)){ modify(A,a[++j],1); modify(B,a[i],1); } pre[i]=j; } memset(A,0,sizeof A); memset(B,0,sizeof B); j=0; vector ans; for(i=1;i<=m;++i){ int ins=i-j; while(1){ if(j==0) break; if(ask(A,a[j+1]-1)==ask(B,b[i]-1)) break; int _=pre[j]; while(j>_){ modify(B,b[ins++],-1); modify(A,a[j--],-1); } } if(ask(A,a[j+1]-1)==ask(B,b[i]-1)){ modify(A,a[++j],1); modify(B,b[i],1); } if(j==n){ int ins=i-j+1; while(j>pre[n]){ modify(B,b[ins++],-1); modify(A,a[j--],-1); } ans.push_back(i-n+1); } } printf("%d\n",ans.size()); for(i=0;i
BZOJ1461
基本同上一题,但是还需要考虑到相等元素的影响,需要分别比较小于的个数以及等于的个数,需要均相等才能匹配.
BZOJ1390
注意到111>3*20,所以一棵树能够围起来的话,肯定是要围起来.
将所有的固定点拿出来做凸包,然后在凸包外面的树就可以放弃治疗了.
在凸包里面的树肯定都是能被保护到的,然后把这些树都拿出来做一个凸包,那么我们要找出最少的固定点把这个凸包围起来.
窝是大逗比...只会$O(n^4)$枚举起点暴力dp...
然而我忘了一个非常简单的东西--直接Floyd求最小环就行了啊!
这样只有$O(n^3)$.
BZOJ1767
NOI2014的d2t3就是从这里来的吧...
这道题太弱了就说原题吧.
树分治做法:
首先找出树的重心,首先分治含有根的那一部分子树(包括重心),然后把剩下的所有点按照购买的范围从小到大排序,这样就可以离线把重心到根路径上的点插入凸包,并直接二分就行了.然后再分治剩下的子树就行了.
线段树+凸包做法:
每到一个点,线段树上都存的是从根到这个点父亲路径上的序列的那些点,然后就像一个区间那样维护,询问的时候二分找到限制的范围,然后进行区间查询,对于每个线段树节点都二分寻找最优值.
怎么维护这个线段树呢?计算完答案,向下dfs时,将这个点插入凸包,由于$x$坐标是递增的,只需要插在末尾就行了.然后向上回溯时在吧这个点删除就行了,也是只删除末尾的点就行了.
关键是我们如果真的模拟一个栈,复杂度就不对了.
所以我们插入的时候直接二分得到应该插入在哪里,然后直接更改尾指针就行了,稍微记录一点东西就能够$O(1)$还原了.
这样只需要严格$O(logn)$就能插入了.
树链剖分+线段树+凸包做法:
玛德我就暴力3个log你管我?
策爷现场好像就是这么过的?
BZOJ3874
猜结论可以发现最终的答案关于叫外卖的次数是一个单峰函数.(玛德!)
于是三分.
那么怎么知道此时的值呢.
我们把所有的外卖进行排序,得到一个关于保质期价格单调递增的序列,然后按照保质期从小到大把外卖塞进这些次的叫外卖中就行了.
于是时间为$O(nlog(10^{18}))$.
BZOJ1789
yy了好长时间的dp没有yy出来QwQ.
结果题解是说最终相同的串必定是某个串的前缀!
这个证明还是很显然吧.
然后模拟就行啦QwQ.
BZOJ3454
暴力并查集.
BZOJ3233
首先我们考虑一个很显然的事情,假如知道硬币序列,那么最少应该用多少枚硬币呢?
我们从大到小贪心就行了,可以证明这样一定是最优的.
不妨令$f[i][j]$表示序列中第$i$大的为$j$时的最小硬币数.
我们预处理$g[j]=\sum_{i=1}^{n}a_i\%j$备用.
注意到序列最多只有$O(logn)$项,且第$i$项不超过$\frac{10^5}{2^{i-1}}$.
那么我们就可以这样转移:$f[i][j]=\sum_{j|k}min\{{f[i-1][k]+(g[k]-g[j])/j}\}$
然后转移的时候充分利用取值范围的限制.
具体的复杂度我就不分析了,但总之转移的总量完全可以接受.
#include#include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define N 51 int a[N]; int f[21][100010],g[100010]; int main(){ int n; scanf("%d",&n;); int i,j,k,p,Max=0; for(i=1;i<=n;++i){ scanf("%d",&a;[i]); Max=max(Max,a[i]); } for(i=1;i<=n;++i) for(j=1;j<=Max;++j) g[j]+=a[i]%j; memset(f,0x3f,sizeof f); for(i=1;i<=Max;++i){ f[1][i]=0; for(j=1;j<=50;++j) f[1][i]+=a[j]/i; } for(i=2;i<=17;++i) for(j=1;j<<(i-1)<=Max;++j){ for(k=2*j;k<<(i-2)<=Max;k+=j){ if(f[i-1][k]!=inf) f[i][j]=min(f[i][j],(g[k]-g[j])/j+f[i-1][k]); } } int ans=inf; for(i=1;i<=17;++i) ans=min(ans,f[i][1]); cout< <
BZOJ3460
树上莫队大法嚎!
BZOJ4129
带修改树上莫队大法嚎!
/*强烈鄙视某些人把我送回家种田了*/
弱省胡策Round5A
考试时:
通过找规律发现了$A_i=\sum_{j=i}^{n}C_{j}^{i}(-1)^{j-i}B_{j}$.
然后?不会啦...
明明展开之后用一点技巧就变成卷积了...
结果我根本没展开,而是构造了一个大多项式,但是并没有卵用.
我真TM是大逗比.
#include#include #include #include #include using namespace std; typedef long long ll; #define N 262144 int b[N]; #define P 998244353 #define g 3 inline int ksm(int x,int y){ int re=1,t=x; for(;y;y>>=1,t=(ll)t*t%P) if(y&1) re=(ll)re*t%P; return re; } inline int inv(int x){ return ksm(x,P-2); } int fac[N],ifac[N]; int X[N],Y[N],pow[N]; inline int revbit(int x,int bit){ int re=0; for(int i=0;i >i)&1) re|=1<<(bit-1-i); return re; } inline void fft(int A[],int n,int rev){ static int B[N]; int bit=0,i,j,k; for(int tmp=n;tmp^1;tmp>>=1,++bit); for(i=0;i <=n;k<<=1) for(wn=ksm(g,rev==1?(P-1)/k:(P-1)-(P-1)/k),i=0;i <(k>>1);++j,w=(ll)w*wn%P){ t=(ll)A[i+j+(k>>1)]*w%P; A[i+j+(k>>1)]=(A[i+j]-t+P)%P; (A[i+j]+=t)%=P; } if(rev==-1){ int _inv=inv(n); for(i=0;i <<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return x; } int main(){ //freopen("tt.in","r",stdin); int n=getint(); int i,j; for(i=0;i<=n;++i) b[i]=getint(); for(fac[0]=1,i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%P; for(i=0;i<=n;++i) ifac[i]=inv(fac[i]); for(pow[0]=1,i=1;i<=n;++i) pow[i]=P-pow[i-1]; for(i=0;i<=n;++i){ X[i]=((ll)fac[i]*b[i]%P*pow[i]%P+P)%P; Y[i]=ifac[n-i]; } int M; for(M=1;M<(2*n+2);M<<=1); fft(X,M,1); fft(Y,M,1); for(i=0;i <=n;++i){ if(i) putchar(' '); printf("%d",((ll)X[n+i]*ifac[i]%P*pow[i]%P+P)%P); } return 0; }
弱省胡策Round2B
考试是没看出来是构造一个无向图...反而硬找规律...
其实就是构造一个连通无向图使得最长的最短路为$k$.
我们可以构造一个长度为$k-2$的链,然后往两个端点加叶子就行了.
#include#include #include #include #include using namespace std; int G[310][310]; inline void addedge(int a,int b){ G[a][b]=G[b][a]=1; } int main(){ int n,k; scanf("%d%d",&n;,&k;); if(k==1){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j) putchar('1'); puts(""); } } else{ for(int i=1;i<=n;++i) addedge(i,i); for(int i=1;i <=n;++i) addedge(i,k-1); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j) printf("%d",G[i][j]); puts(""); } } return 0; }
弱省胡策Round5C
好神的dp...
考虑一个$n\times{m}$的矩阵,假设现在我们要往里面填充第$k$种颜色.
那么现在是有一个长度为$n$的序列,每个元素都表示一行这种元素的个数.
假设我们把这个序列排好了序.
我们肯定需要枚举最小值,以及这个最小值出现了多少次.
不妨令$f_{n,m,d,k}$表示一个$n\times{m}$的矩阵,现在要填充第$k$种颜色,且序列的最小值为${d}$且合法的方案数.
记录一个前缀和$g_{n,m,d,k}=\sum_{i=0}^{d}f_{n,m,i,k}$.
我们枚举这个最小值出现了多少次,假设出现$i$次.
那么这种方案就是$\binom{n}{i}\times\binom{m}{d}^i\times{g_{i,m-d,m-d,k-1}\times{(g_{n-i,m,m,k}-g_{n-i,m,d,k})}}$.
(以上仅仅是基本思路,还有一些坑以及特判,详情看代码吧QAQ)
#include#include #include #include #include #include using namespace std; #define N 21 #define M 51 #define P 101 typedef long long ll; static const int mod=(1e9)+7; inline void inc(int&x;,int y){ if((x+=y)>=mod) x-=mod; } int C[M][M],pC[M][M][N]; int g[N][M][M][P]; int main(){ int n,m,p; cin>>n>>m>>p; int i,j,_i,k; C[0][0]=C[1][0]=C[1][1]=1; for(i=2;i<=50;++i){ C[i][0]=C[i][i]=1; for(j=1;j<=50;++i){ for(j=0;j<=i;++j){ pC[i][j][0]=1; for(k=1;k<=20;++k) pC[i][j][k]=(ll)pC[i][j][k-1]*C[i][j]%mod; } } for(j=1;j<=m;++j) g[1][j][j][1]=1; for(k=2;k<=p;++k) for(i=1;i<=n;++i) for(j=1;j<=m;++j){ for(int d=0;d < <
BZOJ3052
经典的带修改树上莫队.
VFK的博客已经写得非常详细了.
这里我再稍微说一点心得.
首先是树分块的姿势.
设每一块大小的基准值为$B$.
对树进行dfs,给每个点维护一个一开始为空的等待序列,然后向上回溯的时候返回这个等待序列.
那么这个点要依次遍历他的儿子,每搞完一个儿子,就把这个儿子的等待序列加入自己的等待序列.如果加入之后发现等待序列的长度$\geq{B}$,就把当前等待序列里面的所有点都分成一个块,并从等待序列中删除.
这样做完之后,把这个点自己加入自己的等待序列(此时就算满足$B$分块的条件也不分成一块),然后向上回溯.
那么最后根还会返回一个等待序列,这怎么分块呢?
直接加入最后一个块就行啦.
我们分析一下:一个点向上返回的等待序列的长度肯定$\leq{B}$,刚才分成的每个块的大小$siz$肯定满足$B\leq{siz}\leq{2B-1}$,所以这两个加在一起最大不超过$3B$.并且由于dfs序的性质,这个块肯定是连通的.
这样就满足所有块的大小都满足$[B,3B]$.
我们定义状态$(u,v,t)$表示有效路径为$u,v$之间的路径再抛去$lca(u,v)$,且时间为$t$的答案.
这个答案需要记录的是真实的答案,以及每个点当前的颜色,以及有效路径上每种颜色出现多少次,以及所有点的有效性.
这样才能实现$O(1)$的修改.
路径之间的转移就是简单把两对端点之间的去lca路径有效性取反.(详细见VFK博客)
时间的转移就是改变某个点的颜色,也非常简单.
注意的是时间倒流的时候,需要还原在这个时间的修改,则需要知道上一个时刻这个点是什么颜色,我用了vector+二分.
类似莫队算法,我们把所有询问按照第一个端点的块序号为第一关键字,第二个端点的块序号为第二关键字,时间为第三关键字排序.
然后如上面所述转移就行了.
令$B=n^{\frac{2}{3}}$,则块的数目有$n^{\frac{1}{3}}$,则总转移数目为:$O(n^{\frac{5}{3}})$.(证明见VFK博客)
另外再跪一下VFK.
#include#include #include #include #include #include #include using namespace std; typedef long long ll; #define N 100010 #define M 100010 #define Q 100010 int n,m,q,head[N],next[N<<1],end[N<<1]; inline void addedge(int a,int b){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q++; } inline void make(int a,int b){ addedge(a,b); addedge(b,a); } int val[M],w[N],c[N]; inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return x; } int dep[N],pa[N][21],belong[N],cnt,stack[N],top,B; inline int lca(int x,int y){ if(dep[x] =0;--i) if(dep[pa[x][i]]>=dep[y]) x=pa[x][i]; if(x==y) return x; for(int i=20;i>=0;--i) if(pa[x][i]!=pa[y][i]) x=pa[x][i],y=pa[y][i]; return pa[x][0]; } inline int dfs(int x,int fa){ int size=0; for(int j=head[x];j;j=next[j]){ if(end[j]!=fa){ dep[end[j]]=dep[x]+1; pa[end[j]][0]=x; int t=dfs(end[j],x); if((size+=t)>=B){ ++cnt; while(size--) belong[stack[top--]]=cnt; } } } stack[++top]=x; return ++size; } int type[Q],x[Q],y[Q]; struct Query{ int u,v,t; Query(){} Query(int _u,int _v,int _t):u(_u),v(_v),t(_t){ if(belong[u]>belong[v]) swap(u,v); } bool operator<(const Query&B;)const{ if(belong[u]!=belong[B.u]) return belong[u] ti[N],col[N]; inline ll getans(){ return G+(ll)w[num[c[_lca]]+1]*val[c[_lca]]; } ll ans[Q]; inline void c_s(int x){ if(vis[x]){ vis[x]=0; G-=(ll)w[num[c[x]]--]*val[c[x]]; } else{ vis[x]=1; G+=(ll)w[++num[c[x]]]*val[c[x]]; } } inline void c_c(int x,int _c){ if(vis[x]){ G-=(ll)w[num[c[x]]--]*val[c[x]]; G+=(ll)w[++num[c[x]=_c]]*val[_c]; } else c[x]=_c; } inline void go(int t){ if(type[t]==0) c_c(x[t],y[t]); } int rx[Q],ry[Q]; inline void ret_pre(){ for(int i=1;i<=q;++i){ if(type[i]==0){ int _x=x[i]; int d=lower_bound(ti[_x].begin(),ti[_x].end(),i)-ti[_x].begin(); rx[i]=_x; ry[i]=col[_x][d-1]; } } } inline void ret(int t){ if(type[t]==0) c_c(rx[t],ry[t]); } inline void uppath(int u,int v){ int _lca=lca(u,v); for(;u!=_lca;u=pa[u][0]) c_s(u); for(;v!=_lca;v=pa[v][0]) c_s(v); } int main(){ #ifndef ONLINE_JUDGE freopen("tt.in","r",stdin); #endif n=getint(); m=getint(); q=getint(); int i,j; for(i=1;i<=m;++i) val[i]=getint(); for(i=1;i<=n;++i) w[i]=getint(); for(i=1;i <=20;++j) for(i=1;i<=n;++i) pa[i][j]=pa[pa[i][j-1]][j-1]; for(i=1;i<=n;++i){ ti[i].push_back(0); col[i].push_back(c[i]=getint()); } for(i=1;i<=q;++i){ type[i]=getint(); if(type[i]==0){ x[i]=getint(); y[i]=getint(); ti[x[i]].push_back(i); col[x[i]].push_back(y[i]); } else{ S[++numQ]=Query(getint(),getint(),i); } } ret_pre(); sort(S+1,S+numQ+1); u=v=_lca=1; t=G=0; for(i=1;i<=numQ;++i){ uppath(u,S[i].u); uppath(v,S[i].v); _lca=lca(u=S[i].u,v=S[i].v); while(t S[i].t) ret(t--); ans[S[i].t]=getans(); } for(i=1;i<=q;++i) if(type[i]==1) printf("%lld\n",ans[i]); return 0; }
现在开始,再战"紫荆花之恋"!
233