MaxDYF的随笔Blog

May all the beauty be blessed.

发表于 更新于 分类于

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

阅读全文 »

发表于 更新于 分类于

A. Shuffle Party

比赛想法：

观察样例，发现答案小于等于n，且是2的整数次幂，猜测答案为小于等于n的最大的2的整次幂。

赛后证明：

显然，对于一个整数\(d\)，它的最小倍数一定是\(2d\)。则对于1来说，每次都×2，最终答案就是最大的小于n的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
// Problem: A. Shuffle Party
// Contest: Codeforces - Codeforces Round 930 (Div. 2)
// URL: https://codeforces.com/contest/1937/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()
{
	ll n;
	cin >> n;
	cout << (1LL << (int)log2(n)) << '\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Binary Path

显然，蚱蜢只会向右移动一次，总共有n种可能，所以我们可以枚举向右走的地方。

我们设两个变量maxid和s，分别表示在第maxid行向右行，以及有s个与其相等的序列。假设现在在第\(i\)行，显然有两种可能：向下走和向右走。有3种情况：

  1. 两个数相等：则这两种情况相等，s累加上1。
  2. 向下的是0，向右的是1：则只有向下走一种可能，更新maxid，s重置为1。
  3. 向下的是1，向右的是0：则显然只能向右走了，后面没有分支了，直接break。
阅读全文 »

发表于 更新于 分类于

比赛忘记打了，只能赛后补题了（悲

D. Slimes

推导一下条件：

  1. 必须严格大的吃严格小的\(\rightarrow\)相同的不能吃\(\rightarrow\)至少要两个不同的数才能一路吃成一个数
  2. 要求最小步数\(\rightarrow\)一个数左右相邻的一串数被吃成一个后，再吃掉这个数本身。

第一步判断不同的数可以\(O(n)\)预处理出上一个不同的数位置，2可以通过在前缀和上二分算出。要特判一下相邻的数直接吃的情况。

总复杂度\(O(nlogn)\)​。

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
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

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), ans(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		ans[i] = inf;
	auto check = [&](bool rev)
	{
		vector<ll> sum(n), pre(n);
		for (int i = 0; i < n; i++)
			sum[i] = i > 0 ? sum[i - 1] + a[i]
						   : a[i];
		pre[n - 1] = inf;
		for (int i = n - 2; i >= 0; i--)
			pre[i] = a[i] == a[i + 1] ? pre[i + 1]
									  : i + 1;
		for (int i = n - 2; i >= 0; i--)
		{
			
			int it = upper_bound(sum.begin(), sum.end(), sum[i] + a[i]) - sum.begin();
			int ans1, ans2;
			ans1 = (it == n) ? inf : it - i;
			ans2 = pre[i + 1] - i;
			int realID = rev ? (n - i - 1) : i;
			ans[realID] = min(ans[realID], max(ans1, ans2)); 
		}
	};
	for (int i = 0; i < n; i++)
		if ((i > 0 && a[i - 1] > a[i]) || (i < n - 1 && a[i + 1] > a[i]))
			ans[i] = 1;
	check(false);
	reverse(a.begin(), a.end());
	check(true);
	for (auto x : ans)
		cout << (x > (int)3e5 ? -1 : x) << ' ';
	cout << '\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

E. Count Paths

可以发现，路径可以分为两种：

  1. 祖先与子孙的
  2. 没有祖孙关系的
阅读全文 »
0%