20220509 noi6
- tot 160 (300)
- rk 3/12
魔法宝石
100pts
\(\log^{2}\) 轻松过，白纠结了
考场代码
const int N = 5e5+5, X = 1e9;
int n,a[N],f[19][N];
Vi add[N],del[N];
gp_hash_table cnt;
int _max(int i,int j) { return a[i]>a[j] ? i : j; }
int maxx(int l,int r) {
int k = __lg(r-l+1);
return _max(f[k][l],f[k][r-(1<>n; For(i,1,n) io>>a[i];
iota(f[0]+1,f[0]+n+1,1);
For(i,1,18) For(j,1,n-(1< 商人
20pts, max = 100pts
看数据范围基本可以放弃 DP，考虑组合数
先算答案 \(\ge i\) 的方案数，做差得到 \(=i\) 的。枚举左括号个数 \(x\in[i,n-i]\)，不妨设 \(x\ge n-x\)（否则把下面的过程全部逆序），把 ( 看作 \(1\)，) 看作 \(-1\)，记前缀和最小值为 \(y\le 0\)，匹配的括号数即为 \(n-x+y\)。相当于要统计 \(n-x+y\ge i\iff y\ge i+x-n\) 的方案数
把 ( 看作向右上走，) 看作向右下走，等于从 \((0,0)\) 走到 \((n,2x-n)\) 且不触碰 \(y=i+x-n-1\) 的方案数，为 \({n\choose x}-{n\choose n-i+1}\)（注意不是 \(n\choose i-1\)）。
最后需要对每个 \(i\) 计算 \(\sum_{x=i}^{n-i}{n\choose x}-{n\choose n-i+1}\)，时间复杂度 \(O(n)\)
code
const int N = 1e6+5;
int ty,n,m;
LL ans[N],fac[N],ivf[N];
auto C=[](int n,int m) { return fac[n] * ivf[m] %mod * ivf[n-m] %mod; };
signed main() { freopen("b.in","r",stdin); freopen("b.out","w",stdout);
io>>ty>>n; if( ty == 1 ) io>>m;
fac[0] = fac[1] = ivf[0] = ivf[1] = 1;
For(i,2,n) fac[i] = fac[i-1]*i%mod, ivf[i] = (mod-mod/i)*ivf[mod%i]%mod;
For(i,2,n) (ivf[i] *= ivf[i-1]) %=mod;
LL s = Pow(2,n);
For(i,0,n/2)
ans[i] = Mod(s - (n-2*i+1) * C(n,n+1-i) %mod),
ckadd(s,-Mod(C(n,i)+C(n,n-i)));
Rep(i,0,n/2) ckadd(ans[i],-ans[i+1]);
if( ty == 1 ) io<防御工事
40pts, max = 100pts
想到了结论，但暴力试了下发现不对（事实上是写挂了），所以没管，还是应该严谨证明一下。后来给树写了个『幻想乡战略游戏』，写一半发现复杂度要乘上度数，这题没保证。。。好在还是数据水过了
考虑树的部分分。结论是建虚树后首都一定在虚树点上。证明：首都显然不会在虚树外，若在虚树边上，调整到权值和较大的端点一定不劣。在虚树上换根 DP 求出每个点为首都的答案即可
图的话先建圆方树，结论类似。区别在于首都不能建在方点上，把边上与方点相邻的圆点也加入虚树即可。写起来有点烦
code
const int N = 4e5+5;
int n,m,q,val[N];
Vi a,b;
namespace T {
int ind,fa[N],dep[N],dis[N],siz[N],son[N],top[N],dfn[N];
Vi e[N];
#define subtree(u,v) (dfn[u]<=dfn[v]&&dfn[v] siz[son[u]] ) son[u] = v;
}
}
void dfs2(int u,int t) {
top[u] = t, dfn[u] = ++ind;
if( son[u] ) dfs2(son[u],t);
for(int v : e[u]) if( v != fa[u] && v != son[u] ) dfs2(v,v);
}
int lca(int u,int v) {
for(; top[u] != top[v]; u = fa[top[u]])
if( dep[top[u]] < dep[top[v]] ) swap(u,v);
return dep[u] n ) b.pb(jmp(u,v)); if( v > n ) b.pb(jmp(v,u));
}
}
void bld() {
static int t,s[N];
auto cmp=[](int x,int y) { return dfn[x] < dfn[y]; };
sort(all(a),cmp), s[t=1] = 1, b = {1};
for(int v : a) if( s[t] != v ) {
int u = lca(s[t],v);
while( t > 1 && dep[s[t-1]] >= dep[u] ) e[s[t-1]].pb(s[t]), --t;
if( s[t] != u ) e[u].pb(s[t]), s[t] = u, b.pb(u);
s[++t] = v, b.pb(v);
} while( --t ) e[s[t]].pb(s[t+1]);
dfs(1,0), sort(all(b),cmp);
for(int i : b) e[i].clear();
s[t=1] = b[0];
for(int u : b) if( s[t] != u ) {
while( !subtree(s[t],u) ) --t;
e[s[t]].pb(u), s[++t] = u;
}
}
void clr() {
for(int i : b) f[i] = val[i] = 0, e[i].clear();
a.clear();
}
void dfs1(int u) {
for(int v : e[u])
dfs1(v), f[u] += f[v]+val[v]*(dis[v]-dis[u]), val[u] += val[v];
}
void dfs2(int u) {
if( u <= n ) ckmin(ans,f[u]);
for(int v : e[u])
f[v] = f[u] - val[v]*(dis[v]-dis[u]) + (m-val[v])*(dis[fa[v]]-dis[fa[u]]),
dfs2(v);
}
void main() {
bld();
ans = LLONG_MAX, dfs1(1), dfs2(1);
io<<(n-1ll)*m-ans<>n>>m>>q; For(i,1,m, x,y) io>>x>>y, G::adde(x,y);
G::tarjan(1), T::main();
while( q-- ) {
io>>m; For(i,1,m, x) io>>x, ++val[x], a.pb(x);
VT::main();
}
return 0;
}