Namomo Test Round 2

Tsukkomi

A 忘开 long long WA 一发,数组开小了 TLE 一发 qwq
B 又忘开 long longWA 一发 他忘开 long long 一直可以的 qwq
C, D 直接不会,总得来说这场打得很僵硬 orz


Problem A. 请求配对

Description

给定 2n2n (1n105)\left(1\leq n\leq10^5\right) 个属于 [1,109]\left[1,10^9\right] 的整数,初始时 ans=1ans=1 .
现进行 nn 次操作,每次取两个未被取过的整数 x,yx,y 并令 ans=ans(x+y)ans=ans\left(x+y\right) .
存在一种方案使得 ansans 最大,求这个最大值,结果对 109+710^9+7 取模。

Solution

签到题。

设这 2n2n 个整数的 均值avgavg .
均值不等式 知应使得每次操作的 x+yx+y 尽可能靠近 2avg2avg .
易证将整数 排序 后依次 首尾配对 即可。

时间复杂度:O(nlogn)\mathcal O\left(n\log n\right) .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int p = 1e9 + 7;
int n, x[N << 1];
int ans;

void solve(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n), ans = 1;
for (int i = 1; i <= 2 * n; i++) scanf("%d", x + i);
sort(x + 1, x + 2 * n + 1);
for (int i = 1; i <= n; i++)
ans = (ans * 1ll * (x[i] + x[2 * n - i + 1]) % p) % p;
printf("%d\n", ans);
}

Problem B. Namomo子串

Description

称字符串 SSNamomo 串,当且仅当:

  • 2S2\mid\left|S\right| ,仅由小写字母构成。
  • 下标从 11 开始,奇数下标位置为辅音字母,偶数下标位置为元音字母。
    辅音字母指非元音字母,元音字母指 a, e, i, o, u .
  • S6\left|S\right|\geq6 ,且对 i(4,S], Si=Si2\forall i\in\left(4,\left|S\right|\right],\ S_i=S_{i-2} .

给定仅由小写字母构成的字符串 SS (1S5×105)\left(1\leq\left|S\right|\leq5\times10^5\right) ,求有多少个 Namomo 子串。

Solution

注意到长度为 2k2k (k3)\left(k\geq3\right)Namomo 串共包含 (k1)(k2)2\frac{\left(k-1\right)\left(k-2\right)}2Namomo 子串。
仅枚举不被 Namomo 串包含的 Namomo 子串,求 贡献 即可。

时间复杂度:O(S)\mathcal O\left(\left|S\right|\right) .

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 5e5 + 5;
char s[N];
int n;
bool isv[N];
ll ans;

void solve(void);
bool isvowel(char x);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%s", s + 1), n = strlen(s + 1);
for (int i = 1; i <= n; i++) isv[i] = isvowel(s[i]);
for (int i = 1, k; i < n - 2; i++) {
if (isv[i] || !isv[i + 1]) continue;
if (i > 2 && s[i] == s[i - 2] && s[i + 1] == s[i - 1]) continue;
k = (i > 2 && !isv[i - 2] && isv[i - 1]) + 1;
for (int j = i + 2; j < n; j += 2, k++)
if (s[j] != s[i] || s[j + 1] != s[i + 1]) break;
ans += (k - 1) * 1ll * (k - 2) / 2;
}
printf("%lld\n", ans);
}

inline bool isvowel(char x) {
return x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u';
}

Problem C. 序列

Description

给定长度为 nn (1n5×105)\left(1\leq n\leq5\times10^5\right) 的非负序列 aa (0ai109)\left(0\leq a_i\leq10^9\right) .
现有一种操作 (l,r)\left(l,r\right) (1lrn)\left(1\leq l\leq r\leq n\right) ,表示对 i[l,r]\forall i\in\left[l,r\right]ai=ai1a_i=a_i-1 .
操作 (l,r)\left(l,r\right) 的代价为 (rl+1)2\left(r-l+1\right)^2 ,现要求用最少的操作将 aa 中所有项变为 00 .
分别求最小代价和最大代价,结果对 109+710^9+7 取模。

