Codeforces Round 903 (Div. 3)A~F

A - Don't Try to Count

题意:字符串s每次操作后变成s+s，问能否操作若干次是t是s的字串。

思路：数据范围很小，len(s)和len(t)最大25，要么如果枚举到len(s)长度大于等于len(t)的二倍，还没有出现答案，之后就不会出现答案。故需要枚举log2(50)上取整次，即六次。

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
void solve()
{
	int n, m; cin >> n >> m;
	string s1, s2; cin >> s1 >> s2;
	int ans = 0; 
	for(int i = 1; i <= 6; i ++)
	{
		if(s1.find(s2) < s1.size())
		{
			cout << ans << '\n';
			return;
		}
		s1 += s1;
		ans ++;
	}
	cout << -1 << '\n';
}
 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t --) solve(); 
}

 B - Three Threadlets

题意：给n个数，问三次操作能否把数分成相等的值。

要切的操作最少，那么切成min值最优。因为如果要切成更小的值，必须得先经历切成min的操作数。

比如8要切成2，因8 = 2 + 2 + 2 + 2，至少要切 8 / 2 - 1次。

故将所有次数累加即可。

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
void solve()
{
	int a, b, c; cin >> a >> b >> c;
	int minn = min({a, b, c}); 
	if((a % minn == 0) && (b % minn == 0) && (c % minn == 0))
	{
		int ans = 0;
		ans += (a / minn) - 1, ans += (b / minn) - 1, ans += (c / minn) - 1;
		if(ans <= 3)
		{
			cout << "YES" << '\n';
			return;
		}
	}
	cout << "NO" << '\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t = 1; cin >> t;
	while(t --) solve(); 
}

C. Perfect Square（几何）

题意：给一个n x n的字母正方形，n为偶数，要使向右旋转九十度后的字母重合，需要多少次操作。每次操作可以使当前字母变成字母表下一个字母。

思路：根据绕中心旋转的性质，我们只需要（n / 2）x (n / 2)的正方形，就能得到其他应该相同的位置。

找字母应该相同的点时，我们可以发现，把大的正方形分成四个（n / 2）x (n / 2)的小正方形后，这四个小正方形有四个参照点，顺时针依次为(0,0) (0,n-1) (n-1,n-1) (n-1,0)，无论怎么旋转在小正方形里它们与参照点的相对位置是不变的。

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
using i64 = long long;
void solve() 
{
    int n; cin >> n;
    vector<string>s(n);
    for(auto &ss : s) cin >> ss;
    int ans = 0;
	for(int i = 0; i < n / 2; i ++)
    {
    	for(int j = 0; j < n / 2; j ++)
    	{
    		int sum = s[i][j] + s[j][n - 1 - i] + s[n - 1 - i][n - 1 - j] + s[n - 1 - j][i];
    		int maxx = max({s[i][j], s[j][n - 1 - i], s[n - 1 - i][n - 1 - j], s[n - 1 - j][i]});
    		ans += maxx * 4 - sum;
		}
	}
	cout << ans << '\n';
}
 
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) solve();
 
}

D. Divide and Equalize（筛质数，数论）

注意这题卡常，尽量用数组。

题目:给一个长度为n的数组，你可以进行若干次操作：选出两个数ai和aj，以及任意的满足x|ai的x，使得ai = ai / x, aj = aj * x。问是否能让数组中所有数相等。

思路:

对所有数分解质因数并求出质因数的次数，每次操作可以使一个位置的数的质因数次数+1，另一个位置的数的质因数次数-1，那么进行若干次操作，我们可以尽量将质因数的次数匀给每个数。

显然，如果每个出现的质因数的次数是n的整数倍，操作后可以均分，使得每个数相等。

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
const int N = 1e6;
vector<int>minp, primes;
void sieve(int n)
{
	minp.assign(n + 1, 0);
	primes.clear();
	for(int i = 2; i <= n; i ++)
	{
		if(minp[i] == 0) minp[i] = i, primes.push_back(i);
		for(auto p : primes)
		{
			if(i * p > n) break;
			minp[i * p] = p;
			if(p == minp[i]) break;
		}
	} 
}
int cnt[N + 1];
void solve() 
{
    int n; cin >> n;
    vector<int>a(n), stk;
    for(auto x : a)
    {
    	cin >> x;
    	while(x > 1)
    	{
    		int p = minp[x];
    		x /= p;
    		stk.push_back(p);
    		cnt[p] ++;
		}
	}
    bool ok = 1;
    for (auto x : stk) 
	{
        if (cnt[x] % n) ok = 0;
        cnt[x] = 0;
    }
    cout << (ok ? "YES" : "NO") << '\n';
}
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve(N);
    int t; cin >> t;
    while (t--) solve();
}

