Bubble Cup 11 - Finals（codeforces 1045）
卫和洽
Bubble Cup 11 - Finals
四题滚粗了，结束后30秒过了第五题。
如果状态好点，没看错题的话，应该至少能过个6题的吧。
A. Last chance (cf 1045A)
题目描述
http://codeforces.com/contest/1045/problem/A
题解
第一类武器直接连边。
第二类武器线段树优化建图。
第三类武器题目有个条件说是不交叉的，所以先暴力连边暴力跑。
对于第三类武器，如果只匹配了一个点，那就把它对应的另外两个点随便选一个，因为不交叉所以把那个点的对于匹配的武器换掉就好了。
输出方案的话，就按费用流那样每条流量增广一下就好了。
几十万条边跑网络流只要100多毫秒？？？喵喵喵喵喵？？？
代码
#include<bits/stdc++.h>
#define inf 1050000000
#define N 20000
#define M 400000
using namespace std;
int n,m,S,T,ans,rt,cnt,lc[N],rc[N],pos[N];
int tag[N],A[N][3],from[N],dep[N],q[N];
int k=1,la[N],ff[M],cur[N],ss[N];
struct node{int a,b,c;}e[M];
void add(int a,int b,int c)
{
e[++k]=(node){a,b,c};ff[k]=la[a];la[a]=k;
e[++k]=(node){b,a,0};ff[k]=la[b];la[b]=k;
}
int dfs(int x,int flow)
{
if(x==T)return flow;
int res=0,tmp;
for(int a=cur[x];a&&flow;a=ff[a])
{
cur[x]=a;
if(dep[e[a].b]==dep[x]+1&&e[a].c)
{
tmp=dfs(e[a].b,min(flow,e[a].c));
e[a].c-=tmp;e[a^1].c+=tmp;res+=tmp;flow-=tmp;
}
}
if(!res)dep[x]=-1;
return res;
}
bool bfs()
{
memset(dep,0,sizeof(dep));
for(int i=S;i<=T;i++)cur[i]=la[i];
int l=1,r=2;q[1]=S;dep[S]=1;
while(l<r)
{
int x=q[l];l++;
for(int a=la[x];a;a=ff[a])
if(!dep[e[a].b]&&e[a].c)
q[r]=e[a].b,dep[q[r]]=dep[x]+1,r++;
}
return dep[T];
}
void build(int &x,int l,int r,int pre)
{
if(!x)x=++cnt;
if(pre)add(pre,x,r-l+1);
if(l==r){pos[l]=x;return;}
int mid=l+r>>1;
build(lc[x],l,mid,x);
build(rc[x],mid+1,r,x);
}
void solve(int x,int l,int r,int ql,int qr,int S)
{
if(ql<=l&&r<=qr){add(S,x,1);return;}
int mid=l+r>>1;
if(ql<=mid)solve(lc[x],l,mid,ql,qr,S);
if(qr>mid)solve(rc[x],mid+1,r,ql,qr,S);
}
int find(int x,int flow,int pos)
{
if(x==T)return flow;int res=0,tmp;
for(int a=la[x];a;a=ff[a])
if(!(a&1)&&e[a^1].c)
{
tmp=find(e[a].b,min(flow,e[a^1].c),pos);
e[a^1].c-=tmp;e[a].c+=tmp;res+=tmp;flow-=tmp;
if(e[a].b==T)from[x]=pos;
}
return res;
}
int main()
{
int tp,x,len,l,r,a,b,c;
scanf("%d%d",&n,&m);
cnt=n;build(rt,1,m,0);T=cnt+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&tp);cnt++;
if(tp==0)
{
scanf("%d",&len);add(S,i,1);
for(int j=1;j<=len;j++)
scanf("%d",&x),add(i,pos[x],1);
}
if(tp==1)
{
scanf("%d%d",&l,&r);
add(S,i,1);solve(rt,1,m,l,r,i);
}
if(tp==2)
{
scanf("%d%d%d",&a,&b,&c);
tag[i]=1;A[i][0]=a;A[i][1]=b;A[i][2]=c;
add(S,i,2);add(i,pos[a],1);
add(i,pos[b],1);add(i,pos[c],1);
}
}
for(int i=1;i<=m;i++)add(pos[i],T,1);
while(bfs())ans+=dfs(S,inf);
for(int a=la[S];a;a=ff[a])
if(e[a^1].c)find(e[a].b,e[a^1].c,e[a].b);
for(int i=1;i<=m;i++)ss[from[pos[i]]]++;
for(int i=1;i<=n;i++)
if(tag[i]&&ss[i]==1)
{
int flag=0;
for(int j=0;j<=2;j++)
if(from[pos[A[i][j]]]&&from[pos[A[i][j]]]!=i)
{from[pos[A[i][j]]]=i;flag=1;break;}
if(flag)continue;
for(int j=0;j<=2;j++)from[pos[A[i][j]]]=0;
ans--;
}
printf("%d\n",ans);
for(int i=1;i<=m;i++)
if(from[pos[i]])printf("%d %d\n",from[pos[i]],i);
return 0;
}
B. Space Isaac（cf 1045B）
题目描述
http://codeforces.com/contest/1045/problem/B
题解
一个数字如果不能被表示，那等价于它减去ai后仍然属于a数组。
所以可以发现，如果数字a不能被表示，那么a=a1+ai=a2+ai-1=a3+ai-2…
所以判一下i之前是不是回文串就好了。
代码
队友写的，不贴代码了。
C. Hyperspace Highways
题目描述
http://codeforces.com/contest/1045/problem/C
题解
裸的圆方树。
每条边都连1/2，求两点距离就好了。
代码
#include<bits/stdc++.h>
#define N 200010
#define M 2000010
#define D 20
using namespace std;
int n,m,Q,cnt,tp,tot,dfn[N],low[N],blo[N],q[M];
int k,la[N],ff[M],flag[N],dep[N],w[N][D+1];
struct node{int a,b;}e[M];
vector<int>s[M];
void add(int a,int b)
{
e[++k]=(node){a,b};ff[k]=la[a];la[a]=k;
e[++k]=(node){b,a};ff[k]=la[b];la[b]=k;
}
void insert(int x,int p)
{
if(blo[x]==p)return;
s[p].push_back(x);blo[x]=p;
}
void dfs(int x,int pre)
{
dfn[x]=++cnt;low[x]=dfn[x];
for(int a=la[x];a;a=ff[a])
{
if(!dfn[e[a].b])
{
q[++tp]=a;dfs(e[a].b,x);
low[x]=min(low[x],low[e[a].b]);
if(low[e[a].b]>=dfn[x])
{
tot++;
for(;tp;tp--)
{
insert(e[q[tp]].a,tot);
insert(e[q[tp]].b,tot);
if(q[tp]==a){tp--;break;}
}
}
}
else if(dfn[e[a].b]<dfn[x]&&e[a].b!=pre)
{
q[++tp]=a;low[x]=min(low[x],dfn[e[a].b]);
}
}
}
void solve()
{
k=0;memset(la,0,sizeof(la));
for(int i=1;i<=tot;i++)
for(int j=0;j<s[i].size();j++)add(n+i,s[i][j]);
}
void dfs2(int x)
{
for(int i=1;i<=D;i++)
w[x][i]=w[w[x][i-1]][i-1];
for(int a=la[x];a;a=ff[a])
{
if(e[a].b==w[x][0])continue;
dep[e[a].b]=dep[x]+1;
w[e[a].b][0]=x;dfs2(e[a].b);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=D;i>=0;i--)
if(dep[w[x][i]]>=dep[y])x=w[x][i];
if(x==y)return x;
for(int i=D;i>=0;i--)
if(w[x][i]!=w[y][i])x=w[x][i],y=w[y][i];
return w[x][0];
}
int main()
{
int a,b,pos;
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=m;i++)
scanf("%d%d",&a,&b),add(a,b);
dfs(1,0);solve();dep[1]=1;dfs2(1);
while(Q--)
{
scanf("%d%d",&a,&b);pos=lca(a,b);
printf("%d\n",(dep[a]+dep[b])/2-dep[pos]);
}
return 0;
}
D. Interstellar battle
题目描述
http://codeforces.com/contest/1045/problem/D
题解
大傻逼题。
训练的时候看成可恢复的修改然后大力dp一波死活不过样例。
其实根本不用什么dp。
因为是一棵树，每个点可以单独计算贡献。
它到根如果断了，那么联通块数必然+1。
随便写写就好了。
代码
#include<bits/stdc++.h>
#define inf 2100000000
#define N 100010
#define D 18
using namespace std;
int n,Q,fa[N],k,la[N],ff[N*2];double s[N],sum[N],ans;
struct node{int a,b;}e[N*2];
void add(int a,int b)
{
e[++k]=(node){a,b};ff[k]=la[a];la[a]=k;
e[++k]=(node){b,a};ff[k]=la[b];la[b]=k;
}
void dfs(int x)
{
ans+=(1-s[x])*s[fa[x]];sum[fa[x]]+=1-s[x];
for(int a=la[x];a;a=ff[a])
if(e[a].b!=fa[x])fa[e[a].b]=x,dfs(e[a].b);
}
int main()
{
int a,b,x;double y;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf",&s[i]);
for(int i=1;i<n;i++)
scanf("%d%d",&a,&b),add(a+1,b+1);
s[0]=1;dfs(1);
scanf("%d",&Q);
while(Q--)
{
scanf("%d%lf",&x,&y);x++;
ans-=(1-s[x])*s[fa[x]];ans-=s[x]*sum[x];
sum[fa[x]]-=1-s[x];s[x]=y;sum[fa[x]]+=1-s[x];
ans+=(1-s[x])*s[fa[x]];ans+=s[x]*sum[x];
printf("%lf\n",ans);
}
return 0;
}
EF留坑
G. AI robots
题目描述
http://codeforces.com/contest/1045/problem/G
题解
对于每个点按xi排序。
每对点能交流的前提是，xi-ri<=xj<=xi+ri，xj-rj<=xi<=xj+rj。
我们把它画到一个二维平面上，就等价于对于每条y坐标为xi，x坐标范围在[xi-ri,xi+ri]的线段和x坐标为xj，y坐标为[xj-rj,xj+rj]的线段求交点个数。
所以按xi排序扫描线扫一波拿个线段树维护一下就好了。
qi的限制，因为k只有20，所以并没有什么卵用。
对于每个qi分别维护一棵线段树，查询的时候暴力查一下前后k就好了。
代码
#include<bits/stdc++.h>
#define N 300010
#define ll long long
using namespace std;
int n,k,res,tot,Tnum,num[N],h[N],C[N],cnt,rt[N];ll ans;
struct data{
int x,l,r,c;
bool operator<(const data &p)const{return x<p.x;}
}s[N];
struct info{
int x,p,c,inv;
bool operator<(const info &p)const{return x<p.x;}
}q[N];
struct node{int lc,rc,size;}t[N*20];
class seg_tree{
public:
void modify(int &x,int l,int r,int pos,int inv)
{
if(!x)x=++cnt;t[x].size+=inv;
if(l==r)return;
int mid=l+r>>1;
if(pos<=mid)modify(t[x].lc,l,mid,pos,inv);
else modify(t[x].rc,mid+1,r,pos,inv);
}
int qry(int x,int l,int r,int ql,int qr)
{
if(!x)return 0;
if(ql<=l&&r<=qr)return t[x].size;
int mid=l+r>>1,lc=t[x].lc,rc=t[x].rc,res=0;
if(ql<=mid)res+=qry(lc,l,mid,ql,qr);
if(qr>mid)res+=qry(rc,mid+1,r,ql,qr);
return res;
}
}T;
int main()
{
int a,b,c,p,l,r;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c);
q[++tot]=(info){a-b,a,c,1};
q[++tot]=(info){a+b+1,a,c,-1};
num[++res]=a-b;num[++res]=a;
num[++res]=a+b;C[i]=c;
s[i]=(data){a,a-b,a+b,c};
}
sort(q+1,q+tot+1);sort(s+1,s+n+1);
sort(C+1,C+n+1);sort(num+1,num+res+1);
Tnum=unique(C+1,C+n+1)-C-1;
res=unique(num+1,num+res+1)-num-1;
for(int i=1,j=1;i<=n;i++)
{
for(;j<=tot&&q[j].x<=s[i].x;j++)
{
c=lower_bound(C+1,C+Tnum+1,q[j].c)-C;
p=lower_bound(num+1,num+res+1,q[j].p)-num;
T.modify(rt[c],1,res,p,q[j].inv);
}
l=lower_bound(num+1,num+res+1,s[i].l)-num;
r=lower_bound(num+1,num+res+1,s[i].r)-num;
for(int j=s[i].c-k;j<=s[i].c+k;j++)
{
c=lower_bound(C+1,C+Tnum+1,j)-C;
if(C[c]==j)ans+=T.qry(rt[c],1,res,l,r);
}
}
printf("%I64d\n",(ans-n)/2);
return 0;
}
H. Self-exploration
题目描述
http://codeforces.com/contest/1045/problem/H
题解
大概就是先利用10和01的限制把数字分开，然后再把00和11塞进去。
赛后30秒就过了。。
代码
队友写的，不贴代码了。
I. Palindrome Pairs
题目描述
http://codeforces.com/contest/1045/problem/I
题解
签到题。
统计一下每个串每个字母的01个数。
两个串随机排列回文的话，就是01个数相等，或者只有一位不等。
随便搞搞就好了。
代码
#include<bits/stdc++.h>
#define ll long long
#define N 1000010
using namespace std;
int n,m,flag[30],S;char s[N];ll ans;
unordered_map<int,int>cnt;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
memset(flag,0,sizeof(flag));S=0;
scanf(" %s",s+1);m=strlen(s+1);
for(int j=1;j<=m;j++)flag[s[j]-'a']^=1;
for(int j=0;j<26;j++)S=(S<<1)+flag[j];
for(int j=0;j<26;j++)ans+=cnt[S^(1<<j)];
ans+=cnt[S];cnt[S]++;
}
printf("%I64d\n",ans);
return 0;
}
J. Moonwalk challenge
题目描述
http://codeforces.com/contest/1045/problem/J
题解
训练的时候没看到|S|<=100的条件，以为是什么SAM神题，遂弃之。
|S|<=100，那就随便hash存存就好了嘛。
对于每个点求一下它往上100个点内的hash值，存一下。
对于一个询问，不跨lca的拿个hash表统计一下就好了。
跨lca的，因为串长只有100，所以暴力把那部分搞出来，然后暴力判一下就好了。
为了方便些，把询问离线了，每个询问等价于x点+，x往上某点-。
这个题用map写会被卡内存，手写hash表才过的。。
代码
#include<bits/stdc++.h>
#define ll long long
#define M 10000007
#define seed 19990213
#define N 100010
#define D 18
using namespace std;
int n,m,fa[N],dep[N],w[N][D+1],k,la[N],ff[N*2];
ll h[N],mul[N];char s[N],str[N];int po[N],ans[N];
int cnt,fst[M+1],nxt[M+1],g[M+1];ll f[M+1];
struct node{int a,b;char c;}e[N*2];
struct info{ll ha;int inv,id;};
vector<info>t[N];
void add(int a,int b,char c)
{
e[++k]=(node){a,b,c};ff[k]=la[a];la[a]=k;
e[++k]=(node){b,a,c};ff[k]=la[b];la[b]=k;
}
void insert(ll v,int val)
{
int x=(v%M+M)%M;
for(int a=fst[x];a;a=nxt[a])
if(f[a]==v){g[a]+=val;return;}
f[++cnt]=v;g[cnt]=val;nxt[cnt]=fst[x];fst[x]=cnt;
}
int qry(ll v)
{
int x=(v%M+M)%M;
for(int a=fst[x];a;a=nxt[a])
if(f[a]==v)return g[a];
return 0;
}
void dfs1(int x)
{
w[x][0]=fa[x];
for(int i=1;i<=D;i++)w[x][i]=w[w[x][i-1]][i-1];
for(int a=la[x];a;a=ff[a])
{
if(dep[e[a].b])continue;
fa[e[a].b]=x;s[e[a].b]=e[a].c;
dep[e[a].b]=dep[x]+1;dfs1(e[a].b);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=D;i>=0;i--)
if(dep[w[x][i]]>=dep[y])x=w[x][i];
if(x==y)return x;
for(int i=D;i>=0;i--)
if(w[x][i]!=w[y][i])x=w[x][i],y=w[y][i];
return w[x][0];
}
int find(int x,int d)
{
for(int i=D;i>=0;i--)
if(dep[w[x][i]]>=d)x=w[x][i];
return x;
}
ll get(int l,int r)
{
return h[r]-h[l-1]*mul[r-l+1];
}
void qry(int x,int y,char *str,int id)
{
int p=lca(x,y),a=x,b=y,tot=0,A,B;
int len=strlen(str),pos;ll ha=0;
for(int i=0;i<len;i++)ha=ha*seed+str[i];
if(dep[x]-dep[p]>=len)a=find(x,dep[p]+len-1);A=a;
if(dep[y]-dep[p]>=len)b=find(y,dep[p]+len-1);B=b;
while(a!=p)po[++tot]=a,a=fa[a];pos=tot;
while(b!=p)po[++tot]=b,b=fa[b];
reverse(po+pos+1,po+tot+1);
for(int i=1;i<=tot;i++)h[i]=h[i-1]*seed+s[po[i]];
for(int i=1;i+len-1<=tot;i++)
if(get(i,i+len-1)==ha)ans[id]++;
if(A!=x){
t[x].push_back((info){ha,1,id});
t[A].push_back((info){ha,-1,id});
}
ha=0;for(int i=len-1;i>=0;i--)ha=ha*seed+str[i];
if(B!=y){
t[y].push_back((info){ha,1,id});
t[B].push_back((info){ha,-1,id});
}
}
void dfs2(int x)
{
ll ha=0;
for(int i=1,p=x;i<=100&&p;p=fa[p],i++)
insert(ha=ha*seed+s[p],1);
for(int i=0;i<t[x].size();i++)
ans[t[x][i].id]+=t[x][i].inv*qry(t[x][i].ha);
for(int a=la[x];a;a=ff[a])
if(dep[e[a].b]==dep[x]+1)dfs2(e[a].b);
ha=0;
for(int i=1,p=x;i<=100&&p;p=fa[p],i++)
insert(ha=ha*seed+s[p],-1);
}
int main()
{
int a,b,pos,len;char c;ll ha;
scanf("%d",&n);
for(int i=1;i<n;i++)
scanf("%d%d %c",&a,&b,&c),add(a,b,c);
dep[1]=1;dfs1(1);mul[0]=1;
for(int i=1;i<=n;i++)mul[i]=mul[i-1]*seed;
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d%d %s",&a,&b,str),qry(a,b,str,i);
dfs2(1);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
类似资料：