POI2002
T1 火车线路 超级大水题，直接线段树就行了
#include<cstdio>
#include<algorithm>
using namespace std;
int n,s,m,x,y,z,mv[255555],cv[255555];
int ask(int k,int l,int r,int x,int y){
if(x<=l&&r<=y)return mv[k];
int mid=l+r>>1,now=0;
if(x<=mid)now=max(now,ask(k<<1,l,mid,x,y));
if(y>mid)now=max(now,ask(k<<1|1,mid+1,r,x,y));
return now+cv[k];
}
void add(int k,int l,int r,int x,int y,int z){
if(x<=l&&r<=y){mv[k]+=z,cv[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])+cv[k];
}
int main(){
for(scanf("%d%d%d",&n,&s,&m);m--;){
scanf("%d%d%d",&x,&y,&z);y--;
if(ask(1,1,n,x,y)+z<=s)add(1,1,n,x,y,z),puts("T");else puts("N");
}
}
T2 商务旅行 傻逼题，直接把一道树剖拉下来了，其实直接模拟说不定都能过。。
#include<cstdio>
#include<algorithm>
#define N 33333
using namespace std;
int n,m,i,x,y,tot,sz,ans,a[N],fir[N],zs[N],fa[N],h[N],pos[N],bl[N],la[N<<1],ne[N<<1];bool v[N];
void insert(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
zs[x]=1;v[x]=1;
for(int i=fir[x];i;i=ne[i])if(!v[y=la[i]]){
fa[y]=x;h[y]=h[x]+1;
dfs(y);zs[x]+=zs[y];
}
}
void dfs2(int x,int f){
int now=0;pos[x]=++sz;bl[x]=f;
for(int i=fir[x];i;i=ne[i])if(zs[y=la[i]]>zs[now]&&h[x]<h[y])now=y;
if(!now)return;dfs2(now,f);
for(int i=fir[x];i;i=ne[i])if(h[x]<h[y=la[i]]&&now!=y)dfs2(y,y);
}
void queryin(int x,int y){
for(;bl[x]!=bl[y];x=fa[bl[x]]){
if(h[bl[x]]<h[bl[y]])swap(x,y);
ans+=pos[x]-pos[bl[x]]+1;
}
if(pos[x]>pos[y])swap(x,y);ans+=pos[y]-pos[x];
}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),insert(x,y),insert(y,x);
dfs(1);dfs2(1,1);
for(scanf("%d",&m),a[0]=i=1;i<=m;i++)scanf("%d",&a[i]),queryin(a[i-1],a[i]);
printf("%d",ans);
}
T3 超级马 如果能到达(1,0)(-1,0)(0,1)(0,-1)四个点就可以到达全图了，只要宽搜一遍这四个点可以到达就可以了，宽搜的范围可以定在[-100,100]，这样正好可以卡过去。。
#include<cstdio>
#include<cstring>
int T,n,i,x,y,h,t,a[110],b[110];bool v[222][222];
struct P{int x,y;}q[44444];
int main(){
for(scanf("%d",&T);T--;){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
for(memset(v,0,sizeof(v)),h=0,q[t=1]=P{100,100},v[100][100]=1;h^t;){
x=q[++h].x;y=q[h].y;
for(i=1;i<=n;i++){
if(x+a[i]<=200&&x+a[i]>=0&&y+b[i]<=200&&y+b[i]>=0)if(!v[x+a[i]][y+b[i]]){
v[x+a[i]][y+b[i]]=1;
q[++t]=P{x+a[i],y+b[i]};
}
}
}
puts(v[100][99]&&v[100][101]&&v[99][100]&&v[101][100]?"TAK":"NIE");
}
}
T4 敌对球迷 直接剪下来单调扫一遍就行了
#include<cstdio>
#include<algorithm>
#define N 50500
int i,j,n,a[N];long long sum[N],ans;
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
for(i=n+1;i<=n*2;i++)a[i]=a[i-n],sum[i]=sum[i-1]+a[i];
for(i=1;i<=2*n;i++){
for(;(sum[i]-sum[j])*2>sum[n];j++);
ans=std::max(ans,sum[i]-sum[j]);
}
printf("%lld",ans);
}
T5 绝缘体 又一道傻逼题，排序后扫一遍就行啦
#include<cstdio>
#include<algorithm>
int n,i,ans,a[100100];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),ans+=a[i];
for(std::sort(a+1,a+n+1),i=1;i<=n>>1;i++)ans+=a[n-i+1]-a[i];
printf("%d",ans);
}
T6 最大的园地 悬线法裸题，但是用单调栈更方便，很明显最优的答案在高度和宽度上一定是单调的，对于每个点先算出它往上最多能到哪里，然后弹栈，再把该点压进栈，每次弹出时统计答案，就能得到最优答案
#include<cstdio>
#include<algorithm>
#define N 2222
using namespace std;
int n,i,j,x,t,ans,q[N],h[N],st[N];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&x);if(x)h[j]=0;else h[j]++;q[t+1]=0;
for(;st[t]>h[j]&&t;t--)ans=max(ans,(j-q[t])*st[t]);
if(st[t]!=h[j]){st[++t]=h[j];if(!q[t])q[t]=j;}
}
for(;t;t--)ans=max(ans,(n-q[t]+1)*st[t]);
}
printf("%d",ans);
}
T7 出圈游戏 一道裸的中国剩余定理，可是直接套模板似乎不太资磁。。
要把所有形如$x^p$的项取出来进行中国剩余定理，然后对剩下的项进行判定，这样才能得到正确的答案
#include<cstdio>
using namespace std;
int n,i,j,u,pp,now,la,a[22],sum,d,x,y,ans;bool v[22];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
void exgcd(int a,int b,int&x,int&y){
if(!b){x=1;y=0;return;}
exgcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
}
int main(){
for(scanf("%d",&n),i=sum=1;i<=n;i++)scanf("%d",&a[i]),sum/=gcd(sum,i),sum*=i;
for(la=i=1;i<=n;i++){
for(j=1;j<=n;j++)if(a[j]==i)u=j;
for(now=1,j=la;j!=u;j=j%n+1)if(!v[j])now++;
d=sum/(n-i+1);exgcd(d,n-i+1,x,y);
if(now==n-i+1)now=0;
ans=(ans+d*x*now)%sum;
v[u]=1;la=u;
}
while(ans<=0)ans+=sum;
printf("%d",ans);
}
#include<cstdio>
using namespace std;
int n,i,j,u,pp,now,la,a[22],b[22],sum,d,x,y,ans,p[]={0,2,3,5,7,11,13,17,19};bool v[22];
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
void exgcd(int a,int b,int&x,int&y){
if(!b){x=1;y=0;return;}
exgcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
}
int main(){
for(scanf("%d",&n),i=sum=1;i<=n;i++)scanf("%d",&a[i]),sum/=gcd(sum,i),sum*=i;
for(la=i=1;i<=n;i++){
for(j=1;j<=n;j++)if(a[j]==i)u=j;
for(now=1,j=la;j!=u;j=j%n+1)if(!v[j])now++;
if(now==n-i+1)now=0;
b[n-i+1]=now;v[u]=1;la=u;
}
for(i=1;p[i]<=n;i++){
for(j=p[i];j*p[i]<=n;j*=p[i]);
d=sum/j;exgcd(d,j,x,y);
ans=(ans+d*x*b[j])%sum;
}
while(ans<=0)ans+=sum;
for(i=1;i<=n;i++)if(ans%i!=b[i])return puts("NIE"),0;
printf("%d",ans);
}
T8 滑雪胜地 这题是求小于等于一个长度的最长路，由于这个长度比较小，可以考虑dp，用$f[i][j]$表示用了$i$的费用是否能走到$j$，然后直接扫一遍就可以得到正确答案了
#include<cstdio>
#define N 1100
#define M 5100
int n,u,m,x,y,s,h,t,tot,i,j,q[N],fir[N],la[M],ne[M],a[N],b[N],c[N];bool v[N<<1][N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d%d",&n,&u,&m);m--;)scanf("%d%d",&x,&y),ins(x,y);
for(scanf("%d",&m),i=1;i<=m;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(scanf("%d%d",&x,&s),v[0][q[t=1]=x]=1;h^t;)
for(i=fir[x=q[++h]];i;i=ne[i])if(!v[0][la[i]])v[0][q[++t]=la[i]]=1;
for(j=1;j<=s;j++){
for(i=1;i<=m;i++)if(j>=c[i])v[j][b[i]]|=v[j-c[i]][a[i]];
for(h=t=0,i=1;i<=n;i++)if(v[j][i])q[++t]=i;
for(;h^t;)for(i=fir[x=q[++h]];i;i=ne[i])if(!v[j][la[i]])v[j][q[++t]=la[i]]=1;
}
for(i=s;i;i--)for(j=1;j<=u;j++)if(v[i][j])return printf("%d",s-i),0;
}
T9 协议 统计方案后高精度取对数，但这东西似乎挺难的，可以取出最高位然后把剩下答案的贡献暴力算，但这样精度有点问题，会WA一个点，把参数调小一点就能A了。。
#include<cstdio>
#include<cmath>
#define M 32767
int k,n,m,l,i,w,sum,ans[30],f[110][30];double v,q;
void mul(int *a,int b,int *c){
for(int i=1;i<=w;i++)c[i]+=a[i]*b,c[i+1]+=c[i]>>15,c[i]&=M;
if(c[w+1])w++;
}
void add(int *a,int *b){
for(int i=1;i<=w;i++)b[i]+=a[i],b[i+1]+=b[i]>>15,b[i]&=M;
if(b[w+1])w++;
}
void del(int *a,int *b){
for(int i=1;i<=w;i++){
b[i]-=a[i];
if(b[i]<0)b[i]+=M,b[i+1]--;
}
for(;!b[w];w--);
}
int main(){
scanf("%d%d%d%d",&k,&n,&m,&l);l--;ans[w=1]=f[1][1]=k;
for(i=2;i<=m;i++){
mul(ans,k-1,f[i]);add(f[i],ans);
if(i>l)del(f[i-l],ans);
}
for(i=14;i>=0;i--)if(ans[w]>>i)break;
for(sum=i+w*15-15,v=1;i>=0;i--,v/=2)if(ans[w]>>i&1)q+=v;
for(;--w;)for(i=14;i>=0&&v>0.05;i--,v/=2)if(ans[w-1]>>i&1)q+=v;
printf("%d\n",sum*(n/m)+(int)(log2(q)*(n/m)));
}
T10 滑雪者 求最小可行流，先建出图来，统计出最多要走多少次，再减去最大流的值即可求出最小可行流
#include<cstdio>
#define N 5200
#define M 1001000
#define inf 1e9
int n,m,x,i,u,s,t,now,tot,ans,tmp,du[N],fir[N],cur[N],nb[N],d[N],pre[N],va[M],la[M],ne[M];
void ins(int x,int y,int z){
la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;
la[++tot]=x;va[tot]=0;ne[tot]=fir[y];fir[y]=tot;
}
void ISAP(){
for(i=1;i<=t;i++)cur[i]=fir[i];
u=s;nb[0]=t;
while(d[s]<t){
if(u==t){
now=inf;
for(i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];
for(i=s;i!=t;i=la[cur[i]])va[cur[i]]-=now,va[cur[i]^1]+=now;
ans-=now;
}
for(i=cur[u];i;i=ne[i])if(va[i]&&d[la[i]]+1==d[u])break;
if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
if(0==--nb[d[u]])break;
for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])if(d[la[i]]<tmp&&va[i])tmp=d[la[i]];
++nb[d[u]=tmp+1];
if(u!=s)u=pre[u];
}
}
}
int main(){
for(scanf("%d",&n),tot=1,s=n+1,t=s+1,i=1;i<n;i++)
for(scanf("%d",&m),du[i]+=m;m--;)scanf("%d",&x),ins(i,x,inf),du[x]--;
for(i=1;i<n;i++)if(du[i]>0)ins(i,t,du[i]),ans+=du[i];else ins(s,i,-du[i]);
ISAP();printf("%d",ans);
}
T11 B-Smooth数 直接枚举素数后暴力，求出可行的$[l,r]$区间，每次统计这个区间内的素数个数就可以得到正确答案了，速度还是很快的
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,m,k,i,j,sz,ans,a[N],b[N],p[N];bool v[N];
void dfs(int x,int y){
int l=(n-1)/x+1,r=(n+m)/x;
for(int i=y;i<=sz&&p[i]<=r/p[i];i++)dfs(x*p[i],i);
l=max(l,p[y]);l=min(l,k+1);r=min(r,k+1);
if(b[l]<a[r])ans+=a[r]-b[l];
}
int main(){
for(scanf("%d%d%d",&n,&m,&k),p[0]=1e9,b[1]=1,i=2;i<=k;i++){
b[i]=sz;if(!v[i])p[++sz]=i;a[i]=sz;
for(j=1;j<=sz&&p[j]*i<=k&&i%p[j-1];j++)v[i*p[j]]=1;
}a[k+1]=b[k+1]=sz;
dfs(1,1);printf("%d",ans+(n==1));
}
T12 括号 黈力出的题就是大，考的时候根本不会，直接写了个60的暴力
首先要建出一个括号树，向右走奇数次就是-，偶数次就是+，考虑dp，用$dp[i][j]$表示前$i$个已经归位，最右边的一条链长度为$j$时的方案数
则当(j&1)==(s=='-')时$dp[i][j]=\sum dp[i-1][(j-1)~(i-1)]$，表示在$j$这个位置插入该点的方案数，推导去看题解吧~
#include<cstdio>
#define M 1000000000
int n,i,j,e,v,u,ans,f[2][5010];char s[9];
int main(){
scanf("%d%s",&n,s);n--;if(s[0]=='-')f[0][0]=1;
for(e=i=1;i<n;i++,e^=1){
for(scanf("%s",s),u=s[0]=='+',v=0,j=i;j>=0;j--){
if(j)v=(v+f[!e][j-1])%M;
if(u^(j&1))f[e][j]=0;else f[e][j]=v;
}
}
for(i=n;i>=0;i--)ans=(ans+f[!e][i])%M;
printf("%d",ans);
}
评论 (0)
