考场
乍一看都不可做
T1 算了半天样例，一直算出来 \(\frac{81}{400}\)，直接丢了
T1 推了推发现是求最长连续 \(0\) 的数量，那就是线段树合并加上《玫瑰花精》
T3 完全不会。甚至不知道该状压还是乱搞
先敲了 T1 T3 两个暴力和 T3 完全图+边权相同的部分分，8 点多开始写 T2。结果出奇的顺利，9,00 就过了样例和测速（测速时发现线段树节点数忘 \(\times4\) 了，担心 MLE，换成了 merge 时不新建点的写法）。拍上后决定手模一些小数据，结果第一个就挂了。。。发现答案要和前缀 \(0\) 数+后缀 \(0\) 数取 \(\max\)，暴力也没考虑，9.30 加上并过了自己造的小数据。
回头看 T1，还是没有想法。先加了个记忆化，又用分数类输出了一下样例，发现是 \(\frac{11}5\)？？？一直i疑惑到 10.00。交了T1 T3，发现编译器只有 C++11 gcc 8.2.0 一个选项，担心 T2 被卡常。造了链、菊花、二叉树的满数据，都在 0.3s 跑完了，感觉很稳。
res
rk4 20+100+20
T1 在求 \(\sum w_i\) 时没有模，导致算分母逆元时爆 LL 了，挂 25pts
T3 有完全图但边权不相等情况，挂 10pts
rk1 肖鸣孜 45+100+40
Hunter
考察了对期望的线性性本质的理解
要求的是在第一个猎人之前死的期望猎人数 \(+1\)，即 \(\text{E}(\sum_{i=2}^nA_i)+1\)，等于 \(\sum_{i=2}^n\text{E}(A_i)+1\)，而每个猎人在第一个猎人之前死的期望是 \(\frac{w_i}{w_1+w_i}\times1\)。
code
const int N = 1e5+5, mod = 998244353;
int n;
LL a[N];
LL ans;
LL Pow(LL x,LL y=mod-2)
{ LL res=1; for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod; return res; }
signed main() {
read(n);
For(i,1,n) read(a[i]);
For(i,2,n) ans = (ans + a[i] * Pow(a[1]+a[i])) %mod;
write((ans+1)%mod);
return iocl();
}
Defence
线段树合并+线段树求最长连续 \(0\) 数
考场代码
const int N = 1e5+5;
int n,m,q;
vector<int> to[N];
int rt[N],pre[N],suf[N],ans[N];
#define ls(u) t[u].ch[0]
#define rs(u) t[u].ch[1]
#define mid ((l+r)>>1)
int ind;
struct Node { int l,r; int len() { return r-l-1; } };
bool operator < (Node x,Node y) { return x.len() < y.len(); }
struct Seg { int ch[2],ll,rr; Node mx; } t[N*4*18];
void up(int u) {
t[u].mx = max(t[ls(u)].mx,t[rs(u)].mx);
if( ls(u) && rs(u) ) ckmax(t[u].mx,Node{t[ls(u)].rr,t[rs(u)].ll});
t[u].ll = t[ ls(u)?ls(u):rs(u) ].ll, t[u].rr = t[ rs(u)?rs(u):ls(u) ].rr;
}
void insert(int &u,int l,int r,int p) {
if( !u ) u = ++ind;
if( l == r ) {
t[u].ll = t[u].rr = p, t[u].mx = {p,p};
return;
}
if( p <= mid ) insert(ls(u),l,mid,p);
else insert(rs(u),mid+1,r,p);
up(u);
}
int merge(int u,int v,int l,int r) {
if( !u || !v ) return u | v;
if( l == r ) return u;
ls(u) = merge(ls(u),ls(v),l,mid), rs(u) = merge(rs(u),rs(v),mid+1,r);
up(u); return u;
}
#undef ls
#undef rs
#undef mid
void dfs(int u,int fa) {
for(int v : to[u]) if( v != fa ) {
dfs(v,u);
rt[u] = merge(rt[u],rt[v],0,m);
ckmin(pre[u],pre[v]), ckmax(suf[u],suf[v]);
}
if( suf[u] ) ans[u] = max(t[rt[u]].mx.len(),pre[u]-0-1+m-suf[u]-1);
else ans[u] = -1;
}
signed main() {
// printf("%d\n",sizeof(t));
// return 0;
// freopen("b1.in","r",stdin);
// freopen("b1.out","w",stdout);
read(n,m,q); ++m;
For(i,1,n-1) {
int x,y; read(x,y);
to[x].pb(y), to[y].pb(x);
}
For(i,1,n) pre[i] = m, insert(rt[i],0,m,0), insert(rt[i],0,m,m);
while( q-- ) {
int x,y; read(x,y);
insert(rt[x],0,m,y);
ckmin(pre[x],y), ckmax(suf[x],y);
}
dfs(1,0);
For(i,1,n) write(ans[i]);
return iocl();
}
Connect
本质是要保留一条 \(1\) 到 \(n\) 的链，其他点与这条链只有一个交点，求删去边的最小权值和。
\(n\) 很小，考虑状压 DP。
设 \(f[s,i]\) 为当前考虑过的点集为 \(s\)，链的结尾为 \(i\) 的保留，每次考虑添加一个点到链中或找一个联通块，使这个联通块中的点与这条链的交点为 \(i\)。具体看代码