E. Block Sequence（dp）

很激动第一次十几分钟一发命中dp，感觉比D好写一些。

题目：对于每个块，满足第一个数是长度len，后面紧跟着len个数，如4 x x x x是一个块。需要执行若干次删除操作使数组由多个块组成。

思路：

定义dp[i]为使得数组i~n变成连续块的最小操作数。

状态转移：

1.每个数都可以选择删除自己dp[i] = dp[i + 1] + 1

2.如果之后的个数没有a[i]个，那么只能由右边的数转移来dp[i] = dp[i + 1] + 1

如果之后的个数恰好等于a[i]个，那么形成一个块dp[i]=0

如果之后的个数小于a[i]个，那么在形成了长度为len的块之后，需要接上后面的块的最小操作数

dp[i] = dp[i + a[i] + 1]

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
const int N = 1e6;
void solve() 
{
    int n; cin >> n;
    vector<int>a(n + 1), dp(n + 2);
    for(int i = 1; i <= n; i ++) cin >> a[i];
	dp[n + 1] = 0;
	for(int i = n; i >= 0; i --)
    {
    	if(a[i] + i > n) dp[i] = dp[i + 1] + 1;
    	else if(a[i] + i == n) dp[i] = 0;
    	else dp[i] = dp[i + a[i] + 1];
    	dp[i] = min(dp[i], dp[i + 1] + 1);
	}
	cout << dp[0] << '\n';
}
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
}

F - Minimum Maximum Distance（树形结构，bfs）

题目：给一棵n个点的树，其中k个点有标记。定义f(i)为点i到所有标记点的距离中的最大值。要求输出min(f(1)~f(n))。

思路：先求出所有f(i)，再算最小值。

要求出f(i)：

首先，我们使点1为根，求出深度最大的标记点a。我们可以发现，除a点所在的子树外所有子树上面的所有点的 f(i) 等于它们各自到 a 的距离，同时f(1)也等于到a的距离，如下图红色部分已经解决。

然后我们找出离a距离最大的标记点b。

如果b在上边已经解决的位置，那么剩下的所有点都不跟b在同一子树，剩下的点的距离f(i)要么等于到a的距离要么等于到b的距离。

如果b不在上边已经解决的位置，又因为最大距离不超过maxdeep(a)。故剩下的点的距离f(i)要么等于到a的距离要么等于到b的距离。所有点得到解决。

综上所述，f(i)要么等于distance(i，a)要么等于distance（i，b），两者取最大值。最后在所有f(i)里取最小值。

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
const int N = 1e6;
void solve() 
{
    int n, k; cin >> n >> k;
    vector<int>mark(n);
    for(int i = 0; i < k; i ++)
    {
    	int x; cin >> x;
    	x --;
    	mark[x] = 1;
	}
    vector<vector<int>>adj(n);
	for(int i = 0; i < n - 1; i ++)
    {
    	int a, b; cin >> a >> b;
    	a --, b --;
    	adj[a].push_back(b);
    	adj[b].push_back(a);
	}
	vector<int>dis(n);
	auto bfs = [&](int x)
	{
		dis.assign(n, - 1);
		queue<int>q;
		q.push(x);
		dis[x] = 0;
		while(q.size())
		{
			int u = q.front();
			q.pop();
			for(auto v : adj[u])
			{
				if(dis[v] != -1) continue;
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
		int t = -1;
		for(int i = 0; i < n; i ++)
		{
			if(mark[i] && (t == -1 || dis[i] > dis[t])) t = i;
		}
		return t;
	};
	int a = bfs(0), b = bfs(a);
	auto f = dis;
	bfs(b);
	int ans = 1e9;
	for(int i = 0; i < n; i ++)
	{
		ans = min(ans, max(f[i], dis[i]));
	} 
	cout << ans << '\n';
}
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
}