E
题意:有t个长度为n的字符串s, 求最短字符串k的长度, 使得k可以重复多次连接成长度为n的字符串s1, 字符串s1和s最多只有一个地方不同。
我们可以先求出n的因数,再进行判断,
所有下标同余的字符,字符种类只有一种,或者字符种类至多为 2种,
且其中一种字符的数量为 1(后者这种情况不超过 次)
const int N = 2e5 + 10;
int st[N][26];
string s;
int n;
int check(int k)
{
//初始化
for(int i = 0; i < k; i ++)
for(int j = 0; j < 26; j ++)
st[i][j] = 0;
//统计在 i%k 这个位置上的字符
for(int i = 0; i < n; i ++)
st[i % k][s[i] - 'a'] ++;
int ans = 0;
for(int i = 0; i < k; i ++)
{
vector<int>v;
for(int j = 0; j < 26; j ++)
if(st[i][j])
v.push_back(st[i][j]);
//如果说在i位置上有超过2个的字符, 那就不符合题意
if(v.size() > 2)
return 0;
sort(v.begin(), v.end());
//如果说恰好两个字符, 就判断最小个数
if(v.size() == 2)
{
//如果说最小个数不是1, 那么意味着有超过两个位置上字符有不一样的字符
if(v[0] != 1) return 0;
ans ++;
}
}
//最多只能存在一组
return ans <= 1;
}
void solved()
{
cin >> n >> s;
vector<int>v;
for(int i = 1; i <= n / i; i ++)
{
if(n % i == 0)
{
v.push_back(i);
if(n / i != i) v.push_back(n / i);
}
}
sort(v.begin(), v.end());
for(auto x : v)
{
if(check(x))
{
cout << x << endl;
return;
}
}
cout << n << endl;
}
int main()
{
int t; cin >> t;
while(t --) solved();
return 0;
}
F
给出a, b, c; 求一棵有 a+b+c个顶点的有根树 †的最小高度,该树满足以下条件:a个顶点正好有 2个子顶点、b个顶点正好有1个子顶点,且c个顶点正好有 0个子顶点。如果不存在这样的树,您应该报告它
首先判断能否构造成树, 节点数n=a+b+c,度数 = 2a+b,如果 n-1 = 2a+b 就能构造成, 否则不行
bfs
const int N = 3e5 + 10;
int dep[N];//记录深度
void solved()
{
int a, b, c; cin >> a >> b >>c;
int n = a + b + c;
//判断能否构造成树
if(2 * a + b != n - 1)
{
cout << "-1" << endl;
return;
}
int ans = 0, idx = 0;
queue<int>q;
q.push(++ idx); //插入根
//初始化深度
for(int i = 0; i <= n; i ++) dep[i] = 0;
while(q.size())
{
auto t = q.front();
q.pop();
ans = max(ans, dep[t]); //记录最大深度
if(a)
{
//给t分配两个子节点, 并 a --
int l = ++ idx;
int r = ++ idx;
dep[l] = dep[r] = dep[t] + 1;
q.push(l), q.push(r);
a --;
}
else if(b)
{
//给t分配一个子节点, 并 b --
int l = ++ idx;
dep[l] = dep[t] + 1;
q.push(l);
b --;
}
}
cout << ans << endl;
}
int main()
{
int t; cin >> t;
while(t --) solved();
return 0;
}