目录
A. Don't Try to Count
因为字符串的长度很小，我们可以暴力求解，每次操作都可以使字符串s的长度倍增，可以在s的子串找到字符串t的条件是s长度必须要长于t，当长度比t长还是没有找到答案基本就可以返回-1了。
#include<bits/stdc++.h>
#define int long long
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e5 + 10;
const int M = 1e3 + 10;
using namespace std;
bool ok(string a, string b)
{
if (a.size() < b.size()) return false;
for (int i = 0; i < a.size() - b.size() + 1; i++)
{
if (a.substr(i, b.size()) == b) return true;
}
return false;
}
void solve() {
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
int ans = 0;
bool can = true;
while (!ok(s, t))
{
ans++;
string temp = s;
s.reserve();
s = temp + s;
if (ans > 6)
{
can = false;
break;
}
}
if (can)
cout << ans << "\n";
else cout << "-1\n";
}
signed main() {
ios;
TEST
solve();
return 0;
}B. Three Threadlets
数学思维题，我们必须将所有绳子的长度变成一样的，但是剪最短的绳子只会得到更短的，此时其他的绳子也要剪得更短，所以对最短的绳子操作是不优的，因为我们的次数只有三次。
其余两个绳子的长度为最短的绳子的长度的公倍数才有答案，要剪的次数就是其余两个绳子除最大的绳子的除数的和。
#include<bits/stdc++.h>
#define int long long
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e5 + 10;
const int M = 1e3 + 10;
using namespace std;
void solve() {
vector<int>a(4);
for (int i = 1; i <= 3; i++) cin >> a[i];
sort(a.begin() + 1,a.end());
int mi = a[1];
int ans = 0;
for (int i = 2; i <= 3; i++)
{
if (a[i] % mi != 0)
{
cout << "NO\n";
return;
}
ans += (a[i] / mi) - 1;
}
if (ans <= 3) cout << "YES\n";
else cout << "NO\n";
}
signed main() {
ios;
TEST
solve();
return 0;
}C. Perfect Square
模拟一下，每个字符的位置都有三个匹配的位置，我们要求的就是将这四个位置变成这四个位置的最大值的次数和。
#include<bits/stdc++.h>
#define int long long
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e5 + 10;
const int M = 1e3 + 10;
using namespace std;
char temp[1001][1001];
void solve() {
int n;
cin >> n;
vector<string>st(n);
for (int i = 0; i < n; i++) cin >> st[i];
int ans = 0;
for (int i = 0; i < n / 2; i++)
{
for (int j = 0; j < n / 2; j++)
{
int m1 = st[i][j], m2 = st[j][n - 1 - i], m3 = st[n - 1 - i][n - 1 - j], m4 = st[n - 1 - j][i];
int mx = max({ m1,m2,m3,m4 });
ans += mx * 4 - (m1 + m2 + m3 + m4);
}
}
cout << ans << "\n";
}
signed main() {
TEST
solve();
return 0;
}D. Divide and Equalize
就是看看是否有一个数的n次方等于数组所有元素相乘。
但是直接暴力去求解会爆数据，所有我们可以找到所有因子的个数，看看这些因子的个数可不可以平均分配给n个数。
#include<bits/stdc++.h>
#define int long long
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 2e6 + 10;
const int M = 1e3 + 10;
using namespace std;
void solve() {
int n;
cin >> n;
vector<int>a(n);
for (int i = 0; i < n; i++) cin >> a[i];
map<int, int>q;
for (int i = 0; i < n; i++)
{
if (a[i] > 1)
{
for (int j = 2; j * j <= a[i]; j++)
{
while (a[i] % j == 0)
{
q[j]++;
a[i] /= j;
}
}
}
q[a[i]]++;
}
for (auto it: q)
{
if (it.first > 1)
{
if (it.second % n != 0)
{
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
signed main() {
ios;
TEST
solve();
return 0;
}E. Block Sequence
从n到1动态规划答案。
#include<bits/stdc++.h>
#define int long long
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e6 + 10;
const int M = 1e3 + 10;
using namespace std;
void solve() {
int n;
cin >> n;
vector<int>a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<int>dp(n + 2, 0x7fffffff);
dp[n + 1] = 0;
for (int i = n; i >= 1; i--)
{
dp[i] = min(dp[i], dp[i + 1] + 1);
if (i + a[i] <= n)
{
dp[i] = min(dp[i], dp[i + a[i] + 1]);
}
}
cout << dp[1] << "\n";
}
signed main() {
ios;
TEST
solve();
return 0;
}F. Minimum Maximum Distance
了解到题目要求我们去求一个节点到最远标记点的最小距离。
我们发现答案存在于最远标记点之间的节点。
答案就是最远标记点的距离除以2向上取整。
求最远距离就是需要去了解树的直径的知识了，两次dfs可以求出来。
#include<bits/stdc++.h>
#define int long long
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N = 1e6 + 10;
const int M = 1e3 + 10;
using namespace std;
int n, k;
vector<vector<int>>f;
int dis[N];
void dfs(int now, int pre)
{
if (pre != -1) dis[now] = dis[pre] + 1;
for (auto x : f[now])
{
if (x == pre) continue;
dfs(x, now);
}
}
void solve() {
cin >> n >> k;
for (int i = 0; i <= n; i++) f.clear(), dis[i] = 0;
f.resize(n + 1);
vector<int>tag(k + 1);
for (int i = 1; i <= k; i++)
{
cin >> tag[i];
}
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
f[u].push_back(v);
f[v].push_back(u);
}
if (k == 1)
{
cout << "0\n";
return;
}
int ans;
dis[0] = -1;
dfs(1, -1), ans = tag[1];
for (int i = 1; i <= k; i++) if (dis[tag[i]] > dis[ans]) ans = tag[i];
for (int i = 1; i <= n; i++) dis[i] = 0;
dis[0] = -1;
dfs(ans, -1);
ans = tag[1];
for (int i = 1; i <= k; i++) if (dis[tag[i]] > dis[ans]) ans = tag[i];
cout << (dis[ans] + 1) / 2 << "\n";
}
signed main() {
ios;
TEST
solve();
return 0;
}