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即可，推导一下也行，但是脑子不够快的话就不要把时间花在推式子上了。$\text{\color{#ff0000}{写BFS和DFS记得剪枝！！！！}}$

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?

暴力即可，但是记得别暴力过头了，$n=3000$ 的数据不是给你开 $O(n^3)$ 的算法用的。记得优化一下。

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，你看不到它”

题意是给定 $n$ 和 $k$ ，要求构造一个排列，使完全联通块数量尽可能少，也就是要求尽可能连边

分析核心式子 $|i - j| + |a_i - a_j| \le k$，考虑 $1$ 到 $k+1$， $k+1$ 和 $1$ 已经在下标上相差 $k$ 了，再加上数值上的相差，必然不可能连边，所以每个联通块最大为 $k$。因此分组关系的答案应该是 $k$ 个 $1$，$k$ 个 $2$，…，$k$ 个 $n$，$k’$ 个 $n+1$ 的形式（其中 $k’\le k$）

再来考虑如何构造每个组，对于一个组，他的序号是没法改的，所以要使每个组的成员均两两满足式子，先考查 $|i-j|$ 的规律，取极限情况，首项和尾项，得到差值为 $k-1$，然后一步步往中间跳，差值会逐渐缩小。因此 $a_i$ 的选取应当满足：取首项和尾项时相差最小，往中间一步步跳的时候，差值逐渐增大。

所以每个组(偶数情况)，构造：$\frac{n}{2},\frac{n}{2}-1,\frac{n}{2}-2,\dots,1,n,n-1,\dots,\frac{n}{2}+1$ 即可。

当然你反过来构造：$\frac{n}{2},\frac{n}{2}+1,\frac{n}{2}+2,\dots,n,1,2,\dots,\frac{n}{2}-1$ 也行。

考虑奇数情况，易知如上构造也符合题意，让正中间的元素最大即可。

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;
}