「Codeforces」寒假训练 2023 #3

A. String LCM

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int q;
string s, t;
int lens, lent;
int _lcm;
char ans[N];
int len;
int gcd(int u, int v)
{
	return v == 0 ? u : gcd(v, u % v);
}
int lcm(int u, int v)
{
	return u * v / gcd(u, v);
}
bool check()
{
	int k = 0;
	for(int i = 0; i < len; i++)
	{
		if(t[k++] != ans[i]) return false;
		if(k >= lent) k = 0;
	}
	return true;
}
int main()
{
	cin >> q;
	while(q--)
	{
		cin >> s >> t;
		lens = s.length();
		lent = t.length();
		len = 0;
		_lcm = lcm(lens, lent);
		while(len < _lcm)
		{
			for(int i = 0; i < lens; i++)
			{
				ans[len++] = s[i];
			}
		}
		if(check())
		{
			for(int i = 0; i < len; i++)
			{
				printf("%c", ans[i]);
			}
			cout << endl;
		}
		else cout << "-1" << endl;
	}
	return 0;
}

B. ABBB

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t;
char s[N];
char h[3] = "BB";
int main()
{
	cin >> t;
	char u = getchar();
	while(t--)
	{
		char ch;
		bool f = false;
		int k = 0;
		while((ch = getchar()) != '\n')
		{
			if(ch == 'A') f = true;
			else if(ch == 'B' && f)
			{
				k--;
				if(k == 0) f = false;
				else if(s[k - 1] == 'A') f = true;
				else if(s[k - 1] == 'B') f = false;
				continue;
			}
			s[k++] = ch;
		}
		s[k] = '\0';
		int len = strlen(s);
		int ans = 0;
		bool r = true;
		if(len == 0) r = false;
		for(int i = 0; i < len - 1; i++)
		{
			bool matched = true;
			for(int j = 0; j < 2; j++)
			{
				if(s[i + j] != h[j])
				{
					matched = false;
					break;
				}
			}
			if(matched)
			{
				i++;
				if(i == len - 1) r = false;
				continue;
			}
			ans++;
		}
		if(r) ans++;
		cout << ans << endl;
	}
	return 0;
}

C. Repainting Street

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t;
int n, k;
int s[N];
int main()
{
	cin >> t;
	while(t--)
	{
		set<int> c;
		scanf("%d%d", &n, &k);
		for(int i = 0; i < n; i++)
		{
			scanf("%d", s + i);
			c.insert(s[i]);
		}
		int ans = N;
		for(set<int>::iterator it = c.begin(); it != c.end(); it++)
		{
			int res = 0;
			for(int j = 0; j < n; j++)
			{
				if(s[j] != *it)
				{
					res++;
					j += k - 1;
				}	
			}
			ans = min(ans, res);
		}
		cout << ans << endl;
	}
	return 0;
}

D. WeirdSort

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		int a[N];
		set<int> p;
		for(int i = 0; i < n; i++)
		{
			scanf("%d", a + i);
		}
		for(int i = 0; i < m; i++)
		{
			int x;
			scanf("%d", &x);
			p.insert(x);
		}
		int f = true;
		for(int i = 0; i < n - 1; i++)
		{
			for(int j = 0; j < n - 1 - i; j++)
			{
				if(a[j] > a[j + 1])
				{
					if(!p.count(j + 1))
					{
						f = false;
						break;
					}
					int tmp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = tmp;
				}
			}
			if(!f) break;
		}
		if(f) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

E. Valera and Tubes

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, k;
int cnt;
bool f, h;
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	if(m % 2) f = true;
	for(int x = 1; x <= n; x++)
	{
		if(x % 2)
		{
			for(int y = 1; y <= m; y += 2)
			{
				if(cnt != k - 1)
				{
					cnt++;
					printf("2 %d %d ", x, y);
					if(f && y + 1 > m) printf("%d %d\n", x + 1, y);
					else printf("%d %d\n", x, y + 1);
				}
				else
				{
					if(!h)
					{
						h = true;
						printf("%d ", n * m - cnt * 2);
					}
					printf("%d %d ", x, y);
					if(f && y + 1 > m)
					{
						if(x != n) printf("%d %d ", x + 1, y);
					}
					else printf("%d %d ", x, y + 1);
				}
			}
		}
		else
		{
			for(int y = m; y >= 1; y -= 2)
			{
				if(f && y == m)
				{
					y++;
					continue;
				}
				if(cnt != k - 1)
				{
					cnt++;
					printf("2 %d %d %d %d\n", x, y, x, y - 1);
				}
				else
				{
					if(!h)
					{
						h = true;
						printf("%d ", n * m - cnt * 2);
					}
					printf("%d %d %d %d ", x, y, x, y - 1);
				}
			}
		}
	}
	printf("\n");
	return 0;
}