考场上写的A，C，H，L，M
下来补一下剩下的
E
注意\(p[i]<i\)这个性质
和重心关系不大，一个简单的构造，手模几个样例就能发现规律。
倒着枚举：
\(c[i]=0\)的是叶子，不用处理
\(c[i]>0\)，这个点连到父亲所在连通块的根上即可。
并查集维护连通块以及连通块的根，根就是连通块中最小编号的点。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
const int N=2e5+5;
#define LL long long
int n;
int fa[N];
int find(int x) {
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int c[N];
vector<int>p[N];
void merge(int x,int y) {
int fx=find(x),fy=find(y);
if(fx>fy) swap(fx,fy);//id小的做根
fa[fy]=fx;
}
bool vis[N];
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
fa[i]=i;
vis[i]=0;
p[i].clear();
}
for(int i=1;i<=n;i++) {
scanf("%d",&c[i]);
if(c[i]==0)
continue;
for(int j=1,x;j<=c[i];j++) {
scanf("%d",&x);
p[i].push_back(x);
}
}
for(int i=n;i;i--) {
for(int j=0;j<c[i];j++) {
int x=find(p[i][j]);
printf("%d %d\n",i,x);
merge(i,x);
}
}
}
return 0;
}
K 小凯的省奖之梦
（考场上根本没读这题）
大模拟，在暴力的基础上优化即可，就是考验码力
暴力想法是，两层循环，枚举买几个p，几个q，然后去check加上这些分后是否能拿到省奖，
算一下复杂度，
check是 nlogn，但由于要多次排序，常数挺大。
\(100*100*500*log(500)*const=5e7*const\)
t飞
第一次优化，二分q。在第22个点TLE。
第二次优化，发现可以分开处理两个学期的得奖情况，\(O(100*nlogn)\)处理好第一学期的，然后存在vector里，第二学期直接在第一学期基础上做就好。
AC代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 505;
int rk[N];
int n;
struct Stu {
int id;
string nam;
int a1, a2, b1, b2, c1, c2;//zhi ,de ,ti
int sum1, sum2;
int prize;//奖项分
} s[N];
vector<Stu> sav[101];
vector<Stu> v1;
bool cmp1(Stu x, Stu y) {
return x.nam < y.nam;
}
char str[30];
Stu kk;
int fir, sec, thi;
int m, q, p;
void get_rk(vector<Stu> v) {
v.push_back(kk);
sort(v.begin(), v.end(), cmp1);
int cnt = 0;
for (auto x: v) {
rk[x.id] = ++cnt;
}
}
bool cmp2(Stu x, Stu y) {
if (x.sum1 == y.sum1) {
return x.a1 == y.a1 ? rk[x.id] < rk[y.id] : x.a1 > y.a1;
} else {
return x.sum1 > y.sum1;
}
}
bool cmp3(Stu x, Stu y) {
if (x.sum2 == y.sum2) {
return x.a2 == y.a2 ? rk[x.id] < rk[y.id] : x.a2 > y.a2;
} else {
return x.sum2 > y.sum2;
}
}
bool cmp4(Stu x, Stu y) {
if (x.prize == y.prize) {
if (x.sum1 + x.sum2 == y.sum1 + y.sum2) {
return x.a1 + x.a2 == y.a1 + y.a2 ? rk[x.id] < rk[y.id] : x.a1 + x.a2 > y.a1 + y.a2;
} else {
return x.sum1 + x.sum2 > y.sum1 + y.sum2;
}
} else {
return x.prize > y.prize;
}
}
bool cmp_z1(Stu x, Stu y) {
return x.a1 > y.a1;
}
bool cmp_z2(Stu x, Stu y) {
return x.a2 > y.a2;
}
int rk_zhi[N];//智yu排序
int score1, score2, score3;
void sinister1(vector<Stu> &v, int add, int fir, int sec, int thi) {
kk.a1 += add;
kk.sum1 += add;
v.push_back(kk);
sort(v.begin(), v.end(), cmp_z1);
int nowrank = 1;
for (int i = 0; i < n; i++, nowrank++) {
if (i > 0 && v[i].a1 == v[i - 1].a1) {
rk_zhi[v[i].id] = rk_zhi[v[i - 1].id];
} else
rk_zhi[v[i].id] = nowrank;
}
sort(v.begin(), v.end(), cmp2);
nowrank = 0;
for (auto &it: v) {
nowrank++;
it.prize = 0;
if (fir && rk_zhi[it.id] <= score1) {
it.prize += 15;
fir--;
continue;
}
if (sec && rk_zhi[it.id] <= score2) {
it.prize += 10;
sec--;
continue;
}
if (thi && rk_zhi[it.id] <= score3) {
it.prize += 5;
thi--;
continue;
}
}
kk.a1 -= add;
kk.sum1 -= add;
}
//拷贝
bool check(vector<Stu> v, int add, int fir, int sec, int thi) {
for (int i = 0; i < n; i++) {
if (kk.id == v[i].id) {
v[i].a2 += add;
v[i].sum2 += add;
break;
}
}
sort(v.begin(), v.end(), cmp_z2);
int nowrank = 1;
for (int i = 0; i < n; i++, nowrank++) {
if (i > 0 && v[i].a2 == v[i - 1].a2) {
rk_zhi[v[i].id] = rk_zhi[v[i - 1].id];
} else
rk_zhi[v[i].id] = nowrank;
}
sort(v.begin(), v.end(), cmp3);
nowrank = 0;
for (auto &it: v) {
nowrank++;
if (fir && rk_zhi[it.id] <= score1) {
it.prize += 15;
fir--;
continue;
}
if (sec && rk_zhi[it.id] <= score2) {
it.prize += 10;
sec--;
continue;
}
if (thi && rk_zhi[it.id] <= score3) {
it.prize += 5;
thi--;
continue;
}
}
sort(v.begin(), v.end(), cmp4);
bool ok = 0;
nowrank = 0;
for (auto &it: v) {
nowrank++;
if (it.id == kk.id) {
if (nowrank <= m) ok = 1;
break;
}
}
return ok;
}
int main() {
scanf("%d", &n);
kk.nam = "crazyzhk";
for (int i = 1; i <= n; i++) {
scanf("%s %d %d %d %d %d %d", str, &s[i].a1, &s[i].b1, &s[i].c1, &s[i].a2, &s[i].b2, &s[i].c2);
s[i].nam = str;
s[i].id = i;
s[i].sum1 = s[i].a1 + s[i].b1 + s[i].c1;
s[i].sum2 = s[i].a2 + s[i].b2 + s[i].c2;
if (s[i].nam == kk.nam) {
kk.a1 = s[i].a1;
kk.a2 = s[i].a2;
kk.b1 = s[i].b1;
kk.b2 = s[i].b2;
kk.c1 = s[i].c1;
kk.c2 = s[i].c2;
kk.id = i;
kk.sum1 = s[i].sum1;
kk.sum2 = s[i].sum2;
} else {
v1.push_back(s[i]);
}
}
get_rk(v1);
fir = floor(0.15 * (double) n);
sec = floor(0.25 * (double) n);
thi = floor(0.35 * (double) n);
score1 = floor(0.25 * (double) n);
score2 = floor(0.45 * (double) n);
score3 = floor(0.75 * (double) n);
bool flg = 0;
int ans = 1e8;
scanf("%d %d %d", &m, &p, &q);
for (int i = 0; i + kk.a1 <= 100; i++) {
sav[i] = v1;
sinister1(sav[i], i, fir, sec, thi);
int L = 0, R = 100 - kk.a2;
while (L <= R) {
int mid = (L + R) >> 1;
if (check(sav[i], mid, fir, sec, thi)) {
flg = 1;
ans = min(ans, i * p + mid * q);
R = mid - 1;
} else {
L = mid + 1;
}
}
}
if (flg) {
printf("%d", ans);
} else {
puts("Surely next time");
}
return 0;
}