Educational Codeforces Round 163
A - Special Characters
签到题,循环输出AABB即可(有人输出AAB,我觉得也行)
void solve(){
CIN(n);
if(n%2==0){
CY;
FOR(i,1,n/2){//感觉还是AAB更优雅一点
cout<<"AB"[i%2]<<"AB"[i%2];
}
cout<<ET;
}else{
CN;
}
}
B - Array Fix
贪心题,倒序遍历一遍,如果找到首次不合法则特判这个不合法能不能通过拆分解决,如果不能直接返回,如果能,后面继续遍历时所有数都得拆。
void solve(){
CIN(n);
vector<ll> a;a.push_back(0);
FOR(i,1,n){
CIN(now);a.push_back(now);
}
ll MIN_MAX=a[n];
bool flag=0;
rFOR(i,n,2){
if(!flag){
if(a[i]<a[i-1]){
if(a[i-1]<10){CN;return;}
if(a[i-1]%10<a[i-1]/10){CN;return;}
if(a[i-1]%10>a[i]){CN;return;}
flag=1;
}
}else{
if(a[i]%10<a[i]/10){CN;return;}
if(a[i-1]%10<a[i-1]/10){CN;return;}
if(a[i]>=10){
if(a[i-1]%10>a[i]/10){CN;return;}
}else{
if(a[i-1]%10>a[i]){CN;return;}
}
}
}
CY;return;
}
C - Arrow Path
数据量略有点小,直接无脑上BFS即可,推导一下也行,但是脑子不够快的话就不要把时间花在推式子上了。
bool vis[3][200005];
void solve(){
CIN(n);
string a[3];
cin>>a[1]>>a[2];
a[1]=" "+a[1];
a[2]=" "+a[2];
map<char,int> move;
move['<']=-1;move['>']=1;
memset(vis,0,sizeof vis);
queue<pair<int,int>> q;
q.push({1,1});
while(!q.empty()){
auto &[y,x]=q.front();q.pop();
if((y==2&&x==n)||(y==1&&x==n)||(y==2&&x==n-1)){CY;return;}
if(vis[y][x])continue;
vis[y][x]=1;
if(x>=3&&move[a[y][x-1]]!=1&&!vis[y][x-2])q.push({y,x-2});
if(x<=n-2&&move[a[y][x+1]]!=-1&&!vis[y][x+2])q.push({y,x+2});
if(y==1&&!vis[2][x+move[a[2][x]]])q.push({2,x+move[a[2][x]]});
if(y==2&&!vis[1][x+move[a[1][x]]])q.push({1,x+move[a[1][x]]});
}
CN;return;
}
D - Tandem Repeats?
暴力即可,但是记得别暴力过头了,
void solve(){
string s;cin>>s;s=" "+s;
int n=s.length()-1;
int ans=0;
rFOR(offset,n/2,1){
int tmp=0;
FOR(i,1,n-offset+1){//利用tmp++,并在不符合时重新计数来记忆当前遍历的最大连续长度
if(tmp>=offset){cout<<offset*2<<ET;return;}
if(!(s[i+offset]=='?')&&!(s[i]=='?')&&(s[i]!=s[i+offset]))tmp=0;
else tmp++;
}
if(tmp>=offset){cout<<offset*2<<ET;return;}
}
cout<<0<<ET;
}
E - Clique Partition
RF神说是道水题
- “我搞不懂为什么这题的n和k这么小,它完全可以再大一点的”
- “我觉得D是大于E的,E唯一的难点就在于它是E,你看不到它”
题意是给定
分析核心式子
再来考虑如何构造每个组,对于一个组,他的序号是没法改的,所以要使每个组的成员均两两满足式子,先考查
所以每个组(偶数情况),构造:
当然你反过来构造:
考虑奇数情况,易知如上构造也符合题意,让正中间的元素最大即可。
void solve(){
CIN(n);CIN(k);
vector<int> a(n+1),GROUP(n+1);
int cnt=0;
auto f=[&](auto f,int l,int gruop){
if(l>n)return;
cnt=gruop;
int num=min(n-l+1,k);//判断剩下的能不能凑一个长度为k的组
int now=l;
//rFOR(j,l+num/2-1,l){a[j]=now++;GROUP[j]=i;}//构造方案1
//rFOR(j,l+num-1,l+num/2){a[j]=now++;GROUP[j]=i;}
FOR(j,l+num/2,l+num-1){a[j]=now++;GROUP[j]=gruop;}//构造方案2
FOR(j,l,l+num/2-1){a[j]=now++;GROUP[j]=gruop;}
f(f,l+num,gruop+1);
};
f(f,1,1);
FOR(i,1,n)cout<<a[i]<<" ";
cout<<ET<<cnt<<ET;
FOR(i,1,n)cout<<GROUP[i]<<" ";
cout<<ET;
}
附录
这里贴上头部定义和main函数部分:
#include<iostream>
#include<vector>
#include<bits\stdc++.h>
#define ll long long
#define ld long double
using namespace std;
#define ET '\n'
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
#define CIN(a) ll a;cin>>a
#define DCIN(a) ld a;cin>>a
#define CA cout<<ans<<ET
#define CY cout<<"YES"<<ET
#define CN cout<<"NO"<<ET
//没有C++20就不能用ranges了
//#define PP(l,r,CK) *ranges::partition_point(ranges::iota_view((l),(r)+1),(CK))
string ANS[2]={"No\n","Yes\n"};
//solve函数代码
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//pre();
CIN(t);while(t--)
solve();
return 0;
}