Codeforces Round 903 (Div. 3)
A. Don't Try to Count
大概题意给你两个字符串a,b。a串可进行的操作为将整个a串复制到之前的a串后面（直接用a+a即可），然后看操作多少次可以让b串变为a串的子串如果不能就输出-1。
#include <iostream>
using namespace std;
string a,b;
void solve()
{
int n,m;
cin>>n>>m;
cin>>a>>b;
int cnt=0;
while(n<m)
{
a=a+a;
n<<=1;
cnt++;
}
for(int i=0;i<n;++i)
{
bool pd=1;
for(int j=i;j<i+m;++j)
{
if(a[j]!=b[j-i])
{
pd=0;
break;
}
}
if(pd)
{
cout<<cnt<<endl;
return ;
}
}
a=a+a;
n<<=1;
cnt++;
for(int i=0;i<n;++i)
{
bool pd=1;
for(int j=i;j<i+m;++j)
{
if(a[j]!=b[j-i])
{
pd=0;
break;
}
}
if(pd)
{
cout<<cnt<<endl;
return ;
}
}
cout<<-1<<endl;
}
int main() {
int t;
cin>>t;
while(t--) {
solve();
}
return 0;
}
B. Three Threadlets
题意：给三个数，分开他们使得剩下的为相同的
思路：三次分法，可以不完全用，所以只需要考虑最差的情况，将三个数排序为max，min，mid。如果三个数相等直接输出“YES”，如果三个数不相等的话那么就不能分min，如果mid也可以不分的话那么就有这两种情况
$$
max:mid:min=3:2:1(三次都用)/2:2:1(只用两次)
$$
如果mid=min那么只有max需要分那么就有比例为
$$
max:mid:min=4:1:1/3:1:1/2:1:1
$$
#include <iostream>
using namespace std;
void solve(){
int a,b,c;
cin>>a>>b>>c;
if(a==b&&b==c) {
cout<<"YES"<<"\n";
return ;
}int ma=a,mi=a;
ma=max(ma,b);
ma=max(ma,c);
mi=min(mi,b);
mi=min(mi,c);
int mid=a+b+c-mi-ma;
if(ma==2*mi&&mid==2*mi) {
cout<<"YES"<<"\n";
return ;
}if(mid==mi&&ma==3*mi){
cout<<"YES"<<"\n";
return ;
}if(ma==3*mi&&mid==2*mi) {
cout<<"YES"<<"\n";
return ;
}if(mid==mi&&ma==2*mi){
cout<<"YES"<<"\n";
return ;
}if(mid==mi&&ma==4*mi){
cout<<"YES"<<"\n";
return ;
}
cout<<"NO"<<"\n";
}
int main() {
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. Perfect Square
题意：有一个正方形矩阵，我们对其的操作一次为将一个字母++，当这个字母变成'z'时就不会再改变了，问多少次之后我们旋转90°之后和原来的矩阵重合
思路：一共有四种(90/360)，我们可以求出这四个坐标中最大的，然后剩下的++记作一次操作
#include <bits/stdc++.h>
using namespace std;
char mp[1010][1010];
void solve(){
int m;
cin>>m;
long long int res=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=m/2;i++){
for(int j=1;j<=m/2;j++){
int ma=max(mp[i][j],max(mp[m-j+1][i],max(mp[m-i+1][m-j+1],mp[j][m-i+1])));
res+=ma*4-mp[i][j]-mp[m-j+1][i]-mp[m-i+1][m-j+1]-mp[j][m-i+1];
}
}
cout<<res<<endl;
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
D. Divide and Equalize
题意：操作：找到一个数x使得ai=ai/x;aj=aj/x；要求：所有数相等
思路：这个变化会使他的乘积没有变化，故我们可知他们的乘积为一个数的n次方，那么他的因数个数应该为n的倍数。
板子：质因数分解
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
map<int,int> q;
for(int j=0;j<n;j++){
int x;
cin>>x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
q[i]+=s;
}
if (x > 1) q[x]++;
}
for(auto x:q){
if(x.second%n!=0){
cout<<"NO"<<"\n";
return ;
}
}
cout<<"YES"<<"\n";
}
signed main() {
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
E. Block Sequence
题意：操作：删除一个数；要求：让数列分成一块一块的（什么叫块：假设你a[i]=x,那么a[i]~a[i+x-1]为一个块）
1.把自身直接删了dp[i]=dp[i-1]+1;
2.假设左边已经有一个完美的块，要使整个序列都为完美，只需要后面也为完美块，假设后面的数<a[i],dp[i]=d[i+1]+1;如果相等dp[i]=0,如果后面的数>a[i]那么dp[i]=ap[i+a[i]+1];
#include <bits/stdc++.h>
using namespace std;
const int MAX=1e6+10;
int dp[MAX],arr[MAX];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
dp[n + 1] = 0;
for(int i = n; i >= 0; i --)
{
if(arr[i] + i > n) dp[i] = dp[i + 1] + 1;
else if(arr[i] + i == n) dp[i] = 0;
else dp[i] = dp[i + arr[i] + 1];
dp[i] = min(dp[i], dp[i + 1] + 1);
}
cout << dp[0] << '\n';
}
int main()
{
int t;
cin>>t;
while (t--){
solve();
}
return 0;
}