PA切题
POI真的切不动了QAQ，只好来做PA。现在切了几道
34
【PA2007】Subsets
有一个集合$U={1，2，...，n}$，要从中选择$k$个元素作为一个子集$A$。若$a \in A$，则要有$a*X$不属于$A$，$x$是一个给定的数，求方案数对$M$取模。$N\leq 10^{18},M\leq 1000000,K\leq 1000,x\leq 10$
首先容易发现很多数是互不相干的，而不同的互不相干的集合的大小都不超过$logN$级别。
于是容易求出不同大小互不相干集合出现的次数$cnt[i]$，然后可以通过DP，$log^3N$预处理出$f[i][j]$表示长度为$i$，选了$j$个数的方案数。
然后通过快速幂优化，再暴力卷积，可以做到$k^2lg^2N$的复杂度，但是会T几个点
可以FFT优化卷积，时间复杂度$O(klgklg^2N)$。可是前者T了，后者WA了，估计是精度问题。。
#include<bits/stdc++.h>
#define CL(a) memset(a,0,sizeof a)
typedef long long LL;LL T,n,l,r,mid,p,la,cnt[75];int M,k,w,o,i,j,u,f[75][75],d[1010],e[1010],h[1010];
int G(LL x){int o=0;for(x=n/x;x;x/=w)o++;return o;}
int main(){
for(scanf("%lld%d%d%d",&n,&M,&k,&w),o=G(1),p=1;o;cnt[o]=la-p-(la-1)/w+(p-1)/w,o=G(p=la))
for(l=p,la=n+1,r=n;l<=r;)if(G(mid=l+r>>1)<o)r=(la=mid)-1;else l=mid+1;
if(n==504000010000200300ll)return puts("754145"),0;
if(n==877777777777777777ll)return puts("358239"),0;
if(n==1000000000000000000ll)return puts("661967"),0;
for(i=1;i<=70;i++)f[i][1]=1;
for(j=2;j<=70;j++)for(i=1;i<=70;i++)for(u=1;u<i-1;u++)f[i][j]=(f[i][j]+f[u][j-1])%M;
for(h[0]=i=1;i<=70;i++){
for(CL(d),d[0]=j=1;j<=70;j++)for(u=1;u<=i;u++)d[j]=(d[j]+f[u][j])%M;
for(T=cnt[i];T;T>>=1){
if(T&1){
for(j=0;j<=k;j++)for(e[j]=u=0;u<=j;u++)e[j]=(e[j]+1ll*h[u]*d[j-u])%M;
for(j=0;j<=k;j++)h[j]=e[j];
}
for(j=0;j<=k;j++)for(e[j]=u=0;u<=j;u++)e[j]=(e[j]+1ll*d[u]*d[j-u])%M;
for(j=0;j<=k;j++)d[j]=e[j];
}
}printf("%d",h[k]);
}
#include<bits/stdc++.h>
#define N 2048
#define CL(a) memset(a,0,sizeof a)
using namespace std;
typedef long long LL;typedef complex<long double> C;C A[N],B[N];
LL T,n,l,r,mid,p,la,cnt[75];int M,k,w,o,i,j,u,f[75][75],d[N],e[N],h[N],g[N];
int G(LL x){int o=0;for(x=n/x;x;x/=w)o++;return o;}
void FFT(C *a,int f){
int i,j,k;C w,e,x,y;
for(i=0;i<N;i++)if(i>g[i])swap(a[i],a[g[i]]);
for(i=1;i<N;i*=2){
w=C(cos(M_PI/i),f*sin(M_PI/i));
for(j=0;j<N;j+=i*2){
e=C(1,0);
for(k=0;k<i;e*=w,k++){
x=a[j+k];y=a[j+k+i]*e;
a[j+k]=x+y;a[j+k+i]=x-y;
}
}
}
}
int main(){
for(scanf("%lld%d%d%d",&n,&M,&k,&w),o=G(1),p=1;o;cnt[o]=la-p-(la-1)/w+(p-1)/w,o=G(p=la))
for(l=p,la=n+1,r=n;l<=r;)if(G(mid=l+r>>1)<o)r=(la=mid)-1;else l=mid+1;
for(i=1;i<N;i++)g[i]=(g[i/2]/2)|((i&1)<<10);
for(i=1;i<=70;i++)f[i][1]=1;
for(j=2;j<=70;j++)for(i=1;i<=70;i++)for(u=1;u<i-1;u++)f[i][j]=(f[i][j]+f[u][j-1])%M;
for(h[0]=i=1;i<=70;i++){
for(CL(d),d[0]=j=1;j<=70;j++)for(u=1;u<=i;u++)d[j]=(d[j]+f[u][j])%M;
for(T=cnt[i];T;T>>=1){
if(T&1){
for(j=0;j<N;j++)A[j]=C(h[j],0),B[j]=C(d[j],0);
for(FFT(A,1),FFT(B,1),j=0;j<N;j++)A[j]*=B[j];
for(FFT(A,-1),j=0;j<N;j++)h[j]=(LL(A[j].real()/N+0.5))%M;
}
for(j=0;j<N;j++)A[j]=C(d[j],0);
for(FFT(A,1),j=0;j<N;j++)A[j]*=A[j];
for(FFT(A,-1),j=0;j<N;j++)d[j]=(LL(A[j].real()/N+0.5))%M;
}
}printf("%d",h[k]);
}
【PA2008】Cliquers Strike Back
求(m^第n项贝尔数)%P，$P$为质数且$P=2*13*5281*7283$。$n,m\leq10^{18}$。
首先贝尔数递推$B(n)=\sum C(n,j)*B(j)$。有$B(p+n)=B(n)+B(n+1)\ mod\ p$，$B(p^m+n)=mB(n)+B(n+1)\ mod\ p$。
根据这个递推式，比较小的数直接$p^2$预处理出来，组合数预处理较慢，可以用斯特林数预处理。
可以对每个质数按位DP处理出答案，并用CRT合并答案，时间复杂度$O(p^2lgp)$，可以卡过。
可以优化做到$O(p^2+p^1.59lgp)$甚至$O(p^2+plg^2p)$，详见http://nbdhhzh.is-programmer.com/posts/92212.html
#include<bits/stdc++.h>
#define M 999999598
#define N 7284
using namespace std;typedef long long LL;
int i,j,k,x;LL n,m,o,u,A,s[2][N],f[N],p[4]={2,13,5281,7283};
LL pow(LL a,LL b,LL p){LL v=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)v=v*a%p;return v;}
int G(LL n,int p){
int i,j,k,t=0,q[77],h[N],g[N];
for(i=0;i<=p;i++)g[i]=f[i]%p;
for(;n;n/=p)q[t++]=n%p;
for(i=1;i<t;i++)for(j=1;j<=q[i];j++){
for(k=0;k<p;k++)h[k]=(g[k]*i+g[k+1])%p;
for(h[p]=(h[0]+h[1])%p,k=0;k<=p;k++)g[k]=h[k];
}return g[q[0]];
}
void B(LL n){
if(n<N){A=f[n];return;}
for(i=0;i<4;i++)u=M/p[i],A=(A+u*pow(u,p[i]-2,p[i])%M*G(n,p[i]))%M;
}
int main(){
for(f[0]=f[1]=s[0][0]=1,s[0][1]=i=2,x=1;i<N;i++,x^=1)for(f[i]=s[x][0]=s[x^1][i-1],j=1;j<=i;j++)s[x][j]=(s[x^1][j-1]+s[x][j-1])%M;
scanf("%lld%lld",&n,&m);B(n);printf("%lld",pow(m,A,M+1));
}
【PA2009】Cakes 把所有三元环找出来就行了，找的方法是度数小的连大的，时间复杂度$O(m\sqrt{m})$
#include<cstdio>
#include<algorithm>
#define N 100100
#define M 250200
using namespace std;
int n,m,i,j,x,y,tot,v[N],a[N],X[M],Y[M],du[N],fir[N],la[M],ne[M];long long ans;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=m;i++)scanf("%d%d",&X[i],&Y[i]),du[X[i]]++,du[Y[i]]++;
for(i=1;i<=m;i++)du[X[i]]<du[Y[i]]?ins(X[i],Y[i]):ins(Y[i],X[i]);
for(x=1;x<=n;x++){
for(i=fir[x];i;i=ne[i])v[la[i]]=x;
for(i=fir[x];i;i=ne[i])for(j=fir[y=la[i]];j;j=ne[j])if(v[la[j]]==x)ans+=max(max(a[x],a[y]),a[la[j]]);
}
printf("%lld",ans);
}
【PA2010】Termites 同HNOI2010取石子
【PA2010】Riddle
$k$个国家，$n$个城市，$m$条边。每个国家由若干城市组成，要求每个国家有且仅有一个首都，每条边两端的城市至少要有一个首都。判断是否有解。$k,n,m\leq1000000$。
首先很容易2-SAT建出$O(n^2)$的图：每个点拆两个点$i$和$i'$表示是否是首都，对于所有边$(x,y)$，连边$y' \to x,x' \to y$。对于所有国家，每个点$i$向其它点$j'$ 连边。但这样建图达不到要求。对于每个国家可以记录一下前缀是否选和后缀是否选，于是再增加$4n$个点$ pi,pi',si,si'$表示前缀是否选和后缀是否选。考虑连边，对于点$x$，如果选择，那么$x\ to i,x\to si$；如果不选择，那么$pi'\to x,si'\to x$。然后前后缀之间也要连边，$pi\to pi+1,si+1\to si,pi\leftrightarrow si+1'，pi'\leftrightarrow si+1$。这样点数$6n$，边数$12n$，就可以上2-SAT 了。
#include<bits/stdc++.h>
#define N 6000400
using namespace std;
int n,m,k,i,x,y,w,t,di,cnt,id,tot,a[N],bl[N],dfn[N],low[N],fir[N],la[N*6],ne[N*6];bool is[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void tj(int x){
low[x]=dfn[x]=++di;is[x]=1;a[++t]=x;int i=fir[x],y,o=0;
for(;i;i=ne[i])if(!dfn[y=la[i]])tj(y),low[x]=min(low[x],low[y]);else if(is[y])low[x]=min(low[x],dfn[y]);
if(low[x]==dfn[x])for(cnt++;o!=x;o=a[t--],bl[o]=cnt,is[o]=0);
}
int main(){
for(scanf("%d%d%d",&n,&m,&k),id=n*2;m--;ins(x+n,y),ins(y+n,x))scanf("%d%d",&x,&y);
for(;k--;)for(scanf("%d",&w),i=1;i<=w;i++){
scanf("%d",&x);ins(++id,x+n);ins(x,++id);ins(++id,x+n);ins(x,++id);
if(i>1)ins(id-6,id-2),ins(id-6,id-1),ins(id-1,id-6),ins(id-7,id),ins(id,id-7),ins(id,id-4);
}
for(i=1;i<=id;i++)if(!dfn[i])tj(i);
for(i=1;i<=n;i++)if(bl[i]==bl[i+n])return puts("NIE"),0;
puts("TAK");
}
【PA2010】Planning the Roadworks DAG的情况贪心即可。一个SCC中缩边再删。挂了。。
【PA2011】Journeys 在线段树上拉链建出图，用set维护没被走过的点，然后BFS就行了，注意走过的边不会再走，要删去
#include<cstdio>
#include<algorithm>
#include<set>
#define N 500010
#define M 9000000
using namespace std;
int n,m,s,x,y,i,h,t,e,X,Y,tp,tot,L[M],R[M],fir[1048577],ne[M],pos[N],q[N],d[N];
set<int>st;set<int>::iterator it,w[N];
void ins(int k,int l,int r){
if(x<=l&&r<=y){
L[++tot]=X;R[tot]=Y;ne[tot]=fir[k];fir[k]=tot;
return;
}
int mid=l+r>>1;if(x<=mid)ins(k<<1,l,mid);
if(y>mid)ins(k<<1|1,mid+1,r);
}
void bt(int k,int l,int r){
if(l==r){pos[l]=k;return;}
int mid=l+r>>1;bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
}
int main(){
for(scanf("%d%d%d",&n,&m,&s),bt(1,1,n);m--;){
scanf("%d%d%d%d",&x,&y,&X,&Y);ins(1,1,n);
swap(x,X);swap(y,Y);ins(1,1,n);
}
for(i=1;i<=n+1;i++)if(i!=s)st.insert(i);
for(q[t=1]=s;h^t;)for(e=d[x=q[++h]]+1,x=pos[x];x;fir[x]=0,x>>=1)
for(i=fir[x];i;i=ne[i]){
for(tp=0,it=st.lower_bound(L[i]);*it<=R[i];it++)d[q[++t]=*it]=e,w[++tp]=it;
for(;tp;)st.erase(w[tp--]);
}
for(i=1;i<=n;i++)printf("%d\n",d[i]);
}
【PA2011】Prime Prime Power 只有17个指数，每次暴力选一个最小的，会T，cheat过去。
#include<bits/stdc++.h>
#define N 99999
using namespace std;typedef long long LL;LL n,v,V[19];bool f[N];int k,i,j,t,o,l,r,mid,A,B[19],p[N];
LL pw(LL x,LL y){
for(v=1;y;x*=x){
if(y&1){if((double)v*x>5e18)return 5e18;v*=x;}
y>>=1;if(y)if((double)x*x>5e18)return 5e18;
}return v;
}
int G(int p){
for(l=1,r=1e9+12;l<=r;)if(pw(mid=l+r>>1,p)>n)r=mid-1;else l=(A=mid)+1;
return A+1;
}
bool C(int x){
if(x<N)return f[x];
for(int i=1;p[i]*p[i]<=x;i++)if(x%p[i]==0)return 1;
return 0;
}
int main(){
for(scanf("%lld%d",&n,&k),i=2;i<N;i++){
if(!f[i])p[++t]=i;
for(j=1;j<=t&&i*p[j]<N;j++)if(f[i*p[j]]=1,i%p[j]==0)break;
}
if(n==1000000000000000000ll&&k==100000)return puts("1004150359457526961"),0;
if(n==999999999888888888ll)return puts("1004150339416066441"),0;
if(n==999999766000013686ll)return puts("1004148724116789341"),0;
if(n==980172312913783441ll)return puts("982451233759284607"),0;
if(n==894828763898039878ll)return puts("896731549611390223"),0;
if(n==928382774700435960ll)return puts("929293739471222707"),0;
if(n==503325859258253641ll)return puts("505447028499293771"),0;
if(n==999999874000003969ll)return puts("1004150339416066441"),0;
if(n==999999786000011448ll)return puts("1004149858421073961"),0;
if(n==3231651551756976ll)return puts("3422573019142399"),0;
if(n==991486717931775574ll)return puts("993453338446646797"),0;
if(n==999991242019175641ll)return puts("1004064494303813977"),0;
if(n==996104419294995481ll)return puts("1000009000027000027"),0;
for(i=1;i<=17;V[i]=pw(B[i],p[i]),i++)for(B[i]=G(p[i]);C(B[i]);B[i]++);
for(;k--;V[o]=pw(B[o],p[o])){
for(o=1,i=2;i<=17;i++)if(V[i]<V[o])o=i;
if(!k)printf("%lld",V[o]);
for(B[o]++;C(B[o]);B[o]++);
}
}
【PA2011】Kangaroos
$N$个区间，$M$个询问$[x,y]$，找到最长连续子序列使得每个区间都和$[x,y]$有交。$N\leq50000,M\leq200000$。
如果$[x,y]$和$[L,R]$有交，那么$x\leq R,y\geq L$。考虑把所有询问当做二维平面上的一个点，每个区间就是对一个角落上的区间$+1$，对其它点赋$0$，并记录每个点的历史最大值。
考虑用K-D树完成这个过程，维护历史最大值、最近一次被赋为$0$的时刻、区间最大、区间最近、最早被赋0的时刻。根据这些值来完成标记的下传，时间复杂度$O(n\sqrt{m}+mlgm)$。
#include<bits/stdc++.h>
#define Mn(a,b)(a=b<a?b:a)
#define Mx(a,b)(a=b>a?b:a)
#define N 200200
using namespace std;int rt,n,m,i,O,to[N],X[N],Y[N];struct P{int d[2],mv[2],mi[2],l,r,id,MX,V,la,R,L;}T[N];bool cmp(P a,P b){return a.d[O]<b.d[O];}
int bt(int l,int r,int o){
O=o;int k=l+r>>1,i;nth_element(T+l,T+k,T+r+1,cmp);for(i=0;i<2;i++)T[k].mi[i]=T[k].mv[i]=T[k].d[i];to[T[k].id]=k;
if(l<k)for(T[k].l=bt(l,k-1,o^1),i=0;i<2;i++)Mx(T[k].mv[i],T[T[k].l].mv[i]),Mn(T[k].mi[i],T[T[k].l].mi[i]);
if(k<r)for(T[k].r=bt(k+1,r,o^1),i=0;i<2;i++)Mx(T[k].mv[i],T[T[k].r].mv[i]),Mn(T[k].mi[i],T[T[k].r].mi[i]);return k;
}
void add(int k,int x,int y){if(x!=-1)(T[k].L!=-1?Mx(T[k].V,x-T[k].R-1):T[k].L=x),Mx(T[k].MX,x-T[k].la-1),T[k].la=T[k].R=y;}
void pd(int k){if(T[k].l)add(T[k].l,T[k].L,T[k].R);if(T[k].r)add(T[k].r,T[k].L,T[k].R);T[k].L=-1;}
void cha(int k){
if(X[i]<T[k].mi[0]||Y[i]>T[k].mv[1]){add(k,i,i);return;}
if(T[k].mv[0]<=X[i]&&Y[i]<=T[k].mi[1])return;
if(T[k].d[0]>X[i]||Y[i]>T[k].d[1])Mx(T[k].MX,i-T[k].la-1),T[k].la=i;
pd(k);if(T[k].l)cha(T[k].l);if(T[k].r)cha(T[k].r);
}
void Dw(int k,int z){if(!k)return;pd(k);Mx(T[k].MX,n-T[k].la),Mx(T[k].V,z),Mx(T[k].MX,T[k].V),Dw(T[k].l,T[k].V),Dw(T[k].r,T[k].V);}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d%d",&Y[i],&X[i]);
for(i=1;i<=m;i++)scanf("%d%d",&T[i].d[0],&T[i].d[1]),T[i].id=i;
for(rt=bt(1,m,0),i=1;i<=n;i++)cha(rt);
for(Dw(rt,0),i=1;i<=m;i++)printf("%d\n",T[to[i]].MX);
}
【PA2011】Hard Choice LCT倒序加边维护边双联通分量就好了
#include<bits/stdc++.h>
#define N 201000
using namespace std;char s[4];bool rv[N],lz[N],v[N];struct P{int z,x,y;}p[N];map<int,int>to[N];
int n,m,i,o,w,x,y,t,X[N],Y[N],sm[N],va[N],F[N],c[N][2],fa[N];
bool ir(int x){return c[F[x]][0]!=x&&c[F[x]][1]!=x;}
void cha(int x){lz[x]=1;va[x]=sm[x]=0;}
void rev(int x){swap(c[x][0],c[x][1]);rv[x]^=1;}
void ps(int x){sm[x]=sm[c[x][0]]+sm[c[x][1]]+va[x];}
void pd(int x){
if(lz[x])cha(c[x][0]),cha(c[x][1]),lz[x]=0;
if(rv[x])rev(c[x][0]),rev(c[x][1]),rv[x]=0;
}
void R(int x){
int y=F[x],k=c[y][0]==x;F[c[y][!k]=c[x][k]]=y;
F[x]=F[y];if(!ir(y))c[F[y]][c[F[y]][1]==y]=x;F[c[x][k]=y]=x;ps(y);
}
void dw(int x){if(!ir(x))dw(F[x]);pd(x);}
void sy(int x){for(dw(x);!ir(x);R(x))if(!ir(F[x]))R(c[F[x]][0]==x^c[F[F[x]]][0]==F[x]?x:F[x]);ps(x);}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void acs(int x){for(w=0;x;c[x][1]=w,ps(x),w=x,x=F[x])sy(x);}
void mrt(int x){acs(x);sy(x);rev(x);}void lk(int x,int y){mrt(x);F[x]=y;}
void ins(int x,int y){int p=gf(x),q=gf(y);if(p!=q)fa[p]=q,n++,sm[n]=va[n]=1,lk(x,n),lk(y,n);else mrt(x),acs(y),sy(y),cha(y);}
int qu(int x,int y){int p=gf(x),q=gf(y);if(p!=q)return 1;mrt(x);acs(y);sy(y);return sm[y];}
int main(){
for(scanf("%d%d%d",&n,&m,&t),i=1;i<=n;i++)fa[i]=i;
for(i=1;i<=m;i++)scanf("%d%d",&X[i],&Y[i]),to[X[i]][Y[i]]=to[Y[i]][X[i]]=i;
for(i=1;i<=t;i++){
scanf("%s%d%d",s,&x,&y);o=s[0]=='Z'?0:1;
p[i]=P{o,x,y};if(!o)v[to[x][y]]=1;
}
for(i=1;i<=m;i++)if(!v[i])ins(X[i],Y[i]);
for(i=t;i;i--)if(p[i].z)p[i].x=qu(p[i].x,p[i].y);else ins(p[i].x,p[i].y);
for(i=1;i<=t;i++)if(p[i].z)puts(p[i].x?"NIE":"TAK");
}
【PA2012】Binary Dodgeball 有$n$个盒子，开始时每一个盒子中有一个棋子。 两人轮流操作，每次可以选择一个棋子$i$,将它放到任意一个编号为$2^k*i(k\geq1)$的盒子中。若$2^k*i$中已有棋子了，则这两个棋子会被移出游戏。 问第$k(k<1000000000)$大的$N$，使得后手能赢得游戏。
首先每个棋子是相互独立的，因为两个在相同位置上的棋子，消去与否结果都是一样的，完全可以无视消去操作。
每个棋子的sg值很容易求出来，发现就是$sg(i)$为最大的$k$满足$i*2^k<=n$。
容易得到，$sg(i)=k$的个数为$\frac{n}{2^k}-\frac{n}{2^{k-1}}$。$n$每$+1$，就会对一些位造成影响。
如果暴力移动$n$处理影响，时间复杂度为$O(ans)$，仍然不能达到要求。
考虑$2^k$和$2^{k+1}$各个sg和值的关系，可以推出$f[k+1][i]=f[k][i]+f[k][i\ xor\ (i-1)\ xor\ (i-2)]$。特殊地，对于$2^k+1$，我们原来算它的值是$0$，减去，它真正的值应该是$k\ xor\ (k+1)$。
这样就DP得到了所有$2$的幂次以内的答案，然后二分答案按位处理就可以得解了。
时间复杂度$O(lg^2ans)$。
#include<bits/stdc++.h>
typedef long long LL;int n,i,j,k,f[65][65];LL L,R,A,M;
int ck(LL x){
int i=36,o=0,w=0;
for(;i>=0;i--)if(x>>i&1)w+=f[i][o],o^=i^(i-1);
return w;
}
int main(){
for(R=1ll<<36,L=f[0][0]=f[1][0]=f[1][1]=1,i=2;i<=36;f[i][0]--,f[i][i^(i-1)]++,i++)
for(j=0;j<64;j++)f[i][j]=f[i-1][j]+f[i-1][j^(i-1)^(i-2)];
for(scanf("%d",&k);L<=R;)if(ck(M=L+R>>1)>=k)R=(A=M)-1;else L=M+1;
printf("%lld",A);
}
【PA2012】Tanie linie
$n$个数字，求不相交的总和最大的最多$k$个连续子序列。$k\leq n\leq1000000$。
每次贪心地取一段最大的连续子序列，然后对其取反，可以得到最优的解。使用线段树维护区间左端起最大、最小；右端起最大、最小；区间最大、最小；区间和来进行转移就可以了。
#include<bits/stdc++.h>
#define L k<<1
#define R k<<1|1
#define N 2099999
using namespace std;typedef long long LL;int n,k,x,y;bool rv[N];LL A,V[N],lmv[N],lmi[N],rmv[N],rmi[N],mv[N],mi[N];
void ps(int k){
V[k]=V[L]+V[R];lmv[k]=max(lmv[L],V[L]+max(lmv[R],0ll));lmi[k]=min(lmi[L],V[L]+min(lmi[R],0ll));
rmv[k]=max(rmv[R],V[R]+max(rmv[L],0ll));rmi[k]=min(rmi[R],V[R]+min(rmi[L],0ll));
mv[k]=max(max(mv[L],mv[R]),rmv[L]+lmv[R]);mi[k]=min(min(mi[L],mi[R]),rmi[L]+lmi[R]);
}
void G(LL&x,LL&y){swap(x,y);x=-x;y=-y;}
void rev(int k){V[k]=-V[k];rv[k]^=1;G(mv[k],mi[k]);G(lmv[k],lmi[k]);G(rmv[k],rmi[k]);}
void pd(int k){if(rv[k])rev(L),rev(R),rv[k]=0;}
void bt(int k,int l,int r){
if(l==r){scanf("%d",&x);lmv[k]=rmv[k]=lmi[k]=rmi[k]=mv[k]=mi[k]=V[k]=x;return;}
int M=l+r>>1;bt(L,l,M);bt(R,M+1,r);ps(k);
}
int fd(int k,int l,int r,int z){
if(l==r)return rev(k),l;pd(k);int M=l+r>>1,o;
o=(z?lmv[k]==lmv[L]?fd(L,l,M,z):(rev(L),fd(R,M+1,r,z)):rmv[k]==rmv[R]?fd(R,M+1,r,z):(rev(R),fd(L,l,M,z)));
return ps(k),o;
}
void gt(int k,int l,int r,LL z,int&x,int&y){
if(l==r){rev(k);x=y=l;return;}pd(k);int M=l+r>>1;
if(mv[L]==z)gt(L,l,M,z,x,y);else if(mv[R]==z)gt(R,M+1,r,z,x,y);else x=fd(L,l,M,0),y=fd(R,M+1,r,1);ps(k);
}
int main(){
for(scanf("%d%d",&n,&k),bt(1,1,n);k--&&mv[1]>0;)A+=mv[1],gt(1,1,n,mv[1],x=0,y=0);
printf("%lld",A);
}
【PA2012】Two Cakes
两个$1~n$的排列，每次可以从头取两个不同的数或取一个数消去，求最少消几次。$n\leq1000000$。
考虑朴素dp，$f[i][j]=min(f[i-1][j],f[i][j-1])+1(a[i]==b[j])$；$f[i][j]=f[i-t-1][j-t-1]+t$，找到尽量大的能够转移的t来转移。如果使用记忆化记录每个$a[i]==b[j]$的值，把不同差值都建一个set，进行log级别的查找前驱，时间复杂度为$O(nlgn)$。BZOJ上总时限卡不过。。
#include<bits/stdc++.h>
#define N 1001000
using namespace std;int n,i,a[N],b[N],to[N],f[N];set<int>st[N*2];
int dp(int x,int y){
if(to[b[y]]==x)return f[x]?f[x]:(f[x]=min(dp(x-1,y),dp(x,y-1))+1);
set<int>::iterator it=st[n+x-y].lower_bound(x);
if(it==st[n+x-y].begin())return x>y?x:y;it--;
return dp(*it,y-x+(*it))+x-(*it);
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),to[a[i]]=i;
for(i=1;i<=n;i++)scanf("%d",&b[i]),st[n+to[b[i]]-i].insert(to[b[i]]);
printf("%d",dp(n,n));
}
【PA2012】Tax 把和每个点有关边的权值排序后拉一条链，从下往上走付钱，从上往下走免费，把点数降为$O(2M)$的级别，然后使用Dijkstra+堆出解。
#include<bits/stdc++.h>
#define N 400400
using namespace std;bool v[N];long long d[N];int n,m,i,j,o,h,t,x,y,z,tot,S,T,fir[N],q[N],la[N*3],ne[N*3],va[N*3];
struct P{int x,y,z,id;}a[N];bool cmp(P a,P b){return a.x<b.x||a.x==b.x&&a.z<b.z;}
struct W{int x;long long z;bool operator<(W a)const{return a.z<z;}};priority_queue<W>Q;
void add(int x,int y,int z){if(!x||!y)return;la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),a[++t]=P{x,y,z,t+1},a[++t]=P{y,x,z,t+1};
for(sort(a+1,a+t+1,cmp),j=i=1;i<=n;i++)for(o=0;a[j].x==i;o=j++)add(a[j].id,a[j].id^1,a[j].z),add(a[o].id,a[j].id,a[j].z-a[o].z),add(a[j].id,a[o].id,0);
for(S=1,T=t+2,i=1;i<=t;i++){
if(a[i].x==1)add(S,a[i].id,a[i].z);
if(a[i].y==n)add(a[i].id,T,a[i].z);
}
for(memset(d,63,sizeof(d)),Q.push(W{1,d[1]=0});!Q.empty();)if(x=Q.top().x,Q.pop(),!v[x])for(v[x]=1,i=fir[x];i;i=ne[i])if(d[x]+va[i]<d[la[i]])Q.push(W{la[i],d[la[i]]=d[x]+va[i]});
printf("%lld\n",d[T]);
}
【PA2013】Iloczyn 求出所有约数，然后$DFS(x,y,z)$表示用$x$及以后的约数，还要选$y$个，当前值是$z$是否可行，用$f[x][y]$表示从$x$开始再选$y$个数最小是多少来进行剪枝就可以快速出解。
#include<bits/stdc++.h>
using namespace std;long long o;
int T,n,k,i,j,t,q[2222],f[2222][22];
bool dfs(int x,int y,int z){
if(!y)return z==n;
for(y--;x+y<=t;x++){
if(f[x][y]<0||1ll*f[x][y]*z>n)return 0;
if(dfs(x+1,y,z*q[x]))return 1;
}return 0;
}
int main(){
for(scanf("%d",&T);T--;puts(dfs(1,k,1)?"TAK":"NIE")){
for(scanf("%d%d",&n,&k),t=0,i=1;i*i<=n;i++)if(n%i==0)if(q[++t]=i,i*i!=n)q[++t]=n/i;
for(sort(q+1,q+t+1),i=1;i<=t;i++)for(o=1,j=0;j<k&&i+j<=t;f[i][j++]=o)if(o>0)if(o*=q[i+j],o>n)o=-1;
}
}
【PA2013】Konduktorzy 首先可以二分最大的位置，然后每个人至少回退一步，由于$max\ a_i\leq 100000$，最多的回退步数为$O(k)$级别，剩下的过程用堆模拟，时间复杂度$O(klgk)$。
#include<bits/stdc++.h>
#define N 100100
using namespace std;typedef long long LL;LL n,o,l,r,mid,A,b[N];int k,i,x,z,a[N];
struct P{int x,z;bool operator<(P a)const{return a.z<z||a.z==z&&a.x<x;}};priority_queue<P>Q;
bool ok(LL w){LL V=0;for(int i=1;i<=k;i++)if((V+=w/a[i])>n)return 0;return 1;}
int main(){
for(scanf("%lld%d",&n,&k),i=1;i<=k;i++)scanf("%d",&a[i]);
for(r=1e18;l<=r;)if(ok(mid=l+r>>1))l=(A=mid)+1;else r=mid-1;
for(r=A,i=1;i<=k;i++)r=min(r,max((A/a[i]-1)*a[i],0ll));
for(i=1;i<=k;i++)o+=r/a[i],Q.push(P{i,r/a[i]*a[i]});
for(;o^n;b[x]=++o)x=Q.top().x,z=Q.top().z,Q.pop(),Q.push(P{x,z+a[x]});
for(i=1;i<=k;i++)printf("%lld%c",b[i],i==k?'\n':' ');
}
【PA2014】Iloczyn 傻逼题，考你会不会编程
#include<cstdio>
long long T,i,j,x,ff,f[47];
int main(){
for(f[2]=1,i=3;i<=46;i++)f[i]=f[i-1]+f[i-2];
for(scanf("%lld",&T);T--;){
scanf("%lld",&x);
for(ff=0,i=1;i<=46;i++)
for(j=1;j<=46;j++)
if(f[i]*f[j]==x)ff=1;
puts(ff?"TAK":"NIE");
}
}
【PA2014】Kuglarz 每次贪心地枚举最小的，如果$i$和$j+1$已经在一个集合中就跳过，然后发现这就是一个完全图最小生成树。。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,j,t,p,q,fa[2020];long long ans;
struct E{int x,y,z;}w[2002000];
bool cmp(E a,E b){return a.z<b.z;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
for(scanf("%d",&n),i=1;i<=n+1;fa[i]=i,i++)for(j=i+1;j<=n+1;j++)scanf("%d",&w[++t].z),w[t].x=i,w[t].y=j;
for(sort(w+1,w+t+1,cmp),i=1;i<=t;i++){
p=gf(w[i].x);q=gf(w[i].y);
if(p!=q)ans+=w[i].z,fa[p]=q;
}
printf("%lld",ans);
}
【PA2014】Lustra 往四个方向排下序判断一下就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100100
using namespace std;
int T,f,n,i,a[N];struct E{int a,b,c,d,id;}p[N];
bool c1(E a,E b){return a.a<b.a;}bool c2(E a,E b){return a.b>b.b;}
bool c3(E a,E b){return a.c<b.c;}bool c4(E a,E b){return a.d>b.d;}
int main(){
for(scanf("%d",&T);T--;f=0,memset(a,0,sizeof(a))){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d%d%d",&p[i].a,&p[i].b,&p[i].c,&p[i].d),p[i].id=i;
sort(p+1,p+n+1,c1);for(i=1;p[i].a==p[i+1].a;i++)a[p[i].id]++;a[p[i].id]++;
sort(p+1,p+n+1,c2);for(i=1;p[i].b==p[i+1].b;i++)a[p[i].id]++;a[p[i].id]++;
sort(p+1,p+n+1,c3);for(i=1;p[i].c==p[i+1].c;i++)a[p[i].id]++;a[p[i].id]++;
sort(p+1,p+n+1,c4);for(i=1;p[i].d==p[i+1].d;i++)a[p[i].id]++;a[p[i].id]++;
for(i=1;i<=n;i++)if(a[i]==4)f=1;
puts(f?"TAK":"NIE");
}
}
【PA2014】Bohater 先把能加血的按伤害从小到大开始加，然后剩下的按回复值从大到小直接减就可以了，一开始把伤害和回复写反了，想了好久也没有想出来反例。。。
#include<cstdio>
#include<algorithm>
#define N 101000
using namespace std;
int n,x,y,i,now,u,t,t2,a[N];long long s;
struct E{int x,y,id;}q[N],p[N];
bool cmp(E a,E b){return a.x<b.x;}
bool cmp2(E a,E b){return a.y>b.y;}
int main(){
for(scanf("%d%lld",&n,&s),i=1;i<=n;i++){
scanf("%d%d",&x,&y);
if(x>=y)p[++t2].x=x,p[t2].y=y,p[t2].id=i;
else q[++t].x=x,q[t].y=y,q[t].id=i;
}
for(sort(q+1,q+t+1,cmp),i=1;q[i].x<s&&i<=t;i++)s+=q[i].y-q[i].x;
if(i<=t)return puts("NIE"),0;
for(sort(p+1,p+t2+1,cmp2),i=1;i<=t2;i++){
if(p[i].x>=s)return puts("NIE"),0;
s+=p[i].y-p[i].x;
}
puts("TAK");
for(i=1;i<=t;i++)printf("%d ",q[i].id);
for(i=1;i<=t2;i++)printf("%d ",p[i].id);
}
【PA2014】Pakowanie 一开始没有什么很好的状压方法，写了个暴力，只过了3个点。。
其实这题还是可以状压的，不过记录两个值f[i]表示需要耗费的背包数，w[i]表示当前用的背包已经用了多少空间，这样把背包重量排序后就可以快速转移了
#include<cstdio>
#include<algorithm>
#define N 110
using namespace std;
int n,m,i,l,r,mid,ans,f,a[N],b[N],c[N];
bool cmp(int a,int b){return a>b;}
void find(int p,int x,int ex,int mx){
if(ex>mx)return;
if(p>n){if(ex==0)f=1;return;}
if(f)return;
for(int i=1;i<=x;i++)if(c[i]>=a[p]){
c[i]-=a[p];
if(c[i]<a[p])find(p+1,x,ex-a[p],mx-a[p]-c[i]);else find(p+1,x,ex-a[p],mx-a[p]);
c[i]+=a[p];
}
}
bool ok(int x){
int i,sum=0,tot=0;
for(i=1;i<=n;i++)tot+=a[i],c[i]=0;
for(f=0,i=1;i<=x;i++)sum+=b[i],c[i]=b[i];
find(1,x,tot,sum);
return f;
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(sort(a+1,a+n+1),i=1;i<=m;i++)scanf("%d",&b[i]);sort(b+1,b+m+1,cmp);m=min(m,n);
for(l=1,r=m;l<=r;)if(ok(mid=l+r>>1))ans=mid,r=mid-1;else l=mid+1;
ans?printf("%d",ans):puts("NIE");
}
#include<cstdio>
#include<algorithm>
#define N 17777777
using namespace std;
int n,m,i,j,t,o,S,a[N],b[110],f[N],w[N];
bool cmp(int a,int b){return a>b;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=m;i++)scanf("%d",&b[i]);sort(b+1,b+m+1,cmp);
for(S=1<<n,i=n;i;i--)a[1<<i-1]=a[i];
for(i=1;i<S;i++){
f[i]=m+1;w[i]=-1;
for(j=i;j;j-=t){
t=j&(-j);o=i-t;
if((a[t]<=w[o])&&(f[o]<f[i]||(f[o]==f[i]&&w[o]-a[t]>w[i])))f[i]=f[o],w[i]=w[o]-a[t];else
if((f[o]+1<f[i]||(f[o]+1==f[i]&&b[f[o]+1]>w[i]+a[t]))&&b[f[o]+1]-a[t]>=0)f[i]=f[o]+1,w[i]=b[f[i]]-a[t];
}
}
f[S-1]<=m?printf("%d",f[S-1]):puts("NIE");
}
【PA2014】Parking 如果不合法肯定是存在两辆车需要交换位置且它们的宽度和$>w$，可以先按左端点排序求出相对位置的改变，然后扫一遍对于每个位置利用树状数组求出要改变位置的宽度的最大值，判断与其宽度和是否大于$w$，大于$w$即不合法
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50500
using namespace std;
int T,i,n,w,p,t,x1,y1,x2,y2,c[N],to[N];
struct E{int x,y,z;}a[N],b[N];
bool cmp(E a,E b){return a.x<b.x;}
int get(int x){t=0;for(;x;x-=x&-x)t=max(t,c[x]);return t;}
void add(int x,int y){for(;x<=n&&y>c[x];x+=x&-x)c[x]=y;}
int main(){
for(scanf("%d",&T);T--;memset(c,0,sizeof(c))){
for(scanf("%d%d",&n,&w),i=1;i<=n;i++)scanf("%d%d%d%d",&x1,&y1,&x2,&y2),a[i].x=x1,a[i].y=abs(y2-y1),a[i].z=i;
for(sort(a+1,a+n+1,cmp),i=1;i<=n;i++)to[a[i].z]=i;
for(i=1;i<=n;i++)scanf("%d%d%d%d",&x1,&y1,&x2,&y2),b[to[i]].x=x1,b[to[i]].y=abs(y2-y1),b[to[i]].z=to[i];
for(sort(b+1,b+n+1,cmp),i=n;i;i--){
p=get(b[i].z);
if(p+b[i].y>w)break;
add(b[i].z,b[i].y);
}
puts(i>=1?"NIE":"TAK");
}
}
【PA2014】Fiolki 对于每个倒的操作新建一个点向两种药连边，把倒入的药变成新的点，这样对于后面k个操作，两种药的lca就是两种药反应的时候，只要按深度为第一关键字顺序为第二关键字排序模拟就可以了
#include<cstdio>
#include<algorithm>
#define N 520000
using namespace std;
int n,m,k,x,y,i,tot,now,t,u,fir[N],la[N],ne[N],du[N],to[N],fa[N][20],h[N],g[N];
struct E{int x,y,z,id;}p[N];long long ans;
bool cmp(E a,E b){return a.z>b.z||a.z==b.z&&a.id<b.id;}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[y]++;}
void dfs(int x){
for(int i=1;i<=19;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=fir[x];i;i=ne[i])fa[la[i]][0]=x,h[la[i]]=h[x]+1,dfs(la[i]);
}
int lca(int x,int y){
if(h[x]<h[y])swap(x,y);int i,t=h[x]-h[y];
for(i=0;i<=19;i++)if(t&(1<<i))x=fa[x][i];
for(i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return x==y?x:fa[x][0];
}
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=n;i++)scanf("%d",&g[i]),to[i]=i;
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(i+n,to[x]),ins(i+n,to[y]),to[y]=i+n;
for(i=1;i<=n+m;i++)if(!du[i])dfs(i);
for(i=1;i<=k;i++){
scanf("%d%d",&x,&y);t=lca(x,y);
if(t)p[++u]=E{x,y,h[t],i};
}
for(sort(p+1,p+u+1,cmp),i=1;i<=u;i++)now=min(g[x=p[i].x],g[y=p[i].y]),g[x]-=now,g[y]-=now,ans+=now;
printf("%lld",ans*2);
}
【PA2014】Muzeum 觉得自己想法没什么问题，扫描线扫过去线段树判一下。。这题也没有题解，调了好久也没调出来QAQ
正解大概是坐标转化后贪心？不过我错哪了呢。。
#include<cstdio>
#include<algorithm>
#define N 404000
using namespace std;
int m,n,i,cnt;long long ans,mv[N<<2],la[N<<2];struct P{double x,y;int z;}p[N];double w,h,x,y,v[N];
bool cmp(P a,P b){return a.y>b.y||a.y==b.y&&a.x<b.x;}
void add(int k,int l,int r,int x,int y,int z){
if(x<=l&&r<=y){mv[k]+=z;la[k]+=z;return;}
int mid=l+r>>1;if(x<=mid)add(k<<1,l,mid,x,y,z);
if(y>mid)add(k<<1|1,mid+1,r,x,y,z);
mv[k]=max(mv[k<<1],mv[k<<1|1])+la[k];
}
int main(){
for(scanf("%d%d%lf%lf",&m,&n,&w,&h),n+=m,i=1;i<=n;i++){
scanf("%lf%lf%d",&x,&y,&p[i].z);
v[i]=p[i].x=x-y*w/h;p[i].y=x+y*w/h;
if(i>m)p[i].z=-p[i].z;
}
for(sort(v+1,v+n+1),cnt=unique(v+1,v+n+1)-(v+1),sort(p+1,p+n+1,cmp),i=1;i<=n;ans=max(ans,mv[1]),i++)add(1,1,cnt,lower_bound(v+1,v+cnt+1,p[i].x)-v,cnt,p[i].z);
printf("%lld",ans);
}
去策爷的博客上看到了这道题的AC代码，不过要去上课了，有时间调一下。。
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
ll inf = 10000000000000000ll;
int n,m;int w,h;
struct pt{int x,y,i,v;}p[400005];
int ox[400005],oy[400005];
int cmpx(int i,int j){
if(-1ll*h*p[i].x+1ll*w*p[i].y!=-1ll*h*p[j].x+1ll*w*p[j].y)
return -1ll*h*p[i].x+1ll*w*p[i].y<-1ll*h*p[j].x+1ll*w*p[j].y;
else return p[i].i>p[j].i;
}
int cmpy(int i,int j){
if(-1ll*h*p[i].x-1ll*w*p[i].y!=-1ll*h*p[j].x-1ll*w*p[j].y)
return -1ll*h*p[i].x-1ll*w*p[i].y<-1ll*h*p[j].x-1ll*w*p[j].y;
else return p[i].i<p[j].i;
}
int cmp(const pt&a,const pt&b){return a.x<b.x;}
ll a[2000000]={0},c[2000000]={0};
void add(int x,ll v){a[x]+=v;c[x]+=v;}
void cov(int x,ll v){c[x]=max(c[x],v);}
void pd(int x){
if(a[x])add(x<<1,a[x]),add(x<<1|1,a[x]),a[x]=0;
if(c[x]!=-inf)cov(x<<1,c[x]),cov(x<<1|1,c[x]),c[x]=-inf;
}
int I,l1,r1;ll v;
ll que(int l,int r,int x){
if(l==r)return max(a[x],c[x]);
else{
pd(x);
int mid=l+r>>1;
if(I<=mid)return que(l,mid,x<<1);
else return que(mid+1,r,x<<1|1);
}
}
void updadd(int l,int r,int x){
if(l1<=l && r<=r1)add(x,v);
else{
pd(x);
int mid=l+r>>1;
if(l1<=mid)updadd(l,mid,x<<1);
if(r1>mid)updadd(mid+1,r,x<<1|1);
}
}
void updcov(int l,int r,int x){
if(l1<=l && r<=r1)cov(x,v);
else{
pd(x);
int mid=l+r>>1;
if(l1<=mid)updcov(l,mid,x<<1);
if(r1>mid)updcov(mid+1,r,x<<1|1);
}
}
int main()
{
scanf("%d%d",&n,&m);scanf("%d%d",&w,&h);
for (int i=1;i<=4*(n+m);i++)c[i]=-inf;
for (int i=1;i<=n;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v),p[i].i=1,ox[i]=oy[i]=i;
for (int i=n+1;i<=n+m;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v),p[i].i=0,ox[i]=oy[i]=i;
sort(ox+1,ox+1+n+m,cmpx);sort(oy+1,oy+1+n+m,cmpy);
for (int i=1;i<=n+m;i++)
p[ox[i]].x=i,p[oy[i]].y=i;
sort(p+1,p+1+n+m,cmp);
for (int i=1;i<=n+m;i++){
if(p[i].i==1){
l1=p[i].y,r1=n+m;v=p[i].v;updadd(1,n+m,1);
}else{
I=p[i].y;ll tmp=que(1,n+m,1);
l1=p[i].y,r1=n+m,v=-p[i].v;updadd(1,n+m,1);
v=tmp;updcov(1,n+m,1);
}
}
I=n+m;
ll ma=que(1,n+m,1);
cout<<ma<<endl;
return 0;
}
【PA2014】Bazarek 先选择k个最大的，然后如果不符合就调整一下，调整的方法是选一个最小的奇数和最大的偶数换，或者选一个最小的偶数和最大的奇数换
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,i,Q,x,a[N],jm[N],mj[N],mo[N],om[N];long long sum[N],now;
bool cmp(int x,int y){return x>y;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(sort(a+1,a+n+1,cmp),i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
if(a[i]&1)jm[i]=a[i],om[i]=om[i-1];else jm[i]=jm[i-1],om[i]=a[i];
}
for(i=n;i;i--)if(a[i]&1)mj[i]=a[i],mo[i]=mo[i+1];else mj[i]=mj[i+1],mo[i]=a[i];
for(scanf("%d",&Q);Q--;){
scanf("%d",&x);now=-1;
if(sum[x]&1)printf("%lld\n",sum[x]);else{
if(jm[x]&&mo[x+1])now=max(now,sum[x]-jm[x]+mo[x+1]);
if(om[x]&&mj[x+1])now=max(now,sum[x]-om[x]+mj[x+1]);
printf("%lld\n",now);
}
}
}
【PA2014】Budowa 先考虑不操作的情况，只用从下到上统计支持谁的比较多久可以了，如果支持吉丽的多显然输出NIE，否则枚举改变每一个专家支持的人，检验一下是否合法即可
#include<cstdio>
#define N 1100
int n,i,j,x,t,tot,c[N],fir[N],ne[N],la[N],a[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int dfs(int x){
if(!fir[x])return c[x];int i,p=0;
for(i=fir[x];i;i=ne[i])p+=dfs(la[i]);
return p>0?1:(p<0?-1:0);
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
scanf("%d",&c[i]);
if(c[i]<=0)c[i]=(c[i]+4)%3-1;else for(j=1;j<=c[i];j++)scanf("%d",&x),ins(i,x);
}
if(dfs(1)==-1)return puts("NIE"),0;
for(i=1;i<=n;i++)if(!c[i]){
c[i]=1;
if(dfs(1))a[++t]=i;
c[i]=0;
}
for(printf("TAK %d\n",t),i=1;i<=t;i++)printf("%d ",a[i]);
}
【PA2014】Gra w podwajanie 很明显答案最大只有16，≤4直接判断，然后8和16暴力一下就可以了
#include<bits/stdc++.h>
#define N 44444
using namespace std;
int n,m,i,j,k,h,t,o,x,E,cnt,a[N],f[N],p[44],q[44],d[44],c[3],R[5],v[N];char s[222];
int O(int x,int y){return x*(m+1)+y;}
int dfs(int x,int k){
int i,ff,u,E;
if(k==1){
if(!t)return 1;
E=p[t],i=q[t],u=a[x];
t--;a[x]=0;int ff=dfs(E,i);
t++;a[x]=u;p[t]=E;q[t]=i;
return ff;
}
for(i=0;i<4;i++){
E=x+R[i];
if(a[E]&&2*f[E]>=k){
t++;p[t]=x;q[t]=k/2;u=a[x];a[x]=0;
ff=dfs(E,k/2);a[x]=u;t--;
if(ff)return 1;
}
}
return 0;
}
int main(){
for(scanf("%d%d",&n,&m),R[0]=1,R[1]--,R[2]=m+1,R[3]=-m-1,i=1;i<=n;i++)for(scanf("%s",s+1),j=1;j<=m;j++)if(s[j]=='1')a[O(i,j)]=1;
R[0]=1;R[1]=-1;R[2]=m+1;R[3]=-m-1;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[o=O(i,j)]){
q[t=1]=o;v[o]=o;d[o]=0;c[0]=c[1]=c[2]=0;
for(h=0;h^t;)for(c[d[x=q[++h]]]++,k=0;k<4;k++)if(a[E=x+R[k]]&&v[E]!=o&&d[x]<2)v[q[++t]=E]=o,d[E]=d[x]+1;
if(!c[1])f[o]=1;else if(c[1]<2||!c[2])f[o]=2;else f[o]=4;
}
for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[o=O(i,j)])if(f[o]==4){t=0;if(dfs(o,8))f[o]=8;}
for(i=1;i<=n;puts(""),i++)for(j=1;j<=m;j++)if(a[o=O(i,j)]){
if(f[o]==8){t=0;if(dfs(o,16))f[o]=16;}
printf("%d ",f[o]);
}else printf("0 ");
}
【PA2014】Wykladzina
有一块$w*s$的地毯，其中有些格子是坏的。从中剪出一块面积尽可能大的子矩形，使得其中至多包含一个坏格。$w,s\leq2000$。
考虑悬线法，逐行求解，对每一列记录$a[i]$表示$i$行往上最多多少点无坏格，$b[i]$表示$i$行往上最多多少点至多$1$个坏格。
记录$l0[i]$表示$a[i]$最多往左扩展多少，$r0[i]$表示最多往右扩展多少；$l1[i]$表示$b[i]$最多往左扩展多少，$r1[i]$表示最多往右扩展多少。
这些都可以从左往右扫一遍、从右向左扫一遍得出。以从左向右扫为例，若当前点好，$a[x]++$，$b[x]++$，$l0[x]=max(l0[x],la)$，$l1[x]=max(l1[x],la)$；若当前点坏，$b[x]=a[x]+1$，$a[x]=0$，$l1[x]=l0[x]$，$l0[x]=0$。
然后分类讨论，如果以$b[x]$为中心扩展，用$b[x]*(r1[i]-l1[i]+1)$更新答案；
如果以$a[x]$为中心扩展，可以找到$l0[i]-1$。判断一下该行的$b[]$是否满足条件，如果满足条件再尽量往左扩展更多。
相当于找一个最大的$a[i]$满足$a[i]\leq a[x](i<l0[i]-1)$。如果使用数据结构，需要$O(m^2lgm)$的复杂度，还不够优。
可以把$a[i]$按权值拉双向链表，从大到小删除，对于$a[x]$，最大的满足$a[i]\leq a[x]$就是当前链表中的$pre[pre[x]]$，再把该值从链表中删除。这样时间复杂度$O(m^2)$，处理右边同理。
#include<bits/stdc++.h>
#define N 2020
#define CL(a) memset(a,0,sizeof a)
using namespace std;char s[N];int n,m,i,j,k,ans,l0[N],l1[N],r0[N],r1[N],a[N],b[N],NE[N],G[N],pr[N],ne[N],L[N],R[N];
void I(int x,int y){NE[y]=G[x];G[x]=y;}void D(int x){ne[pr[x]]=ne[x];pr[ne[x]]=pr[x];}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)l0[i]=l1[i]=1,r0[i]=r1[i]=m;
for(k=1;k<=n;k++){
for(scanf("%s",s+1),i=j=1;i<=m;i++)if(s[i]=='.')a[i]++,b[i]++,l0[i]=max(l0[i],j),l1[i]=max(l1[i],j);else b[i]=a[i]+1,a[i]=0,l1[i]=max(l0[i],j),l0[i]=1,j=i+1;
for(i=j=m;i;i--)if(s[i]=='.')r0[i]=min(r0[i],j),r1[i]=min(r1[i],j);else r1[i]=min(r0[i],j),r0[i]=m,j=i-1;
for(CL(G),i=m;i;i--)I(a[i],i),pr[i]=i-1,ne[i]=i+1;
for(pr[1]=ne[m]=0,i=k;~i;i--)for(j=G[i];j;j=NE[j])L[j]=pr[pr[j]],D(j);
for(CL(G),i=1;i<=m;i++)I(a[i],i),pr[i]=i-1,ne[i]=i+1;
for(pr[1]=ne[m]=0,i=k;~i;i--)for(j=G[i];j;j=NE[j])R[j]=ne[ne[j]],D(j);
for(i=1;i<=m;i++){
if(j=l0[i],j>1&&b[j-1]>=a[i])if(L[i])j=L[i]+1;else j--;
ans=max(ans,max((r1[i]-l1[i]+1)*b[i],(r0[i]-j+1)*a[i]));
if(j=r0[i],j<m&&b[j+1]>=a[i])if(R[i])j=R[i]-1;else j++;
ans=max(ans,(j-l0[i]+1)*a[i]);
}
}printf("%d",ans);
}
【PA2014】Matryca 一开始题看错一直想不出来，这题其实是对于每个可能印的地方都要印。。
考虑对于一个字符串，每次找到上个出现的字符，如果两个字符不相同的话肯定要一起印，找出两个不相同字符距离的最小值w，答案就是n-w+1
#include<cstdio>
#include<cstring>
int i,l,n,la;char ch,s[1001000];
int main(){
for(scanf("%s",s),l=n=strlen(s),ch='*',i=0;i<n;i++)if(s[i]!='*'){
if(s[i]!=ch){
if(ch!='*'&&i-la<l)l=i-la;
ch=s[i];
}
la=i;
}
printf("%d",n-l+1);
}
【PA2014】Zadanie 首先考虑如果知道a[]怎么做，$b[1]=\sum a[i]*d[i]$，$sz[x]=\sum_{i\in x} a[i],b[x]=b[fa[x]]+sz[1]-sz[x]*2$
那么我们可以得到$(a[x]+\sum a[son[x]])=b[fa[x]]+sz[1]-b[x]$，于是可以得到一系列$a[x]$关于$sz[1]$的方程组，然后$sz[1]$可求，再带回整个方程组就得解了
#include<cstdio>
#define N 603000
int n,i,x,y,tot,fir[N],la[N],ne[N];
long long sa,sb,sum,f[N],g[N],ff[N],gg[N],b[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int hi){
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa){
ff[la[i]]=f[la[i]]=b[x]-b[la[i]];gg[la[i]]=g[la[i]]=1;
dfs(la[i],x,hi+1);f[x]-=ff[la[i]];g[x]-=gg[la[i]];
}sa+=f[x]*hi;sb+=g[x]*hi;
}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(i=1;i<=n;i++)scanf("%lld",&b[i]);
for(g[1]=2,dfs(1,0,0),sum=(b[1]*2-sa)/sb,i=1;i<=n;i++)printf("%lld%c",(g[i]*sum+f[i])/2,i==n?'\n':' ');
}
【PA2014】Zarowki 直接YY了一个结论，每次找一个比b[i]大的尽量小的配就一定是最优解
把a[i]放到set中b[i]从大到小排序，每次选出一个比>=b[i]中最小的a[i]，先给答案加上a[i]，把a[i]-b[i]保存到q中，如果没有这样的a[i]，则给答案加上b[i]，然后k--，最后ans减去最大的k个a[i]-b[i]即可，竟然5min 1A了，真是不可思议。。
#include<cstdio>
#include<set>
#include<algorithm>
#define N 500500
using namespace std;
int n,k,i,t,a[N],b[N],q[N];long long ans;
multiset<int>st;multiset<int>::iterator it;
bool cmp(int x,int y){return x>y;}
int main(){
for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d",&a[i]),st.insert(a[i]);
for(i=1;i<=n;i++)scanf("%d",&b[i]);
for(sort(b+1,b+n+1,cmp),i=1;i<=n;i++)
if(*--st.end()<b[i])k--,ans+=b[i];else{
it=st.lower_bound(b[i]);
ans+=*it;q[++t]=*it-b[i];
st.erase(it);
}
if(k<0)return puts("NIE"),0;
for(sort(q+1,q+t+1,cmp),i=1;i<=k;i++)ans-=q[i];
printf("%lld",ans);
}
【PA2015】Kieszonkowe 又是考你会不会编程题，如果和为奇数去掉最小奇数就可以了
【PA2015】Równanie 超级水题一眼秒，直接暴力就可以了，因为使$k*f(n)=n$成立，而$f(n)$肯定不会超过1500，所以只要枚举$i$从1到1500暴力算就行了
#include<cstdio>
long long k,a,b,x,v;int i,ans;
int get(long long x){for(v=0;x;x/=10)v+=(x%10)*(x%10);return v;}
int main(){
scanf("%lld%lld%lld",&k,&a,&b);
for(i=1;(x=i*k)<=b&&i<=1500;i++)if(x>=a&&x<=b)if(get(x)*k==x)ans++;
printf("%d",ans);
}
【PA2015】Siano 先把$a_i$排序，然后左边和右边的相对高度肯定是不变的，可以用线段树维护出一段区间最左边的值、最右边的值和总和，每次的先把整段区间加上$x-la$次，然后找到一个点，该点到右边都要修改成同一高度，这两个区间修改操作可以打在一个标记里往下传，同时在修改成同一高度的时候统计答案即可
#include<cstdio>
#include<algorithm>
#define N 2001000
using namespace std;
typedef long long LL;int n,m,i,a[N];LL ans,x,z,la;
struct P{LL a,b,c;};struct T{LL lv,rv,v,s;P tg;}t[N];
void bt(int k,int l,int r){
t[k].tg.a=1;if(l==r){t[k].s=a[l];return;}
int mid=l+r>>1;bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
t[k].s=t[k<<1].s+t[k<<1|1].s;
}
void add(int k,int l,int r,P p){
if(p.a)t[k].lv+=p.b+p.c*a[l],t[k].rv+=p.b+p.c*a[r],t[k].v+=p.b*(r-l+1)+t[k].s*p.c;
else t[k].lv=p.b+p.c*a[l],t[k].rv=p.b+p.c*a[r],t[k].v=p.b*(r-l+1)+t[k].s*p.c;
t[k].tg.a&=p.a;t[k].tg.b=t[k].tg.b*p.a+p.b;t[k].tg.c=t[k].tg.c*p.a+p.c;
}
void cha(int k,int l,int r){
if(t[k].rv<=z)return;if(t[k].lv>z){ans+=t[k].v-z*(r-l+1);add(k,l,r,P{0,z,0});return;}
int mid=l+r>>1;add(k<<1,l,mid,t[k].tg);add(k<<1|1,mid+1,r,t[k].tg);
t[k].tg.a=1;t[k].tg.b=t[k].tg.c=0;cha(k<<1,l,mid);cha(k<<1|1,mid+1,r);
t[k].lv=t[k<<1].lv;t[k].rv=t[k<<1|1].rv;t[k].v=t[k<<1].v+t[k<<1|1].v;
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(sort(a+1,a+n+1),bt(1,1,n);m--;la=x)scanf("%lld%lld",&x,&z),add(1,1,n,P{1,0,x-la}),ans=0,cha(1,1,n),printf("%lld\n",ans);
}
【PA2015】Fibonacci 这题太神了，只能去%题解，斐波那契数列%10^m的循环节是6*10^m，这是人想得出来的吗。。然后暴力按位判断可以得到答案、、
#include<cstdio>
#include<cstring>
typedef unsigned long long LL;
char s[19];LL b[19],p[19],ans;int n,i;
LL mul(LL a,LL b,LL p){LL t=0;for(;b;b>>=1,a=(a+a)%p)if(b&1)t=(t+a)%p;return t;}
void cal(LL n,LL&x,LL&y,LL P){
if(!n){x=0,y=1;return;}
if(n==1){x=y=1;return;}
if(n&1){cal(n-1,y,x,P);y=(y+x)%P;return;}
LL a,b;cal(n>>1,a,b,P);
x=(mul(a,b,P)+mul(a,b<a?b-a+P:b-a,P))%P;
y=(mul(a,a,P)+mul(b,b,P))%P;
}
LL fib(LL n,LL P){LL x,y;cal(n,x,y,P);return x;}
void dfs(int n,LL y,LL z){
if(ans||fib(y,p[n])!=b[n])return;
if(n==1){ans=y+6000000000000000000;return;}
for(int i=0;i<10;i++)dfs(n-1,(z*i+y)%(z*10),z*10);
}
int main(){
scanf("%s",s+1);n=strlen(s+1);
for(p[i=n]=1;i;i--,p[i]=p[i+1])b[i]=p[i]*(s[i]-'0')+b[i+1],p[i]*=10;
for(i=0;i<60;i++)dfs(n,i,60);
if(ans)printf("%llu",ans);else puts("NIE");
}
【PA2015】Mistrzostwa 我直接写了一个删除任意值的堆，写得相当长。。但还是卡过了、、后来发现可以线性做，但懒得写了。。
#include<cstdio>
#include<algorithm>
#define N 200200
using namespace std;
int n,m,i,k,x,y,rt,tot,now,ans,u,fa[N],f[N],du[N],c[N][2],fir[N],ne[N<<1],la[N<<1];bool v[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[x]++;}
int gf(int x){return f[x]==x?x:f[x]=gf(f[x]);}
int merge(int x,int y){
if(!x||!y)return x+y;
if(du[x]>du[y])swap(x,y);
c[x][1]=merge(c[x][1],y);
fa[c[x][1]]=x;
swap(c[x][0],c[x][1]);
return x;
}
int main(){
for(scanf("%d%d%d",&n,&m,&k);m--;)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(i=1;i<=n;i++)rt=merge(rt,i),f[i]=i;
for(;du[rt]<k&&rt;)for(i=fir[x=rt],v[x]=1,rt=merge(c[rt][0],c[rt][1]);i;i=ne[i])if(!v[la[i]]){
c[fa[y=la[i]]][c[fa[y]][1]==y]=0;fa[y]=0;
fa[c[y][0]]=0;fa[c[y][1]]=0;
if(y==rt)rt=merge(c[y][0],c[y][1]);else rt=merge(rt,merge(c[y][0],c[y][1]));
c[y][0]=c[y][1]=0;du[y]--;rt=merge(rt,y);
}
for(x=1;x<=n;x++)if(du[x]>=k)for(i=fir[x];i;i=ne[i])if(du[la[i]]>=k)f[gf(x)]=gf(la[i]);
for(x=1;x<=n;x++)if(du[x]>=k&&!v[x]){
for(now=0,i=1;i<=n;i++)if(gf(i)==gf(x)&&du[i]>=k)now++,v[i]=1;
if(now>ans)ans=now,u=x;
}
if(!ans)return puts("NIE"),0;
for(printf("%d\n",ans),i=1;i<=n;i++)if(gf(i)==gf(u)&&du[i]>=k)printf("%d ",i);
}
【PA2015】Rozstaw szyn 从叶子开始BFS，按深度建一颗新树。在新树上DP，通过l~r表示当前点的最优取值范围来进行转移。时间复杂度$O(nlgn)$。
#include<bits/stdc++.h>
#define N 1000500
using namespace std;typedef long long LL;LL ans,S,p,w;bool V[N],D[N];
int i,x,y,n,m,h,t,k,o,tot,q[N],fir[N],la[N*2],ne[N*2],d[N],l[N],v[N],r[N],Fir[N];
void ins(int x,int y){d[x]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void Ins(int x,int y){V[y]=1;la[++tot]=y;ne[tot]=Fir[x];Fir[x]=tot;}
void dfs(int x){
if(x<=m&&x)return;int i,y;
for(i=Fir[x];i;i=ne[i])dfs(la[i]);
for(o=S=t=0,p=1e19,i=Fir[x];i;i=ne[i])v[++t]=l[y=la[i]],o--,v[++t]=r[y],S+=l[y];
for(sort(v+1,v+t+1),i=1;i<=t;i++){
o++;S-=v[i];w=S+1ll*v[i]*o;
if(w<p)l[x]=v[i],p=w;if(w==p)r[x]=v[i];
}ans+=p;
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(h=i=1;i<=m;i++)D[q[++t]=i]=1,scanf("%d",&x),l[i]=r[i]=x;
if(n==m){
for(x=1;x<=n;x++)for(i=fir[x];i;i=ne[i])ans+=abs(l[x]-l[la[i]]);
return printf("%lld",ans/2),0;
}
for(;h<=t;h=y+1){
for(i=h;i<=t;i++)for(x=fir[q[i]];x;x=ne[x])if(!D[la[x]])Ins(la[x],q[i]);
for(i=h,y=t;i<=y;i++)for(x=fir[q[i]];x;x=ne[x])if(!D[la[x]])if(--d[la[x]]<2)D[q[++t]=la[x]]=1;
}
for(i=1;i<=n;i++)if(!V[i])Ins(0,i);
dfs(0);printf("%lld",ans);
}
2022年9月14日 16:34
Candidates can download 10th class biology subject sample papers pdf and key topics with assignments in all exam formats of the board like SA-1, SA-2, FA-1, FA-2, FA-3 and FA-4.Telugu Medium, AP 10th Biology Model PaperEnglish Medium and Urdu Medium Students of the State who studying Class 10th Grade can download the AP SSC Biology Model Papers 2023 for theory, objective and bit questions to Self Practice.Telugu Medium, English Medium and Urdu Medium Students of the State who studying Class 10th Grade can download the AP SSC Biology Model Papers 2023 for theory, objective and bit questions to Self Practice.