Solution

比赛时想到 DP 去了,惨。

a0=an+1=0a_0=a_{n+1}=0 ,考虑 差分序列 dd .
即对 i[1,n+1]\forall i\in\left[1,n+1\right] ,有 di=aiai1d_i=a_i-a_{i-1} .
则操作 (l,r)\left(l,r\right) 等价于令 dl=dl1, dr+1=dr+1+1d_l=d_l-1,\ d_{r+1}=d_{r+1}+1 .
aa 中所有项变为 00 当且仅当 dd 中所有项变为 00 .

注意到 i=1n+1di=0\sum\limits_{i=1}^{n+1}d_i=0 恒成立。
要使得操作次数最少,则:

  • di=0d_i=0ii 不可为 l / (r+1)l\ /\ \left(r+1\right) .
  • di>0d_i>0ii 不可为 r+1r+1 .
  • di<0d_i<0ii 不可为 ll .

则操作次数和参数集均已固定,只需考虑 l,rl,r 如何配对。
记第 ii 次操作为 (li,ri)\left(l_i,r_i\right) ,则代价为

cost=(rili+1)2=(li2+ri2+2ri2li+1)2liricost=\sum\left(r_i-l_i+1\right)^2=\sum\left(l_i^2+r_i^2+2r_i-2l_i+1\right)-2\sum l_ir_i

排序不等式 得:

  • lili+1, riri+1l_i\leq l_{i+1},\ r_i\leq r_{i+1}costcost 最小。
  • lili+1, riri+1l_i\leq l_{i+1},\ r_{i}\geq r_{i+1}costcost 最大。

分别用 队列 维护即可。

时间复杂度:O(n)\mathcal O\left(n\right) .

Code

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
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
const int p = 1e9 + 7;
int n, a[N];
int cmi, cmx, d[N];
queue<int> q;
stack<int> s;

void solve(void);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1, j, k; i <= n + 1; i++) {
if (!(d[i] = a[i] - a[i - 1])) continue;
if (d[i] > 0) {
q.push(i);
continue;
}
while (d[i] && d[q.front()] + d[i] <= 0) {
j = q.front(), q.pop(), k = i - j;
cmi = (cmi + d[j] * 1ll * k % p * k % p) % p, d[i] += d[j];
}
if (!d[i]) continue;
j = q.front(), k = i - j;
cmi = (cmi + (-d[i]) * 1ll * k % p * k % p) % p, d[j] += d[i];
}
for (int i = 1, j, k; i <= n + 1; i++) {
if (!(d[i] = a[i] - a[i - 1])) continue;
if (d[i] > 0) {
s.push(i);
continue;
}
while (d[i] && d[s.top()] + d[i] <= 0) {
j = s.top(), s.pop(), k = i - j;
cmx = (cmx + d[j] * 1ll * k % p * k % p) % p, d[i] += d[j];
}
if (!d[i]) continue;
j = s.top(), k = i - j;
cmx = (cmx + (-d[i]) * 1ll * k % p * k % p) % p, d[j] += d[i];
}
printf("%d %d\n", cmi, cmx);
}

Problem D. 字符串

Description

给定 nn (1n2×103)\left(1\leq n\leq2\times10^3\right) 个仅由字符 a, b 构成的字符串。
ii 个字符串为 SiS_i (Si1)\left(\left|S_i\right|\geq1\right) ,现有两种操作:

  • 选择一个非空字符串 SS ,删去 SS 的末尾字符。
  • 选择一个字符串 SS ,在 SS 的末尾添加一个字符 a / b .

现要使得字典序意义下对 i[1,n)\forall i\left[1,n\right)SiSi+1S_i\leq S_{i+1} ,求最少的操作次数。
保证 i=1nSi5×104\sum\limits_{i=1}^n\left|S_i\right|\leq5\times10^4 .

