D. Money Game
一开始有 \(n\) 个人围成一圈，第 \(i\) 个人手上有 \(a_i\) 的存款（实数），每一轮从第一个人开始，每个人把自己手上的一半存款给下一个人，问稳定时每个人手上存款有多少。
考虑两个人的情况：
\[(x,1) \to (x/2,1+x/2) \to (3/4x+1/2,1/2+x/4) \]所以：
\[x=2 \]类似的，三个人的情况可以知道稳态解为：
\[(2,1,1) \]不难发现，\(n\) 个人的稳态解一定是：
\[(2,1,1,1,1,\cdots,1) \]相当于每个人给下一个人传了一单位。
设 \(w=\frac{1}{n+1}\sum_{i=1}^{n} a_i\)，则答案为：
\[(2w,w,w,\cdots,w) \]#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int n;
ll a[N];
int main() {
scanf("%d", &n);
ll sum = 0;
for(int i = 1 ; i <= n ; ++ i) {
scanf("%lld", &a[i]);
sum += a[i];
}
ll prod = n + 1;
printf("%.6lf ", (double) sum * 2 / prod);
double tmp = (double) sum / prod;
for(int i = 2 ; i <= n ; ++ i) {
printf("%.6lf ", tmp);
}
}
F. Da Mi Lao Shi Ai Kan De
签到题，为了防止被卡hash还写了个双hash。
#include <bits/stdc++.h>
using namespace std;
int n;
int len;
set<pair<int, int> > vis;
const int b1 = 149, b2 = 137;
const int m1 = 998244353, m2 = 1e9 + 7;
typedef long long ll;
char str[int(1e5) + 10];
int geths(int b, int m) {
int res = 0;
for(int i = 1 ; i <= len ; ++ i) {
res = ((ll) res * b + str[i]) % m;
}
return res;
}
int hasstr() {
int h1 = geths(b1, m1);
int h2 = geths(b2, m2);
if(vis.find(make_pair(h1, h2)) == vis.end()) {
vis.insert(make_pair(h1, h2));
return 0;
} else {
return 1;
}
}
int bie() {
for(int i = 1 ; i + 2 <= len ; ++ i) {
if(str[i] == 'b') {
if(str[i + 1] == 'i' && str[i + 2] == 'e') {
return 1;
}
}
}
return 0;
}
int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n ; ++ i) {
int m; scanf("%d", &m);
int flag = 0;
while(m --) {
scanf("%s", str + 1);
len = strlen(str + 1);
if(bie()) {
if(!hasstr()) {
puts(str + 1);
flag = 1;
}
}
}
if(!flag) {
puts("Time to play Genshin Impact, Teacher Rice!");
}
}
}
M. Please Save Pigeland
给定一棵 \(n\) 个点的树，上面有 \(k\) 个关键点，对于每一个点 \(u\)，求：
- \(u\) 到所有关键点的距离之和；
- \(u\) 到所有关键点的距离的 \(\gcd\)。
首先 \(u=1\) 时，这两个信息都很容易求到，考虑换根的同时维护这两个信息。
将关键点的 dfs 序离散化，当转移 \(u \to v\) 时（边权为 \(w\)），相当于把在 \(v\) 子树内的关键点距离都减去 \(w\)，然后把在 \(V\) 子树外的关键点距离都加上 \(w\)，即在 dfs 序上是维护区间加，然后查询全区间的和。
对于 \(\gcd\) 信息，由更相减损术可知：
\[\boxed{ \gcd(a_1,a_2,\cdots,a_n)=\gcd(a_1,a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1}) } \]因此只需要维护差分数组的 \(\gcd\)，然后求 \([2,n]\) 的 \(\gcd\) 与原数组 \([1,1]\) 的 \(\gcd\) 即可。
需要注意一些边界情况：
- 若 \(k=1\)，则答案为 \(0\)；
- 若某一个点的子树中无关键点，则转移到这个点时应该将全区间的距离都加上 \(w\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct FastIO {
static const int S = 2e7;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar() {
static char buf[S];
static int len = 0, pos = 0;
if (pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if (pos == len) exit(0);
return buf[pos++];
}
inline int operator () () {
int c = xchar(), x = 0, flag = 0;
while (c <= 32) flag |= c == '-', c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return flag ? -x : x;
}
inline ll operator ! () {
int c = xchar(); ll x = 0;
while (c <= 32) c = xchar();
for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline void wchar(int x) {
if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos++] = x;
}
inline void operator () (ll x) {
if (x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n) s[n++] = '0' + x % 10, x /= 10;
while (n--) wchar(s[n]);
wchar('\n');
}
inline void space(ll x) {
if (x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while (x || !n) s[n++] = '0' + x % 10, x /= 10;
while (n--) wchar(s[n]);
wchar(' ');
}
inline void nextline() {
wchar('\n');
}
~FastIO() {
if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
const int N = 1e6 + 10;
int n, k;
int head[N], rest[N * 2], to[N * 2], w[N * 2], tot;
void add(int u, int v, int w) {
to[++ tot] = v;
:: w[tot] = w;
rest[tot] = head[u];
head[u] = tot;
}
int imp[N];
int clk, dfnl[N], dfnr[N], rev[N], tid[N];
ll dep[N];
int sz[N];
ll bgcd(ll a, ll b) {
return b ? bgcd(b, a % b) : a;
}
#define lc (id << 1)
#define rc (id << 1 | 1)
namespace seg_diff {
ll gcd[N * 8];
void modify(int id, int l, int r, int pos, ll val) {
if(pos < l || pos > r) return ;
int mid = (l + r) >> 1;
if(l == r) {
gcd[id] += val;
return ;
} else if(pos <= mid) {
modify(lc, l, mid, pos, val);
} else {
modify(rc, mid + 1, r, pos, val);
}
gcd[id] = bgcd(gcd[lc], gcd[rc]);
}
ll query(int id, int l, int r, int ql, int qr) {
int mid = (l + r) >> 1;
if(ql <= l && r <= qr) {
return gcd[id];
} else if(qr < l || ql > r) {
return 0;
} else {
return bgcd(query(lc, l, mid, ql, qr), query(rc, mid + 1, r, ql, qr));
}
}
};
namespace seg_norm {
ll tag[N * 8], sum[N * 8];
void modify(int id, int l, int r, int ql, int qr, ll val) {
if(ql <= l && r <= qr) {
tag[id] += val;
} else if(qr < l || ql > r) {
return ;
} else {
int mid = (l + r) >> 1;
sum[id] += val * (min(r, qr) - max(l, ql) + 1);
modify(lc, l, mid, ql, qr, val);
modify(rc, mid + 1, r, ql, qr, val);
}
}
ll query(int id, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return sum[id] + tag[id] * (r - l + 1);
} else if(qr < l || ql > r) {
return 0;
} else {
int mid = (l + r) >> 1;
ll t = tag[id] * (min(r, qr) - max(l, ql) + 1);
return t + query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr);
}
}
};
ll ans_dis[N], ans_gcd[N];
int rev_l[N], rev_r[N];
signed main() {
n = io(), k = io();
for(int i = 1, x ; i <= k ; ++ i) {
imp[io()] = 1;
}
for(int i = 1 ; i < n ; ++ i) {
int u = io(), v = io(), w = io();
add(u, v, w);
add(v, u, w);
}
if(k == 1) {
puts("0");
return 0;
}
if(1) {
function<void(int, int)> dfs = [&] (int u, int fa) {
++ clk;
dfnl[u] = clk;
tid[clk] = u;
sz[u] = imp[u];
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i];
if(v == fa) continue;
dep[v] = dep[u] + w[i];
dfs(v, u);
sz[u] += sz[v];
}
dfnr[u] = clk;
};
dfs(1, 0);
}
vector<int> lsh;
for(int i = 1 ; i <= n ; ++ i) {
if(imp[i]) {
lsh.push_back(dfnl[i]);
}
}
sort(lsh.begin(), lsh.end());
lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
for(int i = 1 ; i <= n ; ++ i) {
rev[i] = lower_bound(lsh.begin(), lsh.end(), dfnl[i]) - lsh.begin() + 1;
rev_l[i] = rev[i];
rev_r[i] = upper_bound(lsh.begin(), lsh.end(), dfnr[i]) - lsh.begin();
rev_r[i] = max(rev_r[i], rev_l[i]);
}
int len = lsh.size();
vector<int> arr;
for(int i = 0 ; i < len ; ++ i) {
arr.push_back(tid[lsh[i]]);
}
for(int i = 0 ; i < len ; ++ i) {
seg_norm :: modify(1, 1, len, i + 1, i + 1, dep[arr[i]]);
seg_diff :: modify(1, 1, len, i + 1, dep[arr[i]] - (i==0?0:dep[arr[i-1]]));
}
if(1) {
function<void(int, int)> dfs = [&] (int u, int fa) {
ans_dis[u] = seg_norm :: query(1, 1, len, 1, len);
ans_gcd[u] = bgcd(seg_norm :: query(1, 1, len, 1, 1),
seg_diff :: query(1, 1, len, 2, len));
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i];
if(v == fa) continue;
if(sz[v] == 0) {
seg_norm :: modify(1, 1, len, 1, len, w[i]);
seg_diff :: modify(1, 1, len, 1, w[i]);
dfs(v, u);
seg_norm :: modify(1, 1, len, 1, len, -w[i]);
seg_diff :: modify(1, 1, len, 1, -w[i]);
} else {
seg_norm :: modify(1, 1, len, rev_l[v], rev_r[v], -w[i]);
seg_norm :: modify(1, 1, len, 1, rev_l[v]-1, w[i]);
seg_norm :: modify(1, 1, len, rev_r[v]+1, len, w[i]);
seg_diff :: modify(1, 1, len, 1, w[i]);
seg_diff :: modify(1, 1, len, rev_l[v], -2*w[i]);
seg_diff :: modify(1, 1, len, rev_r[v]+1, 2*w[i]);
dfs(v, u);
seg_norm :: modify(1, 1, len, rev_l[v], rev_r[v], w[i]);
seg_norm :: modify(1, 1, len, 1, rev_l[v]-1, -w[i]);
seg_norm :: modify(1, 1, len, rev_r[v]+1, len, -w[i]);
seg_diff :: modify(1, 1, len, 1, -w[i]);
seg_diff :: modify(1, 1, len, rev_l[v], 2*w[i]);
seg_diff :: modify(1, 1, len, rev_r[v]+1, -2*w[i]);
}
}
};
dfs(1, 0);
}
ll ans = ans_dis[1] / abs(ans_gcd[1]);
for(int i = 1 ; i <= n ; ++ i) {
ans = min(ans, ans_dis[i] / abs(ans_gcd[i]));
}
printf("%lld\n", ans * 2);
}