前言
比赛网址：http://47.110.12.131:9016/contest/3
总体来说，这次比赛是有一定区分度的， ( ext{ACM}) 赛制也挺有意思的。
题解
A. 云之彼端，约定的地方
考点：
无（签到题）
解法：
本题是拓扑学中的欧拉公式的结论题。
我们发现 (V=E-F+2) ，于是便得到了答案。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int e,f;
scanf("%d%d",&e,&f);
printf("%d",e-f+2);
return 0;
}
B. 秒速 5 厘米
考点：
拓展欧几里得，裴蜀定理，简单数论/构造。
由于近年来考试加强了对数论的考察，今年更是考了一道构造题，故出此题来考考大家。
解法：
要使所有的数清零，也就是要使方程 (len_1 imes x + len_2 imes y + len_3 imes z + X = 0) 这个方程一定有解。
于是联想到裴蜀定理： (ax+by=c) 有解当且仅当 (gcd(x,y)|c) 。
故我们知道当 (gcd(x,y)=1) 时，这个方程一定有解。
所以我们考虑第一次操作修改区间 ([1,n]) ，第二次修改区间 ([1,n-1]) ，第三次修改 (n)。
由于 (n) 和 (n-1) 互质，所以一定存在方法使前两次之和加上原数等于 (0) ，而最后一次操作又能使最后一个数变成 (0) 。
具体构造方案就变成了求方程 (nx + (n-1)y = C) 的任意一组解。
而这不管是交给小学奥数还是交给拓展欧几里得都是可以的。
这题的构造其实不难想到，当然观察样例也可以发现，可以说观察样例是极其重要的能力。
代码： （来自 liyiming ，出题人是用拓欧写的，放这个比较友好。）
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << 1 << " " << n - 1 << endl;
cout << a[1] * (n - 1);
for (int i = 2; i <= n - 1; i++) cout << " " << a[i] * (n - 1);
cout << endl;
cout << 1 << " " << n << endl;
for (int i = 1; i <= n - 1; i++) cout << -a[i] * n << " ";
cout << 0 << endl;
cout << n << " " << n << endl;
cout << -a[n];
cout << endl;
return 0;
}
C. 追逐繁星的孩子
考点：
树论，树的遍历，概率的基本计算。
解法：
对于题目中给的这棵树，从 (1) 号节点开始进行一次 ( ext{dfs}) ，并在过程中计算经过该点的概率即可。
当然，如果当前概率已经不合法，则可以剪枝优化。
本题的难度明显小于 B 题， AC 人数不符合预期……
代码：
#include <bits/stdc++.h>
#define Re register
using namespace std;
const int maxn=500005;
vector<int> T[maxn],E[maxn];
int n,q,cnt;
void dfs(int x,int fa,long double p)
{
if(p*100<q) return;
cnt++;
for(Re int i=0;i<T[x].size();i++)
{
if(T[x][i]==fa) continue;
dfs(T[x][i],x,p*E[x][i]/100);
}
}
int main()
{
scanf("%d%d",&n,&q);
for(Re int i=1;i<n;i++)
{
int u,v,p;
scanf("%d%d%d",&u,&v,&p);
T[u].push_back(v);
T[v].push_back(u);
E[u].push_back(p);
E[v].push_back(p);
}
dfs(1,1,1.0);
printf("%d",cnt);
return 0;
}
D. 言叶之庭
代码：
int n;
cin>>n;
for (int i = n - 1; i >= 0; i--)
{
f[i] = f[i+1] + (double)n / ((double)n - i);
g[i] = g[i+1] + (double)i / ((double)n - i) * f[i]+ f[i+1] + (double)n / ((double)n - i);
}
printf("%.2lf",g[0]);
考点:
期望相关知识。
可以说期望是一个大难点，如何逾越它是个重要的问题。
题解:
本题为 Luogu P4550 原题……
E. 你的名字
考点:
组合数学，计数问题。
计数问题是福建省选的黄金考点，六题能出四道计数。
题解:
使用 Burnside 引理（(egin{aligned}cnt = frac{1}{|G|}sumlimits chi (x)end{aligned})）或者简单的容斥可得：
而 (2) 的那么多次方直接用快速幂计算即可。
（考虑利用费马小定理，我们可以进一步优化，这里就不介绍了，可以看下面代码自行理解……）
代码：
cout<<(2*1ll*qpow(2,ksc(n/2,n/2,mod-1))+qpow(2,ksc(n/2,n,mod-1))+qpow(2,ksc(n,n,mod-1)))%mod*1ll*inv4%mod;
F. 天气之子
考点:
计数问题，树论。
树论是 noip / CSP 中最重要的考点之一。
题解:
这种方法叫做 贡献 法，考虑一个连通块在哪些 ([l,r]) 中出现过。
我们需要取其中一个点作为这个连通块的代表，不妨就取深度最浅的那个点。
于是我们枚举每个结点作为连通块的最浅结点，显然它能作为最浅结点当且仅当它的父节点没有被取到，当它的父节点被取到时，它就不是最浅节点，也可以认为这个连通块它不存在。
然后就做完了本题……
代码：
u64 ans = 0;
for (int i = 2; i <= n; i++)
{
if (fat[i] < i)
{
ans += (i - fat[i]) * 1ll * (n - i + 1);
}
else
{
ans += (fat[i] - i) * 1ll * i ;
}
}