Solution

以下所说的字符串前缀均包含 空串 ,字符串有序均指字典序意义下。

记所有原串的前缀构成字符串集合 SSss' 为字符串 ss 后添加一个字符 b .
则操作后对 i[1,n]\forall i\in\left[1,n\right] ,或有 SiSS_i\in S ,或 sS\exists s\in S 使得 Si=sS_i=s' .
S={ssS}S'=\left\{s'\big|s\in S\right\} ,将 SSS\cup S' 中所有字符串插入一棵 TrieTT 中。
DFS 一遍按字典序 从小到大TT 上的点重新编号,不妨设从 11 开始。

考虑 DP ,记 sus_uTT 上点 uu 所表示的字符串,ii'SiS_iTT 上的编号。
dpi,jdp_{i,j} 为使得前 ii 个字符串从小到大有序且 Si=sjS_i=s_j 的最少操作次数。
TT 中树边的边权均为 11 ,记 disu,vdis_{u,v}TT 上点 uu 到点 vv 的简单路径的长度。
显然有状态转移方程

dpi,j=min1kjdpi1,k+disi,jdp_{i,j}=\min_{1\leq k\leq j}dp_{i-1,k}+dis_{i',j}

边界条件 dp0,1=0dp_{0,1}=0 .
disi,jdis_{i',j} 可在枚举 ii 时预处理,空间问题用 滚动数组 优化即可。
m=SSm=\left|S\cup S'\right| ,则 ans=min1imdpn,ians=\min\limits_{1\leq i\leq m}dp_{n,i} .

时间复杂度:O(ni=1nSi)\mathcal O\left(n\sum\limits_{i=1}^n\left|S_i\right|\right) .

Code

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5;
const int M = 5e4 + 5;
const int inf = 1e9 + 5;
int n;
char s[M];
int ct = 1, idx[N], tag[M << 1], dis[M << 1], tr[M << 1][2];
int edg = 1, head[M << 1], to[M << 2], nxt[M << 2];
int ans, dp[2][M << 1];

void solve(void);
int insert(char *s);
void dfs0(int u = 1);
void dfs1(int u, int f = 0);
void add_edge(int u, int v);

int main(void) { return solve(), 0; }

void solve(void) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%s", s + 1), idx[i] = insert(s);
ct = 0, dfs0(), ans = inf, dis[0] = -1;
memset(dp[0], 63, (ct + 1) * sizeof(int)), dp[0][1] = 0;
for (int i = 1, x = 1, u, mi; i <= n; i++, x = !x) {
u = tag[idx[i]], dfs1(u), mi = inf;
for (int j = 1; j <= ct; j++)
mi = min(mi, dp[!x][j]), dp[x][j] = mi + dis[j];
}
for (int i = 1, x = n & 1; i <= ct; i++) ans = min(ans, dp[x][i]);
printf("%d\n", ans);
}

int insert(char *s) {
int rt = 1, ls = strlen(s + 1);
for (int i = 1; i <= ls; i++) {
if (!tr[rt][s[i] - 'a']) tr[rt][s[i] - 'a'] = ++ct;
if (!tr[rt][1]) tr[rt][1] = ++ct;
rt = tr[rt][s[i] - 'a'];
}
if (!tr[rt][1]) tr[rt][1] = ++ct;
return rt;
}

void dfs0(int u) {
tag[u] = ++ct;
for (int i = 0; i < 2; i++) {
int v = tr[u][i];
if (v) dfs0(v), add_edge(tag[u], tag[v]);
}
}

void dfs1(int u, int f) {
dis[u] = dis[f] + 1;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v ^ f) dfs1(v, u);
}
}

inline void add_edge(int u, int v) {
to[++edg] = v, nxt[edg] = head[u], head[u] = edg;
to[++edg] = u, nxt[edg] = head[v], head[v] = edg;
}

Welcome to my other publishing channels