AGC010C

先找个非叶子作为根，（把 \(n=2\) 判掉），然后考虑一个等效次数 \(f(u)\)，就是相当于一个节点和儿子必须满足方程：\(\exists\,x:f(u)=a[u]-x=sum-2x\) ，其中 \(x\) 是对当前节点的等效情形的操作次数。这样对于每个经过 \(u\) 的路径就可以合理地分配给各个儿子，从而分配到最后的叶子。于是 dfs 一遍判每个节点的解 \(x\) 是否存在就做完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//　静かな海
#include <bits/stdc++.h>
#define dbg(x, y...) fprintf(stderr, x, y)
#define pline() (dbg("Passing Line #%d in Func [%s]", __LINE__, __FUNCTION__))
using namespace std;

inline int rd() {
  int x=0,c,f=1;while(!isdigit(c=getchar()))if(c=='-')f=-1;
  for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}
const int N = 1e5+3;
#define int long long

int n, a[N], f[N], d[N];
vector<int> G[N];

void dfs(int u, int fa) {
  if (d[u] == 1) return void(f[u] = a[u]);

  int sum = 0, mx = 0;
  for (int v:G[u]) if (v^fa) {
    dfs(v, u);
    sum += f[v], mx = max(mx, f[v]);
  }

  f[u] = 2*a[u] - sum;
  if (a[u] > sum || a[u] < mx || f[u] < 0)
    puts("NO"), exit(0);
}

signed main() {
  n = rd();
  for (int i=1; i<=n; i++) a[i] = rd();
  if (n == 2) return 0 * puts(a[1] == a[2] ? "YES" : "NO");
  for (int i=1; i<n; i++) {
    int u = rd(), v = rd();
    G[u].push_back(v), G[v].push_back(u);
    d[u]++, d[v]++;
  }

  int rt;
  for (int i=1; i<=n; i++)
    if (d[i] > 1) { rt = i; break; }
  
  dfs(rt, 0);

  puts(f[rt] ? "NO" : "YES");
}

AGC011D

有点水，推一推或者直接打表都可以发现每次要么第一个数取反要么整体左移并取反， 以至于很快尾部出现 BABA 型循环节，最后把所有数字顶掉，形成 1~2 周期的循环， 于是 bitset 暴力模拟一下即可。

不知道为啥 47 个点就是过不去，WA，就放这儿吧，反正只有我自己看这文章，懒得仔细看了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//　静かな海
#include <bits/stdc++.h>
#define dbg(x, y...) fprintf(stderr, x, y)
#define pline() (dbg("Passing Line #%d in Func [%s]", __LINE__, __FUNCTION__))
using namespace std;

inline int rd() {
  int x=0,c,f=1;while(!isdigit(c=getchar()))if(c=='-')f=-1;
  for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}
const int N = 1e5+3;

int n, k;
bitset<200000> b;

signed main() {
  n = rd(), k = rd();
  for (int i=0; i<n; i++)
    b[i] = getchar() == 'B';
  
  int tg = 0;
  for (int i=1; i<=k && i<=2*n+1; i++) {
    if (b[0] ^ tg) b>>=1, tg ^= 1, b[n-1] = tg;
    else b[0].flip();
  }

  if (2*n+1 < k) {
    int rem = k - 2*n - 1;
    if (!(b[0] ^ tg)) tg ^= rem & 1;
  }

  for (int i=0; i<n; i++)
    putchar((b[i]^tg) ? 'B' : 'A');
  
  putchar('\n');
}

Over

一个国家有 \(N\) 个村庄，第 \(i\) 个村庄有一个奇妙的权值 \(A_i\)，以及另一个奇妙的权值 \(B_i\)。 其中 \(B_i=\sum_j^i A_j\)。 我们保证 \(B_N=0\)。

现在要从任意一个村庄出发，遍历除起点外任意不少于\(1\)个村庄，之后回到起始村庄。当从第\(i\)个村庄走到第\(j\)个村庄的时候，贡献是\(\dfrac{(A_i−A_j)B_iB_j}{2A_iA_j}\)。

假设遍历顺序是 \(P_1,P_2,P_3,...,P_k,P_{k+1}\)（当然，由于起始位置必须相同，这里 \(P_{k+1}=P_1\)），他希望存在一个 \(2\le i\le k\)，使得对于任意 \(j<i\), 都满足 \(B_{P_j}\le B_{P_{j+1}}\)；而对于任意 \(k\ge j\ge i\), 都满足\(B_{P_j}\ge B_{P_{j+1}}\)。

换句话说，\(B\) 权值在到达某个村庄之前是单调不降的，而之后又是单调不增的。在这个限制下最大化贡献和。

\[ \frac{(A_i−A_j)B_iB_j}{2A_iA_j}=\frac12\left(B_i\frac{B_j}{A_j}-B_j\frac{B_i}{A_i}\right) \]

于是求凸包面积即可

1
// gugu