Codeforces Round #828 (Div. 3) A-F

比赛链接

A

题解

知识点：贪心，模拟。

遇到没用过的数字就给个字母，遇到用过的数字就对照字母是否一致。

时间复杂度 O(n)

空间复杂度 O(n)

代码

#include 
#define ll long long
 
using namespace std;
 
int a[57];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    string s;
    cin >> s;
    s = "?" + s;
    map<int, char> vis;
    for (int i = 1;i <= n;i++) {
        if (!vis.count(a[i])) vis[a[i]] = s[i] - 'a';
        if (vis[a[i]] != s[i] - 'a') return false;
    }
    cout << "YES" << '\n';
    return true;
}
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << "NO" << '\n';
    }
    return 0;
}

B

题解

知识点：数学，模拟。

记录奇数数量，每次模拟一下变化即可。

时间复杂度 O(n+q)

空间复杂度 O(1)

代码

#include 
#define ll long long
 
using namespace std;
 
bool solve() {
    int n, q;
    cin >> n >> q;
    ll sum = 0;
    int cnt1 = 0;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        sum += x;
        if (x & 1) cnt1++;
    }
    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 0) {
            sum += 1LL * (n - cnt1) * x;
            if (x & 1) cnt1 = n;
        }
        else {
            sum += 1LL * cnt1 * x;
            if (x & 1) cnt1 = 0;
        }
        cout << sum << '\n';
    }
    return true;
}
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

题解

知识点：枚举，模拟。

last 存当前位置右边第一个绿灯。把 s 复制一遍到后面，方便最后一个绿灯的后面一段也能被算到。

时间复杂度 O(n)

空间复杂度 O(n)

代码

#include 
#define ll long long
 
using namespace std;
 
bool solve() {
    int n;
    char ch;
    cin >> n >> ch;
    string s;
    cin >> s;
    s = "?" + s + s;
    int last = 0;
    int ans = 0;
    for (int i = 2 * n;i >= 1;i--) {
        if (s[i] == 'g') last = i;
        else if (s[i] == ch) ans = max(ans, last - i);
    }
    cout << ans << '\n';
    return true;
}
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

题解

知识点：数论，贪心。

先把原来数字的 2 因子个数加到 sum 。然后再把 [1,n] 的每个数的 2 因子存起来，贪心地从大到小拿，这样次数最小，直到 sum 超过 n 或取完所有数字。最后小于 n 则 −1 ，否则输出操作次数。

时间复杂度 O(nlogn)

空间复杂度 O(n)

代码

#include 
#define ll long long
 
using namespace std;
 
bool solve() {
    int n;
    cin >> n;
    int sum = 0;
    vector<int> tb2;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        while (x % 2 == 0) sum++, x /= 2;
        x = i;
        int idx = 0;
        while (x % 2 == 0) idx++, x /= 2;
        if (idx) tb2.push_back(idx);
    }
    sort(tb2.begin(), tb2.end(), [&](int a, int b) {return a > b;});
    int cnt = 0;
    for (auto x : tb2) {
        if (sum >= n) break;
        sum += x;
        cnt++;
    }
    if (sum < n) return false;
    else cout << cnt << '\n';
    return true;
}
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

E

题解

知识点：dfs，数论，分解质因数。

题目要求找到 x∈(a,c],y∈(b,d] 满足 a⋅b|x⋅y 。

显然 x,y 需要分摊到 a⋅b 的所有质因子，即 x,y 一定是 a⋅b 两个成对因子 f1,f2 的倍数。

注意到 1018 内的数，因子数最多有 103680 个 ；109 内的数，因子数最多有 1344 个。因此，我们不妨先枚举 x 可能分摊到的因子 f1(f1≤c) ，同时可以求出另一个因子 f2(f2≤d)，最后将他们分别加倍到比 a 和 b 大，最终检验一下是否还在区间即可。

时间复杂度 O(105)

空间复杂度 O(105)

代码

#include 
#define ll long long
 
using namespace std;
 
