Educational Codeforces Round 94 (Rated for Div. 2)

A

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e5 + 5;
 
int n, m, _, k;
 
int main() {
    IO;
    for (cin >> _; _; --_) {
        string s, t = ""; cin >> n >> s;
        for (int i = 0; i < n; ++i) {
            int j = 0;
            while (j < t.size() && t[j] != s[i + j]) ++j;
            if (j < t.size()) continue;
            t += s[i + j]; 
        }
        while (t.size() < n) t += '0';
        cout << t << '
';
    }
    return 0;
}

C

s先全部为1, 然后按照t的0去改s

在判断一遍, 改后的s, 是否是的t的1正确, 不正确就-1

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
 
const int N = 1e5 + 5;
 
int n, m, _, k;
char s[N], t[N];
 
int main() {
    IO;
    for (cin >> _; _; --_) {
        cin >> s + 1 >> m;
        for (n = 1; s[n]; ++n) t[n] = '1';
        t[n--] = '';
 
        bool f = 1;
        rep (i, 1, n) {
            if (s[i] == '0'){
                if (i > m) t[i - m] = '0';
                if (i + m <= n) t[i + m] = '0';
            } 
        }
 
        rep (i, 1, n) 
            if (s[i] == '1') {
                if (i > m && t[i - m] == '1') continue;
                else if (i + m <= n && t[i + m] == '1') continue;
                else { f = 0; break; }
            }
 
        if (f) cout << t + 1 << '
';
        else cout << -1 << '
';
    }
    return 0;
}

B

搞什么贪心, 直接暴力

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
 
const int N = 4e5 + 5;
 
int n, m, _, k;
int x, y, a, b;
 
int main() {
    IO;
    for (cin >> _; _; --_) {
        cin >> n >> m >> x >> y >> a >> b;
        int ans = 0;
        if (a > b) swap(a, b), swap(y, x);
        if (n / a + m / a <= x) { cout << n / a + m / a << '
'; continue; }
        rep (i, 0, x) {
            if (m - (x - i) * a < 0) continue;
            if (n - i * a < 0) break;
            ans = max(ans, min((n - i * a) / b + (m - (x - i) * a) / b, y) + x);
        }
        cout << ans << '
';
    }
    return 0;
}

D

ABAB, 型, 那直接把每两个位置拼成一个数, 直接每次找有多少AB就行

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
 
const int N = 3e3 + 5;
 
int n, m, _, k;
int a[N], tax[N * N];
 
int main() {
    IO;
    for (cin >> _; _; --_) {
        cin >> n;
        memset(tax, 0, sizeof tax);
        rep (i, 1, n) cin >> a[i], --a[i];
        ll ans = 0;
        rep (i, 1, n) {
            rep (j, 1, i - 1) ++tax[a[j] * n + a[i]];
 
            rep (j, i + 2, n) ans += tax[a[i + 1] * n + a[j]];
        }
        cout << ans << '
';
    }
    return 0;
}

E

原题