Educational Codeforces Round 79题解。

A. New Year Garland

        对三个数排一个序,然后若最大的比两个较小的和加上一还要大,那么就是No,否则为Yes。这是因为满足这个条件时,较小的那两个最多产生它们的和加一这样多的空隙,从而使最大的一个不相邻。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int op[5];
int main()
{
int t;
scanf("%d", &t);
while (t--) {
for (int i = 1; i <= 3; i++) scanf("%d", op + i);
sort(op + 1, op + 4);
if (op[1] + op[2] + 1 < op[3])
printf("No\n");
else
printf("Yes\n");
}
return 0;
}

B. Verse For Santa

        枚举每一个被删掉的数,然后二分找答案。这里需要用树状数组维护前缀和。

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
#include <bits/stdc++.h>
using namespace std;
#define N 100005
long long tree[N];
int n, s, op[N], ans, maxn;
inline void add(int x, int y)
{
for (; x <= n; x += x & -x) tree[x] += y;
}
inline long long sum(int x)
{
long long s = 0;
for (; x >= 1; x -= x & -x) s += tree[x];
return s;
}
inline int get()
{
int l = 1, r = n + 1, mid;
while (l < r) { //[,)
if (r == l + 1) {
if (sum(l) <= s) return l;
return 0;
}
mid = (l + r) >> 1;
if (sum(mid) > s)
r = mid;
else
l = mid;
}
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; i++) tree[i] = 0;
for (int i = 1; i <= n; i++) scanf("%d", op + i), add(i, op[i]);
ans = 0, maxn = get();
for (int i = 1, p; i <= n; i++) {
add(i, -op[i]);
p = get();
if (p > maxn) maxn = p, ans = i;
add(i, op[i]);
}
printf("%d\n", ans);
}
return 0;
}

C. Stack of Presents

        很明显,最优的策略就是:在调顺序的那一部分中,把将来需要用的按顺序放到最前面。然后模拟一下就可以了。

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
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int tr[N], n, m, pos[N], vis[N], bottom, op[N];
long long ans;
inline void add(int x, int y)
{
for (; x <= n; x += x & -x) tr[x] += y;
}
inline int sum(int x)
{
int s = 0;
for (; x >= 1; x -= x & -x) s += tr[x];
return s;
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m), bottom = ans = 0;
for (int i = 1; i <= n; i++) tr[i] = vis[i] = 0;
for (int i = 1, x; i <= n; i++) add(i, 1), scanf("%d", &x), op[i] = x, pos[x] = i;
for (int i = 1, x; i <= m; i++) {
scanf("%d", &x);
if (vis[x]) {
++ans;
}
else {
ans += 2 * sum(pos[x] - 1) + 1;
while (bottom < pos[x]) vis[op[++bottom]] = 1;
}
add(pos[x], -1);
}
printf("%lld\n", ans);
}
return 0;
}

D. Santa’s Bot

        小学(?)数学题。我们记$f(x)$为第$x$号礼物有多少人选,并且记$S(x)$为$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
#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;
int n, num[1000005], k[1000005], s;
vector<int> vec[1000005];
long long ans;
inline int qPow(int x, int y)
{
int ans = 1, sta = x;
while (y) {
if (y & 1) ans = 1ll * ans * sta % MOD;
sta = 1ll * sta * sta % MOD, y >>= 1;
}
return ans;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", k + i);
for (int j = 1, x; j <= k[i]; j++) scanf("%d", &x), ++num[x], vec[i].push_back(x);
}
for (int i = 1; i <= n; i++) {
for (int j : vec[i]) {
ans += 1ll * qPow(1ll * n * k[i] % MOD * n % MOD, MOD - 2) * num[j] % MOD;
ans %= MOD;
}
}
printf("%lld", ans);
return 0;
}

E. New Year Permutations

        首先注意到满足题意的排列可以分为若干段(可以是1段),其中每一段$[l,r]$都是$[l,r]$范围内的数组成的一个排列,并且每一段$[l,r]$中一定都是最大值$r$位于最左侧。这每一段还需要满足一个性质:从最左侧位于$l$的$r$开始,$[l,r]$中的数均可达。
        考察$[l,r]$中的一段有多少种可能。若记$len=r-l+1$,那么由于$[l,r]$均可以从位于$l$的$r$可达,将抽象为一个有向图,易知有$(len-2)!$种情况。
        现在考虑一个长度为$len$的排列有多少种满足题意。我们枚举第一段的长度,并记$f(x)$为$len=x$时的数目,则有:

        特别地,这里认为$(-1)!=1$。
        根据上面的公式,我们可以很容易地求出要求的排列分为哪些段,求出它们的长度以及排名。现在问题转化为如何根据字典序排名构造一个段。长度为1的段很好构造,考虑大于1的段。
        首选首元素是固定的,我们从下一位开始,从小到大依次放数。在放一个数之前,需要考察这个数是否合法,规则如下:

  • 不能自指。即第$x$位不能放$x$。
  • 不能内部自环。
  • 不能提前返回。即对于段$[l,r]$,若从$l$开始,未遍历所有元素就返回$l$,则非法。

        为什么需要上述条件自行思考。
        判定上述条件,然后用排列去框出对应的段,然后用同样地方法求出其它的段,本题即解决。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll f[60], fac[60], k, g[60];
