【题解】Codeforces Round #619 (Div. 2)
比赛链接:https://codeforces.com/contest/1301
#
- A. Three Strings(思维)
- B. Motarack’s Birthday(思维)
- C. Ayoub’s function(思维)
- D. Time to Run(构造)
A. Three Strings(思维)
原题链接:https://codeforces.com/contest/1301/problem/A
- 题意: 给三个相同长度 n 字符串 a,b,c,c 每个字符必须和 a 或者 b 的相应下标字符交换,问经过 n 次变换后 a 是否可以和 b 相同。
- 思路: a 的字符与 c 的相同或者 b 的字符与 c 的相同既符合交换。如果三个字符都相同也是一样的,交换后还是 a 和 b 还是相同。
Code:
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
int t; cin>>t;
while(t--){
string a,b,c; cin>>a>>b>>c;
ll len=a.length();
int flag=1;
for(int i=0;i<len;i++){
if(a[i]==c[i] || b[i]==c[i])
continue;
else{
flag=0;
break;
}
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
B. Motarack’s Birthday(思维)
原题链接:https://codeforces.com/contest/1301/problem/B
- 题意: 给一个长度为 n 的数组,-1 代表没有数,你需把空位补上相同的 k ,使得数组相邻元素中的最大的差值的绝对值最小。
- 思路: 先找出旁边有空位的数的最大值和最小值,然后取中间值作为 k,将空位全部补上,遍历一遍数组,输出最大的差值的绝对值。
Code:
#include <iostream>
#include <cstring>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N];
int main(){
int t; cin>>t;
while(t--){
memset(a,0,sizeof(a));
int n; cin>>n;
int maxn=0,minn=inf,flag=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]!=-1) flag=1;
}
for(int i=1;i<=n;i++){
if(a[i]!=-1 && (a[i-1]==-1 || a[i+1]==-1)){
maxn=max(maxn,a[i]);
minn=min(minn,a[i]);
}
}
if(!flag){
cout<<0<<' '<<0<<endl;
continue;
}
int mid=(maxn+minn)/2;
for(int i=1;i<=n;i++){
if(a[i]==-1)
a[i]=mid;
}
int ans=0;
for(int i=2;i<=n;i++)
ans=max(ans,(int)abs(a[i]-a[i-1]));
cout<<ans<<' '<<mid<<endl;
}
return 0;
}
C. Ayoub’s function(思维)
原题链接:https://codeforces.com/contest/1301/problem/C
- 题意: 给长度 n ,m 个 1,构造出一个含 1 子串数量最大的字符串,求最多的含 1 子串数量。
- 思路:
- 用子串总数量减掉不含 1 子串数量即为含 1 子串数量。一个字符串子串数量为 n*(1+n) / 2。
- m 个 1 把 n-m 个 0 分割成 m+1 部分,要使得含 1 子串数量最多,就得将 0 平均分给这 m+1 部分。a = (n-m) / (m+1)就是平均每份 0 的数量,剩下的 b = (n-m)%(m+1) 就在 m+1 份放个 1 。没放 1 的部分就有 m+1-b 份。
- 放 1 部分不含 0 的子串数量有 b*(a+2)*(a+1)/2 ,不放 1 部分不含 0 的子串数量有 c(1+a)a/2。
Code:
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
int t; cin>>t;
while(t--){
ll n,m; cin>>n>>m;
ll a = (n-m)/(m+1);
ll b = (n-m)%(m+1);
ll c = m+1-b;
cout<<(1+n)*n/2-b*(a+2)*(a+1)/2-c*(1+a)*a/2<<endl;
}
return 0;
}
D. Time to Run(构造)
原题链接:https://codeforces.com/contest/1301/problem/D
- 题意: 给一个 n*m 的图,路线在图中已标出,问能否在图中走 k 步,路线不能重复,点可以重复。如果不能走,输出“NO”,否则输出 “YES” ,总步骤,每个步骤不能超出 4 个步数,并且总步骤数不能超过 3000 次。
- 思路: 走法如图所示
- 当没走到第 m 列时,每一列都要进行 n-1 次 “D”,n-1 次 “RLU”,1 次 “R”。
- 当走到第 m 列时,要进行 n-1 次 “D”,n-1 次 “U”,m-1 次 “L”。
Code:
#include <iostream>
#include <vector>
using namespace std;
struct node{
int cnt;
string str;
node(int sum,string s){
cnt=sum;
str=s;
}
};
vector<node> a;
void push(node x){
if(x.cnt!=0)
a.push_back(x);
}
int main(){
int n,m,k; cin>>n>>m>>k;
if(4*n*m-2*n-2*m<k)
cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
int cow=1;
while(k){
if(cow!=m){
if(k>=(n-1)){
push({ n-1,"D"});
k-=(n-1);
}
else{
push({ k,"D"});
k=0;
}
if(k==0) break;
if(k>=3*(n-1)){
push({ n-1,"RLU"});
k-=3*(n-1);
}
else{
push({ k/3,"RLU"});
if(k%3==1) push({ 1,"R"});
else if(k%3==2) push({ 1,"RL"});
k=0;
}
if(k==0) break;
if(k>=1){
push({ 1,"R"});
k--;
}
}
else{
if(k>=n-1){
push({ n-1,"D"});
k-=(n-1);
}
else{
push({ k,"D"});
k=0;
}
if(!k) break;
if(k>=n-1){
push({ n-1,"U"});
k-=(n-1);
}
else{
push({ k,"U"});
k=0;
}
if(!k) break;
if(k>=m-1){
push({ m-1,"L"});
k-=(m-1);
}
else{
push({ k,"L"});
k=0;
}
}
cow++;
}
cout<<a.size()<<endl;
for(int i=0;i<a.size();i++)
cout<<a[i].cnt<<' '<<a[i].str<<endl;
}
return 0;
}
还没有评论,来说两句吧...