A Maximal Value

模拟即可。

时间复杂度 $\mathcal O(n)$ 。

 void solve() {
     int n;
     cin >> n;
     vector<int> a(n);
     for (auto &v : a) cin >> v;
     int ans = 0;
     for (int i = 1; i < n - 1; ++i) ans += a[i] > a[i - 1] && a[i] > a[i + 1];
     cout << ans << endl;
 }

B Corridor Watch

$m,d$ 只有 $100$ ，暴力修改即可。

时间复杂度 $\mathcal O(md)$ 。

 void solve() {
     int m, d;
     cin >> m >> d;
     string s;
     cin >> s;
     vector<int> a(m), pos;
     for (int i = 0; i < m; ++i)
         if (s[i] == 'G') pos.push_back(i), a[i] = 1;
     for (auto v : pos) {
         for (int i = max(0LL, v - d); i <= min(m - 1, v + d); ++i) a[i] = 1;
     }
     cout << m - accumulate(a.begin(), a.end(), 0LL) << endl;
 }

C Between P and Q

基础康拓展开$^*$板子题。

康拓展开：用于计算给定排列的字典序。

时间复杂度 $\mathcal O(n^2)$ 。

 int f[20];
 
 void init() {
     f[0] = f[1] = 1;
     for (int i = 2; i < 20; i++) f[i] = f[i - 1] * i;
 }
 
 void solve() {
     int n;
     cin >> n;
     vector<int> p(n), q(n);
     for (auto &v : p) cin >> v;
     for (auto &v : q) cin >> v;
     auto kangtuo = [&](vector<int> str) {
         int ans = 1;
         for (int i = 0; i < n; i++) {
             int tmp = 0;
             for (int j = i + 1; j < n; j++)
                 if (str[i] > str[j]) tmp++;
             ans += tmp * f[n - i - 1];
         }
         return ans;
     };
     int x = kangtuo(p), y = kangtuo(q);
     cout << max(y - x - 1, 0LL) << endl;
 }

D Pre-Palindrome

对于每个中心，暴力扩展即可。

时间复杂度 $\mathcal O(n^2)$ 。

 void solve() {
     string s;
     cin >> s;
     int n = s.size(), ans = 0;
     auto ssolve = [&](int l, int r) {    
         int cnt = 0;
         while (l >= 0 && r < n) {
             if (s[l] != s[r]) cnt++;
             if (cnt > 1) break;
             ans++, l--, r++;
         }
     };
     for (int i = 0; i < n; ++i) ssolve(i, i);
     for (int i = 0; i + 1 < n; ++i) ssolve(i, i + 1);
     cout << ans << endl;
 }

E Sum of Average

$$Ans = \sum\limits_{1\leq l\leq r\leq n} \frac{a_l + a_{l+1} + … + a_r}{r – l + 1}$$

对于每一个元素，系数为

$$w_i = \sum\limits_{l\leq i\leq r} \frac{1}{r – l + 1}$$

令 x = i-l, y = r-i

$$w_i = \sum_{x=0}^{i-1}\sum_{y=0}^{n-i}\frac{1}{x+y+1}$$

固定 x 对 y 求和

$$\sum_{y=0}^{n-i} \frac{1}{x+y+1} = \frac 1{x+1} + \frac 1{x+2} + \cdots + \frac 1{x+n-i+1} = H_{x+n-i+1} – H_{x}$$

所以

$$w_i = \sum_{x=0}^{i-1}(H_{x+n-i+1} – H_{x}) = \sum_{x=n-i+1}^{n} H_x – \sum_{x=0}^{i-1}H_x$$

令 P_x = \sum H_x = (x+1)H_x – x

$$w_i= P_n – P_{n-i} – P_{i-1}$$

