2019.9.14 多校联考题解

T1.树上路径

题目

题目背景

Akari是一个普通的初中生。

题目描述

Akari的学校的校门前生长着一排$n$棵树，从西向东依次编号为$1,2,\dots ,n$。相邻两棵树间的距离都是$1$。

Akari上课的教学楼恰好在树$1$旁，所以每个课间，Akari都很想走出教室，上树活动。Akari会依次经过$m$棵树，从树$1$一路向东跳到树$n$。临近上课时，Akari会再次上树，经过$m$棵树从树$n$一路向西跳到树$1$，准备上课。由于Akari睡眠很充足，Akari每次跳跃至少会移动$k$的距离，因此Akari在上树前需要合理规划她的跳跃路线。我们称每次上树过程中Akari跳过的全部$m$棵树（包含树$1$和树$n$）的集合为一条树上路径。

Akari喜欢按不同的顺序观察各种树木，因此她每次上树时选择的树上路径不会与之前选择过的重复。这意味着，Akari不会选择之前的课间选过的树上路径，且在从树$n$跳回树$1$时，也不会沿这次跳到树n的树上路径原路返回。

如果一次课间开始时，Akari找不到符合条件的树上路径，那么她从此会放弃上树活动，开始专心学习。如果一次课间即将即将结束时，Akari还在树$n$且找不到符合条件的树上路径回到树$1$，她就会十分沮丧，选择逃课。

请你帮助Akari判断，她是否会在某个课间选择逃课。

输入

从文件phantasm.in中读入数据。

每个测试点可能包含多组数据。第一行一个正整数$T$，表示数据组数。

每组数据包括一行三个正整数$n,m,k$，含义见题目描述。

输出

输出到文件phantasm.out中。

对于每组数据，输出一行一个字符串。如果Akari会逃课，输出Yes，否则输出No。

请注意输出字符串的大小写。

样例1输入

3
10 3 2
5 3 1
15 5 3

样例1输出

No
Yes
No

样例1解释

第一组数据中，除了起点和终点外，合法的树上路径只能经过$3,4,5,6,7,8$这$6$棵树，所以合法的树上路径只有$6$种，经过$3$个课间后Akari就会停止上树活动。

第二组数据中，合法的树上路径有$3$种，Akari会在第$2$个课间结束时逃课。

第三组数据中，合法的树上路径有$10$种。

样例2输入

4
15 4 3
15 4 4
15 5 3
16 3 7

样例2输出

Yes
No
No
No

数据范围

提示

本题的输入数据可能很大，请避免使用过于缓慢的读入方式。

分析

不难发现当从$1$到$n$路径数为奇数时，这个人一定会逃课。

那么问题转换为计算从$1$到$n$的路径数的奇偶性。

考虑将这个问题转换为方程模型，即将数$N-1$分成$M-1$个部分，每个部分必须大于等于$K$的方案数。

则我们可列出这样的方程：

• $\forall i,x_i\ge K$；
• ${\sum }_{i=1}^{M-1}{x}_i=N-1$。

考虑将所有的$x_i$减掉$K-1$得到${x_i}^{\prime }$，则得到去掉第一个限制的方程：

• ${\sum }_{i=1}^N{x_i}^{\prime }=N-1-(M-1)(K-1)$。

显然通过隔板法算出这个方程的解的个数：$$\left(\genfrac{}{}{0ex}{}{N-1-(M-1)(K-1)-1}{M-1}\right)$$

到这里我们可以暴力判这个的奇偶性了，即用阶乘表示这个组合数，然后用类似快速幂的算法求出各个阶乘的2的个数作差，判断是否大于零即可。

当然如果要更快，我们可以用Lucas定理。

当$\left(\genfrac{}{}{0ex}{}{n}{m}\right)\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)$时，由Lucas定理，当且仅当二进制位下$m$的各位都不大于在$n$的对应位置上的值。此时我们发现$m$和$n$按位与时的结果必然是$m$。

参考代码

Lucas定理版

