本文主要是介绍Codeforces Round 806 (Div. 4)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
A. YES or YES?
B. ICPC Balloons
C. Cypher
D. Double Strings
E. Mirror Grid
F. Yet Another Problem About Pairs Satisfying an Inequality
G. Good Key, Bad Key
A. YES or YES?
考察大小写转化
直接谁用toupper函数即可
void solve()
{string s; cin>>s;for(int i=0;s[i];i++)s[i]=toupper(s[i]);if(s=="YES") cout<<"YES"<<endl;else cout<<"NO"<<endl;return ;
}B. ICPC Balloons
考察暴力
直接map存起来即可
map<char,int> mp;
int t,n,m;void solve()
{cin>>n;mp.clear();string s; cin>>s;LL ans=0;for(int i=0;i<n;i++){mp[s[i]]++;}for(auto &[k,v]:mp) ans+=v+1;cout<<ans<<endl;return ;
}C. Cypher
考察暴力模拟
数据范围很小直接暴力模拟即可
int a[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){cin>>m;int ans=0;while(m--){char x; cin>>x;if(x=='D') ans++;else ans--;}a[i]=(a[i]+ans+10)%10;}for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<endl;return ;
}D. Double Strings
数据范围暴力
我没可以发现数据范围特别小每一个串我没直接暴力枚举每一个位置就好看是否存在
string s[N];
void solve()
{cin>>n;mp.clear();for(int i=1;i<=n;i++){cin>>s[i];mp[s[i]]++;}for(int i=1;i<=n;i++){string x=s[i];int l=x.size();int f=0;for(int j=1;j<l;j++){if(mp[x.substr(0,j)]&&mp[x.substr(j)]){f=1; break;}}cout<<f;}cout<<endl;return ;
}E. Mirror Grid
经典旋转
把四个点都每一个位置的四个方向都跑一遍接着来看出现的次数是哪一个多判断答案即可
char g[M][M];
bool st[M][M];
int check(int x,int y)
{int ans=0;if(g[x][y]!=g[n-y+1][x]) ans++;if(g[x][y]!=g[y][n-x+1]) ans++;if(g[x][y]!=g[n-x+1][n-y+1]) ans++;if(ans>=2) ans=4-ans;st[x][y]=true;st[n-y+1][x]=true;st[y][n-x+1]=true;st[n-x+1][n-y+1]=true;return ans;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>g[i][j];st[i][j]=false;}}int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(!st[i][j]){ans+=check(i,j);}}}cout<<ans<<endl;return ;
}F. Yet Another Problem About Pairs Satisfying an Inequality
简单式子和前缀和
题目：求 ai< i < aj < j 的对数
我没明显发现具有前面的直接延续到后面的继承性我没只需要对前面的判断是否是满足接着就直接前缀和维护一遍就好了
int t,n,m;
LL a[N],b[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i],b[i]=0;for(int i=1;i<=n;i++){if(a[i]<i){b[i]++;}}LL ans=0;for(int i=1;i<=n;i++) b[i]+=b[i-1];for(int i=1;i<=n;i++){if(a[i]<i){ans+=b[a[i]-1];}}cout<<ans<<endl;return ;
}G. Good Key, Bad Key
性质分析和动态规划
题目意思：n个箱子里面的钱是ai一把钥匙是k元我没可以直接暴力开那么从这个位置到后后面的所有箱子的钱都将会除以2
加黑色不考虑任何东西我们可以直接二维dp但是明显要优化,我们可以发现这个除以2的性质最多除以32个就都是0了所以
我们最多用32把坏钥匙所以状态就变少了常常需要思考除法乘法的性质最少是2的时候32和64都是敏感数字
LL a[N],g[50];
LL f[N][50];
void get()
{g[0]=1;for(int i=1;i<=32;i++) g[i]=g[i-1]*2;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=0;i<=n;i++){for(int j=0;j<=32;j++) f[i][j]=-1e18;}f[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=min(i,32);j++){f[i][j]=max(f[i][j],f[i-1][j]+a[i]/g[j]-m);if(j) f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]/g[j]);if(j>=31) f[i][j]=max(f[i][j],f[i-1][j]);}}LL ans=0;for(int i=0;i<=32;i++) ans=max(ans,f[n][i]);cout<<ans<<endl;return ;
}这篇关于Codeforces Round 806 (Div. 4)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
