2018.8.10 正睿暑期集训营 Day7
时间：2.5h(实际)(不行太闲了)
期望得分：...
实际得分：...
总结
倍增！之前还记得怎么又忘了。。
如果可以任意互换位置 具体什么样我们是不关心的。
A 花园(思路)
只保留两条边，会剩下一个类似基环内向树的图。
每个点到达P的情况有三种可能：1.永远到不了P；2.只会到1次P；3.在某时刻t到达P，然后每隔时间l到达一次P。2是P在环外，3是P在环上。
对每个点分走最长边和次长边DFS两次，记录它到P的时间dis和到P时朝哪(下一次走最长边还是次长边dir)。可以在O(n)时间内预处理。
然后枚举每个点可以得到某一时刻朝哪到达P的有多少点cnt[t][0/1]，这个用每个点走最长边时算的dis和dir更新。
然后再用P相邻两点的dis,dir得到从P走最长边/次长边多长时间f[0/1]会回到P，及回到P时朝哪g[0/1]。
环长最长应该不超过2n，一个点到P开始循环的时间也不超过2n，所以预处理4n时间内的 某一时刻朝哪到达P的有多少点。可以通过类似DP用f[0/1],g[0/1]转移。
其实只求P所在的那个环或是能到P的点就可以了，建个反图，把每个点的两条出边改成两条入边。
DFS的时候记一下之前走的是最长边还是次长边(原图中x下一步要走最长边还是次长边)，如果是次长边则x只能是从最长边来的(还得会走这条边，即连接点要有这条边)；否则如果dgr[x]>1则可以任意从非x的最长边的边来。
当之前走的是最长边时用此时到P的距离更新cnt[t][0/1]。0/1是确定的，只从P DFS我们可以确定到达P时是朝哪的（下次走最长边还是次长边）。
记环长f[0/1]为len，输出的时候时刻应是。。k%len然后一直加len直到>=2n？。。
但是可以直接 \(k%len+[2n/len]*len\)。。我知道后面是\(n<x\leq 2n\)的，但是如果有个点最初需要\(>[2n/len]*len\)的时间到P，K很大的话不是会算不上这个点吗。。
不懂。。神特么看了1天这个题。
//109ms 13392kb
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=150005,M=N<<1;
int n,m,P,Enum,H[N],nxt[M],to[M],dir[M],fir[N],dgr[N],len[2],cnt[N<<2][2],sum[N<<2][2];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
#define AddEdge(u,v,d) to[++Enum]=v,nxt[Enum]=H[u],H[u]=Enum,dir[Enum]=d
void DFS(int x,int dis,bool las,bool direct)//las=0:从x的最长边来(原图中x下一步走最长边)，那么到x的不是x最长边连的点
{
if(!las) ++cnt[dis][direct];
for(int v,i=H[x]; i; i=nxt[i])
if((!las&&((v=to[i])!=fir[x]||dgr[x]==1))||(las&&(v=to[i])==fir[x]))
{
if(v==P && dir[i]==direct)//以direct的方向回到P
len[direct]=dis+1;//不能return，还有其它到x的点要统计！
else DFS(v,dis+1,dir[i],direct);
}
}
int main()
{
n=read(), m=read(), P=read();
for(int u,v; m--; )
{
u=read(), v=read();
if(!dgr[u]) AddEdge(v,u,0), fir[u]=v, ++dgr[u];
else if(dgr[u]==1) AddEdge(v,u,1), ++dgr[u];
if(!dgr[v]) AddEdge(u,v,0), fir[v]=u, ++dgr[v];
else if(dgr[v]==1) AddEdge(u,v,1), ++dgr[v];
}
DFS(P,0,0,0);
if(dgr[P]>1) DFS(P,0,1,1);
int tot=n<<2, l0=len[0], l1=len[1];
for(int i=0; i<tot; ++i)
{
sum[i][0]+=cnt[i][0], sum[i][1]+=cnt[i][1];
if(l0 && i+l0<tot) sum[i+l0][0]+=sum[i][0];
if(l1 && i+l1<tot) sum[i+l1][1]+=sum[i][1];
}
for(int Q=read(),K,t0=l0?2*n/l0*l0:0,t1=l1?2*n/l1*l1:0; Q--; )
{
if((K=read())<tot) printf("%d ",sum[K][0]+sum[K][1]);
else printf("%d ",(t0?sum[K%l0+t0][0]:0)+(t1?sum[K%l1+t1][1]:0));
}
return 0;
}
B 归来(Tarjan 拓扑)
将每种状态转移暴力连边，得到一张有向图，最长路就是答案。
同一强连通分量的点是可以任意转移的，对其缩点后得到DAG，拓扑/记忆化都可以求。\(O(4^n*m)\)，期望得分30~50.
注意到交换是任意的，所以只需要关心当前串每种字符的个数。
对于分别有a,b,c,d个A,B,C,D的串，其个数/排列数为\(\frac{n!}{a!b!c!d!}\)，但是直接算阶乘是爆longlong的。
最大的时候是\(\frac{n!}{7!7!8!8!}\approx 6e15\)，所以直接用组合数\(C_n^a*C_{n-a}^b*C_{n-a-b}^c\)是不会爆longlong的。
总点数是\(C_{30+4-1}^{4-1}=5456\)。同样对状态连边，缩点求最长路。
复杂度\(O(n^3m)\)。
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define MAXIN 10000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define ID(a,b,c) (((a)*nn+(b))*nn+(c))//括号啊！！
typedef long long LL;
const int N=30005,M=810005;//n^3m
int n,nn,tot,m,cnt,top,sk[N],Index,dfn[N],low[N],bel[N];
bool ins[N];
LL val[N],sz[N],f[N];
std::queue<int> q;
char IN[MAXIN],*SS=IN,*TT=IN;
struct Graph
{
int Enum,H[N],nxt[M],to[M],dgr[N];
inline void AddEdge(int u,int v)
{
++dgr[v], to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
}G,D;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void Get(int *num)
{
register char c=gc();
for(; !isalpha(c); c=gc());
for(; isalpha(c); ++num[c-'A'],c=gc());
}
void Init_val()
{
static LL C[35][35];
C[0][0]=1;
for(int i=1; i<=n; ++i)
{
C[i][0]=C[i][i]=1;
for(int j=1; j<i; ++j) C[i][j]=C[i-1][j]+C[i-1][j-1];
}
for(int a=0; a<=n; ++a)
for(int b=0; a+b<=n; ++b)
for(int c=0; a+b+c<=n; ++c)
val[ID(a,b,c)]=C[n][a]*C[n-a][b]*C[n-a-b][c];
}
void Tarjan(int x)
{
dfn[x]=low[x]=++Index, sk[++top]=x, ins[x]=1;
for(int i=G.H[x],v; i; i=G.nxt[i])
if(!dfn[v=G.to[i]]) Tarjan(v), low[x]=std::min(low[x],low[v]);
else if(ins[v]) low[x]=std::min(low[x],dfn[v]);
if(dfn[x]==low[x])
{
++cnt; int tmp;
do
{
tmp=sk[top--];
sz[cnt]+=val[tmp], ins[tmp]=0, bel[tmp]=cnt;
}while(tmp!=x);
}
}
void Toposort()
{
LL ans=0;
for(int i=1; i<=cnt; ++i) if(!D.dgr[i]) q.push(i);
while(!q.empty())
{
int x=q.front(); q.pop();
f[x]+=sz[x], ans=std::max(ans,f[x]);
for(int i=D.H[x],v; i; i=D.nxt[i])
{
f[v=D.to[i]]=std::max(f[v],f[x]);
if(!--D.dgr[v]) q.push(v);
}
}
printf("%lld\n",ans);
}
int main()
{
// freopen("ex_return3.in","r",stdin);
n=read(), m=read(), nn=n+1, tot=n*nn*nn;
for(int i=1; i<=m; ++i)
{
int num1[4]={0,0,0,0},num2[4]={0,0,0,0};
Get(num1), Get(num2);
if(num1[0]==num2[0]&&num1[1]==num2[1]&&num1[2]==num2[2]) continue;
for(int a=num1[0]; a<=n; ++a)//枚举所有含Ai的串啊
for(int b=num1[1]; a+b<=n; ++b)
for(int c=num1[2]; a+b+c<=n; ++c)
{
if(n-a-b-c<num1[3]) break;
G.AddEdge(ID(a,b,c),ID(a-num1[0]+num2[0],b-num1[1]+num2[1],c-num1[2]+num2[2]));
}
}
Init_val();
for(int i=0; i<=tot; ++i) if(!dfn[i]) Tarjan(i);//从0开始！(全D)
for(int x=0,now=bel[x]; x<=tot; now=bel[++x])
for(int i=G.H[x],v; i; i=G.nxt[i])
if(now!=bel[G.to[i]]) D.AddEdge(now,bel[G.to[i]]);//正反当然没关系啊
Toposort();
return 0;
}
C 机场(凸函数 点分治)
为什么函数是凸的，是有位置使得\(f'(0)<0\)。。
判断凹凸性还是去求二次导吧。
80pts代码：
/*
y=x^{3/2}是凸函数，所以$f(x)=\sum_{i=1}^n w[i]dis(x,i)^{3/2}$也(应该)是凸的。
凸函数有个性质：局部最优解就是全局最优解。
所以我们从任意一个点DFS，每次走到答案最小的儿子，一定能找到最优解。
每次直接跳到子树的重心，复杂度就是O(ndlogn)了（d是点的出度）。
期望得分80(注意不要DFS太多点)。
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=2e5+5;
int n,W[N],Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],dis[N],root,Min,sz[N],Cnt;
double Ans,Sum,f[N];
bool vis[N];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AddEdge(int w,int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
void Calc(int x,int f,int d)
{
Sum+=1.0*d*sqrt(d)*W[x];//pow(d,1.5)
for(int i=H[x]; i; i=nxt[i])
if(to[i]!=f) Calc(to[i],x,d+len[i]);
}
void Get_root(int x,int f,int tot)
{
int mx=0; sz[x]=1;
for(int i=H[x],v; i; i=nxt[i])
if(!vis[v=to[i]]&&v!=f)
{
Get_root(v,x,tot), sz[x]+=sz[v];
if(sz[v]>mx) mx=sz[v];
}
mx=std::max(mx,tot-sz[x]);
if(mx<Min) Min=mx, root=x;
}
void Solve(int x)
{
vis[x]=1; double ans=Ans; int p=0;
for(int i=H[x],v; i; i=nxt[i])
{
if(!f[v=to[i]])
if(++Cnt>700) f[v]=Ans;//全DFS要T啊
else Sum=0, Calc(v,0,0), f[v]=Sum;
if(ans>f[v]) ans=f[p=v];
}
Ans=std::min(Ans,ans);
if(p) Min=N, Get_root(p,0,sz[p]), Solve(root);
}
int main()
{
// freopen("ex_airport2.in","r",stdin);
n=read();
for(int i=1; i<=n; ++i) W[i]=read();
for(int i=1; i<n; ++i) AddEdge(read(),read(),read());
Min=N, Get_root(1,0,n), Calc(root,0,0), f[root]=Ans=Sum, Solve(root);
printf("%.7lf\n",Ans);
return 0;
}
考试代码
A
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#define gc() getchar()
const int N=150005;
int n,m,P,Q,K[2005],dgr[N],dis[N][2],ans[N];
std::vector<int> e[N];
#define AddEdge(u,v) e[u].push_back(v)
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
namespace Subtask1
{
int n,m,pre[N],pos[N];
void Main()
{
for(int Q=read(); Q--; )
{
int K=read();
for(int i=1; i<=n; ++i) pos[i]=i, pre[i]=0;
while(K--)
{
for(int x=1,p; x<=n; ++x)
{
p=pos[x];
if(dgr[p]==1||e[p][0]!=pre[x]) pre[x]=p, pos[x]=e[p][0];
else pre[x]=p, pos[x]=e[p][1];
}
}
int res=0;
for(int i=1; i<=n; ++i) if(pos[i]==P) ++res;//printf("%d ",i-1), ++res; putchar('\n');
printf("%d ",res);// putchar('\n');
}
}
}
//int DFS(int x,int f,int d,int anc,int toward)
//{
// if(x==P) ans[anc]=d;
// if(dis[x][toward]) return d+dis[x][toward];
// printf("DFS(%d,%d,%d,%d)\n",x,f,d,anc);
// if(dgr[x]==1||e[x][0]!=f)
// {
// if(x==anc&&d) return d;
// return DFS(e[x][0],x,d+1,anc,0);
//// if(!dis[x][0]) dis[x][0]=DFS(e[x][0],x,d+1,x);
//// return d+dis[x][0];
// }
// else
// {
// return DFS(e[x][1],x,d+1,anc,1);
//// if(!dis[x][1]) dis[x][1]=DFS(e[x][1],x,d+1,x);
//// return d+dis[x][1];
// }
//}
int main()
{
freopen("ex_garden2.in","r",stdin);
// freopen(".out","w",stdout);
n=read(), m=read(), P=read()+1;
for(int i=1,u,v; i<=m; ++i)
{
u=read()+1, v=read()+1;
if(dgr[u]<2) ++dgr[u], AddEdge(u,v);
if(dgr[v]<2) ++dgr[v], AddEdge(v,u);
}
if(n<=1000) {Subtask1::n=n, Subtask1::m=m, Subtask1::Main(); return 0;}
// for(int i=1; i<=n; ++i) if(!dis[i][0]) dis[i][0]=DFS(i,i,0,i,0);
// for(int i=1; i<=n; ++i) printf("dis[%d]: 0:%d 1:%d\n",i-1,dis[i][0],dis[i][1]);
// for(int Q=read(),K; Q--; )
// {
// K=read();
//
// }
return 0;
}
B
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=10004,M=2e6+5;
int n,m,len[N];
char s[N],A[N][N],B[N][N];
namespace Subtask1
{
int cnt,Enum,H[N],nxt[M],to[M],dgr[N],val[N];
char s[N];
bool vis[N];
std::queue<int> q;
inline bool OK(int p,int l,char *t)
{
for(int i=1; i<=l; ++i) if(s[p+i]!=t[i]) return 0;
return 1;
}
inline int Encode(char *s)
{
int res=0;
for(int i=1; i<=n; ++i) res=(res<<2)+(s[i]-'A');
return res;
}
inline void AddEdge(int u,int v)
{
++dgr[u], to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
void Init_S(int now)
{
if(now>n)
{
int hs=Encode(s),hs2;
// printf("%s:%d\n",s+1,hs);
for(int i=1; i<n; ++i)
if(s[i]!=s[i+1])
std::swap(s[i],s[i+1]), hs2=Encode(s), AddEdge(hs,hs2), std::swap(s[i],s[i+1]);
for(int p=0; p<n; ++p)
for(int i=1; i<=m; ++i)
if(p+len[i]<=n && OK(p,len[i],A[i]))
{
// printf("%s->",s+1);
for(int j=1; j<=len[i]; ++j) s[p+j]=B[i][j];
// printf("%s\n",s+1);
hs2=Encode(s), AddEdge(hs,hs2);
for(int j=1; j<=len[i]; ++j) s[p+j]=A[i][j];
}
}
else for(int i=0; i<4; ++i) s[now]='A'+i, Init_S(now+1);
}
void DFS(int x)
{
vis[x]=1, ++cnt;
for(int i=H[x]; i; i=nxt[i])
if(!vis[to[i]]) DFS(to[i]);
}
void Main()
{
Init_S(1); char tmp[7]={"DDDDDD"};
int tot=Encode(tmp);
for(int i=0; i<=tot; ++i) val[i]=1;
for(int i=0; i<=tot; ++i) if(!dgr[i]) q.push(i);
for(int i=0; i<=tot; ++i) if(dgr[i]==1) q.push(i);
int res=0;
while(!q.empty())
{
int x=q.front(); q.pop();
res=std::max(res,val[x]);
// printf("now:%d\n",x);
for(int v,i=H[x]; i; i=nxt[i])
if(dgr[v=to[i]]>1)
{
val[v]=std::max(val[v],val[x]+1);
res=std::max(res,val[v]);
// printf("%d->%d val:%d\n",x,v,val[v]);
if(!--dgr[v]||dgr[v]==1) q.push(v);
}
}
for(int i=0; i<=tot; ++i)
if(!vis[i]) cnt=0, DFS(i), res=std::max(res,cnt);
printf("%d\n",res);
}
}
int main()
{
// freopen("ex_return2.in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1; i<=m; ++i) scanf("%s%s",A[i]+1,B[i]+1), len[i]=strlen(A[i]+1);
if(n<=5) Subtask1::Main();
// printf("%lld\n",Ans);
return 0;
}
C
#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=2e5+5;
int n,W[N],Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],dis[N];
double Ans;
std::pair<int,int> A[N];
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AddEdge(int w,int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
void DFS(int x,int f,int d)
{
Ans+=1.0*pow(d,1.5)*W[x];
for(int i=H[x]; i; i=nxt[i])
if(to[i]!=f) DFS(to[i],x,d+len[i]);
}
int main()
{
// freopen("ex_airport2.in","r",stdin);
// freopen(".out","w",stdout);
n=read();
for(int i=1; i<=n; ++i) W[i]=read();
for(int i=1; i<n; ++i) AddEdge(read(),read(),read());
double res=1e18;
if(n<=5000)
{
for(int i=1; i<=n; ++i)
Ans=0, DFS(i,i,0), res=std::min(res,Ans);
}
else
{
for(int i=1; i<=n; ++i) A[i]=std::make_pair(W[i],i);
std::sort(A+1,A+1+n,std::greater<std::pair<int,int> >());
for(int T=1,v; T<=250; ++T)
Ans=0, DFS(A[T].second,A[T].second,0), res=std::min(res,Ans);
}
printf("%.7lf\n",res);
return 0;
}