#include<cstdio>int main() {freopen("phantasm.in","r",stdin);freopen("phantasm.out","w",stdout);int T;scanf("%d",&T);while(T--) {int N,M,K;scanf("%d %d %d",&N,&M,&K);if(((N-2-(M-1)*(K-1))&(M-2))==(M-2))puts("Yes");else puts("No");}return 0;
}

暴力版

#include<cstdio>int Count_2(int x) {int sum=0;while(x) {sum+=x/2;x/=2;}return sum;
}int main() {freopen("phantasm.in","r",stdin);freopen("phantasm.out","w",stdout);int T;scanf("%d",&T);while(T--) {int N,M,K;scanf("%d %d %d",&N,&M,&K);M--;N-=(K*M+1);if(N<0) {puts("No");continue; }int s=Count_2(N+M-1)-Count_2(M-1)-Count_2(N);if(s>0)puts("No");else puts("Yes");}return 0;
}

T2.泳池

题目

题目背景

小A是个爱玩的女孩子。

暑假终于到了，小A决定请她的朋友们来游泳，她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险，有些地方水太深，有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。

题目描述

小A的城市里有$n$座工厂，编号分别为$1,2,\dots ,n$。工厂间连有$n-1$条双向管道，形成一个无向连通图，其中每条管道都有一定的长度，连接在两座不同的工厂间。

每座工厂都装有废水处理设施，工厂$i$的蓄水量记为$c_i$。由于工厂规模有限，工厂产生的废水必须经由管道输送到.另一座工厂进行处理。

工厂$u$将废水输送到工厂$v$处理时，所需的运输成本等于无向图中$u,v$间最短路径的长度，并且会产生$c_u-c_v$的额外成本（可能为负）。总成本等于运输成本与额外成本的和。

为了降低污染，在接下来的$q$天内，每一天只有一座工厂会产生废水。你需要确定这座工厂将废水输送到哪一座工厂进行处理，可使得总成本最小。由于选择可能不唯一，你只需输出最小的总成本。

输入

从文件skylines.in中读入数据。

第一行一个正整数$n$。

第二行$n$个正整数$c_i$。

下接$n-1$行，每行三个正整数$u,v,w$，表示一条双向管道两端工厂的编号及长度。

第$n+2$行一个正整数$q$。下接$q$行，每行一个正整数$x$，表示这一天进行生产的工厂的编号。

输出

输出到文件skylines.out中。

输出$q$行，每行一个整数，表示这一天总成本的最小值。

样例输入

5
7 7 6 9 9
2 5 5
2 3 1
4 1 1
1 2 2
4
2
5
3
4

样例输出

1
7
0
3

样例解释

第$1$天，工厂$2$输送到工厂$4$是一种最优方案，成本为$3+(-2)=1$。

第$2$天，工厂$5$输送到工厂$2$是一种最优方案，成本为$5+2=7$。

第$3$天，工厂$3$输送到工厂$2$是一种最优方案，成本为$1+(-1)=0$。

第$4$天，工厂$4$输送到工厂$1$是一种最优方案，成本为$1+2=3$。

数据范围

分析

显然我们必须采用离线的方式来回答询问

考虑将点权下放到路径上。对于一条从$u$到$v$的路径，设其长度$d(u,v)$，我们可以将其转为$d(u,v)+c_u-c_v$，可以证明$d(u,v)+c_u-c_v=d(u,w)+c_u-c_w+d(w,v)+c_w-c_v$。

考虑是一条链的情况：设$f_u$为$u$的最佳答案，则 f u = min ⁡ v = ̸ u { d ( u , v ) + c u − c v } f_u=\min_{v=\not u}\{d(u,v)+c_u-c_v\} fu​=minv≠​u​{d(u,v)+cu​−cv​}。

