这里会显示出您选择的修订版和当前版本之间的差别。
后一修订版 | 前一修订版 | ||
2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1 [2021/03/24 20:39] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1 [2021/03/29 10:28] (当前版本) jxm2001 [题解] |
||
---|---|---|---|
行 3: | 行 3: | ||
[[https://codeforces.com/contest/1495|比赛链接]] | [[https://codeforces.com/contest/1495|比赛链接]] | ||
- | ===== E. Enormous XOR ===== | + | ===== C. Garden of the Sun ===== |
==== 题意 ==== | ==== 题意 ==== | ||
+ | 给定一些黑格和一些白格,要求将一些白格转化为黑格,使得所有黑格连通但不出现环路。 | ||
+ | 题目保证以起始时以每个黑格为中心的 $3\times 3$ 范围内没有其他黑格。 | ||
==== 题解 ==== | ==== 题解 ==== | ||
+ | 当 $n\equiv 1\bmod 3$ 时,考虑将第 $1,4,7\cdots$ 行染成黑色,然后对第 $3k+2,3k+3$ 行的每列,最多只有一个黑格。 | ||
+ | 如果第 $3k+2,3k+3$ 行间存在黑格,直接将两行的任意一个黑格所在列全染黑,否则将两行的第一列染黑。易知这样即可完成构造。 | ||
+ | |||
+ | 当 $n\not\equiv 1\bmod 3$ 时,将 $1,4,7\cdots$ 行换成第 $2,5,8\cdots$ 行处理即可。 | ||
<hidden 查看代码> | <hidden 查看代码> | ||
<code cpp> | <code cpp> | ||
+ | const int MAXN=505; | ||
+ | char buf[MAXN][MAXN]; | ||
+ | int main() | ||
+ | { | ||
+ | int T=read_int(); | ||
+ | while(T--){ | ||
+ | int n=read_int(),m=read_int(); | ||
+ | _for(i,0,n)scanf("%s",buf[i]); | ||
+ | int s1,s2; | ||
+ | if(n%3==1){ | ||
+ | s1=0; | ||
+ | s2=2; | ||
+ | } | ||
+ | else{ | ||
+ | s1=1; | ||
+ | s2=3; | ||
+ | } | ||
+ | for(int i=s1;i<n;i+=3)_for(j,0,m)buf[i][j]='X'; | ||
+ | for(int i=s2;i<n;i+=3){ | ||
+ | bool flag=false; | ||
+ | _for(j,0,m){ | ||
+ | if(buf[i-1][j]=='X'||buf[i][j]=='X'){ | ||
+ | buf[i-1][j]=buf[i][j]='X'; | ||
+ | flag=true; | ||
+ | break; | ||
+ | } | ||
+ | } | ||
+ | if(!flag) | ||
+ | buf[i-1][0]=buf[i][0]='X'; | ||
+ | } | ||
+ | _for(i,0,n)puts(buf[i]); | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
+ | </code> | ||
+ | </hidden> | ||
+ | ===== D. BFS Trees ===== | ||
+ | |||
+ | ==== 题意 ==== | ||
+ | |||
+ | 给定一个连通图,定义以点 $x$ 为根的 $\text{BFS}$ 树是生成树且树上所有点到 $x$ 的距离等于连通图该点到 $x$ 的距离。 | ||
+ | |||
+ | 定义 $f(x,y)$ 表示既满足是以点 $x$ 为根的 $\text{BFS}$ 树同时也是以点 $y$ 为根的 $\text{BFS}$ 树的生成树的个数。 | ||
+ | |||
+ | ==== 题解 ==== | ||
+ | |||
+ | 首先给出结论:假定 $x,y$ 之间有超过一条最短路径,则 $f(x,y)=0$。 | ||
+ | |||
+ | 因为对于 $x,y$ 之间最短路上的点 $u$,必有 $\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,y)$,易知树上满足该条件的点仅 $\text{dis}(x,y)+1$ 个。 | ||
+ | |||
+ | 假如 $x,y$ 之间有超过一条最短路径,则图中满足 $\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,y)$ 的点必然超过 $\text{dis}(x,y)+1$ 个,矛盾。 | ||
+ | |||
+ | 接下来仅考虑 $x,y$ 之间仅有一条最短路的情况,首先易知生成树一定包含 $x,y$ 之间的最短路。 | ||
+ | |||
+ | 接下来对除最短路外原图中的每条边 $u\to v$,假如保留该边,则必有 $\text{dis}(x,u)=\text{dis}(x,v)\pm 1,\text{dis}(y,u)=\text{dis}(y,v)\pm 1$。 | ||
+ | |||
+ | 假如 $\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,v)+\text{dis}(v,y)$,则 $u,v$ 必然在 $x\to y$ 的路径上,矛盾。 | ||
+ | |||
+ | 于是为每个不在最短路上的结点指定一个父结点即可,答案即为所有点的所有可选父结点的个数的乘积。 | ||
+ | |||
+ | 设当前结点为 $u$,父结点为 $v$,则父结点应该满足 $\text{dis}(x,u)=\text{dis}(x,v)+1$ 且 $\text{dis}(y,u)=\text{dis}(y,v)+1$。 | ||
+ | |||
+ | 于是可以 $O(m)$ 计算出每个 $f(x,y)$,总时间复杂度 $O(n^2m)$。 | ||
+ | |||
+ | <hidden 查看代码> | ||
+ | <code cpp> | ||
+ | const int MAXN=405,MAXM=605,Mod=998244353; | ||
+ | struct Edge{ | ||
+ | int to,next; | ||
+ | }edge[MAXM<<1]; | ||
+ | int head[MAXN],edge_cnt,dis[MAXN][MAXN]; | ||
+ | void Insert(int u,int v){ | ||
+ | edge[++edge_cnt]=Edge{v,head[u]}; | ||
+ | head[u]=edge_cnt; | ||
+ | } | ||
+ | int main() | ||
+ | { | ||
+ | int n=read_int(),m=read_int(); | ||
+ | mem(dis,127/3); | ||
+ | _rep(i,1,n)dis[i][i]=0; | ||
+ | _for(i,0,m){ | ||
+ | int u=read_int(),v=read_int(); | ||
+ | dis[u][v]=dis[v][u]=1; | ||
+ | Insert(u,v);Insert(v,u); | ||
+ | } | ||
+ | _rep(k,1,n)_rep(i,1,n)_rep(j,1,n) | ||
+ | dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); | ||
+ | _rep(x,1,n){ | ||
+ | _rep(y,1,n){ | ||
+ | int ans=1,cnt=0; | ||
+ | _rep(u,1,n){ | ||
+ | if(dis[x][u]+dis[u][y]==dis[x][y])cnt++; | ||
+ | else{ | ||
+ | int cnt2=0; | ||
+ | for(int i=head[u];i;i=edge[i].next){ | ||
+ | int v=edge[i].to; | ||
+ | if(dis[x][u]==dis[x][v]+1&&dis[y][u]==dis[y][v]+1) | ||
+ | cnt2++; | ||
+ | } | ||
+ | ans=1LL*ans*cnt2%Mod; | ||
+ | } | ||
+ | } | ||
+ | space(cnt==dis[x][y]+1?ans:0); | ||
+ | } | ||
+ | puts(""); | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
+ | </code> | ||
+ | </hidden> | ||
+ | |||
+ | ===== E. Qingshan and Daniel ===== | ||
+ | |||
+ | ==== 题意 ==== | ||
+ | |||
+ | 给定一个圈,圈上有两个队伍的人,每个人有 $a_i$ 张卡。 | ||
+ | |||
+ | 从第一个人开始弃一张卡,然后顺时针找到下一个不同队伍的且手牌不为零的人,继续弃卡,直到有一个队伍没发弃卡为止。 | ||
+ | |||
+ | 问游戏结束时每个人手上的卡。 | ||
+ | |||
+ | ==== 题解 ==== | ||
+ | |||
+ | 不难发现当两个队伍卡牌总数相同时第一个人所在队伍败北,否则卡片总数少的队伍败北。 | ||
+ | |||
+ | 另外对于败北的队伍,显然每个人的卡牌数量为 $0$。 | ||
+ | |||
+ | 接下来考虑获胜队伍的每个人的卡牌数量,首先如果第一个人在获胜队伍,则他先弃一张卡,轮到失败队伍。 | ||
+ | |||
+ | 接下来仅考虑失败队伍先开始弃卡的情况。 | ||
+ | |||
+ | 不难发现失败队伍的每个人弃牌的顺序不影响最终结果,于是将每个人弃的卡转移到下一个人处理即可。 | ||
+ | |||
+ | 考虑到一次遍历圆环可能会仍有剩余卡牌,于是二重遍历圆环,时间复杂度 $O(n)$。 | ||
+ | |||
+ | <hidden 查看代码> | ||
+ | <code cpp> | ||
+ | const int MAXN=5e6+5,Mod=1e9+7; | ||
+ | int seed,base; | ||
+ | int rnd(){ | ||
+ | int ret=seed; | ||
+ | seed=(1LL*seed*base+233)%Mod; | ||
+ | return ret; | ||
+ | } | ||
+ | int a[MAXN],b[MAXN],t[MAXN]; | ||
+ | LL s[2]; | ||
+ | int main() | ||
+ | { | ||
+ | int n=read_int(),m=read_int(),pos=0; | ||
+ | _for(i,0,m){ | ||
+ | int p=read_int(),k=read_int(); | ||
+ | seed=read_int(); | ||
+ | base=read_int(); | ||
+ | while(pos<p){ | ||
+ | t[pos]=rnd()%2; | ||
+ | a[pos]=b[pos]=rnd()%k+1; | ||
+ | pos++; | ||
+ | } | ||
+ | } | ||
+ | _for(i,0,n) | ||
+ | s[t[i]]+=a[i]; | ||
+ | int flag=(s[0]^s[1])?(s[0]<s[1]):(!t[0]); | ||
+ | if(t[0]==flag) | ||
+ | b[0]--; | ||
+ | LL pre=0; | ||
+ | _for(j,0,2){ | ||
+ | _for(i,0,n){ | ||
+ | if(t[i]!=flag){ | ||
+ | pre+=b[i]; | ||
+ | b[i]=0; | ||
+ | } | ||
+ | else{ | ||
+ | int temp=b[i]<pre?b[i]:pre; | ||
+ | b[i]-=temp; | ||
+ | pre-=temp; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | int ans=1; | ||
+ | _for(i,0,n) | ||
+ | ans=1LL*ans*(((a[i]-b[i])^(1LL*(i+1)*(i+1)))%Mod+1)%Mod; | ||
+ | enter(ans); | ||
+ | return 0; | ||
+ | } | ||
+ | </code> | ||
+ | </hidden> | ||
+ | |||
+ | ===== F. Squares ===== | ||
+ | |||
+ | ==== 题意 ==== | ||
+ | |||
+ | 给定一个长度为 $n$ 的序列,每个元素有属性 $p_i,a_i,b_i$,其中 $p_i$ 为 $1\sim n$ 的排列。 | ||
+ | |||
+ | 每轮起点为第一个元素,假设当前位于位置 $i$,则可以花费 $a_i$ 到达 $i+1$ 或花费 $b_i$ 到达 $i$ 右边第一个 $p_j\gt j$ 的位置。 | ||
+ | |||
+ | 当 $i+1\gt n$ 时花费 $a_i$ 可以到达终点,当 $j$ 不存在时花费 $b_i$ 也可以到达终点。 | ||
+ | |||
+ | 给定一个集合 $S$,初始时为空。 | ||
+ | |||
+ | 每轮为集合加入或删除一个元素,问在遍历集合中所有元素的前提下到达终点的最小花费。 | ||
+ | |||
+ | ==== 题解 ==== | ||
+ | |||
+ | 接下来对原图,设每个点连出一条费用为 $a_i$ 的边和费用为 $b_i$ 的边指向对应顶点,同时 $a_0=0,b_0=\infty,p_0=n+1$。 | ||
+ | |||
+ | 于是原题转化为求从 $0$ 号结点到终点的最短路径。 | ||
+ | |||
+ | 将每个点向左边第一个 $p_j\gt j$ 的元素连一条边,不难发现可以得到一棵树,其中 $0$ 为根节点。 | ||
+ | |||
+ | 若当前处于结点 $i$。如果走 $a$ 边则接下来一定会遍历 $i$ 在树上的所有儿子结点,如果走 $b$ 边则将跳过 $i$ 所在的子树的所有结点。 | ||
+ | |||
+ | 设最短路中所有 $a$ 边的起点构成的集合为 $T$,此时总费用为 | ||
+ | |||
+ | $$ | ||
+ | \sum_{i\in T}a_i+\sum_{i\not\in T,f(i)\in T}b_i | ||
+ | $$ | ||
+ | |||
+ | 设 $c_i=a_i-b_i+\sum_{j\in \text{child}(i)}b_j,c_0=\sum_{i\in \text{child}(0)}b_i$,则上式化简为 $\sum_{i\in T}c_i$。 | ||
+ | |||
+ | 设 $\text{dp}(i)$ 表示 $i\in T$ 时 $T$ 集合中 $i$ 的子树结点的 $c_i$ 和的最小值,则有状态转移方程 | ||
+ | |||
+ | $$ | ||
+ | \text{dp}(i)=c_i+\sum_{j\in \text{child}(i)}\min(\text{dp}(j),0) | ||
+ | $$ | ||
+ | |||
+ | 对每个 $S$ 或 $T$ 中的元素 $u$,该元素的父结点 $p$ 一定属于 $T$,否则不可能进入 $p$ 的子树即不可能到达 $u$。 | ||
+ | |||
+ | 于是 $T$ 一定是连通集且 $S$ 的父结点一定属于 $T$,设 $H$ 集合为满足该限制的最小集合,于是最小费用为 | ||
+ | |||
+ | $$ | ||
+ | \begin{equation}\begin{split} | ||
+ | \sum_{i\in T}c_i&=\sum_{i\in H}\left(c_i+\sum_{j\not\in H,j\in \text{child}(i)}\min(\text{dp}(j),0)\right) \\ | ||
+ | &=\sum_{i\in H}\left(\text{dp}(i)-\sum_{j\in H,j\in \text{child}(i)}\min(\text{dp}(j),0)\right)\\ | ||
+ | &=\text{dp}(0)+\sum_{i\neq 0,i\in H}(\text{dp}(i)-\min(\text{dp}(i),0))\\ | ||
+ | &=\text{dp}(0)+\sum_{i\neq 0,i\in H}\max(\text{dp}(i),0) | ||
+ | \end{split}\end{equation} | ||
+ | $$ | ||
+ | |||
+ | 接下来考虑如何维护 $H$ 集合即可,将点权转移为到连向父结点的边权,发现可以用类似构建虚树 $\text{dp}$ 的方式维护最小连通集合。 | ||
+ | |||
+ | 另外由于本题建树的特殊性,使得可以直接让 $\text{dfs}$ 等于结点编号。时间复杂度 $O(n\log n)$。 | ||
+ | |||
+ | <hidden 查看代码> | ||
+ | <code cpp> | ||
+ | typedef set<int>::iterator iter; | ||
+ | const int MAXN=2e5+5; | ||
+ | struct Edge{ | ||
+ | int to,next; | ||
+ | }edge[MAXN]; | ||
+ | int head[MAXN],edge_cnt; | ||
+ | void Insert(int u,int v){ | ||
+ | edge[++edge_cnt]=Edge{v,head[u]}; | ||
+ | head[u]=edge_cnt; | ||
+ | } | ||
+ | int st[MAXN],tp,p[MAXN],a[MAXN],b[MAXN],cnt[MAXN]; | ||
+ | LL c[MAXN],dp[MAXN]; | ||
+ | bool vis[MAXN]; | ||
+ | namespace LCA{ | ||
+ | int d[MAXN],sz[MAXN],f[MAXN]; | ||
+ | int h_son[MAXN],mson[MAXN],p[MAXN]; | ||
+ | LL dis[MAXN]; | ||
+ | void dfs_1(int u,int fa,int depth){ | ||
+ | sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0; | ||
+ | dp[u]=c[u]; | ||
+ | for(int i=head[u];i;i=edge[i].next){ | ||
+ | int v=edge[i].to; | ||
+ | dfs_1(v,u,depth+1); | ||
+ | dp[u]+=min(dp[v],0LL); | ||
+ | sz[u]+=sz[v]; | ||
+ | if(sz[v]>mson[u]) | ||
+ | h_son[u]=v,mson[u]=sz[v]; | ||
+ | } | ||
+ | } | ||
+ | void dfs_2(int u,int top){ | ||
+ | p[u]=top; | ||
+ | if(mson[u])dfs_2(h_son[u],top); | ||
+ | for(int i=head[u];i;i=edge[i].next){ | ||
+ | int v=edge[i].to; | ||
+ | if(v==h_son[u]) | ||
+ | continue; | ||
+ | dfs_2(v,v); | ||
+ | } | ||
+ | } | ||
+ | void dfs_3(int u){ | ||
+ | dis[u]+=max(dp[u],0LL); | ||
+ | for(int i=head[u];i;i=edge[i].next){ | ||
+ | int v=edge[i].to; | ||
+ | dis[v]+=dis[u]; | ||
+ | dfs_3(v); | ||
+ | } | ||
+ | } | ||
+ | void init(int root){ | ||
+ | dfs_1(root,-1,0); | ||
+ | dfs_2(root,root); | ||
+ | for(int i=head[root];i;i=edge[i].next) | ||
+ | dfs_3(edge[i].to); | ||
+ | } | ||
+ | int query_lca(int u,int v){ | ||
+ | while(p[u]!=p[v]){ | ||
+ | if(d[p[u]]<d[p[v]])swap(u,v); | ||
+ | u=f[p[u]]; | ||
+ | } | ||
+ | return d[u]<d[v]?u:v; | ||
+ | } | ||
+ | LL query_dis(int u,int v){ | ||
+ | return dis[u]+dis[v]-dis[query_lca(u,v)]*2; | ||
+ | } | ||
+ | }; | ||
+ | int main() | ||
+ | { | ||
+ | int n=read_int(),q=read_int(); | ||
+ | _rep(i,1,n)p[i]=read_int(); | ||
+ | _rep(i,1,n)a[i]=read_int(); | ||
+ | _rep(i,1,n)b[i]=read_int(); | ||
+ | p[0]=n+1; | ||
+ | _rep(i,1,n){ | ||
+ | while(p[st[tp]]<p[i])tp--; | ||
+ | Insert(st[tp],i); | ||
+ | st[++tp]=i; | ||
+ | } | ||
+ | _rep(u,0,n){ | ||
+ | c[u]=a[u]-b[u]; | ||
+ | for(int i=head[u];i;i=edge[i].next){ | ||
+ | int v=edge[i].to; | ||
+ | c[u]+=b[v]; | ||
+ | } | ||
+ | } | ||
+ | LCA::init(0); | ||
+ | set<int> s; | ||
+ | s.insert(0); | ||
+ | cnt[0]++; | ||
+ | LL ans=0; | ||
+ | while(q--){ | ||
+ | int u=read_int(),p=LCA::f[u]; | ||
+ | if(!vis[u]){ | ||
+ | cnt[p]++; | ||
+ | if(cnt[p]==1){ | ||
+ | iter rig=s.upper_bound(p); | ||
+ | iter lef=--rig; | ||
+ | rig++; | ||
+ | rig=(rig==s.end())?s.begin():rig; | ||
+ | ans+=LCA::query_dis(p,*rig); | ||
+ | ans-=LCA::query_dis(*lef,*rig); | ||
+ | ans+=LCA::query_dis(*lef,p); | ||
+ | s.insert(p); | ||
+ | } | ||
+ | } | ||
+ | else{ | ||
+ | cnt[p]--; | ||
+ | if(cnt[p]==0){ | ||
+ | iter rig=s.find(p); | ||
+ | iter lef=--rig; | ||
+ | rig++;rig++; | ||
+ | rig=(rig==s.end())?s.begin():rig; | ||
+ | ans-=LCA::query_dis(p,*rig); | ||
+ | ans+=LCA::query_dis(*lef,*rig); | ||
+ | ans-=LCA::query_dis(*lef,p); | ||
+ | s.erase(p); | ||
+ | } | ||
+ | } | ||
+ | vis[u]=!vis[u]; | ||
+ | enter(dp[0]+ans/2); | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
</code> | </code> | ||
</hidden> | </hidden> |