Codeforces Round 898 (Div. 4)

A Short Sort

直接枚举许所有情况即可

/*
 * ==================================================================================
 * Author:  north_h
 * Time:    2023-09-21 22:35:49
 *
 * Problem: A. Short Sort
 * Contest: Codeforces - Codeforces Round 898 (Div. 4)
 * URL:     https://codeforces.com/contest/1873/problem/A
 * MemoryL: 256 MB
 * TimeL:   1000 ms
 * ==================================================================================
 */

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define PSI pair<string,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define int128 __int128
#define endl '\n'
#define lcm(x,y) x*y/__gcd(x,y)
#define debug(a,b) cout << (steing)a << '=' << b << endl;
const double PI = 3.1415926;
const int N = 10010;
const int M = 1910;
const int MOD = 998244353;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    string s;
    cin >> s;
    if(s == "abc" || s == "acb" || s == "bac" || s == "cba")cout << "YES" << endl;
    else cout << "NO" << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

B Good Kid

贪心，最优的情况就是加到最小的数上

/*
 * ==================================================================================
 * Author:  north_h
 * Time:    2023-09-21 22:35:53
 *
 * Problem: B. Good Kid
 * Contest: Codeforces - Codeforces Round 898 (Div. 4)
 * URL:     https://codeforces.com/contest/1873/problem/B
 * MemoryL: 256 MB
 * TimeL:   1000 ms
 * ==================================================================================
 */

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define PSI pair<string,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define int128 __int128
#define endl '\n'
#define lcm(x,y) x*y/__gcd(x,y)
#define debug(a,b) cout << (steing)a << '=' << b << endl;
const double PI = 3.1415926;
const int N = 10010;
const int M = 1910;
const int MOD = 998244353;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    int n;
    cin >> n;
    int mn = INT_MAX;
    bool ok = false;
    vector<int> a(n);
    for(int i = 0, x; i < n; i++) {
        cin >> a[i];
    }
    sort(ALL(a));
    a[0]++;
    ll sum = 1;
    for(auto i : a)sum *= i;
    cout << sum << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

C Target Practice

我其实写复杂了，直接手动构造一个靶子即可

/*
 * ==================================================================================
 * Author:  north_h
 * Time:    2023-09-21 22:35:57
 *
 * Problem: C. Target Practice
 * Contest: Codeforces - Codeforces Round 898 (Div. 4)
 * URL:     https://codeforces.com/contest/1873/problem/C
 * MemoryL: 256 MB
 * TimeL:   1000 ms
 * ==================================================================================
 */

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define PSI pair<string,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define int128 __int128
#define endl '\n'
#define lcm(x,y) x*y/__gcd(x,y)
#define debug(a,b) cout << (steing)a << '=' << b << endl;
const double PI = 3.1415926;
const int N = 10010;
const int M = 1910;
const int MOD = 998244353;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    vector<string> g(11);
    for(int i = 0; i < 10; i++) {
        cin >> g[i];
    }
    // for(int i = 0; i < 10; i++) {
    //     cout << g[i] << endl;;
    // }
    int ans = 0;
    int cnt = 0;
    for(int i = 0, x = 0; i < 5; i++, x++) {
        for(int j = x; j < 10 - x; j++) {
            if(g[i][j] == 'X') {
                ans += i + 1;
                cnt++;
                g[i][j] = '.';
            }
        }
    }
    // for(int i = 0; i < 10; i++) {
    //     cout << g[i] << endl;;
    // }
    for(int i = 9, x = 0; i >= 5; i--, x++) {
        for(int j = x; j < 10 - x; j++) {
            if(g[i][j] == 'X') {
                ans += (10 - i);
                cnt++;
                g[i][j] = '.';
            }
        }
    }
    // for(int i = 0; i < 10; i++) {
    //     cout << g[i] << endl;;
    // }
    for(int i = 0, x = 0; i < 5; i++, x++) {
        for(int j = x; j < 10 - x; j++) {
            if(g[j][i] == 'X') {
                ans += i + 1;
                cnt++;
                g[j][i] = '.';
            }
        }
    }
    // for(int i = 0; i < 10; i++) {
    //     cout << g[i] << endl;;
    // }
    for(int i = 9, x = 0; i >= 5; i--, x++) {
        for(int j = x; j < 10 - x; j++) {
            if(g[j][i] == 'X') {
                ans += (10 - i);
                cnt++;
                g[j][i] = '.';
            }
        }
    }
    // for(int i = 0; i < 10; i++) {
    //     cout << g[i] << endl;;
    // }
    // cout << cnt << endl;
    cout << ans << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

D 1D Eraser

也是贪心，从前往后找，只要出现黑色，就跳k格，记录跳的次数就行

/*
 * ==================================================================================
 * Author:  north_h
 * Time:    2023-09-21 22:36:01
 *
 * Problem: D. 1D Eraser
 * Contest: Codeforces - Codeforces Round 898 (Div. 4)
 * URL:     https://codeforces.com/contest/1873/problem/D
 * MemoryL: 256 MB
 * TimeL:   1000 ms
 * ==================================================================================
 */

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define PSI pair<string,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define int128 __int128
#define endl '\n'
#define lcm(x,y) x*y/__gcd(x,y)
#define debug(a,b) cout << (steing)a << '=' << b << endl;
const double PI = 3.1415926;
const int N = 10010;
const int M = 1910;
const int MOD = 998244353;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'B') {
            i += k - 1;
            ans++;
        }
    }
    cout << ans << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

