[BZOJ 3992][SDOI2015]序列统计
终于调过去了……（然而不就是道NTT+生成函数水题吗至于调半天）
首先积非常的恶心，考虑转成和。这个事需要求指标的……求指标的话枚举原根的若干次幂即可（恰好$m$是素数一定有原根……），判断原根用比较大力的手段即可（我搞了一个$O(n\sqrt{n}logn)$的……求轻喷）。
然后这题还算比较简单吧……用生成函数表示原来的集合，然后$n$次幂就可以了。
注意那事个循环卷积……所以要开两倍然后每次乘完了再把右半部分搞过去。
代码：
/**************************************************************
Problem: 3992
User: danihao123
Language: C++
Result: Accepted
Time:6652 ms
Memory:1864 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <cmath>
typedef long long ll;
const int maxn = 32005;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll n, m, gl; int sz;
ll pow_mod(ll a, ll b, ll p) {
if(!b) return 1LL;
ll ans = pow_mod(a, b >> 1, p);
ans = (ans * ans) % p;
if(b & 1LL) ans = (ans * a) % p;
return ans;
}
ll inv(ll x, ll p) {
return pow_mod(x, p - 2LL, p);
}
void break_up(ll x, std::vector<ll> &V) {
int bd = sqrt(x + 0.5);
for(ll i = 2; i <= bd; i ++) {
if(x % i == 0) {
V.push_back(i);
while(x % i == 0) x /= i;
}
if(x == 1LL) break;
}
if(x > 1LL) V.push_back(x);
}
ll get_phi() {
if(m == 2LL) return 1LL;
ll mi = m - 1LL;
std::vector<ll> V;
break_up(mi, V);
for(ll i = 2; i <= mi; i ++) {
bool ok = true;
for(int j = 0; j < V.size(); j ++) {
ll b = mi / V[j];
if(pow_mod(i, b, m) == 1LL) {
ok = false;
#ifdef LOCAL
printf("%lld not passed!\n", i);
#endif
break;
}
}
if(ok) {
return i;
}
}
}
int bi, len;
int flip(int x) {
int ans = 0;
for(int i = 0; i < bi; i ++) {
if((1 << i) & x) {
ans += (1 << (bi - i - 1));
}
}
return ans;
}
void ntt(ll *A, bool flag = false) {
for(int i = 0; i < len; i ++) {
int v = flip(i);
if(v < i) std::swap(A[i], A[v]);
}
for(int L = 1; L < len; L <<= 1) {
ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)), ha);
if(flag) xi_n = inv(xi_n, ha);
for(int i = 0; i < len; i += (L << 1)) {
ll w = 1;
for(int j = i; j < i + L; j ++) {
ll p1 = A[j], p2 = A[j + L];
A[j] = (p1 + (p2 * w) % ha) % ha;
A[j + L] = (p1 - (p2 * w) % ha + ha) % ha;
w = (w * xi_n) % ha;
}
}
}
}
void poly_mul(ll *A, ll *B) {
static ll C[maxn]; memset(C, 0, sizeof(C));
#ifdef LOCAL
printf("A :");
for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
puts("");
printf("B :");
for(int i = 0; i < len; i ++) printf(" %lld", B[i]);
puts("");
#endif
ntt(A); ntt(B);
for(int i = 0; i < len; i ++) C[i] = (A[i] * B[i]) % ha;
ntt(C, true);
ll inv_n = inv(len, ha);
for(int i = 0; i < len; i ++) {
C[i] = (C[i] * inv_n) % ha;
}
#ifdef LOCAL
printf("C (not processed) :");
for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
puts("");
#endif
for(int i = 0; i < len; i ++) {
int v = i % (m - 1LL);
if(v != i) {
C[v] = (C[v] + C[i]) % ha;
C[i] = 0LL;
}
}
#ifdef LOCAL
printf("C :");
for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
puts("");
#endif
std::copy(C, C + len, A);
}
void poly_pow(ll *A, ll b) {
static ll B[maxn];
static ll res[maxn];
std::copy(A, A + len, res);
std::fill(A, A + len, 0); A[0] = 1LL;
#ifdef LOCAL
printf("A :");
for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
puts("");
printf("res : ");
for(int i = 0; i < len; i ++) printf("%lld ", res[i]);
puts("");
#endif
while(b) {
if(1LL & b) {
std::copy(res, res + len, B);
poly_mul(A, B);
std::fill(B, B + len, 0);
}
std::copy(res, res + len, B);
poly_mul(res, B);
std::fill(B, B + len, 0);
b >>= 1LL;
}
}
int main() {
static bool vis[maxn];
static ll A[maxn];
scanf("%lld%lld%lld%d", &n, &m, &gl, &sz);
ll phi = get_phi();
for(int i = 1; i <= sz; i ++) {
int v; scanf("%d", &v);
if(v == 0) continue;
vis[v] = true;
}
int logx = 0;
bi = 0; len = 1;
while(len <= (2 * m - 2)) {
bi ++; len <<= 1;
}
for(int i = 0; i < (m - 1); i ++) {
int v = pow_mod(phi, i, m);
if(vis[v]) {
A[i] ++;
#ifdef LOCAL
printf("log(%d) : %d\n", v, i);
#endif
}
if(v == gl) {
logx = i;
}
}
poly_pow(A, n);
printf("%lld\n", A[logx]);
return 0;
}
[BZOJ 2115][Wc2011]Xor
这个可以有啊（赞赏）！
我们可以发现如果两点间如果有多条路径，那么任意两条路径在一个简单环里。
然后我们还发现，如果说是一个路径，一个环和这个路径有交边，那么走这个环走很多次没有意义（其实相当于从环的两边选一边走）。
然后这样可以发现，用$1$到$n$的路径来异或一个环，可以得到新的一条$1$到$n$的路径。
这样我们可以用DFS树来求出图上所有简单环的异或和，求出其线性基，然后随便找条$1$到$n$的路径，问题就变成了求这条路径和那个线性基的异或和最大是多少。然后这就是线性基乱搞好了……
代码：
/**************************************************************
Problem: 2115
User: danihao123
Language: C++
Result: Accepted
Time:652 ms
Memory:6544 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
typedef long long ll;
const int maxn = 50005;
const int maxm = maxn << 2;
int first[maxn];
int next[maxm], to[maxm];
ll dist[maxm]; int rev[maxm];
int add_edge(int u, int v, ll d) {
static int cnt = 0;
cnt ++;
next[cnt] = first[u]; first[u] = cnt;
to[cnt] = v; dist[cnt] = d;
return cnt;
}
void ins_edge(int u, int v, ll d) {
int e1 = add_edge(u, v, d);
int e2 = add_edge(v, u, d);
rev[e1] = e2; rev[e2] = e1;
}
const int maxb = 61;
ll T[maxb];
void insert(ll x) {
for(int i = 60; i >= 0; i --) {
if(!x) break;
if((x & (1LL << i)) == 0) continue;
if(T[i]) {
x ^= T[i];
} else {
for(int j = i - 1; j >= 0; j --) {
if(x & (1LL << j)) {
x ^= T[j];
}
}
for(int j = i + 1; j < maxb; j ++) {
if(T[j] & (1LL << i)) {
T[j] ^= x;
}
}
T[i] = x; break;
}
}
}
ll sum[maxn];
bool vis[maxn], used[maxm];
void dfs(int x, ll s) {
vis[x] = true; sum[x] = s;
for(int i = first[x]; i; i = next[i]) {
if(used[i]) continue;
int v = to[i];
used[i] = used[rev[i]] = true;
if(vis[v]) {
insert((s ^ sum[v]) ^ dist[i]);
} else {
dfs(v, s ^ dist[i]);
}
}
}
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v; ll d;
scanf("%d%d", &u, &v); scanf(LO, &d);
ins_edge(u, v, d);
}
dfs(1, 0LL);
ll ret = sum[n];
for(int i = 60; i >= 0; i --) {
if(!T[i]) continue;
if(!(ret & (1LL << i))) {
ret ^= T[i];
}
}
printf(LO, ret); puts("");
return 0;
}
[LibreOJ 114]k大异或和
最近学了一点线性基……所以也就做了一些线性基的题目
这题还算挺简单的吧……先转成求第$s - k + 1$（这里用$s$表示异或和有多少种）大。求出线性基，然后从高位向低位枚举，然后乱搞就行……
唯一的坑就是子集要求非空。这样有可能会出现选不出$0$的情况，但是稍微思索一下可以发现如果$|B| < n$（这里用$B$表示线性基）那么一定可以用$B$里的东西凑出来一个数，然后再和不在线性基里的一个数异或一下，这样就能搞出来$0$了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
using ll = long long int;
const int maxb = 51;
ll T[maxb];
void insert(ll x) {
for(int i = 50; i >= 0; i --) {
if(!x) break;
if((x & (1LL << i)) == 0) continue;
if(T[i]) {
x ^= T[i];
} else {
for(int j = i - 1; j >= 0; j --) {
if(x & (1LL << j)) {
x ^= T[j];
}
}
for(int j = i + 1; j < maxb; j ++) {
if(T[j] & (1LL << i)) {
T[j] ^= x;
}
}
T[i] = x; break;
}
}
}
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
int sz = 0;
ll tot = 0;
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
ll x; scanf(LO, &x);
insert(x);
}
for(int i = 0; i < maxb; i ++) if(T[i]) sz ++;
tot = (1LL << sz) - 1LL;
if(sz < n) tot ++;
int m; scanf("%d", &m);
while(m --) {
ll k; scanf(LO, &k);
if(k <= 0LL || k > tot) {
puts("-1");
} else if(sz < n && k == 1LL) {
puts("0");
} else {
k = tot - k + 1LL;
int rest = sz; ll ret = 0;
for(int i = 50; i >= 0; i --) {
if(!T[i]) continue;
rest --;
if(k <= (1LL << rest)) {
ret ^= T[i];
} else {
k -= (1LL << rest);
}
}
printf(LO, ret); puts("");
}
}
return 0;
}
[BZOJ 2876][NOI2012]骑行川藏
我终于A了……不就是拉格朗日乘数法的模板题吗
首先这道题最优情况下一定有（这里用\(E_i\)表示第\(i\)段路程的耗能）：\(\sum_{i = 1}^n E_i = E_u\)。
然后这个东西是一个等式限制条件，然后我们还要最小化总用时，给人拉格朗日乘数法的即视感……
不管怎么说让我们来列式子吧：
\[h(x_1, x_2,\ldots ,x_n, \lambda) = \sum_{i = 1}^n \frac{s_i}{x_i} + \lambda \sum_{i = 1}^n k_i s_i (x_i - v_i)^2\]
\[\frac{\partial h}{\partial x_i} = -\frac{s_i}{x_i^2} + 2\lambda k_i s_i (x_i - v_i)\]
然后你会想这TM怎么解方程……
但是我们想一想，把\(\frac{\partial h}{\partial x_i} = 0\)稍作整理，得：
\[\frac{1}{2k_i\lambda} = x_i^2 (x_i - v_i)\]
对于式子的左边，是一个关于\(x_i\)的增函数（因为这道题默认了\(x_i\geq 0\)且\(x_i\geq v_i\)），然后不妨令\(\frac{1}{\lambda} = u\)，可以发现\(u\)越大则\(x_i\)越大！这样一来那么我们的限制条件就会更加难以满足。
所以我们可以二分这个\(u\)来解这些方程。
BTW，这题卡精度非常厉害……
代码：
/**************************************************************
Problem: 2876
User: danihao123
Language: C++
Result: Accepted
Time:3960 ms
Memory:1524 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cassert>
typedef double R;
const R eps = 1e-12;
const int maxn = 10005;
int sign(R x) {
if(fabs(x) < eps) {
return 0;
} else {
if(x < 0) {
return -1;
} else {
return 1;
}
}
}
R s[maxn], k[maxn], V[maxn];
R rf(int i, R v, R delta) {
return v * v * (v - V[i]) - delta;
}
R rf2(int i, R v) {
return 3 * v * v - 2 * v * V[i];
}
R gen_rt(int i, R delta) {
R x = 1e6;
int lambda = 100;
while(lambda --) {
R a = rf(i, x, delta);
if(sign(a) == 0) break;
R da = rf2(i, x);
x -= a / da;
}
return x;
}
int n; R E;
R gen_lft() {
R l = 1e-14, r = 1e16;
while(r - l > eps) {
#ifdef LOCAL
printf("State [%.18lf, %.18lf]\n", l, r);
#endif
R M = (l + r) / 2;
R T = 0;
for(int i = 1; i <= n; i ++) {
R v = gen_rt(i, M / (2 * k[i]));
T += (v - V[i]) * (v - V[i]) * k[i] * s[i];
}
if(sign(T - E) <= 0) {
l = M;
} else {
r = M;
}
}
return l;
}
int main() {
std::cin >> n >> E;
for(int i = 1; i <= n; i ++) {
std::cin >> s[i] >> k[i] >> V[i];
}
R M = gen_lft();
R tm = 0;
for(int i = 1; i <= n; i ++) {
R v = gen_rt(i, M / (2 * k[i]));
tm += s[i] / v;
}
printf("%.8lf\n", tm);
return 0;
}
[LibreOJ 2135][ZJOI2015]幻想乡战略游戏
竟然1A了蛤蛤蛤蛤蛤
这题用人话说就是给你一个不会动的树，让你求带权重心。
先解决一个问题：如果要求动态修改点权，并且要求多次询问求某点\(x\)的\(\sum_{i = 1}^n d_i\cdot dist(i, x)\)，怎么做？
很显然对于一个点\(x\)，对它造成贡献的点，可能是在以\(x\)为根的点分子树里的，也可能在\(x\)之外。但是一个不在该点分子树内的点要对\(x\)产生贡献，必须要经过\(x\)在分治树上的祖先。
所以我们可以考虑对每个重心，记录下它这个点分子树中所有点对该重心的贡献、对点分树上的父亲的贡献以及该点分子树的点权和。每次求答案时\(x\)所在的分治子树的贡献很好考虑，那考虑一下其分治树上祖先对\(x\)的贡献就行了。
那带权重心怎么求呢？如果我们把树的根变成带权重心，那么我们会发现越远离根则答案越劣。所以我们如果只往使得答案更小的地方走，那么最后一定会走到带权重心上。
我们考虑把这个过程放点分树上。从整棵树的重心开始往下走，每次如果发现有一条出边指向的点答案更好，那就往这个子结构（不是指向的点而是那个联通块的重心，否则时间复杂度不对）里走。最后走不动了，走到的点就是带权重心了。
求LCA我用的是\(O(logn)\)的树剖而不是\(O(1)\)搞法，但是跑的贼快（可能和树剖常数小有关？）。
吐槽一点，原题提到了每个点的度数不超过20，但是网上几乎所有OJ上该题的题面都没提到这一点……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
#include <stack>
typedef long long ll;
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
ll dist[maxe];
void add_edge(int u, int v, ll d) {
static int cnt = 0;
cnt ++;
next[cnt] = first[u];
first[u] = cnt;
to[cnt] = v;
dist[cnt] = d;
}
int n;
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
ll dis[maxn];
void dfs_1(int x, int father = 0, int depth = 1, ll d = 0) {
size[x] = 1;
fa[x] = father;
dep[x] = depth;
dis[x] = d;
int max_siz = 0;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father) {
dfs_1(v, x, depth + 1, d + dist[i]);
size[x] += size[v];
if(size[v] > max_siz) {
max_siz = size[v];
hson[x] = v;
}
}
}
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
static int dfn_clk = 0;
dfn[x] = ++ dfn_clk;
tid[dfn[x]] = x;
top[x] = a;
if(!hson[x]) {
return;
} else {
dfs_2(hson[x], x, a);
}
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father && v != hson[x]) {
dfs_2(v, x, v);
}
}
}
int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
x = fa[top[x]];
}
if(dep[x] > dep[y]) {
return y;
} else {
return x;
}
}
ll calc_dist(int x, int y) {
int l = lca(x, y);
return dis[x] + dis[y] - 2LL * dis[l];
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int f = 0) {
siz[x] = 1;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int nrt, rt;
void gen_rt(int x, int f = 0) {
bool flag = (siz[x] * 2 >= siz[nrt]);
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
flag = (flag && (siz[v] * 2 <= siz[nrt]));
gen_rt(v, x);
}
}
if(flag) rt = x;
}
ll w[maxn];
int crt, cfa[maxn];
ll pans[maxn], give[maxn], sumv[maxn];
int point2[maxe];
/*
void search_p(int x, std::stack<int> *V, int f = 0) {
V -> push(x);
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != f) {
search_p(v, V, x);
}
}
}
*/
int divide(int x) {
nrt = rt = x;
gen_siz(x); gen_rt(x);
x = rt; vis[x] = true;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v]) {
int ch = divide(v);
point2[i] = ch;
cfa[ch] = x;
}
}
return x;
}
void update(int x, ll delta) {
int p = x;
while(p) {
pans[p] += delta * calc_dist(p, x);
if(p != crt) give[p] += delta * calc_dist(x, cfa[p]);
sumv[p] += delta;
p = cfa[p];
}
}
ll get_ans(int x) {
ll ans = pans[x];
int p = x;
while(p != crt) {
int f = cfa[p];
ans += pans[f] - give[p];
ans += calc_dist(x, f) * (sumv[f] - sumv[p]);
p = cfa[p];
}
return ans;
}
ll get_best() {
int p = crt;
std::stack<int> S;
ll now_ans;
while(true) {
S.push(p); vis[p] = true;
bool fix = true;
now_ans = get_ans(p);
for(int i = first[p]; i; i = next[i]) {
int v = to[i];
if(vis[v]) continue;
if(get_ans(v) < now_ans) {
fix = false;
p = point2[i];
break;
}
}
if(fix) break;
}
while(!S.empty()) {
int u = S.top(); S.pop();
vis[u] = false;
}
return now_ans;
}
int main() {
int q; scanf("%d%d", &n, &q);
for(int i = 0; i < n - 1; i ++) {
int u, v; ll d; scanf("%d%d%lld", &u, &v, &d);
add_edge(u, v, d); add_edge(v, u, d);
}
dfs_1(1); dfs_2(1);
crt = divide(1); memset(vis, 0, sizeof(vis));
while(q --) {
int u, e; scanf("%d%d", &u, &e);
update(u, e);
printf("%lld\n", get_best());
}
return 0;
}
[LibreOJ 6238][Baltic2015]Network
LibreOJ真是好用（以后尽可能少用BZOJ）
这题我觉得真是个意识流神题。
考虑所有度数为1的点（姑且称为叶子），这些点是一定要向外连边的（只要有一个度数为1的树边不在一个环中，肯定就出桥了）。
那是否可以只在这种叶子之间连边？答案是肯定的。假设叶子上形成了足够多的环，那么上面的边可以随便上。
那是否叶子配对连边就行了（这说明答案是\(\lceil \frac{l}{2}\rceil\)，其中\(l\)是叶子的数目）？答案也是肯定的。但这种方案里显然两个结点间有新边则两点不可能在根的同一棵子树里。
然后就有一种乱搞做法：找到一个根使得每个子树的叶子数都不超过总数的一半（这种点很显然存在），然后从这个根开始DFS，把所有叶子按照DFS序排序一遍，前一半向后一半依次连边。如果叶子数目是奇数，那么最后一个可以随便连。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <set>
#include <vector>
using std::vector;
const int maxn = 500005;
vector<int> G[maxn];
int n;
int leaves[maxn];
vector<int> L;
int leavenum = 0;
void calc_leave(int x, int fa = 0) {
if(int(G[x].size()) == 1) {
leaves[x] = 1; L.push_back(x);
leavenum ++;
}
for(auto v : G[x]) {
if(v != fa) {
calc_leave(v, x);
leaves[x] += leaves[v];
}
}
}
int gen_rt(int x, int fa = 0) {
for(auto v : G[x]) {
if(v != fa && leaves[v] * 2 >= leavenum) {
return gen_rt(v, x);
}
}
return x;
}
int dfn[maxn];
void calc_dfn(int x, int fa = 0) {
static int cnt = 0;
dfn[x] = ++ cnt;
for(auto v : G[x]) {
if(v != fa) {
calc_dfn(v, x);
}
}
}
bool cmp(const int &x, const int &y) {
return dfn[x] < dfn[y];
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n - 1; i ++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v); G[v].push_back(u);
}
calc_leave(1);
int rt = gen_rt(1);
calc_dfn(rt);
sort(L.begin(), L.end(), cmp);
printf("%d\n", (leavenum + 1) / 2);
int half = leavenum / 2;
for(int i = 0; i < half; i ++) {
printf("%d %d\n", L[i], L[i + half]);
}
if(1 & leavenum) {
printf("%d %d\n", L[half - 1], L[leavenum - 1]);
}
return 0;
}
[BZOJ 3925][ZJOI2015]地震后的幻想乡
赛艇，赛艇.jpg
首先这个问题的本质就是让你求一个边权在\([0, 1]\)间均匀随机分布的无向图的MST的最大边边权的期望……
有一个很经典的式子：
\[E = \int_0^1 p(\geq x)\,\mathrm{d}x\]
然后考虑那个\(p\)咋整。
首先对于每个包含1的点集（我们不妨假设是从点1开始扩展）\(S\)，式子可以这么写（这里不妨用\(T\)来表示两个点集间的边的数目）：
\[p_{S, x} = \sum_{1\in S_0 \subset S} (1 - x)^{T(S_0, S - S_0)}(1 - p_{S_0, x})\]
显然答案是\(\int_0^1 p_{S, x}\,\mathrm{d}x\)，但这玩咋求……
然后我们定义一个状态\(d\)：
\[d_{S, k} = \int_0^1 (1 - x)^k p_{S, x}\,\mathrm{d}x\]
把其中的\(p\)展开，整理一下，得到：
\[
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
里面有两大块定积分，前一块还看起来蛮好求的，但后面一块……
不就是\(d_{S_0, T(S, S - S_0) + k}\) 吗？
然后这样整个$d$就可以搞一波状压DP了。
然后观察\(d_{S, 0}\)（这里不妨假设S为全集）：
\[d_{S, 0}=\int_0^1(1 - x)^0 p_{S, x}\,\mathrm{d}x = \int_0^1 p_{S, x}\,\mathrm{d}x\]
这不就是我们要的答案吗？
至于边界处理，\(d_{\{1\}, x}\)全部搞成0就行。
代码：
/**************************************************************
Problem: 3925
User: danihao123
Language: C++
Result: Accepted
Time:100 ms
Memory:1272 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <bitset>
typedef double R;
const int maxn = 11;
const int maxm = 50;
int edge[maxm][2];
int n, m;
R d[1 << 10][maxm];
bool vis[1 << 10][maxm];
R f(int s, int k) {
if(s == 1) return 0;
if(vis[s][k]) return d[s][k];
d[s][k] = 0;
int lit_s = s >> 1;
for(int lit_s0 = (lit_s - 1) & lit_s; ; lit_s0 = (lit_s0 - 1) & lit_s) {
int s0 = lit_s0 * 2 + 1;
int t = 0;
for(int i = 1; i <= m; i ++) {
int u = edge[i][0], v = edge[i][1];
if(((1 << u) & s) == 0 || ((1 << v) & s) == 0) continue;
if((((1 << u) & s0) == 0) ^ (((1 << v) & s0) == 0)) {
t ++;
}
}
int z = k + t;
d[s][k] += 1.00 / ((double(z)) + 1.00) - f(s0, z);
if(s0 == 1) break;
}
vis[s][k] = true;
return d[s][k];
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v); u --, v --;
edge[i][0] = u, edge[i][1] = v;
}
printf("%.6lf\n", f((1 << n) - 1, 0));
return 0;
}
[BZOJ 1095][ZJOI2007]Hide 捉迷藏
蛤蛤蛤我这题终于调出来了~（然后1A了）
点分树处女作。其实点分树的思想并不难理解，就是把点分的过程抽象化到一棵树上。
其实唯一比较烦人的就是点分树上的儿子给父亲的贡献要开一个堆处理……非常烦人。
代码（其中有海量本来拿来调试的代码，慎读）：
/**************************************************************
Problem: 1095
User: danihao123
Language: C++
Result: Accepted
Time:15268 ms
Memory:128944 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
void add_edge(int u, int v) {
static int cnt = 0;
cnt ++;
next[cnt] = first[u];
first[u] = cnt;
to[cnt] = v;
}
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
void dfs_1(int x, int father = 0, int depth = 1) {
size[x] = 1;
fa[x] = father;
dep[x] = depth;
int max_siz = 0;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father) {
dfs_1(v, x, depth + 1);
size[x] += size[v];
if(size[v] > max_siz) {
max_siz = size[v];
hson[x] = v;
}
}
}
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
static int dfn_clk = 0;
dfn[x] = ++ dfn_clk;
tid[dfn[x]] = x;
top[x] = a;
if(!hson[x]) {
return;
} else {
dfs_2(hson[x], x, a);
}
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != father && v != hson[x]) {
dfs_2(v, x, v);
}
}
}
int lca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
x = fa[top[x]];
}
if(dep[x] > dep[y]) {
return y;
} else {
return x;
}
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa = 0) {
siz[x] = 1;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != fa) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int nrt, rt;
void gen_rt(int x, int fa = 0) {
bool ok = (2 * siz[x] >= siz[nrt]);
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v] && v != fa) {
ok = ok && (2 * siz[v] <= siz[nrt]);
gen_rt(v, x);
}
}
if(ok) rt = x;
}
int crt;
int cfa[maxn];
typedef std::priority_queue<int> heap;
struct dheap {
heap Q, D;
void push(int x) {
Q.push(x);
}
void pop() {
while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
printf("deleting %d\n", D.top());
#endif
Q.pop(); D.pop();
}
Q.pop();
}
int top() {
while(!D.empty() && Q.top() == D.top()) {
#ifdef DEBUG
printf("deleting %d\n", D.top());
#endif
Q.pop(); D.pop();
}
return Q.top();
}
void del(int x) {
D.push(x);
}
size_t size() {
return Q.size() - D.size();
}
int sec() {
int fir = top(); pop();
int ret = top(); push(fir);
return ret;
}
};
dheap all;
dheap Q[maxn], sg[maxn];
int divide(int x) {
nrt = rt = x;
gen_siz(x); gen_rt(x);
x = rt; vis[x] = true;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(!vis[v]) {
cfa[divide(v)] = x;
}
}
return x;
}
int n;
int get_ans(dheap &q) {
return q.top() + q.sec();
}
bool sta[maxn];
int dist(int x, int y) {
int ret = dep[x] + dep[y] - 2 * dep[lca(x, y)];
#ifdef DEBUG
printf("dist(%d, %d) : %d\n", x, y, ret);
#endif
return ret;
}
void light_on(int p) {
sta[p] = true;
int x = p;
int og = -1, ng = 0;
while(x) {
int old_ans = -1, old_sg = -1;
if(Q[x].size() > 1) {
old_ans = get_ans(Q[x]);
}
if(sg[x].size() > 0) {
old_sg = sg[x].top();
}
if(og != -1) Q[x].del(og);
if(ng != -1) Q[x].push(ng);
if(Q[x].size() > 1) all.push(get_ans(Q[x]));
if(old_ans != -1) all.del(old_ans);
if(cfa[x] != 0) {
og = old_sg;
sg[x].push(dist(p, cfa[x]));
ng = sg[x].top();
}
x = cfa[x];
}
}
void light_off(int p) {
sta[p] = false;
int x = p;
int og = 0, ng = -1;
while(x) {
int old_ans = -1, old_sg = -1;
if(Q[x].size() > 1) old_ans = get_ans(Q[x]);
if(sg[x].size() > 0) {
old_sg = sg[x].top();
}
if(og != -1) Q[x].del(og);
if(ng != -1) Q[x].push(ng);
#ifdef DEBUG
printf("%d deleting %d\n", x, og);
#endif
if(Q[x].size() > 1) all.push(get_ans(Q[x]));
if(old_ans != -1) all.del(old_ans);
#ifdef DEBUG
int tmp = -1;
if(Q[x].size() > 1) tmp = get_ans(Q[x]);
printf("ans of %d : %d -> %d\n", x, old_ans, tmp);
#endif
if(cfa[x] != 0) {
og = old_sg;
sg[x].del(dist(p, cfa[x]));
if(sg[x].size() > 0) {
ng = sg[x].top();
} else {
ng = -1;
}
}
x = cfa[x];
}
}
void print_dheap(dheap &q) {
std::vector<int> V;
while(q.size() > 0) {
int t = q.top(); q.pop();
printf("%d ", t);
V.push_back(t);
}
puts("");
for(int i = 0; i < V.size(); i ++) {
q.push(V[i]);
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n - 1; i ++) {
int u, v; scanf("%d%d", &u, &v);
add_edge(u, v); add_edge(v, u);
}
dfs_1(1); dfs_2(1);
#ifdef DEBUG
for(int i = 1; i <= n; i ++) {
printf("%d top fa hson : %d %d %d\n", i, top[i], fa[i], hson[i]);
}
#endif
crt = divide(1);
#ifdef DEBUG
printf("crt id %d\n", crt);
for(int i = 1; i <= n; i ++) {
printf("cfa[%d] : %d\n", i, cfa[i]);
}
#endif
int num = 0;
for(int i = 1; i <= n; i ++) {
light_on(i); num ++;
#ifdef DEBUG
printf("heap while inserting %d : ", i);
print_dheap(all);
#endif
}
int q; scanf("%d", &q);
while(q --) {
char op[3]; scanf("%s", op);
if(op[0] == 'G') {
if(num == 0) {
puts("-1");
} else if(num == 1) {
puts("0");
} else {
printf("%d\n", all.top());
}
} else {
int i; scanf("%d", &i);
if(sta[i]) {
light_off(i);
num --;
} else {
light_on(i);
num ++;
}
}
#ifdef DEBUG
print_dheap(all);
#endif
}
return 0;
}
[BZOJ 3295][CQOI2011]动态逆序对
又一道坑了很久没有写题解的……
删除操作特别的棘手，但好在我们可以离线~时光倒流之后，删除就变成了添加。
每个点加进来之后，对答案的贡献可以分为两部分：
- 加入比他早，位置在他前面，值比他大的点。
- 加入比他早，位置在他后面，值比他小的点。
然后两者都可以用CDQ统计（我还偷懒用同一个CDQ做的）。
代码：
/**************************************************************
Problem: 3295
User: danihao123
Language: C++
Result: Accepted
Time:2332 ms
Memory:5768 kb
****************************************************************/
#include <cstdio>
#include <stack>
#include <algorithm>
using std::stack;
using std::sort;
const int maxn = 100005;
typedef long long ll;
struct Query {
int id;
int p, v;
};
int n;
ll C[maxn];
int lowbit(int x) {
return x & (-x);
}
void add(int p, int v) {
while(p <= n) {
C[p] += v;
p += lowbit(p);
}
}
ll sum(int p) {
ll ret = 0;
while(p > 0) {
ret += C[p];
p -= lowbit(p);
}
return ret;
}
int query(int l, int r) {
return sum(r) - sum(l - 1);
}
void clean(int p) {
while(p <= n && C[p] != 0) {
C[p] = 0;
p += lowbit(p);
}
}
Query A[maxn], tmp[maxn];
ll ans[maxn];
void CDQ(int L, int R, bool flag) {
if(L == R) {
return;
}
int M = L + (R - L) / 2;
CDQ(L, M, flag); CDQ(M + 1, R, flag);
for(int p = L, l = L, r = M + 1; p <= R; p ++) {
if(r > R || (l <= M && (flag ? A[l].p < A[r].p : A[l].p > A[r].p))) {
tmp[p] = A[l];
add(A[l].v, 1);
l ++;
} else {
tmp[p] = A[r];
ans[A[r].id] += query(A[r].v + 1, n);
r ++;
}
}
for(int i = L; i <= M; i ++) {
clean(A[i].v);
}
for(int i = L; i <= R; i ++) {
A[i] = tmp[i];
}
}
bool cmp_id(const Query& a, const Query& b) {
return a.id < b.id;
}
int arr[maxn];
bool del[maxn];
int pos[maxn];
stack<int> delS;
int main() {
int m;
scanf("%d%d", &n, &m);
int id_siz = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", &arr[i]);
}
for(int i = 1; i <= m; i ++) {
int a;
scanf("%d", &a);
delS.push(a);
del[a] = true;
}
for(int i = 1; i <= n; i ++) {
if(del[arr[i]]) {
pos[arr[i]] = i;
} else {
id_siz ++;
A[id_siz].id = id_siz;
A[id_siz].p = i;
A[id_siz].v = arr[i];
}
}
while(!delS.empty()) {
int a = delS.top(); delS.pop();
id_siz ++;
A[id_siz].id = id_siz;
A[id_siz].p = pos[a];
A[id_siz].v = a;
}
CDQ(1, n, true);
sort(A + 1, A + 1 + n, cmp_id);
for(int i = 1; i <= n; i ++) {
A[i].v = n - A[i].v + 1;
}
CDQ(1, n, false);
for(int i = 1; i <= n; i ++) {
ans[i] += ans[i - 1];
}
for(int i = 0; i < m; i ++) {
printf("%lld\n", ans[n - i]);
}
return 0;
}
[BZOJ 2733][HNOI2012]永无乡
我这题竟然很早就做了……
求k小显然可以用平衡树。但是这个题还需要快速的合并平衡树，那就需要启发式合并了。
