抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

记第一次codeforces比赛(上)

发布于：2023年10月14日

次浏览

写在前面

如果要提升自己算法技术的话听说刷Leetcode帮助不大，那现在每日一题转为刷codeforces上的题目吧。

第一次参加codeforces的比赛，只敢打了个div.3。2h15min只能做出两道题来，感觉自己被血虐。

赛后补了下题目，补题的时候又感觉好像也不难。。。

A. Don’t Try to Count (补题AC)

题面

原题链接

(看到这标题吓我一跳)

翻译一下题目大意：

给定两个字符串xx和ss。

可以对xx字符串做复制操作，就是复制自身放到后面。

例如abcabc复制一次变成abcabcabcabc，再复制一次变成abcabcabcabcabcabcabcabc。

问最少需要复制几次xx，可以让ss成为xx的一个子串。

例如：

x=eforcx = eforc
s=forces = force
eforceforc复制一次变成eforceforce\textbf{force}forc
所以只需要复制一次就可以满足条件。

思路

比赛的时候第一题没写出来蚌埠住了。主要是不知道判断复制到什么时候结束。

s字符串的最后一个字符位置乘上2？一直卡在中断条件那。

偏偏没注意到x和s的长度范围是小于25的。

在最极端的情况下x长度为1，s的长度为25。最多只需要复制五次就能达到1∗251*2^5超过25了。

找子串的话可以用KMP模版，但没背。

所以直接用了C++字符串自带的find函数。

1
2
3
4
5
6
s = "abc";
x = "bc";
s.find(x);

在s字符串里找x子串，返回x首个字符所在的位置。
如果没有找到则返回string::npos。

所以最终思路就是：

边复制边查找是否存在子串，一旦找到就退出循环输出当前复制次数。

代码

头文件什么的就省略了。

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
#define mem(a) memset(a,0,sizeof(a))
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define fi(i,l,r) for(int i=l;i<=r;i++) 
#define cd(a) scanf("%d",&a)
typedef long long ll;
using namespace std;
 