时间复杂度 $\mathcal O (n)$ 。

 vector<Z> h(N + 1), p(N + 1);
 
 void init() {
     h[1] = 0;
     for (int i = 1; i <= N; ++i) h[i] = h[i - 1] + Z(1) / i, p[i] = (i + 1) * h[i] - i;
 }
 
 void solve() {
     int n;
     cin >> n;
     vector<Z> a(n + 1);
     for (int i = 1; i <= n; ++i) cin >> a[i];
     Z ans = 0;
     for (int i = 1; i <= n; ++i) ans += a[i] * (p[n] - p[n - i] - p[i - 1]);
     cout << ans << endl;
 }

F Chmax

设当前已经处理过的元素最大值为 mx 。因为每个元素都必须被放入 x 或 y，始终有：

$$max(x, y) = mx$$

若当前 P_k > mx ，它是前缀最大值，必然大于 x,y，因此必得一分。把它放到当前较大的变量上即可，保留较小变量的值，这永远不劣。

对于不是前缀最大值的 P_k ：

放到较大变量上，不得分且状态不变；
放到较小变量上，只有当它大于该变量时才得分，且该变量变为 P_k 。

因此，除去所有前缀最大值后，能额外得分的元素必须组成一个严格递增子序列；反过来也可以按该递增子序列操作。

所以答案为前缀最大值个数 + 非前缀最大值的 LIS 长度

时间复杂度 $O(nlogn)$ 。

 void solve() {
     int n;
     cin >> n;
     vector<int> p(n);
     for (auto &v : p) cin >> v;
     int mx = 0, ans = 0;
     vector<int> lis;
     for (auto v : p) {
         if (v > mx)
             ans++, mx = v;
         else {
             auto it = lower_bound(lis.begin(), lis.end(), v);
             if (it == lis.end())
                 lis.push_back(v);
             else
                 *it = v;
         }
     }
     cout << ans + lis.size() << endl;
 }

G Restricted Permutation

记 E_k 表示值集合 {1,2,\ldots,k} 在排列中恰好占据一个连续段。显然 E_1,E_N 恒成立，因此若 S_1 或 S_N 为 \texttt{x}，答案为 0。

设所有 \texttt{o} 的位置为：

$$a_0=1<a_1<\cdots<a_m=N$$

相邻两个连续块 1,a_{j-1} 与 1,a_j 之间，令 d=a_j-a_{j-1}。将前一个块收缩为一个编号为 0 的点，其余新增的 d 个数重新编号为 1,2,\ldots,d。

此时，中间所有位置均为 \texttt{x}，等价于在这 d+1 个点的排列中，任意真前缀集合 {0,1,\ldots,i}，其中 1\le i<d，都不能形成连续段。

记 f_d 为这种局部排列的数量。对任意 d+1 个点的排列，设首次出现连续前缀块的位置为 i。其内部排列有 f_i 种，收缩后剩余 d+1-i 个元素可任意排列，因此：

$$(d+1)! = \sum_{i=1}^{d} f_i(d+1-i)!$$

于是递推得到：

$$f_d=(d+1)!-\sum_{i=1}^{d-1}f_i(d+1-i)!$$

每一段的选择相互独立，答案为：

$$\prod_{j=1}^{m} f_{a_j-a_{j-1}}$$

时间复杂度 $\mathcal{O}(n^2)$ 。

 void solve() {
     int n;
     string s;
     cin >> n >> s;
     if (s[0] == 'x' || s[n - 1] == 'x') return cout << 0 << endl, void();
     vector<Z> f(n);
     for (int i = 1; i < n; ++i) {
         f[i] = C.fac(i + 1);
         for (int j = 1; j < i; ++j) {
             f[i] -= f[j] * C.fac(i + 1 - j);
         }
     }
     vector<int> a;
     for (int i = 0; i < n; ++i)
         if (s[i] == 'o') a.push_back(i + 1);
     Z ans = 1;
     for (int i = 1; i < a.size(); ++i) ans *= f[a[i] - a[i - 1]];
     cout << ans << endl;
 }