NOIP 8/12 题解
zhujianheng
·
·
个人记录
T1：
题意概述：
有 n 次操作，有两种形式：
1.获得 x 元或 0 元。
2.获得 y 元或 [0,\frac{y}{2}下取整] 元的随机数。
问能不能通过 n 次操作获得 m 元。T 组数据。
30pts：
枚举。
100pts：
数学题。
发现并出来的是一个连续区间 $[\dfrac{y}{2}上取整,y]$。
考虑第一种操作，每次变化量为 $y-x$，所以 $y-x|ny-m$，且 $n(y-x) \ge ny-m$。
代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(0);
int T;
cin>>T;
while(T--){
ll n,x,y,m;
cin>>n>>x>>y>>m;
if(m>n*y){
cout<<"No"<<'\n';
continue;
}
if(n*y-m>=ceil(y/2)&&n*y-m<=n*y){
cout<<"Yes"<<'\n';
continue;
}
if((n*y-m)%(y-x)==0&&(n*(y-x)>n*y-m||n*(y-x)==n*y-m)){
cout<<"Yes"<<'\n';
continue;
}
cout<<"No"<<'\n';
}
return 0;
}
```
T2:
题意概述：
有一个 $n$ 点 $m$ 边的图，原图每个点点权 $a_i$，重新分配权值是 $b_i$。
（1）$ ∀w(u,v),\dfrac{b_u}{b_v}<x$。
（2）$\sum a_i=\sum b_i$。
（3）$ ∀1 \le i \le n,\dfrac{b_i}{a_i} \ge \dfrac{p}{q}$.
求 $x_{\min}$。
10pts：
送分。
30pts：
注意到，平均分配是最优的。
根节点要给自己留下 $\dfrac{p}{q}$ 的权值，剩下每个节点分配出 $\dfrac{1-\dfrac{p}{q}}{n-1}$。为什么要平均分配？如果不平均分配，那么就有一个节点大，一个节点小，则如果 $nq \ge p$，那么 $x$ 会更大。所以答案就是 $(n-1) \dfrac{p}{q-p}$。
60pts:
最坏情况：有一节点无穷大，其他节点权值为 $0$。从 $1$ 到 $n$ 枚举一个点有权值，其他点没权值，建出一颗树。二分 $x$，以每个点为根，做出每个点的深度，求 $\dfrac{1}{x^d}$ 求和，如果小于 $1-\dfrac{p}{q}$ 就可以。
时间复杂度 $O(n^2 \log n)$。
100pts：
以 $i$ 号点为根做出一颗 bfs 树，非树边最多出现在同层或相邻一层，求出最短路径即可。
优化：先跑 bfs 再二分。每个点在 bfs 树的深度时是一样的，所以我们只需要在二分之外再进行 bfs，时间复杂度 $O(nm+n^2 \log \dfrac{ans}{eps})$。
代码：回去补。
T3：
两个 $n$ 个字符的字串 $s$，$t$，只能交换 $s$ 的两个相邻字符，求最少次数使得 $s<t$。
5pts:
```
cout<<-1;
```
15pts:
```
cout<<0;
```
20pts：
找到最小的 $i$ s.t. $s_i<t_1$，$i$ 不存在就输出 $-1$。
60pts：
如何比较 $s$ 和 $t$，一位一位比较。
设 $s$ 和 $t$ 的 LCP 是 $i$，则 $s_1=t_1,...,s_i=t_i$，$s_{i+1}<t_{i+1}$，第一步，枚举 LCP，LCP 中的字符怎么对应？一一对应，选最前面的。如果交换两个相邻字符是不优的。你可以飞快地一一对应完。每次扩展 LCP 时，就把 $t$ 中的对应位置移到 $i$，问题就又转换为 $B$ 性质，我们可以从 $i+1$ 往后枚举就行了，时间复杂度为 $O(n^2)$。
100pts：
对每种字符开一个队列，每次扩展一格的时候，把 $t_i$ 的队列的队头取出，就可以建立一个关系，但是不能暴力计算，需要快速计算。
注意到 LCP 是 $s$ 中最前面的位置，只需要数出星号后有多少个位置往前移动？用树状数组维护，就相当于把 $0$ 改成 $1$，求后缀和问题，就可以快速计算贡献。
时间复杂度 $O(26n \log n)$。
注意到每次都要查一遍，对于 26 个队头，只需要确定最优的查一次就可以了，时间复杂度 $O(26n+n \log n)$。
T4：
形式化题意：
$n$ 个点 $rt$ 为根的图，求树的拓扑序的逆序对的个数和。
15pts：
暴力搜索。
25pts：
状压 DP。
$dp_{i,S}$ 表示当前是 $S$ 状态，能到第 $i$ 个数的逆序对数量。
时间复杂度 $O(2^nn^2)$。
100pts：
如果 $u$ 是 $v$ 的祖先，则 $u$ 在拓扑序上一定先于 $v$，如果 $u<v$ 则贡献为 $0$，否则贡献为 $1$。
一棵树的拓扑序数量就是 $\dfrac{n!}{siz_1 \times siz_2 \times ... siz_n}$。以概率考虑的时候，随机排律满足 $i$ 号点在它的子树的最前面概率是 $\dfrac{1}{siz_i}$，最后概率乘积再乘上排列数 $n!$ 就得到了数量。
问题转化为期望乘上拓扑序数量。
$u,v$ 为祖孙关系已经解决，那如果是非祖先关系呢？
不妨设 $u<v$，设 $cnt_{u,v}$ 表示 $u,v$ 贡献的逆序对个数，$a$ 为 $u$ 到 $lca$ 之间的（不包括 $lca$）点数，$b$ 为 $lca$ 到 $v$ 之间的（不包括 $lca$）点数。考虑只把 $u-lca(u,v)-v$ 这条链拉出来，最后加的点只可能是 $u$ 或者 $v$，如果最后拉出来的是 $u$，则求的就是 $cnt_{fa_u,v}$，那么 $u$ 成为最后一个点的概率是什么？
设 $f_{u,v}$ 代表只考虑 $u$ 子树和 $v$ 子树相互之间产生逆序对的概率之和。我们只需要算出 $v$ 子树中有多少个节点编号小于 $u$ 的。我们只需要预处理出 $sum_{u,i}$，表示 $u$ 中有多少个点编号小于 $i$ 的，只需要将 $u$ 的子树染黑，$v$ 的子树染白，$u$ 就是黑色中最前面的，$v$ 就是白色中最前面的，只需要计算出黑色在最前面的概率。
同理，所以贡献就是 $sum_{v,u} \times \dfrac{siz_u}{siz_u+siz_v}+sum_{u,v} \times \dfrac{siz_v}{siz_u+siz_v}$，所以转移方程就是 $f_{u,v}=(sum_{v,u}+\sum{f_{son(u),v}}) \times \dfrac{siz_u}{siz_u+siz_v}+(sum_{u,v}+\sum{f_{son(v),u}}) \times \dfrac{siz_v}{siz_u+siz_v}$。
答案就是枚举 $lca$，如果 $u,v$ 都是儿子的话，那么答案就是 $f_{u,v}$ 之和，再加上祖孙关系的和。
为什么不能直接算概率？若 $u$ 的子树大，$v$ 的子树很小，那么概率就不是 $\dfrac{1}{2}$ 了。
时间复杂度 $O(n^2)$。