void solve()
{
	int n;
	int m;
	cin >> n >> m;
	string x, s;
	cin >> x >> s;
	fi(i, 0, 5) {
		if (x.find(s) != string::npos) {
			cout << i << '\n';
			return;
		}
		x += x;
	}
	cout << "-1\n";
	return;
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

B. Three Threadlets (AC)

题面

原题链接

题面大意翻译：

给你三根木棍的长度，可以对任意一根木棍砍一刀，让它分成两半（这两半长度不能其中一个为0）。

例如66可以被分为2,42,4和1,51,5，但不能分为0,60,6。

最多能砍三刀，问是否能通过砍几刀，能使所有木棍最后长度相同。

例如：

1,3,2→1,2,1,2→1,1,1,1,2→1,1,1,1,1,11,3,2→1,2,1,2→1,1,1,1,2→1,1,1,1,1,1 可以通过砍3刀来完成任务。

6,36,126,36,12 3刀内不能让它们长度相同。

思路

我的思路有点蠢，但因为数据量小，所以能过。

由题意可知，最后这三根木棍的长度必定是小于或等于最开始的时候最短那根木棍的长度的。

所以每次以最短的那根木棍minLengthminLength为目标，把maxLengthmaxLength那根砍成minLength,maxLength−minLengthminLength,maxLength - minLength这两个长度。

再把获得的新木棍加进数组里再次排序。

如果三次还不能满足条件，那么就是失败了。

看了看题解好像只用保存最小值就够了，只要用比最小值大的数去砍也行。

代码

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
bool check(vector<int>& v) {
	int tmp = v[0];
	int len = v.size();
	for (int i = 1; i != len; ++i) {
		if (v[i] != tmp) {
			return false;
		}
		tmp = v[i];
	}
	return true;
}
 
int main()
{
	int t;
	cin >> t;
	vector<int> a(3);
	int tmp = 0;
	while (t--) {
		a.assign(3);
		scanf("%d %d %d", &a[0], &a[1], &a[2]);
		sort(a.begin(), a.end());
		if (a[0] == a[1] && a[1] == a[2]) {   //已经都相等了就直接输出吧
			cout << "YES" << '\n'; 
			continue;
		}
		a.push_back(a[0]);
		a[2] -= a[0];          //砍第一刀
		sort(a.begin(), a.end());
		if (check(a)) {
			cout << "YES" << '\n';
			continue;
		}
		a.push_back(a[0]);
		a[3] -= a[0];       //砍第二刀
		sort(a.begin(), a.end());
		if (check(a)) {
			cout << "YES" << '\n';
			continue;
		}
		a.push_back(a[0]);
		a[4] -= a[0];       ////砍第三刀
		sort(a.begin(), a.end());
		if (check(a)) {
			cout << "YES" << '\n';
			continue;
		}
		cout << "NO" << '\n';
	}
	return 0;
}

C. Perfect Square (AC)

题面

原题链接

题目大意翻译：

给定一个n∗nn*n的矩阵，n为偶数。

要让这个矩阵顺时针旋转90°90\degree后跟原来的矩阵相同。

可以对这个矩阵的字母进行改变。使a→ba \to b的代价为11，a→da \to d的代价为3。当该字母为zz时不能改变。

问如何以最小的代价，使得这个矩阵顺时针旋转90°90\degree后跟原来的矩阵相同。

例如这个矩阵:

abbabcbbbccbabba\begin{matrix} &a &b &b &a \\ &b &c &\mathbf{b} &b \\ &b &c &c &b \\ &a &b &b &a \end{matrix}

只需要对加粗的bb操作一次让它变成cc就可以满足条件了。

思路

这道题有两个点。

首先是如何遍历这个矩阵。

正常我们是通过横坐标和纵坐标访问元素的，现在需要顺时针访问。

我们可以一步一步走，到达顶点处时加个判断，让它拐个弯。

真巧前几天Leetcode也有一道这种顺时针访问矩阵的题目。把当时写的lambda表达式拿过来用就可以了。

其次是如何找到需要修改的值。

可以使用双指针的办法。

例如最开始cur1cur1指向(0,0)(0,0)，cur2cur2指向(0,m−1)(0, m-1)。

判断cur1和cur2指向的值是否相同，不同的话就让较小的那个字母进行操作让它变成较大的那个字母。把代价存起来。

接下来cur1和cur2都往下走一步，这样依次遍历。

循环一次的话会发现有的值没有被更改，一次不行的话就再来一次，果然循环两次就可以了。

代码

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <cmath>
 
using namespace std;
 
char a[1010][1010];
 
int change(char& a, char& b) {   //较小的那个字母让它变成较大的那个字母。返回代价
	if (a > b) swap(a, b);
	int res = b - a;
	a = b;
	return res;
}
 
int main()
{
	int t;
	int n;
	cin >> t;
	pair<int, int> x, y;   //用pair来存坐标
	auto moveForword = [](pair<int, int>& cur, int start, int end) {   //往下走一步的函数
		if (cur.first == start) {
			if (cur.second == end) cur.first += 1;
			else cur.second += 1;
			return;
		}
		if (cur.second == end) {
			if (cur.first == end) cur.second -= 1;
			else cur.first += 1;
			return;
		}
		if (cur.first == end) {
			if (cur.second == start) cur.first -= 1;
			else cur.second -= 1;
			return;
		}
		if (cur.second == start) {
			if (cur.first == start) cur.second += 1;
			else cur.first -= 1;
			return;
		}
	};
	int cnt = 0;
	while (t--) {
		cnt = 0;
		scanf("%d\n", &n);
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				a[i][j] = getchar();
			}
			getchar();
		}
		for (int i = 1; i <= n / 2; ++i) {
			x.first = i, x.second = i;
			y.first = i, y.second = n - i + 1;
			for (int j = 1; j <= 4 * 2; ++j) {
				for (int w = 1; w <= n - i; ++w) {
					if (a[x.first][x.second] != a[y.first][y.second]) cnt += change(a[y.first][y.second],a[x.first][x.second]);
					moveForword(x, i, n - i + 1);
					moveForword(y, i, n - i + 1);
				}
			}
		}
		printf("%d\n", cnt);
	}
	return 0;
}

更新于：2024年4月2日

codeforces

评论