前言
Rank 5，$130$ 分，第二题因为懒就没怎么打，第三题用玄学拿(pian)到了 $20$ 分。
P1
题面
最近几年，一场新的金融危机爆发了，这场危机使得很多人陷入的经济问题的困境。一些 X 公司的员工试图通过要求加薪度过这一难关。
X 公司有着严格的等级制度，除了公司所有者小 H 以外，其他人都有一个直属上司。没有下属的员工称为工人，其他人则称为领导者。为了加薪，工人们都会向他们的上司提交请愿书。当然，每个领导者都希望自己的下属能够尽可能快乐的工作，所以当至少有 $T%$ 的下属提交请愿书时，那么这个领导者就会向自己的上司提交请愿书。计算百分比时，领导者只会计算直属上司是他的下属，当然，他也只会提交一次请愿书。
如果最会小 H 收到了超过 $T%$ 的请愿书，那么他将为所有工人们加薪。现在给出公司的构架和 $T$ 的数值，你需要计算至少有多少工人提交请愿书才能使得小 H 给工人加薪。
输入格式
第一行 $N,T$ ($1≤N≤100000,1≤T≤100$)。 $N$ 表示公司的总人数（不包括小 H）。每个员工编号为 $1$ 到 $N$。小 H 编号为 $0$ 。
第二行有 $N$ 个数，第 $i$ 个数表示编号的员工直属上司的编号。输出格式
一个数，最小需求的工人数。
思路
员工们组成了一棵树，设 $f[i]$ 为结点 $i$ 之下最少需要几个提交请愿书的工人才能使结点 $i$ 的领导者提交请愿书。叶子结点（工人）的 $f[i]$ 初始为 $1$ 。设 $size(i)$ 表示 $i$ 的直属儿子的个数，则
$$\sum_{x=1}^{size\left(i\right)\times T\%}sorted\left(sons\right)\lbrack x\rbrack\;(\mathrm{取当前结点最小的}size(i)\times k\%\mathrm{个直属子结点的和})$$
求当前结点最小的几个直属子结点的和 可以使用 $STL$ 中的堆 ($priority\_queue$) 来求。
我们用一遍 $DFS$ 求出 $f$ 数组， $f[0]$ 即是答案。
代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int n;
double t;
long long last[200005],to[200005],nextt[200005],s[200005],top=0;
int fa[200005],f[200005],l[200005];
void add(int a,int b,int c){
nextt[++top]=last[a];
to[top]=b;
s[top]=c;
last[a]=top;
}
void dfs(int x){
int cnt=0;
for (int i=last[x];i;i=nextt[i]){
int y=to[i];
if (y==fa[x]){
continue;
}
cnt++;
dfs(y);
}
if (cnt==0){
f[x]=1;
return;
}
priority_queue<int,vector<int>,greater<int> > q;
for (int i=last[x];i;i=nextt[i]){
int y=to[i];
if (y==fa[x]){
continue;
}
q.push(f[y]);
}
for (int i=1;i<=ceil(cnt*t);i++){
f[x]+=q.top();
q.pop();
}
}
int main(){
cin>>n>>t;
t/=100;
for (int i=1;i<=n;i++){
int x;
x=read();
fa[i]=x;
l[x]=1;
add(i,x,1);
add(x,i,1);
}
dfs(0);
cout<<f[0];
return 0;
}
P2
题面
nodgd 的粉丝太多了，每天都会有很多人排队要签名。
今天有$?$个人排队， 每个人的身高都是一个整数， 且互不相同。 很不巧， nodgd 今天去忙别的事情去了，就只好让这些粉丝们明天再来。同时 nodgd 提出了一个要求，每个人都要记住自己前面与多少个比自己高的人，以便于明天恢复到今天的顺序。
但是，粉丝们或多或少都是有些失望的，失望使她们晕头转向、神魂颠倒，已经分不清楚哪一边是“前面”了，于是她们可能是记住了前面比自己高的人的个数，也可能是记住了后面比自己高的人的个数，而且他们不知道自己记住的是哪一个方向。
nodgd 觉得，即使这样明天也能恢复出一个排队顺序，使得任意一个人的两个方向中至少有一个方向上的比他高的人数和他记住的数字相同。 可惜?比较大， 显然需要写个程序来解决， nodgd 很忙，写程序这种事情就交给你了。
第一行输入一个整数$n$， 表示指令的条数。
接下来$n$行， 每行两个整数$a_i,b_i$， 表示一个人的身高和她记住的数字， 保证身高互不相
同。
输出一行，这个队列里从前到后的每个人的身高。如果有多个答案满足题意，输出字典序最小。如果不存在满足题意的排列，输出“impossible”（不含引号）。
思路
先判断无解的情况。对每个 $a_i$，找出有多少个 $a_i$，比他大记为$c_i$，如存在某个的$b_i>c_i$就无解。这一步可以用排序来解决，把所有人按身高排序，然后扫一遍就能求出$c_i$并判定无解。
接下来，我们尝试把这个身高序列构造出来。
一开始我们有一个空序列。按身高从矮到高加入每个人。所有人的身高都不相等，显然身高为a的人要么加入到当前的从左到右的第$b_i+1$个空位置里，要么加入到当前第$c_i-b_i+1$个空位置里。注意到，比$a_i$更小的数值已经全部填入了身高序列中，所以$a_i$是剩下的数中最小的数，要想字典序最小，只需要让$a$的位置尽量靠左就行。于是，将$a_i$填入了第$min(b_i+1,c_i-b_i+1)$个空位置里。
每加入一个数需要$0(n)$的时间来找出填入的位置，所以总的时间复杂度是$O(n)$，可以得到$60$分。
前面算法的瓶颈在于每次去找出从左到右的第$min(b_i+1,c_i-b_i+1)$个空位置。我们针对这一步进行优化。
我们发现，针对空位个数的问题只有两个，一个是删除一个空位，一个是求出第$k$个空位在哪里。显然，我们可以用一个线段树来解决这个问题。首先，我们对整个空序列建一个线段树，线段树的每个节点记录下对应区间内的剩余空位的个数，在建树的时候也就是区间长度。然后，删除一个空位就是在线段树上进行简单的修改操作。求第$k$个空位置可以从线段树的根节点开始向下移动，如果左子节点对应区间的空位置个数大于等于$k$，则递归到左子节点；否则用$k$减去左子节点对应区间的空位置个数，再递归到右子节点；递归到叶子节点时，就找出了第$k$个空位置。
我们知道，这两个线段树上的操作的复杂度都是$O(log(n))$，所以最终的时间复杂度就是$O(log(n))$，可以得到$100$分。
代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int n;
struct node{
int l,r,c;
};
node tree[200005];
int x[200005];
void build_tree(int pos, int l, int r){
tree[pos].l=l;
tree[pos].r=r;
tree[pos].c=r-l+1;
if(l==r){
return;
}
build_tree(pos*2,l,(l+r)/2);
build_tree(pos*2+1,(l+r)/2+1,r);
}
void add_tree(int pos,int m,int u){
tree[pos].c--;
if(tree[pos].l==tree[pos].r){
x[tree[pos].l]=u;
return;
}
if(tree[pos*2].c>=m){
add_tree(pos*2,m,u);
return;
}
add_tree(pos*2+1,m-tree[pos*2].c,u);
}
struct node2{
int a,b;
};
node2 s[200005];
bool cmp(node2 a,node2 b){
return a.a<b.a;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
s[i].a=read();
s[i].b=read();
}
sort(s+1,s+1+n,cmp);
build_tree(1,1,n);
for(int i=1;i<=n;i++){
if(n-i<s[i].b){
cout<<"impossible";
return 0;
}
}
for(int i=1;i<=n;i++){
add_tree(1,min(s[i].b+1,n-s[i].b-i+1),s[i].a);
}
for(int i=1;i<=n;i++){
cout<<x[i]<<" ";
}
return 0;
}
P3
题面
一个无向连通图，顶点从 $1$ 编号到 $N$，边从 $1$ 编号到 $M$。
小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $N$ 号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这 $M$ 条边进行编号，使得小 Z 获得的总分的期望值最小。
输入第一行是正整数 $N$ 和 $M$，分别表示该图的顶点数和边数，接下来 $M$ 行每行是整数$u,v(1≤u,v≤N)$，表示顶点 $u$ 与顶点 $v$ 之间存在一条边。
输出仅包含一个实数，表示最小的期望值，保留 $3$ 位小数。