int n, vis[60], tmp[60];
bool check(int at, int len)
{
int now = at, cnt = 1;
while (true) {
if (tmp[now] == at) return cnt != len + 1;
if (tmp[now] == 0) break;
now = tmp[now], ++cnt;
}
for (int i = at + 1; i <= at + len; i++) {
now = i, cnt = 1;
while (true) {
if (tmp[now] == 0) break;
if (cnt > len + 1) return true;
now = tmp[now], ++cnt;
}
}
return false;
}
inline void get(int at, int len, ll rk)
{
for (int i = at; i <= at + len; i++) tmp[i] = vis[i] = 0;
tmp[at] = at + len;
for (int i = at + 1; i < at + len; i++) {
ll s = 0;
for (int j = at; j <= at + len - 1; j++) {
if (vis[j] || i == j) continue;
tmp[i] = j;
if (check(at, len)) {
tmp[i] = 0;
continue;
}
if (len - (i - at) - 1 > 22 || s + fac[len - (i - at) - 1] >= rk) {
rk -= s, tmp[i] = j, vis[j] = 1;
break;
}
else {
s += fac[len - (i - at) - 1];
}
}
}
for (int i = at; i <= at + len - 1; i++)
if (!vis[i]) tmp[at + len] = i;
}
void DFS(int at, ll num)
{
if (at == n + 1) return;
ll s = 0, sup = 0;
int i = 1;
ll rk = 0;
for (i = 1; i <= n - at + 1; i++) {
if (n - at + 1 - i > 22) break;
s += g[i] * f[n - at + 1 - i];
if (s >= num) break;
}
--i;
for (int j = 1; j <= i; j++) num -= g[j] * f[n - at + 1 - j];
if (n - at + 1 - i <= 22) rk = (num - 1) / f[n - at + 1 - (i + 1)];
if (n - at + 1 - i <= 22) num -= rk * f[n - at + 1 - (i + 1)];
get(at, i, rk + 1);
for (int j = at; j <= at + i; j++) printf("%d ", tmp[j]);
DFS(at + i + 1, num);
}
int main()
{
fac[0] = 1;
for (int i = 1; i <= 23; i++) fac[i] = i * fac[i - 1];
f[0] = 1, f[1] = 1, f[2] = 2, g[1] = 1, g[2] = 1;
for (int i = 3; i <= 23; i++) g[i] = fac[i - 2];
for (int i = 3; i <= 23; i++) {
for (int j = 1; j <= i; j++) f[i] += g[j] * f[i - j];
}
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%lld", &n, &k);
if (n <= 22 && k > f[n]) {
printf("-1\n");
}
else {
DFS(1, k);
printf("\n");
}
}
return 0;
}

