A

题解

知识点：贪心，模拟。

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

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

#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 <bits/stdc++.h>

#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 <bits/stdc++.h>

#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(n \log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

#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 \in (a,c],y \in (b,d]\) 满足 \(a\cdot b | x \cdot y\) 。

显然 \(x,y\) 需要分摊到 \(a\cdot b\) 的所有质因子，即 \(x,y\) 一定是 \(a\cdot b\) 两个成对因子 \(f_1,f_2\) 的倍数。

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

时间复杂度 \(O(10^5)\)

空间复杂度 \(O(10^5)\)

代码

#include <bits/stdc++.h>

#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 \in [1,n]\) ，计算满足 \(med(l,r) < mex(l,r) = x\) 的段的个数（ \(x = 0\) 显然没有满足的）。

首先，对于一段 \([l,r]\) 满足 \(mex(l,r) = x\) 一定包括了 \([0,x-1]\) 的数字。因此，当且仅当段长度 \(r-l+1 \leq 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(1,i-2x+1)\) ，随后每次可以得到 \(\max(0,l-i+1)\) 个合法段。同理可以求 \(pos<l\) 的情况。

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

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

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

}

巴特西

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

A

题解

代码

B

题解

代码

C

题解

代码

D

题解

代码

E

题解

代码

F

题解

代码

最新文章

热门文章