2020 ccpc 威海
G Caesar Cipher
题意:
给你n个数， 你有两种操作
1.将区间 ([l, r])的数加1， 同时在模上65536
2.询问 ([l, l + x], [r, r + x]) 问这两段区间是否一样
判断两个区间是否一样？很容易想到哈希， 对于操作如果直接取模那么就很有可能出现hash冲突， 但是如果维护一个最大值， 然后暴力修改， 然后hash值取模改成1e9 + 7就可以a了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 100;
struct segment {
ll sum, ha, maxn;
}tree[40 * N];
ll fn[N], a[N], flag[40 * N];
const ll mod = 1e9 + 7;
#define m (l + r) / 2
#define lson 2 * node
#define rson 2 * node + 1
void build(int l, int r, int node) {
if (l == r) {
tree[node].sum = fn[l];
tree[node].ha = fn[l] * a[l];
tree[node].maxn = a[l];
return;
}
build(l, m, lson);
build(m + 1, r, rson);
tree[node].sum = tree[lson].sum + tree[rson].sum;
tree[node].maxn = max(tree[lson].maxn, tree[rson].maxn);
tree[node].ha = (tree[lson].ha + tree[rson].ha) % mod;
}
void push_down(int node) {
if (flag[node]) {
tree[lson].maxn += flag[node];
tree[rson].maxn += flag[node];
tree[lson].ha = (tree[lson].ha + (flag[node] % mod * tree[lson].sum % mod) % mod) % mod;
tree[rson].ha = (tree[rson].ha + (flag[node] % mod * tree[rson].sum % mod) % mod) % mod;
flag[lson] += flag[node];
flag[rson] += flag[node];
flag[node] = 0;
}
}
void work(int l, int r, int node) {
if (l == r) {
tree[node].maxn = tree[node].maxn % 65536;
tree[node].ha = tree[node].maxn * tree[node].sum % mod;
return;
}
push_down(node);
if (tree[lson].maxn >= 65536) {
work(l, m, lson);
}
if (tree[rson].maxn >= 65536) {
work(m + 1, r, rson);
}
tree[node].maxn = max(tree[lson].maxn, tree[rson].maxn);
tree[node].ha = (tree[lson].ha + tree[rson].ha) % mod;
}
void update(int ql, int qr, int l, int r, int node) {
if (ql <= l && qr >= r) {
tree[node].maxn++;
tree[node].ha = (tree[node].ha + tree[node].sum) % mod;
flag[node]++;
if (tree[node].maxn >= 65536) {
push_down(node);
work(l, r, node);
}
return;
}
push_down(node);
if (ql <= m) update(ql, qr, l, m, lson);
if (qr > m) update(ql, qr, m + 1, r, rson);
tree[node].maxn = max(tree[lson].maxn, tree[rson].maxn);
tree[node].ha = (tree[lson].ha + tree[rson].ha) % mod;
}
ll query(int ql, int qr, int l, int r, int node) {
if (ql <= l && qr >= r) {
return tree[node].ha;
}
ll ans = 0;
push_down(node);
if (ql <= m) ans = (ans + query(ql, qr, l, m, lson)) % mod;
if (qr > m) ans = (ans + query(ql, qr, m + 1, r, rson)) % mod;
return ans;
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
fn[1] = 1;
for (int i = 2; i <= n + 10; i++) {
fn[i] = fn[i - 1] * 27;
fn[i] %= mod;
}
build(1, n, 1);
while (q--) {
int op, l, r;
scanf("%d %d %d", &op, &l, &r);
if (op == 1) {
update(l, r, 1, n, 1);
} else {
int x; scanf("%d", &x);
ll ha = query(l, l + x - 1, 1, n, 1);
ll ha1 = query(r, r + x - 1, 1, n, 1);
if (l > r) {
int len = l - r;
ha1 = ha1 * fn[len + 1] % mod;
} else {
int len = r - l;
ha = ha * fn[len + 1] % mod;
}
if (ha == ha1) {
puts("yes");
} else {
puts("no");
}
}
}
}
C Rencontre
题意：
给你一颗树， 然后有三个人每个选择m个点最后问这三个到达某个点最短的期望是多少？
题解：
这题有个东西要知道， 假设树上有三个点 (a,b, c)那么这三个点到某点的最近距离是 (frac{1}{2}(dist(a, b) + dist(b, c) + dist(a, c))) 如果你知道这个公式那么答案不就是求
(ans = frac{sum_{iin{a}} sum_{jin{b}} sum_{zin{c}} dist(i, j) + dist(j, z)+ dist(i, z)}{2})
最后的期望就等于 (frac{ans}{cnta * cntb * cntc}) （(cnta)表示a的数量）
等于上面的公式可以在继续化简得到
((sum_{iin{a}} sum_{jin{c}} dist(i, j) ) * cntc + (sum_{iin{a}} sum_{jin c} dist(i, j)) * cntb + (sum_{iin{b}} sum_{jin{c}} dist(i, j) ) * cnta)
知道这个公式后就可以用dp求出 所有a到b的距离和， 所有a到c的距离和， 所有b到c的距离后。
注意爆long long
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
ll dp[N][3], sz[N][3];
int head[N], top = 1, n, a[N], b[N], c[N], visa[N], visb[N], visc[N];
struct edge {
int to, w, nxt;
}e[2 * N];
void add_edge(int u, int v, int w) {
e[top].to = v;
e[top].w = w;
e[top].nxt = head[u];
head[u] = top++;
}
__int128 ab = 0, ac = 0, bc = 0;
ll ma, mb, mc, sum;
void dfs(int u, int fa) {
if (visa[u]) {
sz[u][0] = 1;
}
if (visb[u]) {
sz[u][1] = 1;
}
if (visc[u]) {
sz[u][2] = 1;
}
for (int i = head[u]; i; i = e[i].nxt) {
int to = e[i].to;
int w = e[i].w;
if (to == fa) {
continue;
}
dfs(to, u);
dp[u][0] += dp[to][0] + sz[to][0] * 1ll * w;
dp[u][1] += dp[to][1] + sz[to][1] * 1ll * w;
dp[u][2] += dp[to][2] + sz[to][2] * 1ll * w;
sz[u][0] += sz[to][0];
sz[u][1] += sz[to][1];
sz[u][2] += sz[to][2];
}
}
ll fn[N][3], fz[N][3];
void dfs1(int u, int fa) {
if (visa[u]) {
ac += fn[u][2];
ab += fn[u][1];
}
if (visb[u]) {
bc += fn[u][2];
}
for (int i = head[u]; i; i = e[i].nxt) {
int to = e[i].to;
int w = e[i].w;
if (to == fa) continue;
ll sb = fn[u][1] - dp[to][1] - 1ll* w * sz[to][1];
sb = sb + w * (mb - sz[to][1]);
fn[to][1] = sb + dp[to][1];
ll sc = fn[u][2] - dp[to][2] - 1ll * w * sz[to][2];
sc = sc + w * (mc - sz[to][2]);
fn[to][2] = sc + dp[to][2];
dfs1(to, u);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
scanf("%d", &ma);
for (int i = 1; i <= ma; i++) {
scanf("%d", &a[i]);
visa[a[i]] = 1;
}
scanf("%d", &mb);
for (int i = 1; i <= mb; i++) {
scanf("%d", &b[i]);
visb[b[i]] = 1;
}
scanf("%d", &mc);
for (int i = 1; i <= mc; i++) {
scanf("%d", &c[i]);
visc[c[i]] = 1;
}
sum = ma * mb * mc;
dfs(1, 0);
fn[1][0] = dp[1][0];
fn[1][1] = dp[1][1];
fn[1][2] = dp[1][2];
dfs1(1, 0);
__int128 ans = ac * mb + bc * ma + ab * mc;
ans = ans / 2;
double res = (double)ans / (double)sum;
printf("%.9f
", res);
}