MaxDYF的随笔Blog

May all the beauty be blessed.

发表于 更新于 分类于

A - We Got Everything Covered!

很显然，最短的方案长度一定是\(n \times 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
// Problem: A. We Got Everything Covered!
// Contest: Codeforces - Codeforces Round 921 (Div. 2)
// URL: https://codeforces.com/contest/1925/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 >> m;
	string s;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			s.push_back(j + 'a' - 1);
		}
	}
	cout << s << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - A Balanced Problemset?

一个显而易见的结论是，如果答案是\(y\)，那么一定有\(x \mid y\)。那么直接枚举\(x\)的因子，判断\(\frac y x\)是否大于等于\(n\)即可。时间复杂度\(\Theta(T\sqrt 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
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
// Problem: B. A Balanced Problemset?
// Contest: Codeforces - Codeforces Round 921 (Div. 2)
// URL: https://codeforces.com/contest/1925/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 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;

vector<int> primes;
bool isprime[N];
void preProcess()
{
	fill(isprime + 2, isprime + N, true);
	for (int x = 2; x < N; x++)
	{
		if (isprime[x])
			primes.push_back(x);
		for (int y : primes)
		{
			if (x * y >= N)
				break;
			isprime[x * y] = 0;
			if (x % y == 0)
				break;
		}
	}
}
void work()
{
	cin >> n >> m;
	int ans = 1;
	for (int i = 1; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			if (n / i >= m)
				ans = max(ans, i);
			if (i >= m)
				ans = max(ans, n / i);
		}
	}
	cout << ans << endl;
}
int main()
{
	preProcess();
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Did We Get Everything Covered?

一开始想了个最短路做法（写一半发现太麻烦了）。

可以用一个桶记录字母的出现情况，每次桶里前k个字符都不为空了，就清空桶，总轮数加一，记录下出现次数最少的那个字母（也就是最后一个字母）。最后再检查总轮数是否大于等于n。如果不满足，就在记录下的字母后面添任意字母，直到长度为n，输出即可。

下面是包含写fake了的最短路的代码（

阅读全文 »

发表于 更新于 分类于

K - Master of Both

考虑两个字符串比较，可以发现，我们其实并不在意前面相同的部分，以及后面不同的部分，而是只在意两者第一个不相同的位置（不妨叫它“关键位置”）。只需比较这个位置的对应字符大小，就能判断字符串的大小。

具体的，我们创建一棵\(\text{Trie}\)树， 依次插入每一个字符串，并且每走一步，都记录下当前位置作为关键位置的贡献。在询问时，我们只需要暴力枚举字符集的大小关系，将可用的贡献累加入答案即可。时间复杂度\(\Theta(ns+qs^2)\)，其中\(s\)是字符集大小，可以通过此题。

注意，为了正确比较如aaaaa、aaaaab这样前者是后者前缀的大小，我们需要插入时在每个字符串最后面加上一个“最小的字符”，这样就能够保证最优计数。

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
// Problem: K. Master of Both
// Contest: Codeforces - The 2022 ICPC Asia Hangzhou Regional Programming Contest
// URL: https://codeforces.com/gym/104090/problem/K
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Author: MaxDYF
// 
// Powered by CP Editor (https://cpeditor.org)

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

const int N = 1e6 + 20;
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;
string s;
ll a[27][27];
int tr[N * 8][27];
ll cnt[N];
int tot = 1;
void insert(string s)
{
	int now = 1;
	s = s + (char)('a' - 1);
	for (char nowchar : s)
	{
		int x = nowchar - 'a' + 1;
		for (int y = 0; y < 27; y++)
			if (x != y && tr[now][y])
				a[y][x] += cnt[tr[now][y]];
		if (!tr[now][x])
			tr[now][x] = ++tot;
		now = tr[now][x];
		cnt[now]++;
	}
}
void work()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
	{
		cin >> s;
		insert(s);
	}
	while (q--)
	{
		string cmp;
		cin >> cmp;
		ll ans = 0;
		cmp  = (char)('a' - 1) + cmp;
		for (int i = 0; i < 27; i++)
			for (int j = i + 1; j < 27; j++)
				ans = (ans + a[cmp[j] - 'a' + 1][cmp[i] - 'a' + 1]);
		cout << ans << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
}

发表于 更新于 分类于

A. Constructive Problems

赛事通过观察法可得出答案就是\(\max(n, m)\)（bushi

可以发现，每一行每一列都至少得有一个，所以得证。

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. Constructive Problems
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: MaxDYF
// 
// 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 >> m;
	cout << max(n, m) << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Begginer's Zelda

一开始想复杂了，总想着从直径考虑。其实没有这么复杂。

观察每次操作，可以发现，最优操作下，每次操作必定会少两个原图的叶子节点（最后一次可能只少1个）。所以只需判断叶子的数量\(cnt\),答案即为 \[ \lceil \frac {cnt}2 \rceil = \frac{cnt + 1} 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
55
56
57
// Problem: B. Begginer's Zelda
// Contest: Codeforces - Codeforces Round 915 (Div. 2)
// URL: https://codeforces.com/contest/1905/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: MaxDYF
// 
// 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 x, y;
int in[N];
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		in[i] = 0;
	for (int i = 1, x, y; i < n; i++)
	{
		cin >> x >> y;
		in[x]++;
		in[y]++;
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += (in[i] == 1);
	cout << (cnt + 1) / 2 << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. Largest Subsequence

手玩几组样例可以发现，所有能进行的有效操作，等效于将一个字典序最大的不上升子序列给排序。

阅读全文 »

发表于 更新于 分类于

A - Yet Another AB Problem

对于几种情况，分类讨论一下：

  1. s[i]!=t[i],t[i]=='A'：这种情况，需要向后找一个t[j]=='B'；
  2. s[i]!=t[i],t[i]=='B'：这种情况，需要向前找一个t[j]=='A'。

若所有条件满足，则可以判定可行。要取得最小值，显然我们应当尽可能将1、2两种s[i]!=t[i]情况合起来（一次操作可以解决两个冲突），若是找不到，再与s[i]==t[i]的合起来（一次操作只解决一个冲突）。

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: A - Yet Another AB Problem
// Contest: AtCoder - AtCoder Regular Contest 170
// URL: https://atcoder.jp/contests/arc170/tasks/arc170_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Author: MaxDYF
// 
// 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;
	string s1, s2;
	cin >> s1 >> s2;
	if (s1 == s2)
	{
		cout << 0 << endl;
		return;
	}
	bool isA = 0, needB = 0;
	int cnt = 0, turnA = 0;
	for (int i = 0; i < n; i++)
	{
		if (s1[i] == s2[i] && s1[i] == 'A')
			isA = 1;
		else if (s1[i] == s2[i])
			needB = 0;
		else if (s1[i] == 'A') // need to turn B
		{
			if (turnA > 0)
				turnA--, needB = 0;
			else if (isA)
				cnt++, needB = 0;
			else
			{
				cout << "-1\n";
				return;
			}
		}
		else // need to turn A
		{
			turnA++;
			cnt++;
			isA = 1;
			needB = 1;
		}
	}
	if (needB == 0)
		cout << cnt << endl;
	else
		cout << -1 << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
}

B - Arithmetic Progression Subsequence

容易想到通过枚举中间值，两边找等差数的想法。但是，很难解决子段重复计数的问题（一个区间可能包含多对等差数）。考虑其他做法。

注意到a[i]的值域很小(1~10)，那么，最小的合法子段的长度也很小（至多21个数就会出现3个相等的数）。这样，我们可以暴力枚举子段，然后直接暴力判断字段的合法性。当第一次合法时直接计算剩余贡献即可。时间复杂度为\(\Theta(n\omega^4)\)（\(\omega\)为值域），大约为\(O(1e9)\)左右，可以通过此题。

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 - Arithmetic Progression Subsequence
// Contest: AtCoder - AtCoder Regular Contest 170
// URL: https://atcoder.jp/contests/arc170/tasks/arc170_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Author: MaxDYF
// 
// 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];
int pre[N][11];

void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		for (int j = 1; j <= 10; j++)
			pre[i][j] = pre[i - 1][j];
		pre[i][a[i]] = i;
	}
	auto check = [&](int l, int r)
	{
		for (int i = l;i <= r; i++)
			for (int j = i + 1; j <= r; j++)
				for (int k = j + 1; k <= r; k++)
					if (a[j] - a[i] == a[k] - a[j])
						return true;
		return false;
	};
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (check(i, j))
			{
				ans += n - j + 1;
				break;
			}
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
}

C - Prefix Mex Sequence

阅读全文 »

发表于 更新于 分类于

A - Tricky Template

没啥好说的，就是判断有几个\(a_i=c_i或b_i=c_i\)，有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
56
//#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;
	string a, b, c;
	cin >> a >> b >> c;
	auto check = [&]()
	{
		int cnt = n;
		for (int i = 0; i < n; i++)
		{
			if (a[i] == c[i] || b[i] == c[i])
				cnt--;
		}
		return cnt > 0;
	};
	if (check())
	{
		cout << "YES\n";
	}
	else
	{
		cout << "NO\n";
	}

}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - Forming Triangles

可以发现，\(2^i+2^i = 2^{i+1}\)，可见可构成三角形的只有两种情况：

  1. 两个相等的和一个小的组合
  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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// Problem: B. Forming Triangles
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/B
// 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;

void work()
{
	cin >> n;
	vector<ll> a(n), but(n + 1);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		but[a[i]]++;
	__int128 big_n = n;
	__int128 ans = 0;
	__int128 sum = 0;
	for (int i = 0; i <= n; i++)
	{
		if (but[i] > 1)
		{
			__int128 x = but[i];
			ans += sum * (x * (x - 1)) / 2ll + (x * (x - 1) * (x - 2)) / 6ll;
		}
		sum += but[i];
	}
	auto print = [&](__int128 x)
	{
		string s;
		while (x)
		{
			s.push_back(x % 10 + '0');
			x /= 10;
		}
		reverse(s.begin(), s.end());
		if (s.size())
			cout << s << endl;
		else
			cout << 0 << endl;
	};
	print(ans);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Closest Cities

可以发现，最优路线一定是一直朝着终点走，直接正反递推一下距离即可。

阅读全文 »
0%