Codeforces Round #712 (Div. 2) A~E题解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Round #712 (Div. 2) A~E题解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6622字，纯文字阅读大概需要10分钟。
内容图文
文章目录
A. Déjà Vu
- 解题思路
我们很容易发现，对于一个回文串，如果其中的字母不全是 a a a，那么我们总能找到一个不对称的地方插入 a a a，使得回文串变成非回文串，最简单的就是直接插入头部或尾部。但有一点要注意的是，对于非回文串，我们插入之后需要判断是否变成了回文串，如果在头部插入不满足要求，那么在尾部插入一定满足要求。 - AC代码
/**
*@filename:A
*@author: pursuit
*@CSDNBlog:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-04-06 18:45
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;
int t;
string s;
bool check(string s){
int l=0,r=s.size()-1;
while(l<=r){
if(s[l]!=s[r])return false;
l++,r--;
}
return true;
}
void solve(){
//简单分析一下，如果是回文的，那么如果一直添加a可行，说明该字符串中不是全部的a。
bool flag=true;
for(auto &x:s){
if(x!='a'){
flag=false;
break;
}
}
if(!flag){
cout<<"YES\n";
if(check(s+"a")){
cout<<"a"+s<<endl;
}
else{
cout<<s+"a"<<endl;
}
}
else{
cout<<"NO\n";
}
}
int main(){
while(cin>>t){
while(t--){
cin>>s;
solve();
}
}
return 0;
}
B. Flip the Bits
-
解题思路
题目要求我们翻转前缀（该前缀 0 , 1 0,1 0,1的数量要相等）使得 a ? > b a->b a?>b。那么我们值得注意的就是更改前缀的条件为 0 , 1 0,1 0,1的数量要相等，更改的结果是前缀原来相等的与 b b b不相等，原来不相等的与 b b b相等。 所以我们可以遍历字符串 a a a，统计 0 , 1 0,1 0,1的数量。这里可以利用cnt+=(a[i]=='1')-(a[i]=='0)，这样相当于是 1 1 1就加 1 1 1，是 0 0 0就加 0 0 0，这样保证了 0 , 1 0,1 0,1数量相等的时候 c n t = 0 cnt=0 cnt=0。
我们知道 b b b是需要由 a a a变过来的，那么在遍历的过程中如果遇到需要更改的地方且更改不了（这里需要更改的意思是此时 a a a和 b b b的连续位置 i , i + 1 i,i+1 i,i+1处存在且仅存在一处不相等，那么我这里必须做出更改，因为这种情况无法通过后续的前缀翻转实现相等。），那么自然是无解的。为了方便判断，我们在 a , b a,b a,b字符串后面加上一个 0 0 0，为了提供最后的参照。 -
AC代码
/**
*@filename:B
*@author: pursuit
*@CSDNBlog:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-04-06 18:58
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;
int t,n;
string a,b;
void solve(){
//思维题，我们更改前缀的条件就是0和1的数量要相等。那么如果位于需要更改的地方确不能更改，那就无解了。
int cnt=0;
a+="0",b+="0";//这么做的目的是为了判断更好的前缀。
for(int i=0;i<n;i++){
cnt+=((a[i]=='1')-(a[i]=='0'));//统计0和1的数量是否相等。
//判断该位置是否可以交换。
if((a[i]==b[i])!=(a[i+1]==b[i+1])&&cnt!=0){
//如果出现不相等，且目前不可翻转。
puts("NO");
return;
}
}
puts("YES");
}
int main(){
while(cin>>t){
while(t--){
cin>>n;
cin>>a>>b;
solve();
}
}
return 0;
}
C. Balance the Bits
-
解题思路
核心点就是 1 1 1相同， 0 0 0不同，所以如果我们需要构建一个平衡的括号序列，那么必须满足：- 首尾必须为 1 1 1，因为括号序列第一位必须为(, 最后一位必须为), 即两个序列首尾两个位置必须相同。
- 0 , 1 0,1 0,1的个数必须都是偶数，因为 1 1 1会导致两个括号序列 a , b a,b a,b的位置相同，而如果是奇数的，那么会产生一个没有配对的括号给 0 0 0处理，而 0 0 0会让 a , b a,b a,b所填位置不相同，故无法配对构造出两组序列。
满足了以上，我们就可以构造序列了，双指针扫描序列中的1，左边放左括号，右边放右括号，而剩余的0则轮流放左右括号即可。这样保证了所有的左右括号都能配对上，且构建出的序列 a , b a,b a,b是不相同的。
D. 3-Coloring
-
解题思路
我们简单考虑一下，如果没有颜色禁止，我们构造出一个 n × n n\times n n×n的颜色不相邻的矩阵是完全 o k ok ok的，且只需要 2 2 2中颜色，如下，以 4 × 4 4\times 4 4×4的矩阵为例：2 1 2 1
1 2 1 2
2 1 2 1
1 2 1 2我们是以 x + y x+y x+y的奇偶性来确定颜色填放的，即奇数位放 1 1 1号颜料，偶数位放 2 2 2号颜料。
那么回到这个问题，现在每轮声明一种禁止的颜色，那么我们该怎么处理呢？实际上已经显而易见了，我们完全可以用 3 3 3代替 1 1 1或 2 2 2来填充。例如当我们的奇数位已经填充完了，而偶数位还没填充，且 2 2 2号颜料已经被禁止了，那么我们就可以使用 3 3 3来填充了，这样保证了相邻单元格颜色不相同。 -
AC代码
/**
*@filename:D
*@author: pursuit
*@CSDNBlog:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-04-07 09:07
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;
vector<pair<int,int> > od,ev;//存储坐标。od存储x+y为奇数的坐标。ev存储x+y为偶数的坐标。
int n;
void solve(){
}
int main(){
while(cin>>n){
od.clear(),ev.clear();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if((i+j)&1){
od.push_back({i,j});
}
else{
ev.push_back({i,j});
}
}
}
int temp;
int od_index=0,ev_index=0;//索引。
for(int i=1;i<=n*n;i++){
cin>>temp;
//根据temp判断。
if(temp!=1&&od_index<od.size()){
//如果没有禁用颜色1
cout<<1<<" "<<od[od_index].first<<" "<<od[od_index].second<<endl;
od_index++;
}
else if(temp!=2&&ev_index<ev.size()){
//如果没有禁用颜色2，就填2.
cout<<2<<" "<<ev[ev_index].first<<" "<<ev[ev_index].second<<endl;
ev_index++;
}
else{
//否则根据情况来填充。
if(od_index<od.size()){
cout<<3<<" "<<od[od_index].first<<" "<<od[od_index].second<<endl;
od_index++;
}
else{
cout<<3<<" "<<ev[ev_index].first<<" "<<ev[ev_index].second<<endl;
ev_index++;
}
}
cout.flush();
}
}
return 0;
}
E. Travelling Salesman Problem
-
解题思路
我们知道 ( i , j ) (i,j) (i,j)的花费为 m a x ( c [ i ] , a [ j ] ? a [ i ] ) max(c[i],a[j]-a[i]) max(c[i],a[j]?a[i])，对此进行处理即为 c [ i ] + m a x ( 0 , a [ j ] ? ( a [ i ] + c [ i ] ) ) c[i]+max(0,a[j]-(a[i]+c[i])) c[i]+max(0,a[j]?(a[i]+c[i]))。题目中要求每个点只需要走一次，且最后回到起点，这其实就是一个环，所以已知最低的代价就是 ∑ i = 0 n ? 1 c [ i ] \sum_{i=0}^{n-1}c[i] ∑i=0n?1?c[i]。由于是环，所以我们的起点可以任意选择，同样路径也是可以由我们决定的，所以我们固然是需要贪心的选择，根据 m a x ( 0 , a [ j ] ? ( a [ i ] + c [ i ] ) ) max(0,a[j]-(a[i]+c[i])) max(0,a[j]?(a[i]+c[i]))可知，当 a [ j ] < = ( a [ i ] + c [ i ] ) a[j]<=(a[i]+c[i]) a[j]<=(a[i]+c[i])的时候，我们是可以无额外消耗的直接到达的点，那么我们就可以理解将 a [ i ] + c [ i ] a[i]+c[i] a[i]+c[i]理解为我们所能到达的最远距离，那么这个目标实际上就是将点依次纳入我们已经到达了的点，并统计额外消耗即可。那么我们必然是需要对 a a a进行排序，这样才可以保证我们的额外消耗最小（即抵消的越多）。按顺序维护一个当前的最远距离，不断向后纳入新点并更新最远距离和额外花费。
e x t r a C o s t = ∑ j = 2 n m a x ( 0 , a [ j ] ? m a x ( a [ i ] + c [ i ] ) ) ( i < j ) extraCost = \sum_{j=2}^{n}max(0,a[j]-max(a[i]+c[i]))(i<j) extraCost=∑j=2n?max(0,a[j]?max(a[i]+c[i]))(i<j)， a [ i ] + c [ i ] a[i]+c[i] a[i]+c[i]即当前已经到达的点的最远距离。 -
AC代码
/**
*@filename:E
*@author: pursuit
*@CSDNBlog:unique_pursuit
*@email: 2825841950@qq.com
*@created: 2021-04-07 12:26
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;
int n;//城市数量。
struct node{
int a,c;
}citys[maxn];
bool cmp(node &a,node &b){
return a.a<b.a;
}
void solve(){
}
int main(){
while(cin>>n){
ll ans=0;
for(int i=0;i<n;i++){
cin>>citys[i].a>>citys[i].c;
ans+=citys[i].c;//加上必要花费。
}
sort(citys,citys+n,cmp);//排序。
int maxx=citys[0].a+citys[0].c;//维护一个最远距离。相当于内部是一个集合。
for(int i=1;i<n;i++){
ans+=max(0,citys[i].a-maxx);
maxx=max(maxx,citys[i].a+citys[i].c);
}
cout<<ans<<endl;
}
solve();
return 0;
}
内容总结
以上是互联网集市为您收集整理的Codeforces Round #712 (Div. 2) A~E题解全部内容，希望文章能够帮你解决Codeforces Round #712 (Div. 2) A~E题解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。