CodeTON Round 8 (Div1+Div2)

发表于 更新于 分类于

喜提2 TON币，好耶

A. Farmer John's Challenge

对于\(n=k\)的情况，显然构造一个全为1的序列是合法的。

对于\(k=1\)的情况，显然构造1至n的序列合法。

对于这之外的情况，我们设想一个有序序列，如果其循环左移\(k(k \not=1且k \not= n)\)次后仍然合法，那么也就是说，原序列最小的数要等于最大的数，也就是所有数相等，显然k不可能为n以外的数。所以直接输出-1。

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
// Problem: A. Farmer John's Challenge
// Contest: Codeforces - CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1942/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;

void work()
{
	cin >> n >> k;
	if (n == k)
	{
		for (int i = 1; i <= n; i++)
			cout << 1 << ' ';
		cout << endl;
	}
	else if (k == 1)
	{
		for (int i = 1; i <= n; i++)
			cout << i << ' ';
		cout << endl;
	}
	else
	{
		cout << -1 << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Bessie and MEX

考虑倒推。对于第n位，有\(a_n\) = \(\texttt{MEX}(p_1, p_2, \ldots, p_n) - p_n\)。而\(\texttt{MEX}(p_1, p_2, \ldots, p_n)\)显然应该等于\(n\)，所以\(p_n\)是能够唯一确定的。然后根据这个反推回去即可。

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
// Problem: B. Bessie and MEX
// Contest: Codeforces - CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1942/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int a[N];
int p[N];
bool vis[N];
// p[n    ] = n - a[n]
// p[n - 1] = p[n] - a[n - 1]
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int lst = n;
	for (int i = n; i >= 1; i--)
	{
		p[i] = lst - a[i];
		lst = min(lst, p[i]);
	}
	for (int i = 1; i <= n; i++)
		cout << p[i] << ' ';
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. Bessie's Birthday Cake

Easy Verson Solution

先考虑简单版本的。如果没有加点操作，那么原多边形很显然是被划分成了两部分面积：

  1. 选中的\(x\)个点构成的多边形。
  2. 除了这个多边形剩下的若干个多边形。

对于第一部分，很显然，由于每个点都可以选，它所构成的三角形最多就是\(x-2\)个。

对于第二部分，可以发现他们有且仅有两个相邻的可选点，无法连线构成新的三角形。也就是说，只有在这个多边形本身是个三角形的情况下，才有可能对答案有贡献。所以加上这部分三角形的个数即可。

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
// Problem: C1. Bessie's Birthday Cake (Easy Version)
// Contest: Codeforces - CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1942/problem/C1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int a[N];
void work()
{
	int x, y;
	cin >> n >> x >> y;
	for (int i = 1; i <= x; i++)
		cin >> a[i];
	sort(a + 1, a + x + 1);
	int ans = x - 2;
	for (int i = 1; i < x; i++)
		if (abs(a[i] - a[i + 1]) == 2)
			ans++;
	if (a[1] + n - a[x] == 2)
		ans++;
	cout <<  ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

Hard Version Solution

现在有了加点的操作，我们思考应该怎么加。

第一部分的多边形全部都是计数点，不需要加，所以考虑第二部分的多边形。

设这个多边形除了已选中的两个点外，还有\(p\)个点，那么，我们可以讨论一下：

  1. 如果要将这个多边形产生\(p\)个三角形（即最多的情况下）

    在这种情况下，我们发现，\(p\)的奇偶性会影响加点的个数。

    1. 如果\(p\)为奇数，则需加\(\frac{p-1}2\)个点（加\(k\)个点，产生\(2k+1\)个三角形）
    2. 如果\(p\)为偶数，则要加\(\frac p 2\)个点。（加\(k\)个点，产生\(2k\)个三角形）

    显然，如果我能加的点的个数有限，那我肯定会优先将\(p\)​为奇数的多边形先加满（同等加点下获得的三角形更多），然后才是偶数的多边形。

  2. 如果要产生不足\(p\)个三角形（不加满）

    这种情况下，倘若我加了\(k\)个点，那么会产生\(2k\)个三角形。

综上，只有p为偶数且加满的情况下我们才有额外收获，否则就是一个点两个三角形。我们只要从小到大地对所需的\(p\)为奇数的多边形尽可能取，然后再对其他点应加尽加，最后累计答案即可。

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
// Problem: C1. Bessie's Birthday Cake (Easy Version)
// Contest: Codeforces - CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1942/problem/C1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

ll n, m, k, q;
ll a[N];
ll b[N], c[N];
void work()
{
	ll x, y;
	cin >> n >> x >> y;
	for (int i = 1; i <= x; i++)
		cin >> a[i];
	sort(a + 1, a + x + 1);
	int tot1 = 0, tot2 = 0;
	int ans = x - 2, lst = a[x];
	for (int i = 1; i <= x; i++)
	{
		int dis = (n + a[i] - lst) % n;
		if (dis == 2)
			ans++;
		else if (dis > 2)
		{
			if (dis & 1)
				c[++tot2] = dis;
			else
				b[++tot1] = dis;
		}
		lst = a[i];
	}
	sort(b + 1, b + tot1 + 1);
	sort(c + 1, c + tot2 + 1);
	for (int i = 1; i <= tot1; i++)
	{
		ll t = min(y, (b[i] - 1) / 2);
		y -= t;
		if ((b[i] - 1) - 2 * t == 1)
			ans += 2 * t + 1;
		else
			ans += 2 * t;
	}
	for (int i = 1; i <= tot2; i++)
	{
		ll t = min(y, (c[i] - 1) / 2);
		y -= t;
		ans += 2 * t;
	}
	cout <<  ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D. Learning to Paint(补)

官方题解这个思路很清奇，我也没想好怎么描述，就先放个Link上来罢

Link Here

Let \(\texttt{dp}[i]\) store a list of all \(\min(k, 2^i)\) highest beauties of a painting in non-increasing order if you only paint cells \(1,2,\ldots ,i\). Let's define merging two lists as creating a new list that stores the \(k\) highest values from the two lists. First, let's look at a slow method of transitioning. We iterate over the left endpoint \(l\) such that \(l \ldots i\) is a maximal painted interval. At each \(l\), we merge \(\texttt{dp}[l - 2]\), with \(a_{l,i}\) added to each value, into \(\texttt{dp}[i]\). We also merge \(\texttt{dp}[i - 1]\) into \(\texttt{dp}[i]\) to handle the case in which we do not paint cell \(i\). If implemented well, transitioning takes \(\mathcal{O}(nk)\) time leading to an \(\mathcal{O}(n^2k)\) solution which is too slow. We can speed this up. This merging process boils down to finding the \(k\) largest elements from \(n\) non-increasing lists in \(\mathcal{O}((n + k) \log n)\) time. We can use a priority queue that stores (\(\texttt{element}, \texttt{index}\)) for each list. We can do the following \(k\) times: add the top of the priority queue to our answer, advance its index, and update the priority queue accordingly. This allows us to transition in \(\mathcal{O}((n + k) \log n)\) time which leads to an \(\mathcal{O}((n^2 + nk) \log n)\) solution.

E. Farm Game

很离谱的一道博弈+组合题。

一个小结论

对于\(\ldots ABABAB\ldots\)这样棋局，我们只需考虑\(A\)先手的情况，然后答案乘上2就是最终答案。

证明：对于一个这样的先手必胜态$ABABAB\(，其一定有一个一一对应的、镜像的先手必胜态\)BABABA$，反之亦然。

所以我们接下来可以只讨论\(\ldots ABABAB \ldots\)这种情况。

简化问题

先讨论\(n=1\)的情况，也就是只有一对\(AB\)的情况。

情况1. AB间隔为0

也就是说AB是挨着的。那么，先手自然是没得选，只能往B的反方向走。B只要一直跟着A，就能把\(A\)给堵死在墙角。所以这是个先手必败态。

情况2. AB间隔为1

也就是\(\dots A\_B\ldots\)这种情况。这种情况下就反过来了。A只要往B靠一步，就变成了情况1，也就是后手必败态，先手必胜态。

进一步，我们发现，当间隔继续加大时，为了使自己获胜，\(A\)和\(B\)都会尽可能地向对方靠近以将对方挤到墙边。

所以对于\(AB\)间隔为偶数的情况，实际上和情况1一致，即先手必败；\(AB\)间隔为奇数时，与情况2一致，先手必胜。

多组AB的情况

刚才只讨论了\(AB\)只有一组的情况。倘若有多组呢？

按照刚刚讨论的，一对\(AB\)显然都是要往对方靠拢的（逃离那方显然就是必败了），所以每一组\(AB\)之间的空间，实际上不影响胜负态。所以转而讨论这些\(AB\)间隔。

如果AB间距全为奇数或全为偶数

这样的话，实际上跟上一节的情况0和1就是一样的了，所以不需要过多讨论。

如果AB间距有些为奇数，有些为偶数

作为先手，我可以选择任意个牛移动，那我只需移动间隔为奇数的\(AB\)​对，那么，场上的间隔又变成了全为偶数，情况又转变成了先手必胜态。所以这样是先手必胜。

综上，当存在任意一对奇数间距时，先手必胜。

有无限拉扯的情况吗？

题目说有这种情况，但是仔细思考一下，真的存在这种情况吗？

实际上，就如同刚才说的，对于一对\(AB\)来说，只有两种选择，一是往对方方向跑，二是往反方向跑。而这两种情况都是有限步数的，所以实际上，在两方都是最优选择的情况下，不可能出现无限拉扯的情况。

以此结论，我们得以计算出最后的答案。

答案的计算

上面总结了，当存在任意一对奇数间距时，先手必胜。但是这样显然是不好用组合数计算的。所以我们可以考虑反向计数，即总方案数-全部间距都是偶数的方案数。

总方案数显然为\(\binom{l}{2n}\)，而全部都是偶数的方法，可以使用隔板法计算，计算结果为 \[ subans=\sum_{i=0}^{\lfloor{\frac {l-2n}2}\rfloor}\binom{n+i-1}{n-1}\binom{n +{\lfloor{\frac {l-2n}2}\rfloor}-2i}{n} \] 最终答案为 \[ \binom{l}{2n}-subans \]