bzoj泛做 - HZH's Blog - 自闭症
bzoj泛做
每天bzoj水题切切啊!不会去切些有意义的题么?bzoj上面的题平均难度最低了!——某犇
(找个理由坑了
4155: [Ipsc2015]Humble Captains
合并了两道SB题。第一问网络流第二问DP即可。
#include<cstdio> #include<bitset> #include<cstring> #include<algorithm> #define INF 1e9 #define N 300 #define M 40010 using namespace std; bitset<21000>f; int Q,n,m,S,T,l,v[M],ne[M],fl[M],head[N],hash[N]; int cs[N],flow,now,i,kt[N],w[N],pre[N],ans,m1,gs[N],x,y; void add(int x,int y,int f1,int f2) { v[++l]=y;ne[l]=head[x];head[x]=l;fl[l]=f1; v[++l]=x;ne[l]=head[y];head[y]=l;fl[l]=f2; } void sap() { memset(hash,0,sizeof(hash)); memset(cs,0,sizeof(cs));cs[0]=T+1; hash[0]=T;flow=INF;now=S; for(i=1;i<=T;i++)kt[i]=head[i]; for(;cs[S]<=T;) { w[now]=flow; for(i=kt[now];i;i=ne[i]) if(cs[now]==cs[v[i]]+1&&fl[i]) { flow=min(flow,fl[i]); kt[now]=i; pre[v[i]]=i;now=v[i]; if(now==T) { ans+=flow; for(;now!=S;now=v[pre[now]^1]) fl[pre[now]]-=flow, fl[pre[now]^1]+=flow; flow=INF; } break; } if(i)continue;m1=0; for(i=head[now];i;i=ne[i]) if(cs[v[i]]<cs[v[m1]]&&fl[i])m1=i; if(!(--hash[cs[now]]))return; cs[now]=cs[v[m1]]+1; kt[now]=m1;hash[cs[now]]++; if(now!=S)now=v[pre[now]^1],flow=w[now]; } } int main() { scanf("%d",&Q); while(Q--) { scanf("%d%d",&n,&m); S=n-1;T=n;l=1;ans=0; memset(gs,0,sizeof(gs)); memset(head,0,sizeof(head)); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(y<x)swap(x,y); gs[x]++;gs[y]++; if(y==2){ans++;continue;} if(x==1)add(S,y-2,1,0); if(x==2)add(y-2,T,1,0); if(x>2)add(x-2,y-2,1,1); } sap(); printf("%d ",m-ans); f.reset();f[0]=1; for(i=3;i<=n;i++)f|=f<<gs[i]; for(i=m-gs[1];!f[i];i--); ans=m-gs[1]-i; for(i=m-gs[2];!f[i];i--); ans=min(ans,m-gs[2]-i); printf("%d\n",ans); } }
4149: [AMPPZ2014]Global Warming
一位一位扫过去。。然后维护两个单调栈,然后扭一扭脖子即可。
#include<cstdio> #include<algorithm> #define N 500010 using namespace std; int n,i,a[N],q[N],h[N],top,fro,pre[N],pra[N],sg,xx,ans,yy,j; int main() { scanf("%d",&n);sg=n+1; for(i=1;i<=n;i++) { scanf("%d",&a[i]); for(;a[i]<a[q[top]]&⊤top--); pre[i]=q[top]+1; if(a[i]==a[q[top]]&&top)top--; if(sg>q[top])sg=n+1; q[++top]=i; for(;a[i]>a[h[fro]]&&fro;fro--); pra[i]=h[fro]+1; if(a[i]==a[h[fro]]&&fro)fro--; if(sg>h[fro])sg=n+1; h[++fro]=i; xx=lower_bound(h+1,h+fro+1,pre[i])-h; xx=max(pre[i],pra[h[xx]]); if(xx<sg)sg=xx; xx=lower_bound(q+1,q+top+1,pra[i])-q; xx=max(pra[i],pre[q[xx]]); if(xx<sg)sg=xx; if(i-sg+1>ans)ans=i-sg+1,yy=sg; } printf("%d %d\n",ans,yy); }
4144: [AMPPZ2014]Petrol
考虑一条边。对于他两侧的点,找到最近的关键点,然后对这两个关键点建边。
之后跑kruskal即可。。
#include<cstdio> #include<cstring> #include<algorithm> #define N 200010 #define M 400010 using namespace std; int n,s,m,v[M],ne[M],head[N],len[M],dis[N],pr[N],dad[N],an[N]; int c[N],l,i,x,y,z,j,T,a[N],b[N],f[N],heap[N],wz[N],ln,lls,u; struct str{int x,y,z;}li[M]; int find(int x){return dad[x]==x?x:dad[x]=find(dad[x]);} bool cmp1(str a,str b){return a.z<b.z;} void add(int x,int y,int z) { v[++l]=y;ne[l]=head[x]; head[x]=l;len[l]=z; } void pushup(int x,int y) { for(;x>>1&&dis[heap[x>>1]]<dis[y];x>>=1) heap[x]=heap[x>>1],wz[heap[x]]=x; heap[x]=y;wz[y]=x; } void pushdown(int x,int y) { for(;x<<1<=ln;x=lls) { lls=x<<1; if(lls<ln&&dis[heap[lls|1]]<dis[heap[lls]])lls|=1; if(dis[heap[lls]]>=dis[heap[x]])break; heap[x]=heap[lls];wz[heap[x]]=x; } heap[x]=y;wz[y]=x; } void spfa() { for(i=1;i<=n;i++)if(pr[i]) pushup(++ln,i); for(;ln;) { u=heap[1];pushdown(1,heap[ln--]);wz[u]=0; for(i=head[u];i;i=ne[i]) if(dis[u]+len[i]<dis[v[i]]) { dis[v[i]]=dis[u]+len[i];pr[v[i]]=pr[u]; if(!wz[v[i]])wz[v[i]]=++ln; pushup(wz[v[i]],v[i]); } } } bool cmp(int x,int y){return c[x]<c[y];} int main() { scanf("%d%d%d",&n,&s,&m); memset(dis,63,sizeof(dis)); for(i=1;i<=s;i++) { scanf("%d",&c[i]); dis[c[i]]=0; pr[c[i]]=c[i]; } for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z);add(y,x,z); } spfa(); scanf("%d",&T); for(i=1;i<=T;i++) { scanf("%d%d%d",&a[i],&b[i],&c[i]); f[i]=i; } sort(f+1,f+T+1,cmp);l=0; for(i=1;i<=n;i++) { dad[i]=i; for(j=head[i];j;j=ne[j]) if(pr[v[j]]>pr[i]) { li[++l].x=pr[i]; li[l].y=pr[v[j]]; li[l].z=dis[i]+dis[v[j]]+len[j]; } } sort(li+1,li+l+1,cmp1);j=1; for(i=1;i<=T;i++) { u=f[i]; for(;li[j].z<=c[u]&&j<=l;j++) if(find(li[j].x)!=find(li[j].y)) dad[dad[li[j].x]]=dad[li[j].y]; an[u]=find(a[u])==find(b[u]); } for(i=1;i<=T;i++) an[i]?puts("TAK"):puts("NIE"); }
4145: [AMPPZ2014]The Prices
大力子集DP即可。
#include<cstdio> #include<cstring> using namespace std; int n,m,i,x,j,a[20],g[100010],f[100010],k; int main() { scanf("%d%d",&n,&m); memset(g,63,sizeof(g)); g[0]=0; for(i=1;i<=n;i++) { scanf("%d",&x); for(j=0;j<m;j++) scanf("%d",&a[j]); for(j=0;j<1<<m;j++) { f[j]=g[j]+x; for(k=0;k<m;k++)if(j>>k&1) if(f[j^(1<<k)]+a[k]<f[j]) f[j]=f[j^(1<<k)]+a[k]; if(g[j]>f[j])g[j]=f[j]; } } printf("%d\n",g[(1<<m)-1]); }
4152: [AMPPZ2014]The Captain
把x或y坐标相邻的点之间连边,然后跑最短路即可。加了堆优化跑蛮快的。
#include<cstdio> #include<cstring> #include<algorithm> #define N 200010 #define M 800010 using namespace std; int n,i,dis[N],l,head[N],wz[N],heap[N]; int len[M],v[M],ne[M],ln,ssd,u; struct cpx{int x,y;}a[N],b[N]; bool cmp(cpx a,cpx b) { return a.x<b.x; } void add(int x,int y,int z) { v[++l]=y;ne[l]=head[x]; head[x]=l;len[l]=z; v[++l]=x;ne[l]=head[y]; head[y]=l;len[l]=z; } void pushup(int x,int y) { for(;(x>>1)&&dis[heap[x>>1]]>dis[y];x>>=1) heap[x]=heap[x>>1],wz[heap[x]]=x; heap[x]=y;wz[y]=x; } void pushdown(int x,int y) { for(;(x<<1)<=ln;x=ssd) { ssd=x<<1; if(ssd<ln&&dis[heap[ssd|1]]<dis[heap[ssd]])ssd|=1; if(dis[heap[ssd]]>=dis[y])break; heap[x]=heap[ssd];wz[heap[x]]=x; } heap[x]=y;wz[y]=x; } void dij() { memset(dis,63,sizeof(dis)); dis[1]=0;pushup(ln=1,1); for(;heap[1]!=n;) { u=heap[1];pushdown(1,heap[ln--]);wz[u]=0; for(i=head[u];i;i=ne[i]) if(dis[u]+len[i]<dis[v[i]]) { dis[v[i]]=dis[u]+len[i]; if(!wz[v[i]])wz[v[i]]=++ln; pushup(wz[v[i]],v[i]); } } } int main() { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&b[i].x); a[i].y=b[i].y=i; } sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); for(i=1;i<n;i++) { add(a[i].y,a[i+1].y,a[i+1].x-a[i].x); add(b[i].y,b[i+1].y,b[i+1].x-b[i].x); } dij(); printf("%d\n",dis[n]); }
4143: [AMPPZ2014]The Lawyer
直接求出每天最早的结束时间和最晚的开始时间然后比一比~
#include<cstdio> #include<cstring> #define N 25 using namespace std; char ch; int n,m,i,x,y,z,mi[N],mmi[N],ma[N],mma[N]; void read(int &x) { for(ch=getchar();ch<'0';ch=getchar()); for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0'; } int main() { read(n);read(m); memset(mi,63,sizeof(mi)); for(i=1;i<=n;i++) { read(x);read(y);read(z); if(y<mi[z])mi[z]=y,mmi[z]=i; if(x>ma[z])ma[z]=x,mma[z]=i; } for(i=1;i<=m;i++) { if(mi[i]<ma[i]) printf("TAK %d %d\n",mmi[i],mma[i]); else puts("NIE"); } }
4146: [AMPPZ2014]Divisors
直接nlogn,调和级数。
#include<cstdio> #define N 2000010 using namespace std; int n,i,x,m,j; long long ans,a[N]; char ch; void read(int &x) { for(ch=getchar();ch<'0';ch=getchar()); for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0'; } int main() { read(n); for(i=1;i<=n;i++) { read(x);a[x]++; if(x>m)m=x; } for(i=m;i>=1;i--) { for(j=i<<1;j<=m;j+=i) ans+=a[i]*a[j]; ans+=a[i]*(a[i]-1); } printf("%lld\n",ans); }
3925: [Zjoi20150]地震后的幻想乡
考试的时候由于组合数乘里面了导致此题没调出来。。
终于收复失地,还跑最快蛤蛤。。大概就是子集DP一下就好了。。
由于不用多项式精度没有误差。。所以喽,很资磁!
#include<cstdio> #define N 1024 using namespace std; int n,m,S,V,x,y,g[N],gs[N],j,i,k,l; double s[110][N],ans,tot,C[110][110],ss; int main() { scanf("%d%d",&n,&m); S=1<<n;V=S-1;gs[0]=-1; for(j=1;j<S;j++) gs[j]=gs[j>>1]+(j&1); for(i=0;i<=m;i++)C[0][i]=1; for(i=1;i<=m;i++) for(j=1;j<=i;j++) C[j][i]=C[j-1][i-1]+C[j][i-1]; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y);x--;y--; for(j=0;j<S;j++) if((j>>x&1)&&(j>>y&1))g[j]++; } for(i=1;i<S;i++) { for(j=(i-1)&i;j>(i^j);j=(j-1)&i) for(k=gs[j];k<=g[j];k++) for(l=gs[i^j];l<=g[i^j];l++) s[k+l+1][i]+=s[k][j]*s[l][i^j]*C[k][k+l]*(g[i]-g[j]-g[i^j]); if(i!=V)for(j=gs[i];j<=g[i];j++) s[j][i]+=s[j-1][i]*(g[i]-j+1); if(!gs[i])s[0][i]=1; } ss=1; for(i=g[V];i>=gs[V];i--) { ans+=s[i][V]*i*ss; tot+=s[i][V]*ss; ss=ss*(g[V]-i+1); } printf("%.6lf\n",ans/tot/(m+1)); }
3998: [TJOI2015]弦论
后缀自动机模板题。T=1时在parent树上预处理出每个字串出现的次数。
然后统计出每个节点走下去一共有几种合法的接受状态。然后直接跑出第K大即可。
#include<cstdio> #include<cstring> #include<algorithm> #define N 1000010 using namespace std; char s[N],ap[N]; int T,n,fail[N],son[26][N],wz[N],i,j,ch,tot,p,f[N],cur; long long v[N],vp[N],k; bool cmp(int x,int y) { return wz[x]<wz[y]; } int main() { scanf("%s%d%lld",s+1,&T,&k); n=strlen(s+1);fail[0]=-1;tot=n; for(i=1;i<=n;i++) { ch=s[i]-'a';wz[i]=i; for(j=i-1;j>=0;j=fail[j]) { if(son[ch][j])break; son[ch][j]=i; } if(j<0)fail[i]=0;else if(wz[j]+1==wz[son[ch][j]]) fail[i]=son[ch][j]; else { tot++;p=son[ch][j]; wz[tot]=wz[j]+1; fail[tot]=fail[p]; fail[i]=fail[p]=tot; for(;j>=0;j=fail[j]) { if(son[ch][j]!=p)break; son[ch][j]=tot; } for(j=0;j<26;j++) son[j][tot]=son[j][p]; } } for(i=1;i<=tot;i++)f[i]=i; sort(f+1,f+tot+1,cmp); for(i=tot;i>=1;i--) { if(f[i]<=n||(!T))v[f[i]]++; if(T)v[fail[f[i]]]+=v[f[i]]; vp[f[i]]=v[f[i]]; for(j=0;j<26;j++) vp[f[i]]+=vp[son[j][f[i]]]; } v[0]=0; for(cur=i=0;k>v[cur];i++) { k-=v[cur]; for(j=0;j<26;j++) if(k>vp[son[j][cur]]) k-=vp[son[j][cur]]; else break; cur=son[j][cur];ap[i]='a'+j; } printf("%s\n",ap); }
3997: [TJOI2015]组合数学
求最大和上升子序列即可
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m,i,j,g[1010],f[1010],T; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(g,0,sizeof(g)); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%d",&f[j]); f[j]+=g[j+1]; }for(j=m;j>=0;j--) g[j]=max(g[j],max(g[j+1],f[j])); }printf("%d\n",g[0]); } }
3931: [CQOI2015]网络吞吐量
裸题。在最短路上跑网络流。
跑得奇慢无比,难道是我的姿势不对。。?
#include<cstdio> #include<cstring> #include<algorithm> #define INF 1e15 #define M 600010 #define N 1010 using namespace std; int n,m,x,y,l,head[N],S,q[M],r,i,use[N]; int v[M],ne[M],max1; int hash[N],now,cs[N],kt[N],T,flag,pre[N]; long long dis[N],fl[M],co[M],flow,ans,w[N],c; void add(int x,int y,long long c,long long f) { v[++l]=y;ne[l]=head[x]; head[x]=l;fl[l]=f;co[l]=c; v[++l]=x;ne[l]=head[y]; head[y]=l;fl[l]=0;co[l]=-c; } void spfa() { memset(dis,63,sizeof(dis));dis[S]=0; for(q[l=r=1]=S;l<=r;l++) { for(i=head[q[l]],use[q[l]]=0;i;i=ne[i]) if(dis[q[l]]+co[i]<dis[v[i]]&&fl[i]) { dis[v[i]]=dis[q[l]]+co[i]; if(!use[v[i]])use[v[i]]=1,q[++r]=v[i]; } } } void sap() { hash[0]=T;flow=INF; now=S;cs[0]=1e9; for(i=1;i<=T;i++)kt[i]=head[i]; while(cs[S]<=T) { w[now]=flow;flag=0; for(i=kt[now];i;i=ne[i]) if(fl[i]&&cs[now]==cs[v[i]]+1&&dis[v[i]]==dis[now]+co[i]) { kt[now]=i; flow=min(flow,fl[i]); pre[now=v[i]]=i;flag=1; if(now==T) { ans+=flow; for(;now!=S;now=v[pre[now]^1]) { fl[pre[now]]-=flow; fl[pre[now]^1]+=flow; } flow=w[now]; } break; } if(flag)continue;max1=0; for(i=head[now];i;i=ne[i]) if(fl[i]&&cs[v[i]]<cs[v[max1]]&&dis[v[i]]==dis[now]+co[i]) max1=i; kt[now]=max1;hash[cs[now]]--; if(!hash[cs[now]])return; cs[now]=cs[v[max1]]+1; if(cs[now]<=T)hash[cs[now]]++; if(now!=S)now=v[pre[now]^1];flow=w[now]; } } int main() { scanf("%d%d",&n,&m);l=1; S=n+1;T=n<<1; for(i=1;i<=m;i++) { scanf("%d%d%lld",&x,&y,&c); add(x+n,y,c,INF); add(y+n,x,c,INF); } for(i=1;i<=n;i++) { scanf("%lld",&c); if(i<n)add(i,i+n,0,c); } add(n,T,0,INF); spfa();sap(); printf("%lld\n",ans); }
4001: [TJOI2015]概率论
打表找规律即可。用母函数比较复杂,大概是利用了广义二项式定理,然后结合卡特兰数即可推出。
#include<cstdio> using namespace std; double n; int main() { scanf("%lf",&n); printf("%.9lf\n",n*(n+1)/(4*n-2)); }
4011: [HNOI2015]落忆枫樱
有向图生成树计数。如果不考虑多余边就是除去零入度点每个点的入度的∏。
不合法状态就是从y连了一条链到x。考虑dp。f[i]表示从y走到这个点,所有边的总方案数。
因为每次转移的时候多确定了一条边。所以要把方案数除以转移过去的那个点的入度。
按照拓扑图顺序DP即可。
#include<cstdio> #define mod 1000000007 #define N 100010 #define M 200010 using namespace std; int n,m,x,y,i,a,b,q[N],v[M],ne[M],head[N],l,gs[N],r,j,wz[N],u; long long tot,dis[N],B[N],A[N]; void add(int x,int y) { v[++l]=y;ne[l]=head[x];head[x]=l; } long long powmod(long long x,int y) { long long ans=1; for(;y;y>>=1,x=x*x%mod) if(y&1)ans=ans*x%mod; return ans; } int main() { scanf("%d%d%d%d",&n,&m,&x,&y); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b);gs[b]++; } tot=1; for(i=1;i<=n;i++) { A[i]=gs[i]+(i==y); B[i]=powmod(A[i],mod-2); if(!A[i])q[++r]=i; else tot=tot*A[i]%mod; } for(l=1;l<=r;l++) { wz[q[l]]=l; for(j=head[q[l]];j;j=ne[j]) { gs[v[j]]--; if(!gs[v[j]])q[++r]=v[j]; } } dis[y]=tot%mod; for(i=wz[y];i<=n;i++) { u=q[i];dis[u]%=mod; (dis[u]*=B[u])%=mod; for(j=head[u];j;j=ne[j]) dis[v[j]]+=dis[u]; } tot-=dis[x]; if(tot<0)tot+=mod; printf("%lld\n",tot); }
3996: [TJOI2015]线性代数
把式子展开后就变成[tex]\sum_{1\leqslant i,j\leqslant n}^{ }a_{i}*a_{j}*b_{i,j}-\sum_{1\leqslant i\leqslant n}^{ }a_{i}*c_{i}[/tex]
然后这东西就是一个裸的网络流。建图跑即可。
#include<cstdio> #include<algorithm> #define INF 1e9 #define N 300010 #define M 3000010 using namespace std; int n,S,T,i,j,l,hash[N],flow,now,cs[N],pre[N],ans; int v[M],ne[M],head[N],fl[M],kt[N],w[N],flag,max1,x; void add(int x,int y,int f) { v[++l]=y;ne[l]=head[x];head[x]=l;fl[l]=f; v[++l]=x;ne[l]=head[y];head[y]=l;fl[l]=0; } void sap() { hash[0]=T;flow=INF; now=S;cs[0]=1e9; for(i=1;i<=T;i++)kt[i]=head[i]; while(cs[S]<=T) { w[now]=flow;flag=0; for(i=kt[now];i;i=ne[i]) if(fl[i]&&cs[now]==cs[v[i]]+1) { kt[now]=i; flow=min(flow,fl[i]); pre[now=v[i]]=i;flag=1; if(now==T) { ans-=flow; for(;now!=S;now=v[pre[now]^1]) { fl[pre[now]]-=flow; fl[pre[now]^1]+=flow; } flow=w[now]; } break; } if(flag)continue;max1=0; for(i=head[now];i;i=ne[i]) if(fl[i]&&cs[v[i]]<cs[v[max1]]) max1=i; kt[now]=max1;hash[cs[now]]--; if(!hash[cs[now]])return; cs[now]=cs[v[max1]]+1; if(cs[now]<INF)hash[cs[now]]++; if(now!=S)now=v[pre[now]^1];flow=w[now]; } } int main() { scanf("%d",&n); S=n*n+n+1;T=S+1;l=1; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&x); add(i,i*n+j,INF); add(j,i*n+j,INF); add(i*n+j,T,x); ans+=x; } for(i=1;i<=n;i++) { scanf("%d",&x); add(S,i,x); } sap(); printf("%d\n",ans); }
排名不按做题顺序
2022年8月30日 19:40
Jessore Divisional education board of Bangladesh has successfully conducted the Grade 8th terminal examination tests for both Junior School Certificate & Junior Dakhil Certificate course students at all districts under the division to the academic year of 2022, there are a huge number of students are appeared from all Secondary schools under the board like as previous years, Junior Certificate Result jessore Board and this is most important examination tests for class 8th standard students of the country.Government of Bangladesh, Secondary and Higher Secondary Education Board has successfully completed the JSC & JDC examinations in the month of November 2022 to all eligible students of the division at all selected examination centers at all rural and urban area schools, both of Junior School Certificate & Junior Dakhil Certificate terminal exams are conducted as per date sheet announced by all education board Bangladesh.