int cnt;
bool vis[100007];
int prime[100007];
void euler_screen(int n) {
    for (int i = 2;i <= n;i++) {
        if (!vis[i]) prime[++cnt] = i;
        for (int j = 1;j <= cnt && i * prime[j] <= n;j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
 
int a, b, c, d;
vector<pair<int, int>> fd;
ll val;
vector<int> af;
 
void dfs(int step, ll mul) {
    if (mul > c) return;
    if (step == fd.size()) {
        if (val / mul <= d) af.push_back(mul);
        return;
    }
    for (int i = 0;i <= fd[step].second;i++) {
        dfs(step + 1, mul);
        mul *= fd[step].first;
    }
}
 
bool solve() {
    cin >> a >> b >> c >> d;
    map<int, int> mp;
    int tt = a;
    for (int i = 1;prime[i] * prime[i] <= tt;i++) {
        while (tt % prime[i] == 0) mp[prime[i]]++, tt /= prime[i];
    }
    if (tt > 1) mp[tt]++;
    tt = b;
    for (int i = 1;prime[i] * prime[i] <= tt;i++) {
        while (tt % prime[i] == 0) mp[prime[i]]++, tt /= prime[i];
    }
    if (tt > 1) mp[tt]++;
    fd.clear();
    for (auto [x, y] : mp) fd.push_back({ x,y });
    af.clear();
    val = 1LL * a * b;
    dfs(0, 1);
    int ansx = -1, ansy = -1;
    for (auto x : af) {
        int y = val / x;
        x = (a / x + 1) * x;
        y = (b / y + 1) * y;
        if (x <= c && y <= d) {
            ansx = x;
            ansy = y;
            break;
        }
    }
    cout << ansx << ' ' << ansy << '\n';
    return 1;
}
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    euler_screen(100001);
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

F

题解

知识点：枚举，双指针，数学。

尝试从小到大枚举 x∈[1,n] ，计算满足 med(l,r)<mex(l,r)=x 的段的个数（ x=0 显然没有满足的）。

首先，对于一段 [l,r] 满足 mex(l,r)=x 一定包括了 [0,x−1] 的数字。因此，当且仅当段长度 r−l+1≤2x 才满足中位数 med(l,r)<mex(l,r)=x ，否则必然包括 >x 的数字。

假设要求 mex(l,r)=x ，先得到满足 mex(l,r)=x 的最小段 [l,r] ，随后找到 x+1 的位置 pos （假设 pos 在 [l,r] 外，在里面就不存在这个 mex 了qwq）。

不妨设 pos>r ，只要不包括 pos 这个位置，其他从 [l,r] 扩展的段的 mex 一定是 x ，因此可以枚举 [r,pos) 的每个位置作为右端点 i， 找到最远左端点 j=max ，随后每次可以得到 \max(0,l-i+1) 个合法段。同理可以求 pos 的情况。

我们可以从 mex(l,r) = 1 开始枚举，显然 l = pos[0],r = pos[0] 。

时间复杂度 O(n)

空间复杂度 O(n)

代码

#include 
#define ll long long
 
using namespace std;
 
int p[200007], pos[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 0;i <= n;i++) pos[i] = 0;
    for (int i = 1;i <= n;i++) cin >> p[i], pos[p[i]] = i;
    int l = pos[0], r = pos[0];
    ll ans = 0;
    for (int x = 1;x <= n;x++) {
        if (l <= pos[x] && pos[x] <= r) continue;//目标mex被之前的mex段包括了，说明这个mex不会出现
        int len = 2 * x;//一个mex>med段的最长长度是2mex
        if (pos[x] > r) {//段mex在右侧
            for (int i = r;i < pos[x];i++) {
                int j = max(1, i - len + 1);//长度限制内，左端点可以到哪
                ans += max(0, l - j + 1);
            }
        }
        else {
            for (int i = l;i > pos[x];i--) {
                int j = min(n, i + len - 1);
                ans += max(0, j - r + 1);
            }
        }
        l = min(pos[x], l);
        r = max(pos[x], r);
    }
    cout << ans << '\n';
    return true;
}
 
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}