F. New Year and Handle Change

        本题很好,强烈建议一做。
        首先贪心是不对的,考虑$DP$。
        列出$dp(i,j)$表示$[1,i]$这一段用$j$次覆盖可以得到的最小结果(大写字母和小写字母分两次计算)。我们暂且覆盖小写字母,用$s(x)$表示:若$x$这一位为小写字母,则$s(x)=1$否则$s(x)=0$。
        转移方程很好列,但是并没有什么用,因为这是一个至少$O(nk)$的算法。这里有一种黑科技可以使其降掉一维。
        不妨定义一个二元函数:

        很显然,我们要求的答案就是$dp(n,k)$。
        这里的$f(\lambda,j)$函数引入了$\lambda$这个参数。如果我们能对于一个已知的$\lambda$并求出对应的$f(\lambda,k)$,那么就可以求出$dp(n,k)$。这看起来非常异想天开,不过它确实是可以的。
        我们没有必要求出所有的$f$函数值,只需要求出对于一个固定的$\lambda$,$f$函数的最小极值点$j_\lambda$以及极值。这个过程可以$O(n)$完成。
        我们将$d(j)$定义成一个二元组$\{x,y\}$,其中$x$为当前$f$函数最小值,$y$是可以取到这个值的最小的$j$。那么$d(0)=\{0,0\}$,对于$1\leq j\leq n$递推关系如下:
        首先继承上一次的结果:

        当$j\geq l$时,考虑进行一次操作:

        当$j<l$时,放不下一次操作,但是由于操作之间可能重叠,因此也需要更新:

        最终得到的$d(n)=\{x,y\}$中,$x$就是$f(\lambda,j)$的最小值,$y$就是取到最小值的最小极值点$j_\lambda$。
        接下来讨论进一步的做法。
        $dp(n,j)$显然是不增的,我们说$dp$是凸的,是指下面的不等式成立:

        定义$g(x)=dp(n,x)-dp(n,x-1)$,那么:

        这里的$g(x)$是增函数,并且最大值为0。有$-n\leq g(x)\leq 0$总是成立。考虑到这一点,我们给上式进行调整:

        经过参数$\lambda$的调整,$g(i)+\lambda$仍然是单增的,但是值域变为了$[\lambda-n,\lambda]$。这一步看似没有什么特别的地方,但是它改变了$dp(n,j)+\lambda j$即$f(\lambda,j)$的单调性,使其变为先降后增。根据上文的描述,我们可以在$O(n)$复杂度下求出$f(\lambda,j)$的极值点$j_\lambda$和最小值。下面我们会证明一个引理:
        【引理】若$\lambda_0$是最小的使$j_{\lambda_0}\leq k$成立的值,那么此时$f(\lambda_0,j_{\lambda_0})=dp(n,k)+\lambda_0 k$。
        若$\lambda_0 +g(k+1) < 0$,则必有$f(\lambda_0,k) > f(\lambda_0,k+1)$,显然$j_{\lambda_0}>k$,即$\lambda_0$过小。于是必有$\lambda_0+g(k+1)\geq 0$即$f(\lambda_0,k+1)\geq f(\lambda_0,k)$,这时可以分为三种情况。若$\lambda_0+g(k)>0$,必有$f(\lambda_0,k)>f(\lambda_0,k-1)$,那么$j_{\lambda_0}\leq k$可行。若$\lambda_0+g(k)=0$,那么$f(\lambda_0,k)=f(\lambda_0,k-1)$,也有$j_{\lambda_0}\leq k$。若$\lambda_0+g(k)<0$,则$f(\lambda_0,k)<f(\lambda_0,k-1)$,此时$j_{\lambda_0}=k$。三种情况都可行。于是我们得到$\lambda_0=-g(k+1)$。此时$\lambda_0+g(k)=g(k)-g(k+1)\leq 0$。若等号不成立,则$j_{\lambda_0}=k$,引理直接得证。下面单独证明取等时引理仍然成立。
        很容易想到$j_{\lambda_0}$是第一个满足$g(x)+\lambda_0<0$的$x$,且$x\leq k$。由于$g(k)+\lambda_0=0$成立,那么根据$g(x)+\lambda$的单调性,可以想到对于$j_{\lambda_0}\leq i\leq k$,$g(i)+\lambda_0=0$均成立,即$f(\lambda_0,i)$都是相同的值,引理得证。
        于是我们可以二分出$\lambda_0$,求出对应的$f(\lambda_0,j_{\lambda_0})$,然后用引理求解。这里也可以发现二分参数$\lambda$的本质是找$-g(k+1)$。我们称这种方法叫$\lambda$优化,国内好像叫wqs二分。
        $\lambda$优化充分利用了$dp$函数的凸性质,即间距的单调性找出需要的间距,进而求出$dp$值,方法十分巧妙。

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
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef long long li;
pair<li, li> dp[N];
int n, ll, k, s[N], ans = 0x7fffffff;
char e[N];
inline int check(int v)
{
dp[0] = {0, 0};
for (int i = 1; i <= n; i++) {
dp[i] = {dp[i - 1].first + s[i], dp[i - 1].second};
if (i >= ll)
dp[i] = min(dp[i], {dp[i - ll].first + v, dp[i - ll].second + 1});
else
dp[i] = min(dp[i], {v, 1});
}
return dp[n].second;
}
inline int get()
{
int l = -1, r = n, mid, C = 0;
while (l < r) {
if (r == l + 1) {
check(r);
return dp[n].first - 1ll * r * k;
}
mid = (l + r) >> 1;
int p = check(mid);
if (p > k)
l = mid;
else
r = mid;
}
}
int main()
{
scanf("%d%d%d%s", &n, &k, &ll, e + 1);
for (int i = 1; i <= n; i++) s[i] = !!isupper(e[i]);
ans = min(ans, get());
for (int i = 1; i <= n; i++) s[i] = !!islower(e[i]);
ans = min(ans, get());
printf("%d", ans);
return 0;
}