设$d_u$为$u$到$1$的距离，则 f u = min ⁡ u = ̸ v { min ⁡ v &lt; u { d u + c u − d v − c v } , min ⁡ v &gt; u { − d u + c u + d v − c v } } = min ⁡ u = ̸ v { d u + c u + min ⁡ v &lt; u { − d v − c v } , − d u + c u + min ⁡ v &gt; u { d v − c v } } f_u=\min_{u=\not v}\{\min_{v&lt;u}\{d_u+c_u-d_v-c_v\},\min_{v&gt;u}\{-d_u+c_u+d_v-c_v\}\}=\min_{u=\not v}\{d_u+c_u+\min_{v&lt;u}\{-d_v-c_v\},-d_u+c_u+\min_{v&gt;u}\{d_v-c_v\}\} fu​=minu≠​v​{minv<u​{du​+cu​−dv​−cv​},minv>u​{−du​+cu​+dv​−cv​}}=minu≠​v​{du​+cu​+minv<u​{−dv​−cv​},−du​+cu​+minv>u​{dv​−cv​}}。这样做的话直接遍历两次即可。

考虑一般情况：

对于一个点的答案，可以由它的子树中来，也可以从它的祖先那里来。

观察上面的式子可以得到，若一个点的父亲的最优答案不是这个点，那么这个点在其他子树的最优答案肯定就是父亲的最优答案，否则就是次优答案。

这样我们可以通过树形DP来解决这道题了。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;const int Maxn=2e5;
const int INF=0x3f3f3f3f;struct Edge {int to,dis;Edge *nxt;
};
Edge pool[Maxn*2+5];
Edge *ecnt=&pool[0],*G[Maxn+5];
inline void addedge(int u,int v,int dis) {Edge *p=++ecnt;p->to=v,p->dis=dis;p->nxt=G[u],G[u]=p;
}int N,C[Maxn+5];
int f[Maxn+5],g[Maxn+5],ans[Maxn+5];
int f_id[Maxn+5];void PreDFS(int u,int fa) {f[u]=g[u]=INF,f_id[u]=0;for(Edge *p=G[u];p!=NULL;p=p->nxt) {int v=p->to;if(v==fa)continue;PreDFS(v,u);int val=min(0,f[v])+p->dis+C[u]-C[v];if(val<f[u]) {g[u]=f[u],f[u]=val;f_id[u]=v;} else if(val<g[u])g[u]=val;}
}
void DFS(int u,int fa,int val) {ans[u]=min(f[u],val);for(Edge *p=G[u];p!=NULL;p=p->nxt) {int v=p->to;if(v==fa)continue;if(v==f_id[u])DFS(v,u,min(0,min(g[u],val))+(p->dis+C[v]-C[u]));else DFS(v,u,min(0,min(f[u],val))+(p->dis+C[v]-C[u]));}
}int main() {freopen("skylines.in","r",stdin);freopen("skylines.out","w",stdout);scanf("%d",&N);for(int i=1;i<=N;i++)scanf("%d",&C[i]);for(int i=1;i<N;i++) {int u,v,dis;scanf("%d %d %d",&u,&v,&dis);addedge(u,v,dis),addedge(v,u,dis);}PreDFS(1,0);DFS(1,0,0);int Q;scanf("%d",&Q);while(Q--) {int u;scanf("%d",&u);printf("%d\n",ans[u]);}return 0;
}

T3.空之轨迹

题目

题目背景

七曜历1150年前后，爱普斯泰恩博士发明了导力器，由此，一场席卷塞姆利亚大陆的能源革命——导力革命开始了，它使得大陆进入了空前的发展阶段。另一方面，很多国家为了开发拥有导力力量的兵器而展开激烈的争夺，拥有霸权成为很多国家的意图。在这个错综复杂的时代里，大陆陷入了混乱之中。这个时代，有一个生存于列强罅缝中的独立小国——利贝尔。以利贝尔为舞台的起点，主人公艾丝蒂尔和约修亚将在冒险旅途上遇到各色各样的人物，以成为正式游击士为目标的她，揭开了故事的序幕。以新的世界、新的角色来描述新的故事，这就是开拓时代的物语——空之轨迹。

题目描述

Iri近日沉迷游戏《英雄传说VI空之轨迹》。该游戏共有$n$个章节，第$i$章中有$a_i$次战斗。当第$i$章通关后，游戏会自动存档，然后自动进入第$i+1$章，且不允许回到之前的章节（除非读档）。

