POI2014
T1 Salad Bar 写了个$nlg^2n$的树状数组单点修改区间最值被鏼死了。。改成$nlgn$的线段树才卡过。。大概就是单调栈维护出每个点向左、向右最多扩展的点，然后只要一个点的$l[j]\leq i$且$i\leq l[j]\leq r[i]$则该点合法，每次把符合条件的点加入统计出$i-r[i]$中出现的最大值即可更新答案
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1001000
#define inf 1e9
using namespace std;
int n,i,t,ans,tot,x,w[N],c[N],a[N],q[N],r[N],l[N],la[N],ne[N],fir[N];char s[N];
void add(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void ins(int x,int v){
w[x]=v;
for(;x<=n;x+=x&-x){
c[x]=v;
for(int j=1;j<x&-x;j<<=1)c[x]=max(c[x],c[x-j]);
}
}
int query(int l,int r){
int ans=w[r];
while(1){
ans=max(ans,w[r]);
if(l==r)return ans;
for(r--;r-l>=r&-r;r-=r&-r)ans=max(ans,c[r]);
}
return ans;
}
int main(){
scanf("%d%s",&n,s+2);n++;a[n+1]=-inf;
for(i=2;i<=n;i++)a[i]=a[i-1]+(s[i]=='p'?1:-1);
for(i=1;i<=n+1;q[++t]=i++)for(;t&&a[i]<a[q[t]];)r[q[t--]]=i-1;
for(a[0]=inf,t=0,i=n;i>=0;q[++t]=i--)for(;t&&a[i]>a[q[t]];)l[q[t--]]=i+1;
for(i=1;i<=n;i++)add(l[i],i);
for(x=1;x<=n;x++){
for(i=fir[x];i;i=ne[i])ins(la[i],la[i]);
ans=max(ans,query(x,r[x])-x);
}
printf("%d",ans);
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1001000
#define inf 1e9
using namespace std;
int n,i,t,ans,tot,x,a[N],q[N],r[N],l[N],la[N],ne[N],fir[N];char s[N];
struct Tr{int l,r,v;}T[N*4];
void add(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void bt(int k,int l,int r){
T[k].l=l;T[k].r=r;int mid=l+r>>1;
if(l==r)return;
bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
}
void ins(int k,int x){
int l=T[k].l,r=T[k].r,mid=l+r>>1;
if(l==r){T[k].v=l;return;}
if(x<=mid)ins(k<<1,x);else ins(k<<1|1,x);
T[k].v=max(T[k<<1].v,T[k<<1|1].v);
}
int query(int k,int x,int y){
int l=T[k].l,r=T[k].r,mid=l+r>>1;
if(x<=l&&r<=y)return T[k].v;
if(x>mid)return query(k<<1|1,x,y);else
if(y<=mid)return query(k<<1,x,y);else
return max(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
}
int main(){
scanf("%d%s",&n,s+2);n++;a[n+1]=-inf;
for(i=2;i<=n;i++)a[i]=a[i-1]+(s[i]=='p'?1:-1);
for(i=1;i<=n+1;q[++t]=i++)for(;t&&a[i]<a[q[t]];)r[q[t--]]=i-1;
for(a[0]=inf,t=0,i=n;i>=0;q[++t]=i--)for(;t&&a[i]>a[q[t]];)l[q[t--]]=i+1;
for(i=1;i<=n;i++)add(l[i],i);bt(1,1,n);
for(x=1;x<=n;x++){
for(i=fir[x];i;i=ne[i])ins(1,la[i]);
ans=max(ans,query(1,x,r[x])-x);
}
printf("%d",ans);
}
T2 Hotel 首先很好想到枚举中心店，然后找到离它距离相等的三个点即为答案，我一开始暴力地写了一遍，发现会出现重复统计的情况，因为三个点可能来自同一个子树中，所以要对所有出边各做一次DFS再统计答案，就能得到正确的结果
#include<cstdio>
#include<cstring>
#define N 5010
typedef long long LL;LL sum,cnt[N],ans[N];
int n,i,j,x,y,tot,dis[N],fir[N],la[N<<1],ne[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int dp){
++dis[dp];
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,dp+1);
}
int main(){
scanf("%d",&n);
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(x=1;x<=n;x++){
memset(cnt,0,sizeof(cnt));memset(ans,0,sizeof(ans));
for(i=fir[x];i;i=ne[i]){
memset(dis,0,sizeof(dis));
dfs(la[i],x,1);
for(j=1;j<=n;j++){
sum+=ans[j]*dis[j];
ans[j]+=cnt[j]*dis[j];
cnt[j]+=dis[j];
}
}
}
printf("%lld",sum);
}
T3 Bricks 写了个贪心爆了好几发，终于A啦
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,m,i,s,t,x,la,rt,top,ans[N],val[N],son[N][2];
int merge(int x,int y){
if(!x||!y)return x+y;
if(val[x]<val[y]||val[x]==val[y]&&y==t)swap(x,y);
son[x][1]=merge(son[x][1],y);
swap(son[x][0],son[x][1]);
return x;
}
int main(){
scanf("%d%d%d",&n,&s,&t);val[s]--;val[t]--;
for(i=1;i<=n;i++){
scanf("%d",&x);
m+=x,val[i]+=x;
if(val[i]<0)return puts("0"),0;
rt=merge(rt,i);
}
if(m==1){
if(s==t&&t==1)return printf("%d",s),0;
return puts("0"),0;
}
ans[++top]=s;
for(la=s,i=2;i<m;i++){
if(rt==la){
x=rt;rt=merge(son[rt][0],son[rt][1]);
if(--val[la=rt]<0)return puts("0"),0;
rt=merge(son[rt][0],son[rt][1]);
son[x][0]=son[x][1]=son[la][0]=son[la][1]=0;
rt=merge(rt,x);
}else{
if(--val[la=rt]<0)return puts("0"),0;
rt=merge(son[rt][0],son[rt][1]);
son[la][0]=son[la][1]=0;
}
rt=merge(rt,la);ans[++top]=la;
}
ans[++top]=t;
for(i=1;i<=top;i++)printf("%d ",ans[i]);
}
T4 Couriers 写了个莫队T了。。只好写个主席树，好卡空间啊、、
#include<cstdio>
#include<algorithm>
#define N 501000
using namespace std;
int n,m,i,l,r,a[N],pos[N],ans[N],BS=100;
struct EG{int l,r,z;}eg[N];
struct T{int l,r,v,fm;}t[N*4];
bool cmp(EG a,EG b){if(pos[a.l]==pos[b.l])return a.r<b.r;return a.l<b.l;}
void bt(int k,int l,int r){
t[k].l=l;t[k].r=r;int mid=l+r>>1;
if(l==r){t[k].fm=l;return;}
bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
}
void ins(int k,int x,int z){
int l=t[k].l,r=t[k].r,mid=l+r>>1;
if(l==r){t[k].v+=z;return;}
if(x<=mid)ins(k<<1,x,z);else ins(k<<1|1,x,z);
if(t[k<<1].v>t[k<<1|1].v)t[k].v=t[k<<1].v,t[k].fm=t[k<<1].fm;
else t[k].v=t[k<<1|1].v,t[k].fm=t[k<<1|1].fm;
}
int main(){
scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]),pos[i]=(i-1)/BS+1;
for(i=1;i<=m;i++)scanf("%d%d",&eg[i].l,&eg[i].r),eg[i].z=i;
sort(eg+1,eg+m+1,cmp);bt(1,1,n);
for(i=1,l=1,r=0;i<=m;i++){
for(;r<eg[i].r;r++)ins(1,a[r+1],1);
for(;r>eg[i].r;r--)ins(1,a[r],-1);
for(;l<eg[i].l;l++)ins(1,a[l],-1);
for(;l>eg[i].l;l--)ins(1,a[l-1],1);
if(t[1].v>(eg[i].r-eg[i].l+1)/2)ans[eg[i].z]=t[1].fm;
}
for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}
#include<cstdio>
#define N 9999999
int n,m,x,y,sz,i,root[500010],ls[N],rs[N],sum[N];
void ins(int l,int r,int x,int &y,int v){
sum[y=++sz]=sum[x]+1;
if(l==r)return;int mid=(l+r)>>1;ls[y]=ls[x];rs[y]=rs[x];
if(v<=mid)ins(l,mid,ls[x],ls[y],v);else ins(mid+1,r,rs[x],rs[y],v);
}
int query(int l,int r,int x,int y,int v){
if(l==r)return l;int mid=(l+r)>>1;
if(sum[ls[y]]-sum[ls[x]]>v)return query(l,mid,ls[x],ls[y],v);
else if(sum[rs[y]]-sum[rs[x]]>v)return query(mid+1,r,rs[x],rs[y],v);
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&x),ins(1,n,root[i-1],root[i],x);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
printf("%d\n",query(1,n,root[x-1],root[y],(y-x+1)/2));
}
}
T6 Card 写了个分块，但一开始T了，调了会参还是T，然后加了个读入优化卡过哈哈，代码长度再次碾压
#include<cstdio>
#include<algorithm>
#define N 200020
using namespace std;
int n,i,x,y,bx,by,n1,n2,now,m,BN,BS=200,down[N],up[N],a[N],b[N];char ch;
void read(int &x){
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void get(int x){
n1=a[(x-1)*BS+1];n2=b[(x-1)*BS+1];
for(i=(x-1)*BS+2;i<=x*BS&&i<=n;i++){
if(n1>b[i])n1=1e9;else if(n1>a[i])n1=b[i];else n1=a[i];
if(n2>b[i])n2=1e9;else if(n2>a[i])n2=b[i];else n2=a[i];
}
down[x]=n1;up[x]=n2;
}
int main(){
read(n);BN=(n-1)/BS+1;
for(i=1;i<=n;i++){
read(a[i]);read(b[i]);
if(a[i]>b[i])swap(a[i],b[i]);
}
for(x=1;x<=BN;x++)get(x);scanf("%d",&m);
while(m--){
read(x);read(y);bx=(x-1)/BS+1;by=(y-1)/BS+1;
swap(a[x],a[y]);swap(b[x],b[y]);get(bx);get(by);
for(now=down[1],i=2;i<=BN;i++)if(now>up[i])now=1e9;else if(now>down[i])now=up[i];else now=down[i];
if(now==1e9)puts("NIE");else puts("TAK");
}
}
T7 Around the world 处理出每个点往后的尽量后的点，然后从一个点开始走，每次走尽量后的点，走n步后一定会走到以后优的点。于是从这个优的点出发再走一圈就可以得到答案，时间复杂度$O(ns)$。
#include<bits/stdc++.h>
int n,s,d,i,j,z,p,w,o,ff,a[1001000],ne[1001000];
int main(){
for(scanf("%d%d",&n,&s),i=0;i<n;i++)scanf("%d",&a[i]);
for(;s--;){
for(scanf("%d",&d),i=j=ff=z=0;i<n;i++){
for(;z+a[j%n]<=d;j++)z+=a[j%n];
if(!(ne[i]=j-i))ff=1;z-=a[i];
}
if(ff){puts("NIE");continue;}
for(i=w=p=0;i<n;i++)w=(w+ne[w])%n;
for(o=w;o<w+n;p++)o+=ne[o%n];
printf("%d\n",p);
}
}
T8 Criminals 题目大意：给你一个颜色序列，有两个人会分别从左往右和从右往左走，并在途中任意取走几个格子里面的颜色，直到两个人相遇。已知两个人所取走的颜色序列，并且保证这两个颜色序列的最后一个元素都是同一种颜色，代表两个人相遇的点。还知道两个人出发点的颜色都是相同的，并且他们不会取出发点的颜色（即在两个人的序列中都不会出现）。同时还发现不存在任意一个颜色在这两个序列中出现两次。求出可能的相遇点有多少个，并输出。$N\leq1000000$。
由于每个颜色在序列中只会出现一次 ，于是可以对于每个i找到左边最大的$j$，使得从$j$开始到$i-1$有第一个子序列；找到右边最小的$j$，使得$j$到$i-1$有第二个子序列。通过单调性记录$f[i]$表示长度为$i$的子序列的答案，做到$O(n)$的复杂度。然后枚举相遇点的位置，如果$L[i]$左边、$R[i]$右边存在相同颜色就可以，这也可以单调扫一遍做到$O(n)$复杂度。
#include<bits/stdc++.h>
#define N 1001000
int n,k,x,i,j,m,l,o,t,a[N],c[N],h[N],ne[N],f[N],L[N],R[N],q[N],c1[N],c2[N];
int main(){
for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d",&c[i]);
for(scanf("%d%d",&m,&l),i=1;i<=m;i++)scanf("%d",&a[i]);
for(i=m+l-1;i>=m;i--)scanf("%d",&a[i]);
for(i=1;i<=n;i++)ne[i]=h[c[i]],h[c[i]]=i,f[i]=n+1;
for(i=n;i;i--)if(R[i]=l>1?f[m+l-1]:i,c[i]==a[m+1])for(f[m+1]=i,j=m+2;j<m+l;j++)for(;(x=f[j]<=n?ne[f[j]]:h[a[j]])>f[j-1];f[j]=x);
for(i=1;i<=n;i++)h[i]=n+1,f[i]=0;
for(i=n;i;i--)ne[i]=h[c[i]],h[c[i]]=i;
for(i=1;i<=n;i++)if(L[i]=m>1?f[1]:i,c[i]==a[m-1])for(f[m-1]=i,j=m-2;j;j--)for(;(x=f[j]?ne[f[j]]:h[a[j]])<f[j+1];f[j]=x);
for(i=1;i<=n;i++)if(L[i]>1&&R[i]<n){
for(j=n;j>R[i];j--)c2[c[j]]++;
for(j=1;j<L[i];j++)if((!c1[c[j]]++)&&c2[c[j]])o++;
if(o&&c[i]==a[m])q[++t]=i;break;
}
for(i++;i<=n;i++){
if(R[i]>=n)break;
for(j=R[i-1];j<R[i];j++)if((!--c2[c[j]])&&c1[c[j]])o--;
for(j=L[i-1];j<L[i];j++)if((!c1[c[j]]++)&&c2[c[j]])o++;
if(o&&c[i]==a[m])q[++t]=i;
}
for(printf("%d\n",t),i=1;i<=t;i++)printf("%d ",q[i]);
}
T9 FarmCraft 考虑树形DP，对于一个子树x维护两个值d[]和f[]分别表示走完子树的距离和走完这个子树的最少时间，关键是怎么计算f[]
如果第$i$个走的子树是$y$,它的贡献是$\sum_{j<i} (d[j]+2)+f[x]+1$，目标就是最小化$max(\sum_{j<i}(d[j]+2)+f[x]+1)$
对于相邻两个子树$i,j$，如果$i$比$j$优$max(f[i],d[i]+2+f[j])<max(f[j],d[j]+2+f[i])$
$f[x]=max(c[x],$每个子树的贡献)，DFS一遍最后统计答案即可
#include<cstdio>
#include<algorithm>
#define N 500100
using namespace std;
int n,i,x,y,tot,q[N],c[N],d[N],f[N],fir[N],la[N<<1],ne[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
bool cmp(int x,int y){return max(f[x],d[x]+2+f[y])<max(f[y],d[y]+2+f[x]);}
void dfs(int x,int fa){
int i,t=0,sum=0;
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x),d[x]+=d[la[i]]+2;
for(i=fir[x];i;i=ne[i])if(la[i]!=fa)q[++t]=la[i];
sort(q+1,q+t+1,cmp);
for(i=1;i<=t;sum+=d[q[i++]]+2)f[x]=max(f[x],sum+f[q[i]]+1);
}
int main(){
scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&c[i]),f[i]=c[i];
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
dfs(1,0);printf("%d",max(c[1]+d[1],f[1]));
}
T10 Freight T[i]=max(T[i],T[i-1]+1)，f[i]=min(max(T[i],f[j]+i-j-1)+s*2+i-j-1)=min(max(-j+T[i],f[j]-2*j+i-1))+s*2+i-1=min(min(-j)+T[i](f[j]-j<=T[i]-i+1),min(f[j]-2*j)+i-1(f[j]-j>=T[i]-i+1))+s*2+i-1，用BIT来维护两个最小值就可以了。
#include<bits/stdc++.h>
#define N 1001000
using namespace std;typedef long long LL;int n,i,x,W;LL y,z,S,c[N],d[N],f[N],T[N],v[N];
void A1(int x,LL z){for(;x;x-=x&-x)c[x]=min(c[x],z);}void A2(int x,LL z){for(;x<=W;x+=x&-x)d[x]=min(d[x],z);}
LL Q1(int x){LL V=1e18;for(;x<=W;x+=x&-x)V=min(V,c[x]);return V;}LL Q2(int x){LL V=1e18;for(;x;x-=x&-x)V=min(V,d[x]);return V;}
int main(){
for(scanf("%d%lld",&n,&S),T[0]=-1e9,i=1;i<=n;i++)scanf("%lld",&T[i]),T[i]=max(T[i],T[i-1]+1),v[i]=T[i]-i+1;
for(sort(v+1,v+n+2),W=unique(v+1,v+n+2)-v-1,i=1;i<=W;i++)c[i]=d[i]=1e18;
for(A1(1,0),A2(1,0),i=1;i<=n;i++){
x=lower_bound(v+1,v+W+1,T[i]-i+1)-v;y=Q1(x);z=Q2(x);
f[i]=min(y+i,z+T[i])+S*2+i-1;A1(upper_bound(v+1,v+W+1,f[i]-i)-v-1,f[i]-2*i);A2(lower_bound(v+1,v+W+1,f[i]-i)-v,-i);
}printf("%lld",f[n]);
}
T11 Little Bird 一开始想$nlgn$的DP，但发现最短的500B不到，所以觉得不太可能就改成单调队列，维护一个dp值下降的单调队列，dp值相同时取高度高的，这样就可以保证正确性啦
#include<cstdio>
#define N 1001000
int n,i,Q,x,h,t,f[N],a[N],q[N];
int main(){
scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(scanf("%d",&Q);Q--;){
scanf("%d",&x);q[h=t=1]=1;
for(i=2;i<=n;i++){
for(;h<=t&&i-q[h]>x;h++);
f[i]=f[q[h]]+(a[i]>=a[q[h]]);
for(;h<=t&&(f[i]<f[q[t]]||f[i]==f[q[t]]&&a[i]>=a[q[t]]);t--);
q[++t]=i;
}
printf("%d\n",f[n]);
}
}
T12 Rally 这题蛮神的，加一个虚拟源点S和一个虚拟汇点T，对所有点进行一遍拓扑DP求出从S到该点的最大距离f[]和该点到T的最大距离g[]，那么一条边$x\to y$的权值是$f[x]+g[y]$，这个图的最长链就是所有边边权的最大值
然后拓扑序删点，按照拓扑序依次将该点入边删掉，此时最大值为答案，然后把该点出边加入
我写了个set，顺便还搞懂了multiset的正确姿势，感谢数国队让我代码长度碾压啦
#include<cstdio>
#include<algorithm>
#include<set>
#define N 501000
using namespace std;
multiset<int>st;
int n,m,x,y,h,t,i,j,tot,u,ans,q[N],du[N],fir[N],fir2[N],f[N],g[N],ne[N<<2],la[N<<2];
void ins(int x,int y){du[y]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void ins2(int x,int y){la[++tot]=y;ne[tot]=fir2[x];fir2[x]=tot;}
int main(){
scanf("%d%d",&n,&m);ans=1e9;
while(m--)scanf("%d%d",&x,&y),ins(x,y),ins2(y,x);
for(i=1;i<=n;i++)if(!du[i])q[++t]=i;
while(h<t)for(i=fir[x=q[++h]];i;i=ne[i])if(!--du[la[i]])q[++t]=la[i];
for(j=1;j<=n;j++)for(f[x=q[j]]=max(f[x],1),i=fir[x];i;i=ne[i])f[la[i]]=max(f[la[i]],f[x]+1);
for(j=n;j;j--)for(g[x=q[j]]=max(g[x],1),i=fir[x];i;i=ne[i])g[x]=max(g[x],g[la[i]]+1);
for(i=1;i<=n;i++)st.insert(g[i]);st.insert(0);
for(j=1;j<=n;j++){
for(i=fir2[x=q[j]];i;i=ne[i])st.erase(st.find(f[la[i]]+g[x]));
st.erase(st.find(g[x]));
if(*--st.end()<ans)ans=*--st.end(),u=x;
for(i=fir[x];i;i=ne[i])st.insert(f[x]+g[la[i]]);
st.insert(f[x]);
}
printf("%d %d",u,ans-1);
}
T14 Solar Panels 只需要找到k使得$gcd[\frac{a}{k}~\frac{b}{k},\frac{c}{k}~\frac{d}{k}]\geq1$即可，大力容斥一下就行啦
#include<cstdio>
#include<algorithm>
using namespace std;
int T,a,b,c,d,i,j,ans;
int main(){
for(scanf("%d",&T);T--;){
scanf("%d%d%d%d",&a,&b,&c,&d);
if(b>d)swap(a,c),swap(b,d);a--;c--;
for(i=1;i<=b;i=j+1){
j=min(b/(b/i),d/(d/i));
if(b/j>a/j&&d/j>c/j)ans=j;
}
printf("%d\n",ans);
}
}
T15 Supercomputer $sum[i]$表示深度大于$i$的点数，$ans=max(i+\frac{sum[i]}{k})$，现在有$Q$个$k$值要一一给出答案，可以利用单调性维护答案就可以在$O(n)$时间内出解
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;typedef long long LL;
int n,Q,i,x,u,tot,h,t,q[N],a[N],sum[N],cnt[N],fir[N],la[N],ne[N],ans[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){
cnt[hi]++;u=max(u,hi);
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,hi+1);
}
int ceil(int a,int b){return a/b+(a%b>0);}
int main(){
scanf("%d%d",&n,&Q);for(i=1;i<=Q;i++)scanf("%d",&a[i]);
for(i=2;i<=n;i++)scanf("%d",&x),ins(x,i);
dfs(1,0,1);for(i=u;i;i--)sum[i]=sum[i+1]+cnt[i+1];
for(h=1,i=u;i;q[++t]=i--)for(;h<t&&(LL)(sum[i]-sum[q[t]])*(q[t-1]-q[t])>=(LL)(sum[q[t-1]]-sum[q[t]])*(i-q[t]);t--);
for(i=1;i<=u;i++)printf("%d\n",sum[i]);
for(i=n;i;i--){
for(;h<t&&(LL)i*(q[h]-q[h+1])<=sum[q[h+1]]-sum[q[h]];h++);
ans[i]=q[h]+ceil(sum[q[h]],i);
}
for(i=1;i<=Q;i++)printf(i<Q?"%d ":"%d",a[i]>n?u:ans[a[i]]);
}
T16 Tourism 题目大意：一张$n$个点$m$条边的无向图，每个点有一个权值$C_i$，选出权值和最小的若干关键点，使得任意点离最近关键点的距离不超过$1$。任意两点间不存在节点数超过$10$的简单路径，$n\leq20000,m\leq25000$。
先DFS出一颗树，树深度不超过$10$，且非树边都是前向边。考虑dp，$f(x)[i][j]$表示在$x$点，深度为$i$，状态为$j$的最小代价。0表示没选，1表示没选且没相邻关键点，2表示没选且有相邻关键点。找出所有该点的祖先，考虑转移：1、不选该点，那么若其祖先有一个点选了，$f[i][j+2*pw[i]]=min(f[i][j+2*pw[i]],f[i-1][j])$；2、选该点，那么其祖先状态为1的都可以改为2，$f[i][newj]=min(f[i][newj],f[i-1][j]+co[x])$。然后继续DFS，递归完后用儿子来更新祖先，$f[i][j]=min(f[i+1][j],f[i+1][j+2*pw[i+1]])$。时间复杂度$O((n+m)*3^{10})$，空间复杂度$O(10*3^{10})$。
#include<bits/stdc++.h>
#define N 20020
using namespace std;bool v[N];
int n,m,i,x,y,A,tot,f[15][N*3],d[N],fir[N],la[N*3],ne[N*3],q[N],a[N],pw[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int G(int x,int y){return x/pw[y]%3;}
void dfs(int x,int z){
v[x]=1;d[x]=z;int i,y,S,t=0,A,B;
if(!z)f[z][0]=a[x],f[z][1]=0,f[z][2]=2e9;else{
for(i=fir[x];i;i=ne[i])if(y=la[i],v[y]&&d[y]<z)q[++t]=d[y];
for(S=0;S<pw[z+1];S++)f[z][S]=2e9;
for(S=0;S<pw[z];S++){
for(A=i=1,B=S;i<=t;i++)if(!G(S,q[i]))A=2;else if(G(S,q[i])==1)B+=pw[q[i]];
f[z][S+A*pw[z]]=min(f[z][S+A*pw[z]],f[z-1][S]);f[z][B]=min(f[z][B],f[z-1][S]+a[x]);
}
}
for(i=fir[x];i;i=ne[i])if(!v[y=la[i]])for(dfs(y,z+1),S=0;S<pw[z+1];S++)f[z][S]=min(f[z+1][S],f[z+1][S+2*pw[z+1]]);
}
int main(){
for(pw[0]=i=1;i<12;i++)pw[i]=pw[i-1]*3;
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
for(;m--;ins(x,y),ins(y,x))scanf("%d%d",&x,&y);
for(i=1;i<=n;i++)if(!v[i])dfs(i,0),A+=min(f[0][0],f[0][2]);
printf("%d",A);
}
T17 Ant colony 从食蚁兽所在的边开始DFS，维护两个值[l,r]表示蚂蚁数量的可行范围，在叶子节点时二分查找所在区间即可
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;typedef long long LL;
int n,m,k,i,x,y,tot,fir[N],du[N],a[N],la[N<<1],ne[N<<1];
LL ans,inf=2e9;void ins(int x,int y){du[x]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,LL l,LL r){
if(du[x]==1)ans+=(LL)k*((upper_bound(a+1,a+m+1,(int)r)-a)-(lower_bound(a+1,a+m+1,(int)l)-a));
for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,min(l*max(du[la[i]]-1,1),inf),min((r+1)*max(du[la[i]]-1,1)-1,inf));
}
int main(){
scanf("%d%d%d",&n,&m,&k);for(i=1;i<=m;i++)scanf("%d",&a[i]);sort(a+1,a+m+1);
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
dfs(la[1],la[2],min((LL)k*max(du[la[1]]-1,1),inf),min((LL)(k+1)*max(du[la[1]]-1,1)-1,inf));
dfs(la[2],la[1],min((LL)k*max(du[la[2]]-1,1),inf),min((LL)(k+1)*max(du[la[2]]-1,1)-1,inf));
printf("%lld",ans);
}
评论 (0)
