MaxDYF的随笔Blog

May all the beauty be blessed.

发表于 分类于

喜提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

阅读全文 »

发表于 更新于 分类于

A. Median of an Array

显然，有多少个和中位数相等的数就加多少次。

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
// Problem: A. Median of an Array
// Contest: Codeforces - Codeforces Round 936 (Div. 2)
// URL: https://codeforces.com/contest/1946/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;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a.begin(), a.end());
	int pos = (n - 1) / 2, cnt = 1;
	while (pos < n - 1 && a[pos] == a[pos + 1])
		pos++, cnt++;
	cout << cnt << endl;
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Maximum Sum

很显然，如果没有插入操作的话，答案显然就是最大子段和\(sum\)。

如果有插入操作的话，我们只需要把这个最大子段和的值插在最大子段的旁边，答案就变成了\(2\times sum\)。如是，我们重复k次，答案就变成了\((1+2+4+\ldots +2^k)\times sum=(2^{k+1}-1)\times sum\)。

因为k比较小，直接暴力算就好。最后答案还要加上整个数列的和。

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
// Problem: B. Maximum Sum
// Contest: Codeforces - Codeforces Round 936 (Div. 2)
// URL: https://codeforces.com/contest/1946/problem/B
// 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;
const ll mod = 1e9 + 7;
void work()
{
	cin >> n >> k;
	ll ans = 0;
	ll sum = 0, maxsum = 0, numsum = 0;
	vector<ll> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		numsum += a[i];
		numsum %= mod;
	}
	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		if (sum < 0)
			sum = 0;
		maxsum = max(maxsum, sum);
	}
	for (int i = 1; i <= k; i++)
	{
		ans += maxsum;
		ans %= mod;
		maxsum += maxsum;
		maxsum %= mod;
	}
	cout << (ans + numsum + 2LL * mod) % mod << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. Tree Cutting

看到最小连通块的最大值，很容易想到用二分解决。关键在于设计check(lim)。

阅读全文 »

发表于 更新于 分类于

A.Destroying Bridges

显然，如果k大于等于了n-1，那么可以将与1相连的所有边给去掉，最小值就是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
// Problem: A. Destroying Bridges
// Contest: Codeforces - Codeforces Round 934 (Div. 2)
// URL: https://codeforces.com/contest/1944/problem/A
// 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;
	int ans = n;
	if (k >= n - 1)
		cout << 1 << endl;
	else
		cout << n << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Equal XOR

我们将左半边称作\(A\)，右半边称作\(B\)，发现有以下性质：

  1. 倘若\(A\)里某数只有一个，那\(B\)一定存在且仅存在一个这个数；
  2. 倘若\(A\)里有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
83
84
// Problem: B. Equal XOR
// Contest: Codeforces - Codeforces Round 934 (Div. 2)
// URL: https://codeforces.com/contest/1944/problem/B
// 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;
	vector<int> a(2 * n), but1(n + 1), but2(n + 1);
	for (int i = 0; i < 2 * n; i++)
		cin >> a[i];
	vector<int> q1, q2;
	for (int i = 0; i < 2 * n; i++)
	{
		if (i < n)
			but1[a[i]]++;
		else
			but2[a[i]]++;
	}
	for (int i = 1; i <= n; i++)
		if (but2[i] == 1 && but1[i] == 1 && (int)(q1.size()) < 2 * k)
		{
			q1.push_back(i);
			q2.push_back(i);
		}
	if (q1.size() % 2 == 1)
	{
		q1.pop_back();
		q2.pop_back();
	}
	for (int i = 1; i <= n; i++)
		if ((int)q1.size() < 2 * k && but1[i] == 2)
		{
			q1.push_back(i);
			q1.push_back(i);
		}
	for (int i = 1; i <= n; i++)
		if ((int)q2.size() < 2 * k && but2[i] == 2)
		{
			q2.push_back(i);
			q2.push_back(i);
		}
	for (auto x : q1)
		cout << x << ' ';
	cout << endl;
	for (auto x : q2)
		cout << x << ' ';
	cout << endl;
	
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. MEX Game 1

阅读全文 »

发表于 更新于 分类于

开个坑，记录一下学过的/正在学的/想要学的技术。

序号 课程名 链接 Finished?
1 Web入门：MIT Web Development Crash Course https://weblab.mit.edu/schedule Finished
2 CS61A: Structure and Interpretation of Computer Programs https://inst.eecs.berkeley.edu/~cs61a/su20/ Not Yet

发表于 更新于 分类于

A. Too Min Too Max

令\(a\leq b\leq c\leq d\)，手玩以下就能发现等式得出的最大的取值就是\(2\times (c+d-a-b)\)。sort一下取最大和最小的两个数就行了。

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
// Problem: A. Too Min Too Max
// Contest: Codeforces - Codeforces Round 931 (Div. 2)
// URL: https://codeforces.com/contest/1934/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;
int a[N];
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	cout << (a[n] - a[1] + a[n - 1] - a[2]) * 2 << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Yet Another Coin Problem

如果n比较小，显然简单dp就能解决。

在n比较大的时候，可以发现，一定有一个数取了大部分。先预处理一定范围内的答案（比如1000），然后枚举这个数，用这个数把n减到1000以内，然后两部分答案相加即可。

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
// Problem: B. Yet Another Coin Problem
// Contest: Codeforces - Codeforces Round 931 (Div. 2)
// URL: https://codeforces.com/contest/1934/problem/B
// 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;
int f[N];
int a[] = {0, 1, 3, 6, 10, 15};
void work()
{
	cin >> n;
	int ans = inf;
	for (int i = 1; i <= 5; i++)
	{
		int cnt = max(0, (n - 900) / a[i]);
		int now_n = n - cnt * a[i];
		int now = cnt + f[now_n];
		ans = min(ans, now);
	}
	cout << ans << '\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	for (int i = 1; i <= 1000; i++)
	{
		f[i] = inf;
		for (int j = 1; j <= 5; j++)
			if (i >= a[j])
				f[i] = min(f[i], f[i - a[j]] + 1);
	}
	while (t --> 0)
	{
		work();
	}
}

C. Find a Mine

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
// Problem: C. Find a Mine
// Contest: Codeforces - Codeforces Round 931 (Div. 2)
// URL: https://codeforces.com/contest/1934/problem/C
// 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;

#define int long long
int n, m, k, q;
void work()
{
	cin >> n >> m;
	auto query = [&](int x, int y)
	{
		cout << "? " << x << ' ' << y << endl;
	};
	auto answer = [&](int x, int y)
	{
		cout << "! " << x << ' ' << y << endl;
	};
	int dis1, dis2, dis3, dis4;
	query(1, 1);
	cin >> dis1;
	query(n, 1);
	cin >> dis2;
	query(1, m);
	cin >> dis3;
	auto cross = [&](int k1, int b1, int k2, int b2)
	{
		int x = (b2 - b1) / (k1 - k2);
		int y = k1 * x + b1;
		return make_pair(x, y);	
	};
	auto p1 = cross(-1, dis1 + 2, 1, dis2 - n + 1);
	auto p2 = cross(-1, dis1 + 2, 1, m - dis3 - 1);
	if (1 <= p1.first && p1.first <= n && 1 <= p1.second && p1.second <= m)
	{
		query(p1.first, p1.second);
		cin >> dis4;
		if (dis4 == 0)
			answer(p1.first, p1.second);
		else
			answer(p2.first, p2.second);
	}
	else
		answer(p2.first, p2.second);
	
}
main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D1. XOR Break --- Solo Version

阅读全文 »
0%