Codeforces Round 921 (Div. 2) A~D

本期封面原图 画师村カルキ 这个太太的画风我好喜欢
古早题目洛谷都有翻译我就不写题意了

A - We Got Everything Covered!

思路

没有长度限制，只要我把abcde输出n遍那不管什么匹配我都可以在每一轮拿一个拿到

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int n,k;scanf("%d%d",&n,&k);while(n--){for(int i=0;i<k;i++){printf("%c",'a'+i);}}printf("\n");
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

B - A Balanced Problemset?

思路

不难guess到要找第一个比n大的x的因数求答案，n刚好只到1e8所以可以放心的用最朴素的方法求他的所有因数

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int x,n;scanf("%d%d",&x,&n);vector<int> a;//拆x的所有因数for(int i=1;i*i<=x;i++){if(x%i==0){a.push_back(i);a.push_back(x/i);}}sort(a.begin(),a.end());//找到第一个大于等于n的因数int p=lower_bound(a.begin(),a.end(),n)-a.begin();printf("%d\n",x/a[p]);
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

C - Did We Get Everything Covered?

思路

回想第一题，我们是构造了一轮一轮，在这里我们仍然需要一轮一轮，前k个小写字符都出现过算1轮，至少要有n轮才算成功，遍历一遍就行了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int n,k,m;scanf("%d%d%d",&n,&k,&m);string s;cin>>s;int p=-1;string ans;int vis[26];int CNT=0;int flag=0;while(1){memset(vis,-1,sizeof(vis));int cnt=0;for(int i=p+1;i<m;i++){if(vis[s[i]-'a']==-1){vis[s[i]-'a']=i;cnt++;if(cnt==k){break;}}}if(cnt<k){flag=0;for(int i=0;i<k;i++){if(vis[i]==0){ans+=('a'+i);CNT++;int len=ans.length();for(;len<=n;len++){printf("%c",'a'+i);}break;}}break;}else{int x,y;for(int i=0;i<k;i++){if(vis[i]>x){x=vis[i];y=i;}}ans+=('a'+y);CNT++;p=x;}if(cnt==m){flag=1;break;}}if(flag==0){printf("NO\n");cout<<ans<<endl;}else{printf("YES\n");}
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

D - Good Trip

思路

（看了洛谷的题解补的），设$p=\frac{2}{n(n-1)}$，$s={\sum }_{i=1}^m{f}_i$,每一轮选择时，选择到的友谊值的期望为$p\cdot s$，友谊值总和增加的期望为$p\cdot m$，所以只要不断更新ans和m即可

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll lpw=(int)1e9+7;
ll n,m,k,p,a,b,f,sum,ans;
ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%lpw;a=a*a%lpw;b>>=1;}return ans;
}void solve()
{ans=sum=0;scanf("%lld%lld%lld",&n,&m,&k);p=n*(n-1)%lpw;p=2*qpow(p,lpw-2)%lpw;for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&a,&b,&f);sum=(sum+f)%lpw;}for(int i=1;i<=k;i++)ans=(ans+sum*p%lpw)%lpw,sum=(sum+m*p%lpw)%lpw;printf("%lld\n",ans);
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}