E Building an Aquarium

经典的二分答案，但要特别注意上界的值，因为这个WA了五发，上界最多会到2e9

/*
 * ==================================================================================
 * Author:  north_h
 * Time:    2023-09-21 22:36:06
 *
 * Problem: E. Building an Aquarium
 * Contest: Codeforces - Codeforces Round 898 (Div. 4)
 * URL:     https://codeforces.com/contest/1873/problem/E
 * MemoryL: 256 MB
 * TimeL:   2000 ms
 * ==================================================================================
 */

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define PSI pair<string,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define int128 __int128
#define endl '\n'
#define lcm(x,y) x*y/__gcd(x,y)
#define debug(a,b) cout << (steing)a << '=' << b << endl;
const double PI = 3.1415926;
const int N = 10010;
const int M = 1910;
const int MOD = 998244353;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    int n, x;
    cin >> n >> x;
    // cout << x << endl;
    vector<int> a(n);
    for(auto &i : a)cin >> i;
    auto check = [&](int mid) {
        int res = 0;
        for(auto i : a) {
            res += max(0ll, mid - i);
        }
        // cout << res << "----" << endl;;
        return res <= x;
    };
    int l = 0, r = 2e9, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        // cout << l << ' ' << r << endl;
        if(check(mid))l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    cout << max(ans, 1ll) << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

F Money Trees

二分或者双指针都行，现预处理每个位置最多可以延申到多远的距离，然后去枚举\(l\)，二分\(r\)就行，并且实时更新答案

/*
 * ==================================================================================
 * Author:  north_h
 * Time:    2023-09-21 22:36:10
 *
 * Problem: F. Money Trees
 * Contest: Codeforces - Codeforces Round 898 (Div. 4)
 * URL:     https://codeforces.com/contest/1873/problem/F
 * MemoryL: 256 MB
 * TimeL:   2000 ms
 * ==================================================================================
 */

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define PSI pair<string,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define int128 __int128
#define endl '\n'
#define lcm(x,y) x*y/__gcd(x,y)
#define debug(a,b) cout << (steing)a << '=' << b << endl;
const double PI = 3.1415926;
const int N = 10010;
const int M = 1910;
const int MOD = 998244353;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), b(n + 1), pmax(n + 1), s(n + 1);
    for(int i = 1; i <= n; i++)cin >> a[i], s[i] = s[i - 1] + a[i];
    for(int i = 1; i <= n; i++)cin >> b[i];
    for(int i = 1; i <= n; i++)pmax[i] = i;
    for(int i = n; i > 1; i--) {
        if(b[i - 1] % b[i] == 0)pmax[i - 1] = pmax[i];
    }
    int res = 0;
    for(int i = 1; i <= n; i++) {
        int l = i, r = pmax[i], ans = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            if(s[mid] - s[i - 1] <= k)l = mid + 1, ans = mid;
            else r = mid - 1;
        }
        res = max(res, ans - i + 1);
    }
    cout << res << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

G ABBC or BACB

其实我感觉最简单的方法就是先把\(A\)合并成一堆，每个\(B\)都单独放一堆，贪心，最有的方法就是一个\(B\)和一堆\(A\)配对，如果\(B\)的个数时大于等于\(A\)的堆数时答案就是\(A\)的个数，否则答案就是\(A\)的个数减去个数最小的那一堆

/*
 * ==================================================================================
 * Author:  north_h
 * Time:    2023-09-21 22:36:14
 *
 * Problem: G. ABBC or BACB
 * Contest: Codeforces - Codeforces Round 898 (Div. 4)
 * URL:     https://codeforces.com/contest/1873/problem/G
 * MemoryL: 256 MB
 * TimeL:   1000 ms
 * ==================================================================================
 */

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a, b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define PSI pair<string,int>
#define ALL(a) a.begin(),a.end()
#define rALL(a) a.rbegin(),a.rend()
#define int128 __int128
#define endl '\n'
#define lcm(x,y) x*y/__gcd(x,y)
#define debug(a,b) cout << (string)a << '=' << b << endl;
const double PI = 3.1415926;
const int N = 10010;
const int M = 1910;
const int MOD = 998244353;
const double EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace std;

void solve() {
    string s;
    cin >> s;
    vector<int> a, b;
    int cnt = 0;
    for(auto i : s) {
        if(i == 'A')cnt++;
        else {
            if(cnt)a.push_back(cnt);
            cnt = 0;
        }
    }
    if(cnt)a.push_back(cnt);
    for(auto i : s) {
        if(i == 'B')b.push_back(1);
    }
    sort(ALL(a));
    int ans = 0;
    for(auto i : a)ans += i;
    if(b.size() == 0 || a.size() == 0)cout << 0 << endl;
    else if(b.size() < a.size())cout << ans - a[0] << endl;
    else cout << ans << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    cin >> h_h;
    while (h_h--)solve();
    return 0;
}

H Mad City

本栏目推荐文章
• 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 898 Divcodeforces round 898 div codeforces round 898 a-h codeforces round 911 div codeforces round 864 div codeforces round 913 div codeforces round 887 div codeforces round 863 div codeforces round 915 div codeforces round 912 div codeforces round 888 div