当前位置：首页 > news >正文

Codeforces Round 921 (Div. 2)补题

news 来源：原创 2024/5/20 3:03:14

We Got Everything Covered!（Problem - A - Codeforces）

题目大意：要求找出一个长度最短的字符串，满足任意由前k个字母组成的长度为n的字符串都是它的子序列。输出字符串。

思路：这道题我本来想的很简单，觉得只要在一个字母前，前k个字母都出现n-1次即可，所以我就让前k个字母按顺序排列作为一组，然后输出n遍，然后就过了。但是写到c题才发现，并不是简简单单的出现n-1次就行，因为如果对于aabbab，n=3,k=2来说，我们虽然满足在最后一个a和最后一个b之前a,b都出现n-1次，但实际上我们凑不出baa这个序列。所以正解应该是前k个字母为一组，一共n组，每次从每组中选一个元素，然后就可以得到任意的顺序。因为每组中都包含了前k个元素。

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){for(int j=0;j<k;j++){char c='a'+j;printf("%c",c);}}printf("\n");}
}

A Balanced Problemset?（Problem - B - Codeforces）

题目大意：现有一个数x，我们要把它拆成n个数相加，要求这n个数和为x，同时gcd最大，求出最大gcd是多少。

思路：我最开始想的是gcd最大的话肯定是尽可能地均分，然后如果不能均分的话，我们就令a=x/n,b=x%n,每次a-=1,b+=n，直到a==0,然后每次求出gcd，从中取最大值。但是按照题目给的数据的话会超时。我们再换个角度想想，所有数的gcd与x有什么关系，显然也是x的因数，因为每个数相当于a*g,那么加起来就是(a+b+c+...)*g，所以g一定是x的因数，另外因为我们可以发现均分的时候gcd最大，剩下的时候，gcd只会越变越小，所以我们就在x/n的范围内找x的最大因数即可。用试除法刚好。另外这里n的范围在1e8以内，其实也是暗示了开平方。

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int x,n;scanf("%d%d",&x,&n);int a=x/n;int ans=0;for(int i=1;i<=x/i;i++){if(x%i==0){if(x/i<=a) ans=max(ans,x/i);if(i<=a) ans=max(ans,i);}}cout<<ans<<endl;}
}

Did We Get Everything Covered?（Problem - C - Codeforces）

题目大意：现有一个字符串s，我们需要判断是否由前k个字母组成的长度为n的字符串都是它的子串如果是，输出yes，否则输出no,并输出一个例外。

思路：同a的分析一样，我们将包含前k个字母的一段视为一组，看看是否满足大于等于n组，如果满足那么输出yes，不满足，那么就满足的里面随便挑一个字符，不满足的部分看看谁不存在全部挑出来补在后边即可构成一个不满足要求的字符串。

#include<bits/stdc++.h>
using namespace std;
int st[30];
int main()
{int t;scanf("%d",&t);while(t--){int n,k,m;scanf("%d%d%d",&n,&k,&m);string s;cin>>s;memset(st,0,sizeof st);string c="";for(int i=0;i<s.size();i++){st[s[i]-'a']=1;int flag=1;for(int j=0;j<k;j++){if(!st[j]){flag=0;break;}}if(flag){c+=s[i];memset(st,0,sizeof st);}}if(c.size()>=n) printf("YES\n");else{for(int i=0;i<k;i++){if(!st[i]){while(c.size()<n) c += ('a'+i);}}printf("NO\n");cout<<c<<endl;}}
}

Good Trip(Problem - D - Codeforces)

题目大意：有n个小朋友，m对友谊关系，老师需要进行k次旅行，每次平等独立地挑选两个小朋友，每对友谊关系地初值为fi，如果一对朋友被带出去，那么回来后他们的友谊值会增加1（如果初始值为0，那么不变），现在要求k次带出去的小朋友的友谊值得期望是多少。

思路：显然容易想到，初始值为0得毫无意义，那么就来看初始值非0的，我们可以一对一对来算，假设第i对小朋友在第j次旅行中被选，同时已经被选了z次，那么它对答案的贡献就是：

那么我们可以如下实现：

for(int i=1;i<=m;i++){for(int j=1;j<=k;j++)//当前是第j轮{for(int z=1;z<=j;z++)//这一次被选，所以至少是从1开始，可以j次都选它{int c=(long long)f[j-1]*uf[z-1]%mod*uf[j-z]%mod;sum += (long long)c*qmi(in,j)%mod*qmi(all-1,j-z)%mod*(w[i]+z-1)%mod;sum %= mod;}}}

我当时没分析时间复杂度就交了，显而易见，超时了，只过了5组样例。我们观察一下数据范围可以发现，这个题每组样例需要在O(n)的时间复杂度内解决。那么我们进一步来看这个式子，很容易发现，整个式子中只有w[i]与i有关系，那么我们可以把w[i]提出来，将所有的w[i]加起来求和。

但是显然目前还剩下两层循环，还需要再优化。

我们对单从式子层面很难找到再优化的点，那么我们从实际意义出发:

这样一次循环就算出来了，但是，我在wa了几次后遇到了一个很奇怪的点，m*p的值需要预处理，否则就会wa，另外算p的时候，我们直接算n*(n-1)/2的mod-2次方得逆元，就不要拆开了。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int qmi(long long a,int b)
{long long res=1;while(b){if(b&1) res = res*a%mod;a = a*a%mod;b >>= 1;}return res;
}
int w;
int main()
{int t;scanf("%d",&t);while(t--){int n,m,k;scanf("%d%d%d",&n,&m,&k);int a,b,w;int s=0;for(int i=1;i<=m;i++) scanf("%d%d%d",&a,&b,&w),s=(s+w)%mod;int p=qmi(((long long)n*(n-1)/2)%mod,mod-2);int ad=(long long)p*m%mod; int res=0;for(int i=1;i<=k;i++){res = ((long long)res + (long long)p*s%mod +(long long)p*(i-1)%mod*ad%mod)%mod;}cout<<res<<endl;}
}