临时交题账号

• DAI33
• 3301akioi

425C - Rotate and Sum Query

https://atcoder.jp/contests/abc425/tasks/abc425_c

给你一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 。

请按顺序处理 $Q$ 个查询。查询有两种类型，格式如下：

• 1 c:执行将 $A$ 的第一个元素移动到结尾 $c$ 次的操作。
• 2 l r：输出 $\displaystyle \sum_{i=l}^r A_i$ 的值。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, nn, q;
int a[200000 * 2 + 5];
int sum[200000 * 2 + 5];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i + n] = a[i]; // 破环为链
    }

    // 前缀和
    nn = n * 2;
    for (int i = 1; i <= nn; i++)
        sum[i] = sum[i - 1] + a[i];

    int cc = 0; // 累积移动次数
    while (q--)
    {
        int op, c, l, r;
        cin >> op;
        if (op == 1)
        {
            cin >> c;
            cc = (cc + c) % n;
        }
        if (op == 2)
        {
            cin >> l >> r;
            // a[cc+1]~a[n] a[1]~a[cc]
            // 求上面这个数组的第 l 项到第 r 项的区间和
            // 即破环为链后的第 cc+l ~ cc+r 项
            cout << sum[cc + r] - sum[cc + l - 1] << "\n";
        }
    }

    return 0;
}

425B - Find Permutation 2

https://atcoder.jp/contests/abc425/tasks/abc425_b

给你一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 。这里， $A$ 的每个元素要么是 $-1$ ，要么是介于 $1$ 和 $N$ 之间的整数。

判断是否存在长度为 $N$ 的整数序列 $P=(P_1,P_2,\ldots,P_N)$ 且满足以下所有条件，如果存在，请找出一个。

• $P$ 是 $(1,2,\ldots,N)$ 的排列。
• 对于 $i=1,2,\ldots,N$ , 如果 $A_i \neq -1$ , 那么 $P_i=A_i$ 成立。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[15];
bool vis[15]; // vis[i] 标记 i 是否出现过了
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == -1)
            continue;
        if (vis[a[i]])
        {
            cout << "No\n";
            return 0;
        }
        vis[a[i]] = true;
    }
    cout << "Yes\n";
    int now = 1; // 下一个考虑的数
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != -1)
            cout << a[i] << " ";
        else
        {
            // 把 now 挪到下一个没出现过的数上
            while (vis[now])
                now++;
            vis[now] = true;
            cout << now << " ";
        }
    }
    return 0;
}

425A - Sigma Cubes

https://atcoder.jp/contests/abc425/tasks/abc425_a

给你一个正整数 $N$ 。

对于 $i=1,2,\ldots,N$ ，计算 $(-1)^i \times i^3$ 并求出这 $N$ 个数之和。

即求出 $\displaystyle \sum_{i=1}^N (-1)^i \times i^3$ 。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int now = 1;
        if (i % 2 == 1)
            now *= -1;
        now *= (i * i * i);
        ans += now;
    }
    cout << ans;
    return 0;
}

426C - Upgrade Required

https://atcoder.jp/contests/abc426/tasks/abc426_c

某操作系统有 $N$ 个版本，按时间顺序编号为 $1,2,\dots,N$ 。
共有 $N$ 台个人电脑。个人电脑，而最初 $i$ （一台）个人电脑的操作系统版本是 $i$ 。

按顺序执行 $Q$ 个操作。第 $i$ 次操作如下：

• 将当前操作系统版本为 $X_i$ 或更早的所有 PC 升级到版本 $Y_i(\gt X_i)$ 。然后，打印在此操作中升级的 PC 数量。

请注意，对于 $i\lt Q$ ，在执行第 $(i+1)$ 次操作之前，要先执行第 $i$ 次h操作的升级。

#include <bits/stdc++.h>
using namespace std;
int n, q;
// a[i] 记录版本为 i 的电脑有几台
int a[1000000 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        a[i] = 1;
    int minTyp = 1;
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        int ans = 0;
        for (int i = minTyp; i <= x; i++)
        {
            // 所有版本为 i 的电脑都升级到了 y
            ans += a[i];
            a[y] += a[i];
            a[i] = 0;
        }
        minTyp = max(minTyp, x + 1);
        cout << ans << "\n";
    }
    return 0;
}

426B - The Odd One Out

https://atcoder.jp/contests/abc426/tasks/abc426_b

给你一个长度至少为 $3$ 的字符串 $S$ ，由小写英文字母组成。

其中 $S$ 包含恰好两种类型的字符，而恰好有一个字符与其他字符不同。请找出这一个字符。

例如，如果 $S$ 是 "odd"，则报告 "o"。

426A - OS Versions

https://atcoder.jp/contests/abc426/tasks/abc426_a

某操作系统的版本按时间顺序排列为 "Ocelot"、"Serval"、"Lynx"。
请判断版本 $X$ 与版本 $Y$ 是否相同或更新。

427A - ABC -> AC

https://atcoder.jp/contests/abc427/tasks/abc427_a

给你一个由大写英文字母组成的字符串 $S$ 。这里， $S$ 的长度是奇数。

请打印删除 $S$ 中间字符后得到的字符串。 $S$ 的中间字符是 $S$ 的 $\frac{L+1}{2}$ -th 字符，其中 $L$ 是 $S$ 的长度。

427C - Bipartize

https://atcoder.jp/contests/abc427/tasks/abc427_c

有一个简单的无向图，该图有 $N$ 个顶点和 $M$ 条边。该图由顶点 $1,$ 顶点 $2,\ldots,$ 顶点 $N$ 和连接顶点 $u_i$ 和 $v_i$ 的第 $i$ 条边 $(1\le i\le M)$ 组成。

您将执行以下操作零次或多次：

• 选择一条尚未删除的边并删除它。

您的目标是使图形成为二分图。找出使操作后的图形成为两部分所需的最少操作次数。

什么是二分图？

二方图是指每个顶点都可以涂成黑色或白色，并满足以下条件的图：

• 对于每一条边，由该边连接的两个顶点具有不同的颜色。

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, int> e[50];
int ans; // 最少删几条边
// 考虑到了第 now 个点
int col[15]; // 每个点染的颜色
void dfs(int now)
{
    if (now > n)
    {
        // 1~n 号点的颜色都考虑完了
        // 计算当前分组情况下的最少删除边数
        int cnt = 0; // 删几条
        for (int i = 1; i <= m; i++)
            if (col[e[i].first] == col[e[i].second])
                cnt++;
        ans = min(ans, cnt);
        return;
    }
    col[now] = 1;
    dfs(now + 1);
    col[now] = 0;
    dfs(now + 1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].first >> e[i].second;
    ans = m;
    dfs(1);
    cout << ans;
    return 0;
}