POI2013
T1 Inspector 题目大意：$n$个员工和$m$个记录，每个员工只会在连续的一段时间内工作，写观察记录的时候肯定会在工作，记录会给出当时除了他还有多少人在公司。现在给出$m$条记录分别是谁写的、什么时候写的以及写的时候还有多少人。求第$k$条记录使得前$k$条记录可以同时存在不矛盾，且前$k+1$条记录是矛盾的。$n,m\leq 100000$。
二分答案，然后离散化，弄出所有有用的时间点。如果某个时刻有不同的人数，就不合法。求出每个人的必须区间，差分一下，维护当前的必选人数。维护$lv$表示左端点可移动的人能用几个，$rv$表示右端点可移动的人能用几个，$le$表示还有几个人没有选择。贪心地，对于必选的人，能减$lv$就减$lv$，否则减$rv$。对于不够的人，就只能用$le$来补了。对于多的人，能减$rv$减$rv$，否则减$lv$。时间复杂度$O((n+m)lgm)$。
#include<bits/stdc++.h>
#define N 100100
#define CL(b) memset(b,0,sizeof(b))
using namespace std;
int T,n,m,i,l,r,t,x,y,z,M,S,lv,rv,le,V,A[N],B[N],C[N],L[N],R[N],v[N],d[N],e[N],to[N];
bool ok(int w){
for(lv=rv=V=t=0,i=1;i<=n;i++)L[i]=N;CL(R);CL(v);CL(d);CL(e);
for(i=1;i<=w;i++){
x=A[i];y=B[i];z=C[i]+1;if(v[x]&&v[x]!=z)return 0;
v[x]=z;L[y]=min(L[y],x);R[y]=max(R[y],x);
}
for(i=1;i<=m;i++)if(v[i])to[i]=++t,v[t]=v[i];
for(i=1;i<=n;i++)if(R[i])d[to[L[i]]]++,e[to[R[i]]]++;
for(le=n,i=1;i<=t;i++){
V+=d[i];if(V>v[i])return 0;
for(;d[i]--;)if(lv)lv--;else le--;
for(;V+lv+rv<v[i];)lv++,le--;
for(;V+lv+rv>v[i];)if(rv)rv--;else lv--;
V-=e[i];rv+=e[i];if(le<0)return 0;
}return 1;
}
int main(){
for(scanf("%d",&T);T--;printf("%d\n",S)){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++)scanf("%d%d%d",&A[i],&B[i],&C[i]);
for(l=1,r=m;l<=r;)if(ok(M=l+r>>1))l=(S=M)+1;else r=M-1;
}
}
T2 Price List 首先有一个贪心的想法，直接求出每个点距离，但是这样会有一些问题，因为这个dis不仅包含原点的距离，还包含点对之间的距离
众所周知找三元环的时间复杂度是$O(m\sqrt{m})$，但如果暴力把距离为2的点对合到一起去的复杂度是$n^2$的也是不可取的
考虑从原点出发，每次找到一个距离为2的点，然后把这个点加入队列，把原点出发的边删去，就可以求出点对间的真正距离，而这样的时间复杂度等于找三元环的时间复杂度，是$O(m\sqrt{m})$
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100100
int n,m,i,j,s,a,b,tot,h,t,x,y,inf=1e8,X[N],Y[N],ans[N],d[N],q[N],use[N],pre[N<<1],ne[N<<1],n2[N<<1],la[N<<1],fir[N],fi2[N];
void ins(int x,int y){la[++tot]=y;n2[tot]=ne[tot]=fir[x];fi2[x]=fir[x]=tot;if(fi2[x])pre[fi2[x]]=tot;}
void del(int x,int i){if(fi2[x]==i)fi2[x]=n2[i];if(pre[i])n2[pre[i]]=n2[i];if(n2[i])pre[ne[i]]=pre[i];}
int main(){
for(scanf("%d%d%d%d%d",&n,&m,&s,&a,&b);m--;)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(memset(d,63,sizeof(d)),d[q[t=1]=s]=0;h^t;)for(i=fir[x=q[++h]];i;i=ne[i])if(d[y=la[i]]>inf)d[q[++t]=y]=d[x]+1;
for(b=std::min(b,a*2),i=1;i<=n;i++)ans[i]=d[i]/2*b+((d[i]&1)?a:0);
for(memset(d,63,sizeof(d)),h=d[q[t=1]=s]=0;h^t;){
for(i=fir[x=q[++h]];i;i=ne[i])use[la[i]]=x;
for(i=fir[x];i;i=ne[i])for(j=fi2[la[i]];j;j=n2[j])if(d[y=la[j]]>inf&&use[y]!=x)d[y]=d[x]+2,q[++t]=y,del(la[i],j);
}
for(i=1;i<=n;printf("%d\n",ans[i++]))if(d[i]<inf)ans[i]=std::min(ans[i],d[i]/2*b);
}
T3 Take-out 直接单调栈维护每个c控制的b即可
#include<cstdio>
#include<cstring>
#define N 1001000
int n,k,i,t,tot,h,q[N],sum[N],ans[N];char s[N];
int main(){
for(scanf("%d%d%s",&n,&k,s+1),i=1;i<=n;i++){
q[++t]=i;sum[t]=sum[t-1]+(s[i]=='c');
for(;t>k&&sum[t]-sum[t-k-1]==1;)
for(h=t-k;t>=h;ans[++tot]=q[t--]);
}
for(i=n;i;i--)printf("%d%c",ans[i],i%3==1?'\n':' ');
}
T4 Tales of seafaring 计算出每个点出发到每个点的奇数最短路和偶数最短路然后判断即可，这题先预处理会MLE，要把询问排序后再处理，就不会爆空间了
注意一下询问中$x==y$时要特判一下
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 5010
using namespace std;
int n,m,k,i,j,x,y,h,t,f,u,tot,ans[1001000],d[N][2],fir[N],ne[N<<1],la[N<<1];
struct E{int x,y,z,id;}p[1001000];struct P{int x,y;}q[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
bool cmp(E a,E b){return a.x<b.x;}
int main(){
for(scanf("%d%d%d",&n,&m,&k),i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(i=1;i<=k;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z),p[i].id=i;sort(p+1,p+k+1,cmp);
for(i=j=1;i<=n;i++){
for(h=0,q[t=1]=P{i,0},memset(d,-1,sizeof(d)),d[i][0]=0;h<t;)for(u=fir[x=q[++h].x],f=q[h].y;u;u=ne[u])if(d[y=la[u]][f^1]==-1)d[y][f^1]=d[x][f]+1,q[++t]=P{y,f^1};
for(;p[j].x==i&&j<=k;j++)if(p[j].z&1){if(d[p[j].y][1]<=p[j].z&&d[p[j].y][1]!=-1)ans[p[j].id]=1;}else if(d[p[j].y][0]<=p[j].z&&d[p[j].y][0]!=-1)ans[p[j].id]=1;
}
for(i=1;i<=k;i++)if(p[i].x==p[i].y&&!fir[p[i].x])ans[p[i].id]=0;
for(i=1;i<=k;i++)puts(ans[i]?"TAK":"NIE");
}
T6 Taxis 很明显在前半段肯定是先用大的比较好，因为小的先走效率会低，而后半段一辆车就够了，多了也浪费
一开始想选出一个大于等于后半段的最小的一辆车，然后剩下的车从大到小选，这样如果有解肯定是最优的
但想了会觉得这是可以被叉掉的，于是再直接从大到小贪心一遍，就可以避免无解
#include<cstdio>
#include<algorithm>
#define N 500500
using namespace std;typedef long long LL;
int n,i,j,p,ans;LL m,d,now,a[N];
void cal(LL x){if(now<d){if(x>d-now)now+=x-(d-now);}else now=max(now,d+x);}
int main(){
for(scanf("%lld%lld%d",&m,&d,&n),i=1;i<=n;i++)scanf("%lld",&a[i]);
for(sort(a+1,a+n+1),i=n;i;i--){
cal(a[i]);
if(now>=m){ans=n-i+1;break;}
if(a[i]>=m-d)p=i;
}
if(p)for(now=0,j=1,i=n;i;i--)if(i!=p){
cal(a[i]);j++;
if((now>=d||a[p]>=d-now*2+m)&&(ans==0||j<ans))ans=j;
}
printf("%d",ans);
}
T7 Triumphal arch 首先二分答案，然后就可以DP啦，用$f[x]$表示把$x$及其子树控制住需要多造几次
于是$f[x]=max(0,cnt-cur+\sum_{x\to y}f[y])$（$cnt$为儿子个数），然后如果$f[1]==0$就合法，否则不合法
#include<cstdio>
#include<algorithm>
#define N 300030
int n,i,x,y,l,r,ans,mid,tot,cur,fir[N],ne[N<<1],la[N<<1],f[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
int i,y,cnt=0;
for(i=fir[x];i;i=ne[i])if((y=la[i])!=fa)cnt++,dfs(y,x),cnt+=f[y];
f[x]=std::max(0,cnt-cur);
}
bool ok(int x){cur=x;dfs(1,0);return f[1]==0;}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(l=0,r=n;l<=r;)if(ok(mid=l+r>>1))ans=mid,r=mid-1;else l=mid+1;
printf("%d",ans);
}
T8 Walk 题目大意：有2^N-k个点，每个点有一个独一无二的、长度为n的01串，但是有k个01串没有出现过。每两个点之间有连边当且仅当两个01串之间有且仅有一个位置是不同的。现在询问x和y两个字符串能不能互相到达。N<=60，k<=1000000，n*k<=5000000。
删去k个点后至多存在一个大小大于nk的联通块，根据这个性质可以通过HASH进行BFS，时间复杂度O(n^2k*常数)。
#include<bits/stdc++.h>
using namespace std;const int N=5001000,M=23633333;typedef long long LL;
int n,w,i,k,h,t,tot,fir[M],ne[N];LL S,T,x,a[N],q[N],la[N];
char ch;inline void rd(LL&x){
for(ch=getchar();ch<'0'||ch>'1';ch=getchar());
for(x=0;ch=='0'||ch=='1';ch=getchar())x=x*2+ch-'0';
}
inline void D(LL x){la[++tot]=x;ne[tot]=fir[x%M];fir[x%M]=tot;}
inline void A(LL x){
for(int i=fir[x%M];i;i=ne[i])if(la[i]==x)return;D(x);q[++t]=x;
}
inline bool ok(LL S,LL T){
for(h=t=tot=0,memset(fir,0,sizeof fir),i=1;i<=k;i++)D(a[i]);
for(A(S);h^t&&t<=w;){
if(x=q[++h],x==T){puts("TAK");exit(0);};
for(i=0;i<n;i++)A(x^(1ll<<i));
}
return t<=w?0:1;
}
int main(){
for(scanf("%d%d",&n,&k),w=n*k+5,rd(S),rd(T),i=1;i<=k;i++)rd(a[i]);
puts(ok(S,T)&&ok(T,S)?"TAK":"NIE");
}
T9 只想到了1到n拉链和贪心选点。。感觉讨论太麻烦了
T10 Polarization 题目大意：给一颗树的每条边定向，求出最小的可达点对和最大的可达点对，$n\leq250000$。
最小对数就是$n-1$。求最大对数一个很明显的想法是所有点都经过一个点，有的点指向这个点，有的点从这个点指出，$f[x]=\sum_{x\to y} f[y]+sz[y]$，两遍树形DP求出内部的答案，剩下的定向后会有$x*(n-x-1)$的贡献，$x$为一个子树的大小。如果直接背包的话时间复杂度是$O(n^3)$，不能接受。发现只有重心的最大子树不超过$n/2$，不是重心的点就可以直接求出来，现在只需要求重心的最大贡献。直接压位背包时间复杂度是$O(\frac{n^2}{32})$，还是不能通过。考虑按子树大小分类，大于$\sqrt{n}$的直接背包，小于$\sqrt{n}$的统计个数，然后二进制拆分，再进行背包，并压位优化。时间复杂度$O(\frac{n\sqrt{n}}{32})$。
#include<bits/stdc++.h>
#define N 250250
using namespace std;long long A,ans,f[N];bitset<N>g;
int n,i,j,k,x,y,t,w,rt,tot,fir[N],la[N*2],ne[N*2],mv[N],sz[N],q[N],V[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
sz[x]=1;
for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa)dfs(y=la[i],x),mv[x]=max(mv[x],sz[y]),f[x]+=f[y]+sz[y],sz[x]+=sz[y];
mv[x]=max(mv[x],n-sz[x]);if(mv[x]<mv[rt]||!rt)rt=x;
}
void dfs2(int x,int fa){
ans=max(ans,f[x]+1ll*mv[x]*(n-mv[x]-1));
for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa)f[y=la[i]]+=f[x]-f[y]+n-2*sz[y],dfs2(y,x);
}
int main(){
for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(dfs(1,0),dfs2(1,0),i=fir[rt];i;i=ne[i])if(sz[la[i]]<sz[rt])if(sz[la[i]]<500)V[sz[la[i]]]++;else q[++t]=sz[la[i]];
if(rt!=1)if(n-sz[rt]<500)V[n-sz[rt]]++;else q[++t]=n-sz[rt];
for(g[0]=i=1;i<=t;i++)g|=g<<q[i];
for(i=1;i<500;i++)for(j=V[i],k=1;j;j-=k,k<<=1){
if(j<=k){g|=g<<i*j;break;}
g|=g<<i*k;
}
for(i=1;i<=n;i++)if(g[i])ans=max(ans,f[rt]+1ll*i*(n-i-1));
printf("%d %lld",n-1,ans);
}
T11 Tower Defense Game 条件宽松的构造题，直接暴力构造即可，看上去暴力会T实际上不会T的。。
#include<cstdio>
#define N 500500
int n,m,k,i,j,x,y,top,tot,q[N],fir[N],ne[N<<2],la[N<<2],v[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,&m,&k),i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(x=1;x<=n;x++)if(!v[x]){
q[++top]=x;v[x]=10000;
for(i=fir[x];i;i=ne[i])if(v[y=la[i]]<10000)for(v[y]=10000,j=fir[y];j;j=ne[j])v[la[j]]++;
}
for(printf("%d\n",top),i=1;i<=top;i++)printf("%d ",q[i]);
}
T12 Bytecomputer 直接傻逼DP即可，首先可以证明数列中只会出现$-1$,$0$和$1$，显然不会出现$<-1$的数，然后如果把一个数改为大于$1$的数，$-1$需要$2$的代价，这和改成$1$是一样的，得证。于是随便转移一下就可以$O(n)$出解了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1001000
using namespace std;
int n,i,x,f[N][3];
int main(){
scanf("%d%d",&n,&x);
memset(f,63,sizeof(f));f[1][x+1]=0;
for(i=2;i<=n;i++){
scanf("%d",&x);
f[i][2]=f[i-1][2]+(1-x);
if(x==1)f[i][2]=min(f[i][2],min(f[i-1][0],f[i-1][1]));
f[i][0]=f[i-1][0]+(x+1);
if(x==1)f[i][1]=f[i-1][0]+1;
if(x==0)f[i][1]=min(f[i-1][0],f[i-1][1]);
}
x=min(min(f[n][0],f[n][1]),f[n][2]);
x>1e9?puts("BRAK"):printf("%d",x);
}
剩的题都没有中文题面太难啦，不做啦~
评论 (0)
