Educational Codeforces Round 116

A. AB Balance
分析：只要第一个和最后一个相同，均满足

#include "bits/stdc++.h"
using namespace std;
const int maxn=1000+1;
string s[maxn];
int main()
{
//freopen("in.txt","r",stdin);
int n;
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
int len=s[i].length();
if(s[i][0]==s[i][len-1]) cout<<s[i]<<endl;
else{
s[i][len-1]=s[i][0];
cout<<s[i]<<endl;
}
}
return 0;
}

B. Update Files
分析：如果小于k，则每次对接数量增加一倍，否则对接数量为k

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int main()
{
//freopen("in.txt","r",stdin);
int T;
ios::sync_with_stdio(false);
cin>>T;
while(T--){
LL n,k;
cin>>n>>k;
LL ans=0,cur=1;
while(cur<k){
cur<<=1;
ans++;
}
if(cur<n) ans+=(n-cur+k-1)/k;
cout<<ans<<endl;
}
return 0;
}

C. Banknotes
分析：贪心，尽可能装小的，第$i$种最多可以装$\frac{a[i+1]}{a[i]}-1$个

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=10+1;
int T,n,k;
LL a[maxn];
LL quick_mul(LL a,LL b){
LL res = 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
cin>>T;
while(T--){
cin>>n>>k;
k++;
for(int i=0;i<n;i++){
LL x;
cin>>x;
a[i] = quick_mul(10LL,x);
}
LL ans = 0;
for(int i=0;i<n;i++){
int cnt = k;
if(i!=n-1) cnt=min(cnt,(int)(a[i+1]/a[i]-1));
ans+=1LL*(LL)cnt*a[i];
k-=cnt;
}
cout<<ans<<endl;
}
return 0;
}

D. Red-Blue Matrix
分析：参考这位大佬的做法link

#include "bits/stdc++.h"
using namespace std;
const int maxn=0x3f3f3f3f;
int T;
int main()
{
ios::sync_with_stdio(false);
//freopen("in.txt","r",stdin);
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
int a[n+1][m+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
int Lmax[n+1][m+1],Lmin[n+1][m+1],Rmax[n+1][m+1],Rmin[n+1][m+1];
for(int i=1;i<=n;i++) Lmax[i][1] = a[i][1], Lmin[i][1] = a[i][1];
for(int i=1;i<=n;i++) Rmax[i][m] = a[i][m], Rmin[i][m] = a[i][m];
for(int i=1;i<=n;i++){
for(int j=2;j<=m;j++){
Lmax[i][j] = max(Lmax[i][j-1],a[i][j]);
Lmin[i][j] = min(Lmin[i][j-1],a[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=m-1;j>=1;j--){
Rmax[i][j] = max(Rmax[i][j+1],a[i][j]);
Rmin[i][j] = min(Rmin[i][j+1],a[i][j]);
}
}
int flag = 0;
for(int j=1;j<m;j++){
vector<pair<int,int>>vec;
for(int i=1;i<=n;i++) vec.push_back(make_pair(Lmin[i][j],i));
sort(vec.begin(),vec.end(),[](const pair<int,int>& a,const pair<int,int>& b){
if(a.first==b.first) return a.second < b.second;
return a.first<b.first;
});
int num[n+1];
for(int i=1;i<=n;i++) num[i] = vec[i-1].second;
int lmaxv[n+2],lminv[n+2],rmaxv[n+2],rminv[n+2];
for(int i=0;i<=n+1;i++) lmaxv[i]=rmaxv[i]=0,lminv[i]=rminv[i]=maxn;
for(int i=1;i<=n;i++){
lmaxv[i] = max(lmaxv[i-1],Lmax[num[i]][j]);
rminv[i] = min(rminv[i-1],Rmin[num[i]][j+1]);
}
for(int i=n;i>=1;i--){
lminv[i] = min(lminv[i+1],Lmin[num[i]][j]);
rmaxv[i] = max(rmaxv[i+1],Rmax[num[i]][j+1]);
}
for(int i=1;i<n;i++){
if(lmaxv[i] < lminv[i+1] && rminv[i] > rmaxv[i+1]){
cout<<"YES"<<endl;;
char s[n+1]; s[n]=0;
for(int k=1;k<=n;k++)
s[num[k]-1] = (k<=i ? 'B' : 'R');
cout<<s<<" "<<j<<endl;
flag=1; break;
}
}
if(flag) break;
}
if(!flag) cout<<"NO"<<endl;
}
return 0;
}

E. Arena
分析：$dp(i,j)$表示前i个数，不超过j，最终剩下1个的方案数。显然可得$dp(1,j)=j,dp(2,j)=j\times (j-1)$；当$j\ge 3$时，考虑在$i$个人中，有$k$个人生命值在i以下，则在该轮之后，有$i-k$个勇士的生命值，不超过$j-i+1$，那么$k$个人可以选取的方案数为$(i-1{)}^k$，由此可得状态转移方程为: $dp(i,j)+=dp(i-k,j-i+1)\times (i-1{)}^k\times C_i^k$

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=500+10;
const LL mod = 998244353;
int n,k;
LL c[maxn][maxn],dp[maxn][maxn];
LL quickmod(LL a,int b){
LL res=1;
while(b){
if(b&1) res=res*a%mod;
a = a * a %mod;
b>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k;
c[0][0]=1;
for(int i=1;i<=505;++i){
c[i][0]=1;
for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
for(int i=1;i<=k;i++) dp[1][i]=i,dp[2][i]=i*(i-1)%mod;
for(int i=3;i<=n;i++){
for(int j=1;j<=k;j++){
if(j<i){
dp[i][j]=0;
continue;
}
for(int l=0;l<i;l++){
dp[i][j]+=(((dp[i-l][j-i+1]*quickmod((LL)(i-1),l))%mod)*c[i][l])%mod;
dp[i][j]%=mod;
}
}
}
cout<<(quickmod((LL)k,n)-dp[n][k]+mod)%mod<<endl;
return 0;
}

最后

以上就是贤惠刺猬为你收集整理的Educational Codeforces Round 116的全部内容，希望文章能够帮你解决Educational Codeforces Round 116所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。