由于Iri的游戏设备年久失修，这天早上Iri进入游戏时，发现他的所有存档都消失了，只留下初始的一个序章存档（加载后会开始第$1$章）。不幸的是，游戏的章节切换系统也出现了Bug，在每一章结束的自动存档之后，游戏会从已有的所有存档（包括序章存档）中等概率随机选取一个加载。由于Iri的耐心与精力有限，加载序章存档后，他只会连续玩$m$个章节，然后更换新的设备。需要注意的是，游戏的存档系统没有损坏，即当第i章结束后的自动存档被加载后，一定会开始第$i+1$章。

现在Iri想知道，这$m$章内能进行的战斗总次数的期望值。Iri觉得这个问题太简单了，所以就把它交给了你。由于Iri的游戏技术同样出神入化，你可以认为所有章节他都会一次通关。

输入

从文件kiseki.in中读入数据。

第一行包含两个正整数$n,m.$

第二行$n$个非负整数$a_i.$

输出

输出到文件kiseki.out中。

输出一行一个整数，表示Iri进行的战斗总次数的期望值在模$998244353$意义下的值。

即设答案化为最简分式后的形式为$\frac{a}{b}$，其中$a$和$b$互质，输出整数$x$使得$bx\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}998244353)$且$0\le x<998244353$。可以证明这样的整数$x$是唯一的。

样例1输入

3 2
1 2 1

样例1输出

499122179

样例1解释

答案是$\frac{5}{2}$。由于$499122179\times 2\mathrm{m}\mathrm{o}\mathrm{d}998244353=5$，所以你输出$499122179$。

样例2输入

3 3
5 5 1

样例2输出

332748132

样例3输入

15 10
2 8 6 3 2 6 3 5 9 2 3 4 5 1 6

样例3输出

653958763

数据范围

提示

$x^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$，其中$p$是质数，$x$为$[1,p)$上的整数。

分析

显然看出答案是求$\frac{a}{b}\mathrm{m}\mathrm{o}\mathrm{d}998244353$，就是$a\cdot b^{-1}\mathrm{m}\mathrm{o}\mathrm{d}998244353$。

不难发现每个状态只和序列中出现的数的次数有关。

那么我们考虑将每次的序列手动排序后相邻两个数相减，不难发现只有$0$和$1$才会出现。

设状态$f(i,S)$为现在有了$i$个数，其序列为$S$的方案数，则每个数列的出现概率为$\frac{f(M,S)}{M!}$。

转移时枚举下一个数的位置，再插入到对应的位置上即可。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
const int Maxn=1e5;
const int Maxm=21;
const int Mod=998244353;
const int INF=0x3f3f3f3f;int N,M;
int A[Maxn+5];
int f[2][(1<<Maxm)+1];inline int QuickPow(int a,int k) {int ret=1;while(k) {if(k&1)ret=1LL*ret*a%Mod;a=1LL*a*a%Mod;k>>=1;}return ret;
}int main() {freopen("kiseki.in","r",stdin);freopen("kiseki.out","w",stdout);scanf("%d %d",&N,&M);for(int i=1;i<=N;i++)scanf("%d",&A[i]);f[0][0]=1;int now=0;for(int i=1;i<M;i++) {for(int s=0;s<(1<<(i-1));s++) {f[now^1][s<<1]=(f[now^1][s<<1]+f[now][s])%Mod;int tmp=f[now][s];for(int k=0;k<i-1;k++) {if(s&(1<<k)) {int t=s&((1<<(k+1))-1);int s1=((s^t)<<1)^t;f[now^1][s1]=(f[now^1][s1]+tmp)%Mod;tmp=0;}tmp=(tmp+f[now][s])%Mod;}f[now^1][s|(1<<(i-1))]=(f[now^1][s|(1<<(i-1))]+tmp)%Mod;f[now][s]=0;}now^=1;}int ans=0;for(int s=0;s<(1<<(M-1));s++) {int cnt=1,tmp=A[1];for(int i=0;i<M-1;i++) {if(s&(1<<i))cnt++;tmp+=A[cnt];}ans=(ans+1LL*f[now][s]*tmp%Mod)%Mod;}for(int i=1;i<=M;i++)ans=1LL*ans*QuickPow(i,Mod-2)%Mod;printf("%d\n",ans);return 0;
}