可以发现,本题就是根据要求在环上顺时针或者逆时针走动,那么假设当前的位置是 p,那么逆时针走 x 个到达的位置是 (p?1x)modn1,顺时针走 x 个到达的位置是 (p?1?x)modn1。模拟每一次的指令,判断每次是走顺时针还是逆时针即可。
实现上要注意,C 中对于模运算的定义与数学中的模运算是不同的,我们知道在数学上 amodb=a?b???b??a???,问题就在于 ??b??a??? 的计算上。在大部分编译器中,两个 int 相除,是直接丢弃小数位得到答案的,这就导致了在 C 中两个 int 相除并非总是得到 ??b??a???(例如 ?2???3??=?1),所以 a 为负数的情况下,取模会存在问题,amodb 不一定能够得到一个非负整数,但是我们可以保证这个数在 (?∣b∣,∣b∣) 内,在所以实际需要取模的时候,采用 ((amodb)b)modb 来得到非负整数。
可以考虑对于每一个人 (u,v),都使用 BFS 找出 u→v 的路径,然后更新路径上有满足条件的点即可。至于找出路径的方法,只需要从 u 开始 BFS,并且在 BFS 中从 a 扩展到 b 时,记录 a 的前继为 b,最后我们从 v 开始,不断地找前继,最终到 u,这样就还原出了路径,你可能还需要记录一个到点 v 的距离来帮助判断路径上的点是否满足条件。
// Created by Sengxian on 2016/11/23.// Copyright (c) 2016年 Sengxian. All rights reserved.#include <bits/stdc .h>usingnamespacestd;constintMAX_N=3000003;structedge{edge*next;intto;edge(edge*next=NULL,intto=0):next(next),to(to){}}pool[MAX_N*2],*pit=pool,*first[MAX_N];intn,m,w[MAX_N],ans[MAX_N];intdfn[MAX_N],fa[MAX_N],s[MAX_N],bel[MAX_N],dep[MAX_N],chainDep[MAX_N];voiddfs1(intu,intf){fa[u]=f,s[u]=1;for(edge*e=first[u];e;e=e->next)if(e->to!=f){dep[e->to]=dep[u]1;dfs1(e->to,u);s[u] =s[e->to];}}vector<int>chains[MAX_N];voiddfs2(intu,intnum){staticinttsp=0;dfn[u]=tsp,bel[u]=num;chains[num].push_back(u);intmx=-1,id=0;for(edge*e=first[u];e;e=e->next)if(e->to!=fa[u]&&s[e->to]>mx)mx=s[id=e->to];if(mx==-1)return;chainDep[id]=chainDep[u]1;dfs2(id,num);for(edge*e=first[u];e;e=e->next)if(e->to!=fa[u]&&e->to!=id)chainDep[e->to]=0,dfs2(e->to,e->to);}typedefpair<int,int>state;vector<state>mark1[MAX_N],mark2[MAX_N];#define sz(x) ((int)x.size())intdis(intu,intv){intd=0;while(bel[u]!=bel[v]){if(dep[bel[u]]<dep[bel[v]])swap(u,v);d =chainDep[u]1;u=fa[bel[u]];}if(dep[v]<dep[u])swap(u,v);d =chainDep[v]-chainDep[u]1;returnd-1;}voidsolve(intu,intv){intdisU=0,disV=dis(u,v),d,t;while(bel[u]!=bel[v]){if(dep[bel[u]]>dep[bel[v]]){mark1[u].push_back(state(disU-(sz(chains[bel[u]])-1-chainDep[u]),1));disU =chainDep[u]1;u=fa[bel[u]];}else{d=disV-chainDep[v];mark2[bel[v]].push_back(state(d,1));if(chainDep[v]1!=sz(chains[bel[v]])){t=chains[bel[v]][chainDep[v]1];mark2[t].push_back(state(d,-1));}disV-=chainDep[v]1;v=fa[bel[v]];}}if(dep[u]<dep[v]){mark2[u].push_back(state(disU-chainDep[u],1));if(chainDep[v]1!=sz(chains[bel[v]])){t=chains[bel[v]][chainDep[v]1];mark2[t].push_back(state(disU-chainDep[u],-1));}}else{mark1[u].push_back(state(disU-(sz(chains[bel[u]])-1-chainDep[u]),1));if(v!=bel[v]){mark1[fa[v]].push_back(state(disU-(sz(chains[bel[u]])-1-chainDep[u]),-1));}}}staticintcnt[MAX_N*2],ti[MAX_N*2];intnow_t=0;inlineintget(intx){if(ti[x]!=now_t)ti[x]=now_t,cnt[x]=0;returncnt[x];}inlinevoidadd(intx,intv){if(ti[x]!=now_t)ti[x]=now_t,cnt[x]=0;cnt[x] =v;}voidcal(){for(inttt=0;tt<n;tt)if(bel[tt]==tt){intlen=chains[tt].size();now_t;for(inti=0;i<len;i){for(intj=0;j<(int)mark2[chains[tt][i]].size();j)add(mark2[chains[tt][i]][j].firstn,mark2[chains[tt][i]][j].second);ans[chains[tt][i]] =get(w[chains[tt][i]]-in);}now_t;for(inti=len-1;i>=0;--i){for(intj=0;j<(int)mark1[chains[tt][i]].size();j){add(mark1[chains[tt][i]][j].firstn,mark1[chains[tt][i]][j].second);}ans[chains[tt][i]] =get(w[chains[tt][i]]-(len-1-i)n);}}}intmain(){scanf('%d%d',&n,&m);for(inti=0,u,v;i<n-1;i){scanf('%d%d',&u,&v),--u,--v;first[u]=new(pit)edge(first[u],v);first[v]=new(pit)edge(first[v],u);}for(inti=0;i<n;i)scanf('%d',wi);dfs1(0,-1),dfs2(0,0);for(inti=0,u,v;i<m;i){scanf('%d%d',&u,&v),u--,v--;solve(u,v);}cal();for(inti=0;i<n;i)printf('%d%c',ans[i],i1==n?'\n':' ');return0;}
正解
// Created by Sengxian on 2016/11/23.// Copyright (c) 2016年 Sengxian. All rights reserved.#include <bits/stdc .h>usingnamespacestd;typedeflonglongll;inlineintreadInt(){staticintn,ch;n=0,ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))n=n*10ch-'0',ch=getchar();returnn;}constintMAX_N=3000003,MAX_M=3000003;structedge{edge*next;intto;edge(edge*next=NULL,intto=0):next(next),to(to){}}pool[(MAX_NMAX_M)*2],*pit=pool,*first[MAX_N],*qFirst[MAX_N];intn,m,w[MAX_N],w1[MAX_N],w2[MAX_N];intqueryU[MAX_M],queryV[MAX_M],queryLCA[MAX_N],queryAns[MAX_M];intfa[MAX_N],s[MAX_N],d[MAX_N],dfn[MAX_N],seq[MAX_N];namespacedisjoint_union{intufa[MAX_N];inlinevoidinit(intn){for(inti=0;i<n;i)ufa[i]=i;}inlineintfind(intx){returnufa[x]==x?x:ufa[x]=find(ufa[x]);}inlinevoidunite(intx,inty){x=find(x),y=find(y);ufa[x]=y;}}usingnamespacedisjoint_union;voiddfs(intu,intfa){staticboolvis[MAX_N];staticinttsp=0;vis[u]=true,::fa[u]=fa,s[u]=1;dfn[u]=tsp,seq[tsp]=u;for(edge*e=first[u];e;e=e->next)if(e->to!=fa){d[e->to]=d[u]1;dfs(e->to,u);unite(e->to,u);s[u] =s[e->to];}for(edge*q=qFirst[u];q;q=q->next){intv=queryU[q->to]==u?queryV[q->to]:queryU[q->to];if(vis[v])queryLCA[q->to]=find(v);}}typedefpair<int,int>state;vector<state>mark1[MAX_N],mark2[MAX_N],pos[MAX_N];intcnt1[MAX_N*4],cnt2[MAX_N*4];inlinevoidgiveTag(intu,intv,ints,boolflag=false){if(d[u]<=d[v]){mark1[v].push_back(state(s-d[u],1));if(fa[u]>=0)mark1[fa[u]].push_back(state(s-d[u],-1));}else{mark2[u].push_back(state(sd[u],1));if(flag)mark2[v].push_back(state(sd[u],-1));elseif(fa[v]>=0)mark2[fa[v]].push_back(state(sd[u],-1));}}voidsolve(){for(inti=0;i<n;i)w1[i]=w[i]-d[i];for(inti=0;i<n;i)w2[i]=w[i]d[i];for(inti=0,u,v,LCA;i<m;i){u=queryU[i],v=queryV[i],LCA=queryLCA[i];if(u==LCA||v==LCA)giveTag(u,v,0);elsegiveTag(u,LCA,0,true),giveTag(LCA,v,d[u]-d[LCA]);}for(inti=0;i<n;i){pos[dfn[i]].push_back(state(i,-1));pos[dfn[i]s[i]].push_back(state(i,1));}intdel=n*2;for(inti=0,u;i<n;i){u=seq[i];for(intj=0;j<(int)mark1[u].size();j)cnt1[mark1[u][j].firstdel] =mark1[u][j].second;for(intj=0;j<(int)mark2[u].size();j)cnt2[mark2[u][j].firstdel] =mark2[u][j].second;for(intj=0;j<(int)pos[i1].size();j){statest=pos[i1][j];queryAns[st.first] =cnt1[w1[st.first]del]*st.second;queryAns[st.first] =cnt2[w2[st.first]del]*st.second;}}}intmain(){n=readInt(),m=readInt();for(inti=0,u,v;i<n-1;i){u=readInt()-1,v=readInt()-1;first[u]=new(pit)edge(first[u],v);first[v]=new(pit)edge(first[v],u);}for(inti=0;i<n;i)w[i]=readInt();for(inti=0;i<m;i){queryU[i]=readInt()-1,queryV[i]=readInt()-1;qFirst[queryU[i]]=new(pit)edge(qFirst[queryU[i]],i);qFirst[queryV[i]]=new(pit)edge(qFirst[queryV[i]],i);}init(n),dfs(0,-1);solve();for(inti=0;i<n;i)printf('%d%c',queryAns[i],i1==n?'\n':' ');return0;}
吐槽
考试的时候写了个树链剖分,考完以后写了个线性做法,mdzz 跑的时间居然一样。
换教室 classroom
知识点
数学期望,动态规划,最短路
分析
首先有 v≤300,使用 floyd 算法求出两两点对之间的最短路。接着可以发现,这是一个经典的序列 DP 的模型,每个点有选或者不选两种决策,那么根据期望的线性性,容易发现每次 DP 只与最后两个选不选有关,考虑 dp?i,j,k?? 为到第 i 个点,已经选了 j 个,k 表示第 i 个点是否选择换教室,那么转移就是根据后两个是否选择更换,来分情况讨论(设 p?i?? 为更换成功的概率,c?i?? 为不换的教室,d?i?? 为换的教室,G?i,j?? 为 i 与 j 之间的最短路):
// Created by Sengxian on 2016/11/23.// Copyright (c) 2016年 Sengxian. All rights reserved.#include <bits/stdc .h>usingnamespacestd;typedeflonglongll;inlineintreadInt(){staticintn,ch;n=0,ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))n=n*10ch-'0',ch=getchar();returnn;}constintMAX_N=20003,MAX_M=20003,MAX_V=3003;intn,m,v,e,c[MAX_N],d[MAX_N];doublep[MAX_N];intG[MAX_V][MAX_V];voidfloyd(){for(intk=0;k<v;k)for(inti=0;i<v;i)for(intj=0;j<v;j)G[i][j]=min(G[i][j],G[i][k]G[k][j]);}doubledp[MAX_N][MAX_M][2];voidsolve(){for(inti=0;i<n;i)for(intj=0;j<=m;j)dp[i][j][0]=dp[i][j][1]=1e30;dp[0][0][0]=0.0,dp[0][1][1]=0.0;for(inti=1;i<n;i)for(intj=0;j<=m;j){dp[i][j][0]=min(dp[i-1][j][0]G[c[i-1]][c[i]],dp[i-1][j][1]p[i-1]*G[d[i-1]][c[i]](1-p[i-1])*G[c[i-1]][c[i]]);if(j)dp[i][j][1]=min(dp[i-1][j-1][0]p[i]*G[c[i-1]][d[i]](1-p[i])*G[c[i-1]][c[i]],dp[i-1][j-1][1]p[i]*p[i-1]*G[d[i-1]][d[i]](1-p[i])*p[i-1]*G[d[i-1]][c[i]]p[i]*(1-p[i-1])*G[c[i-1]][d[i]](1-p[i])*(1-p[i-1])*G[c[i-1]][c[i]]);}doubleans=1e30;for(inti=0;i<=m;i)ans=min(ans,min(dp[n-1][i][0],dp[n-1][i][1]));printf('%.2f\n',ans);}intmain(){n=readInt(),m=readInt(),v=readInt(),e=readInt();for(inti=0;i<n;i)c[i]=readInt()-1;for(inti=0;i<n;i)d[i]=readInt()-1;for(inti=0;i<n;i)scanf('%lf',pi);memset(G,0x3f,sizeofG);for(inti=0,f,t,c;i<e;i){f=readInt()-1,t=readInt()-1,c=readInt();G[f][t]=G[t][f]=min(G[f][t],c);}for(inti=0;i<v;i)G[i][i]=0;floyd();solve();return0;}
总结
Day 1 的题还是有一定难度的,第二题是一个不错的题,放在这个位置有不小的震慑力,而且可以意外地让一批伪高手栽下跟头——想不出来正解,也打不出高级数据结构,结果爆 0。第三题如果熟悉期望 DP 的话,是一道比较简单的题,可见此题的目的主要还是用于普及一下数学期望,以便在后续比赛中出现。