Educational Codeforces Round 79
/ / 阅读耗时 20 分钟 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
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
using namespace std;
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
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 |
|
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
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 |
|