Codeforces Round 913 (Div. 3)

div3 两题 新纪录..

我再也不喝完酒打cf了

A. Rook

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;

int board[10][10];

void solve(){
    string s;
    cin>>s;
    int x=s[0] - 'a' + 1;
    int y=s[1] - '0';
    for(int i=1;i<=8;i++){
        if(i!=y) cout<<s[0]<<i<<endl;
    }
    for(char c='a';c<='h';c++){
        if(c!=s[0]) cout<<c<<s[1]<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

B. YetnotherrokenKeoard

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;

int board[10][10];

void solve(){
    string s;
    cin>>s;
    deque<pair<int,char>> path1,path2;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='b')
        {
            if(path1.size()) path1.pop_back();
        }
        else if(s[i]=='B')
        {
            if(path2.size()) path2.pop_back();
        }
        else if(s[i]>='a'&&s[i]<='z') path1.push_back({i,s[i]});
        else if(s[i]>='A'&&s[i]<='Z') path2.push_back({i,s[i]});
    }
    while(path1.size()&&path2.size())
    {
        if(path1.front().first<path2.front().first)
        {
            cout<<path1.front().second;
            path1.pop_front();
        }else
        {
            cout<<path2.front().second;
            path2.pop_front();
        }
    }
    while(path1.size()){
            cout<<path1.front().second;
            path1.pop_front();
    }
    while(path2.size()){
            cout<<path2.front().second;
            path2.pop_front();
    }
    cout<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

C. Removal of Unattractive Pairs

如果所有字符的数量都<=n/2，那么就一定可以两两消到最后。

否则就尽量消数量最多的字符

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
int cnt[26];
void solve(){
    memset(cnt,0,sizeof cnt);
    int n;
    string s;
    cin>>n>>s;
    for(int i=0;i<n;i++) cnt[s[i]-'a']++;
    int x=*max_element(cnt,cnt+26);
    if(x<=n/2) cout<<n%2<<endl;
    else       cout<<x*2-n<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

D. Jumping Through Segments

这题写的时候还看错题目了，搞得以为很难，

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
int ll[N],rr[N];
int n;

bool check(int mid){
    int l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        l = max(l-mid , 0ll);
        r = r + mid;
        if(ll[i]>r||rr[i]<l) return false;
        l = max(l,ll[i]);
        r = min(r,rr[i]);
    }
    return true;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>ll[i]>>rr[i];
    int l=0,r=1e18;
    int ans=1e18;
    while(l<=r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid - 1 , ans = mid;
        else           l = mid + 1;
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

E. Good Triples

这题的核心是要发现每一位都是单独独立的。不能有进位 如5+5+10=20 （5）+（5）+（1）+（0）=6 （2）+（0）= 2 5+5进位后右边只加了1。显然不能有进位。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int cnt[20];

void solve(){
    memset(cnt,0,sizeof cnt);
    for(int i=0;i<10;i++)
        for(int k=0;k+i<10;k++)
            for(int j=0;j+k+i<10;j++)
                cnt[i+k+j]++;
    int n;
    cin>>n;
    string s=to_string(n);
    int ans=1;
    for(int i=0;i<s.size();i++)
    {
        ans*=cnt[s[i]-'0'];
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

F. Shift and Reverse

将链变环，如果有一个点往后递增序列的长度为n，这个点就是起点。找到这个起点，然后暴力求两个解.

自己的码搓的太狗屎了，看看佬的码吧。

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int INF = 1e9;
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n * 2);
        for(int i = 0; i < n; i++) 
            cin >> a[i], a[i + n] = a[i];
    
        int ans = INF;
        for(int i = 0; i < n; i++){
            int j = i;
            while(j + 1 < 2 * n && a[j + 1] >= a[j]) j++;
            for(int k = i; k <= j && k < n; k++){
                int len = j - k + 1;
                if (len >= n){
                    ans = min(ans, (n - k) % n);
                    int rev = n - 1 - k;
                    ans = min(ans, n - 1 - rev + 2);
                }
            }
            i = j;
        }
        for(int i = 0; i < n; i++){
            int j = i;
            while(j + 1 < 2 * n && a[j + 1] <= a[j]) j++;
            for(int k = i; k <= j && k < n; k++){
                int len = j - k + 1;
                if (len >= n){
                    ans = min(ans, (n - k) % n + 1);
                    int rev = n - 1 - k;
                    ans = min(ans, n - 1 - rev + 1);
                }
            }
            i = j;
        }
        if (ans > INF / 2) ans = -1;
        cout << ans << '\n';
    }

}

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;
int a[N] , du[N];
bool vis[N] , light[N] ,used[N];
int n;

void solve(){
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        light[i+1] = (s[i]=='1');
        vis[i+1]=false;
        used[i+1]=false;
        du[i+1]=0;
    }

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        du[a[i]]++;
    }

    queue<int> path;
    for(int i=1;i<=n;i++)
        if(!du[i]) path.push(i);
    vector<int> ans;
    while(path.size()){
        int u=path.front();path.pop();
        if(light[u]){
            light[u]    ^= 1;
            light[a[u]] ^= 1;
            vis[u] = true;
            ans.push_back(u);
        }
        if(--du[a[u]]==0) path.push(a[u]);
    }

    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&du[i]){
            int u=0;
            vector<vector<int>> que(2);
            for(int j=i;!used[j];j=a[j])
            {
                u ^= (light[j]==1);
                que[u].push_back(j);
                used[j] = true;
            }
            if(u){
                cout<<-1<<endl;
                return;
            }
            if(que[0].size()<que[1].size()){
                for(auto x:que[0]){
                    vis[x] = true;
                    ans.push_back(x);
                }
            }else{
                for(auto x:que[1]){
                    vis[x] = true;
                    ans.push_back(x);
                }
            }
            // break 没明白为什么这里不能break
        }
    }
    cout<<ans.size()<<endl;
    for(auto u:ans) cout<<u<<" ";
    cout<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• Hey left 1 Codeforces Round 918 (Div. 4)
• vue3 获取循环的div的总宽度
• CodeForces 1312G Autocompletion
• Educational Codeforces Round 152 (Rated for Div. 2)
• codeforces 918 div4
• div滚动加载数据
• CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP
• CodeForces 1329D Dreamoon Likes Strings
• CodeForces 1237H Balanced Reversals

Codeforces Round 913 Divcodeforces round 913 div codeforces round 911 div codeforces round 864 div codeforces round 887 div codeforces round 863 div codeforces round 915 div codeforces round 917 div codeforces round 912 div codeforces round 888 div codeforces round 901 div