「Codeforces」寒假训练 2023 #2

A. Yet Another Palindrome Problem

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t;
int n;
int a[N];
int res;
int main()
{
	cin >> t;
	while(t--)
	{
		res = 0;
		scanf("%d", &n);
		map<int, vector<int> > mp;
		for(int i = 0; i < n; i++)
		{
			scanf("%d", a + i);
			mp[a[i]].push_back(i);
		}
		for(int i = 0; i < n ; i++)
		{
			int l = mp[a[i]].size();
			vector<int> b = mp[a[i]];
			for(int j = 0; j < l; j++)
			{
				if(b[j] - b[0] >= 2)
				{	
					res = 1;
					break;
				}
			}
			if(res == 1) break;
		}
		if(res == 1) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

B. Shuffle Hashing

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t;
char p[110], h[110];
int main()
{
	cin >> t;
	while(t--)
	{
		scanf("%s", p);
		scanf("%s", h);
		int lenp = strlen(p);
		int lenh = strlen(h);
		map<char, int> mp;
		for(int i = 0; i < lenp; i++)
		{
			mp[p[i]]++;
		}
		bool f = false;
		for(int i = 0; i + lenp - 1 < lenh; i++)
		{
			bool matched = true;
			map<char, int> mh;
			for(int j = i; j < i + lenp; j++)
			{
				mh[h[j]]++;
			}
			for(int j = 0; j < lenp; j++)
			{
				
				if(!mh.count(p[j]) || mh[p[j]] != mp[p[j]])
				{
					matched = false;
					break;
				}
			}
			if(matched)
			{
				f = true;
				break;
			}
		}
		if(f)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
	return 0;
}

C. 2048 Game

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int M = 2048;
bool cmp(int u, int v)
{
	return u > v;
}
int main()
{
	int q;
	cin >> q;
	while(q--)
	{
		int n;
		int a[N];
		cin >> n;
		for(int i = 0; i < n; i++)
		{
			scanf("%d", a + i);
		}
		sort(a, a + n, cmp);
		bool f = false;
		int sum = 0;
		for(int i = 0; i < n; i++)
		{
			if(a[i] <= M && M % a[i] == 0)
			{
				sum += a[i];
			}
			if(sum == M)
			{
				f = true;
				break;
			}
		}
		if(f) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

D. Transformation: from A to B

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10;
int a, b;
int res;
int vis[N];
bool f;
void dfs(int x, int t)
{
	if(x == b)
	{
		f = true;
		res = t;
		return;
	}
	if(x > b)
	{
		return;
	}
	vis[t] = 10 * x + 1;
	if(x <= 1e8)
	{
		dfs(10 * x + 1, t + 1);
	}
	if(f)
	{
		return;
	}
	vis[t] = 2 * x;
	dfs(2 * x, t + 1);
}
int main()
{
	cin >> a >> b;
	vis[0] = a;
	dfs(a, 1);
	if(f)
	{
		cout << "YES" << endl;
		cout << res << endl;
		for(int i = 0 ; i < res ; i++)
		{
			printf("%d ", vis[i]);
		}
		cout << endl;
	}
	else cout << "NO" << endl;
	return 0;
}

E. Getting Zero

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int M = 32768;
int n;
int x;
int main()
{
	int n;
	cin >> n;
	while(n--)
	{
		int res = 15;
		cin >> x;
		for(int i = 0; i <= 15; i++)
		{
			for(int j = 0; j <= 15; j++)
			{
				if(((x + i) << j) % M == 0)
				{
					res = min(res, i + j);
				}
			}
		}
		cout << res << " ";
	}
	return 0;
}