Codeforces Round 903 (Div. 3)A~F
A.Don't Try to Count
输入样例：
12 1 5 a aaaaa 5 5 eforc force 2 5 ab ababa 3 5 aba ababa 4 3 babb bbb 5 1 aaaaa a 4 2 aabb ba 2 8 bk kbkbkbkb 12 2 fjdgmujlcont tf 2 2 aa aa 3 5 abb babba 1 19 m mmmmmmmmmmmmmmmmmmm输出样例：
3 1 2 -1 1 0 1 3 1 0 2 5
思路：签到题，但要注意当字符串a的长度大于2倍的b长度还没有子串b时，说明a中不可能出现子串b，要退出循环。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int t;cin>>t;
while(t--)
{
int n,m;cin>>n>>m;
string a,b;cin>>a>>b;
int cnt=0,f=0;
while(a.find(b)==string::npos)
{
a+=a;
cnt++;
if(a.size()>2*m&&a.find(b)==string::npos)
{
cout<<-1<<endl;
f=1;
break;
}
}
if(!f)
cout<<cnt<<endl;
}
}B. Three Threadlets
输入样例：
15 1 3 2 5 5 5 6 36 12 7 8 7 6 3 3 4 4 12 12 6 8 1000000000 1000000000 1000000000 3 7 1 9 9 1 9 3 6 2 8 2 5 3 10 8 4 8 2 8 4输出样例：
YES YES NO NO YES YES NO YES NO NO YES YES NO YES NO
思路：找规律，通过模拟样例可以发现三根线要一样长，那么最终长度肯定是要与最短的那根线一样长，如果某根线不能剪成最短长度，说明这根线不能被最短的长度整除，直接输出NO就可以了，如果能被整除，那么比较这两根线的长度和/最短长度得到的结果是否会大于3，大于就输出NO，反之YES。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int t;cin>>t;
while(t--)
{
vector<int> v(3);
int f=0,cnt=0;
for(auto &it:v) cin>>it;
sort(v.begin(),v.end());
f=(v[1]%v[0]||v[2]%v[0]);
if(f) puts("NO");
else
{
cnt=v[1]/v[0]-1+(v[2]/v[0]-1);
if(cnt<=3) puts("YES");
else puts("NO");
}
}
}C. Perfect Square
输入样例：
5 4 abba bcbb bccb abba 2 ab ba 6 codefo rcesco deforc escode forces codefo 4 baaa abba baba baab 4 bbaa abba aaba abba输出样例：
1 2 181 5 9
思路： 因为题目要求矩阵翻转90°之后仍保持不变，说明矩阵的每一条边上的字母都得一样，所以我们可以通过从上往下的每一行的边与另外三条边上对应的元素进行比较（总共只需要遍历n/2行），因为只能将字母变大，所以我们要找到这四条边中最大的字母是哪个，然后另外三个字母就变成这个最大字母maxd,变化次数为4*maxd-（a1+a2+a3)，然后我们要记得将原位置更小的字母改成更大的字母，具体可看代码。
代码：
#include<iostream>
using namespace std;
const int N=1e3+5;
char a[N][N];
int main()
{
int t;cin>>t;
while(t--)
{
int n,sum=0;cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>a[i][j];
for(int i=1;i<=n/2;i++)
for(int j=1+i-1;j<=n-i;j++)
{
int a1=a[i][j]-'a'; //cout<<a1<<' ';
int a2=a[n-j+1][i]-'a'; //cout<<a2<<' ';
int a3=a[n-i+1][n-j+1]-'a';// cout<<a3<<' ';
int a4=a[j][n-i+1]-'a'; //cout<<a4<<' ';
int maxd=max(a1,max(a2,a3));
maxd=max(maxd,a4);
sum+=4*maxd-(a1+a2+a3+a4);
if(a1!=maxd)
a[i][j]+=maxd-a1;
if(a2!=maxd)
a[n-j+1][i]+=maxd-a2;
if(a3!=maxd)
a[n-i+1][n-j+1]+=maxd-a3;
if(a4!=maxd)
a[j][n-i+1]+=maxd-a4;
// cout<<maxd<<' '<<sum<<' '<<a1+a2+a3+a4<<endl;
// cout<<maxd<<' '<<a[4][2]<<endl;
//puts("");
}
cout<<sum<<endl;
}
}
D. Divide and Equalize
输入样例：
7 5 100 2 50 10 1 3 1 1 1 4 8 2 4 2 4 30 50 27 20 2 75 40 2 4 4 3 2 3 1输出样例：
YES YES NO YES NO YES NO
思路： 这道题一开始没什么思路，后面看了一些大佬的题解才恍然大悟（heheh(￣▽￣)"终归还是我太菜了）,首先我们要知道每个大于1的数都可以分解成几个质因数的乘积，那么这道题的操作是一个数除k的同时另一个数乘k，因数的个数是不会变的，我们可以将其看成因数的转移，所以这n个数中每个质因数的个数如果为n的整数倍则可以将他们变成一样的数，否则不能。
代码：
#include<iostream>
#include<map>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
map<int,int> h;
for(int i=0;i<n;i++)
{
int x;cin>>x;
for(int m=2;m<=x/m;m++)
{
while(x%m==0)
{
h[m]++;
x/=m;
}
}
if(x>1) h[x]++;
}
int f=0;
for(auto it:h)
{
if(it.second%n!=0)
{
f=1;
break;
}
}
if(f) puts("NO");
else puts("YES");
}
}E. Block Sequence
输入样例：
7 7 3 3 4 5 2 6 1 4 5 6 3 2 6 3 4 1 6 7 7 3 1 4 3 5 1 2 3 4 5 5 1 2 3 1 2 5 4 5 5 1 5输出样例：
0 4 1 1 2 1 0
思路： 这道题我们要从后往前dp，定义dp[i]为从n到i的最少操作次数，由题意可知我们对一个数字有两种操作，删除：dp[i]=dp[i+1]+1,保留 ：dp[i]=dp[i+a[i]+1]，我们只需要在这两种操作中取最小值就可以了。
代码：
#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+5;
int a[N],dp[N];
/*逆向dp*/
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n;i>=1;i--)
{
dp[i]=dp[i+1]+1;//删除
if(i+a[i]<=n) dp[i]=min(dp[i],dp[i+a[i]+1]);//比较保留和删除两种操作
}
cout<<dp[1]<<endl;
}
}F. Minimum Maximum Distance
输入样例1：
6 7 3 2 6 7 1 2 1 3 2 4 2 5 3 6 3 7 4 4 1 2 3 4 1 2 2 3 3 4 5 1 1 1 2 1 3 1 4 1 5 5 2 4 5 1 2 2 3 1 4 4 5 10 8 1 2 3 4 5 8 9 10 2 10 10 5 5 3 3 1 1 7 7 4 4 9 8 9 6 1 10 9 1 2 4 5 6 7 8 9 10 1 3 3 9 9 4 4 10 10 6 6 7 7 2 2 5 5 8输出样例1：
2 2 0 1 4 5输入样例2：
3 6 1 3 1 2 1 3 3 4 3 5 2 6 5 3 1 2 5 1 2 1 3 2 4 3 5 7 1 2 3 2 2 6 6 1 5 6 7 6 4 5输出样例2：
0 2 0
思路： fi的最小值只会出现在两个或多个标记顶点中间的点到标记顶点的最大距离，找两个标记顶点的最大距离相当于找树的直径(传送门)，结果输出（树的直径-1）/2+1。
代码：
/*树的直径————两次dfs
第一次dfs算出所有结点到根节点的距离，到根节点最大距离的那个结点就是树的直径的一个端点
第二次dfs以端点为根节点，算出其他点到直径端点的距离，然后取距离最大的那个点即为直径的另一个端点
第二次dfs求到的到端点的最大距离即为树的直径*/
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=2e5+5;
int depth[N],mark[N];
vector<int> edge[N];
void dfs(int u,int fa)
{
for(auto t:edge[u])
{
if(t==fa) continue;
depth[t]=depth[u]+1;
dfs(t,u);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--)
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++) edge[i].clear();
//vector<int> edge[n];
for(int i=1;i<=k;i++) cin>>mark[i];
for(int i=1;i<n;i++)
{
int a,b;cin>>a>>b;
edge[a].emplace_back(b),edge[b].emplace_back(a);
}
depth[1]=0;
if(k==1)
{
cout<<0<<endl;
continue;
}
dfs(1,-1);
int c=mark[1];
for(int i=2;i<=k;i++)
if(depth[mark[i]]>depth[c]) c=mark[i];//先求直径的一个端点
depth[c]=0;
dfs(c,-1);//从这个被标记的端点出发找另一个端点
c=mark[1];
for(int i=2;i<=k;i++)
if(depth[mark[i]]>depth[c]) c=mark[i];
cout<<(depth[c]-1)/2+1<<endl;
}
}（将近半个月没写cf了，A题都让我TLE了一发，暑假得刷起来了😂，话说学校暑假放得真晚，还在复习期末考试科目(￣▽￣)"。。。
原文地址：https://blog.csdn.net/2302_79372568/article/details/140230416
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！