牛客多校1

按照难度梯度来补题目

设计的难度梯度大概是
CH A BDI FJ EG K

C Sum of Suffix Sums

给定一个初始为空的数组，需要执行 $q$ 次操作：

给定两个非负整数 $t$ 和 $v$ ，从数组末尾取出元素 $t$ 次，然后将 $v$ 追加到数组末尾。在此操作之前，保证 $t$ 不超过数组的长度。

每次操作后，设 $a_{1}, a_{2}, \dots, a_{n}$ 为当前数组，求出 $s_{1}, s_{2}, \dots, s_{n}$ 的和，其中 $s_{i} = a_{i} + a_{i + 1} + \dots + a_{n}$ 为从位置 $i$ 开始的后缀之和。

由于答案可能非常大，因此输出它们的模 $10^{9} + 7$ 。

Solution

根据题目意思，容易知道：需要求的值为 $\sum s_{i} = \sum_{i = 1}^{n} i \times a_{i}$

关键在于取出元素的操作。

坑点：

模数减去的时候只是加上一个 mod 都不一定够，所以还要套一层

#define int long long
constexpr int mod = 1e9 + 7;
int a[500010];
void solve() {
    int q;cin >> q;
    int tt = 0, ans = 0;
    while (q--) {
        int t, v;cin >> t >> v;
        for (int cnt = 0;cnt != t;tt--)ans = ((ans - a[tt] + mod) % mod + mod) % mod, cnt++;
        a[++tt] = tt * v;
        ans += a[tt];ans %= mod;
        cout << ans << '\n';
    }
}

H World Finals

国际乒联世界总决赛即将到来。由于某些原因，第 46 届和第 47 届世界总决赛将同时举行。获得这两项比赛资格的队伍应选择其中一项参加。

我们知道，lzr 010506 的队伍获得了双重资格，应该做出选择。为了做出更明智的选择，lzr 010506 查阅了两项比赛的合格名单，并训练了一个魔法模型来预测两项比赛中所有参赛者的结果。此外，结果还包含解题数量和时间惩罚。解题数量越多，结果越好；如果两队解题数量相同，则时间惩罚越少的结果越好。

现在，lzr 010506 想知道，如果实际结果都与预测结果相同，而且双料冠军队伍的比赛选择可以由他任意安排，那么可能的最佳排名是多少。

Solution

先将两场比赛排序，求出这个队伍前面有多少个队伍。

答案就是该队伍在两场比赛中的排名减去在该场比赛中前面重合队伍个数的最小值。

void solve() {
    int n;cin >> n;
    vector<array<string, 3>>a(n);
    map<string, int>mp;
    for (int i = 0;i < n;i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];mp[a[i][0]]++;
    }
    sort(a.begin(), a.end(), [](auto x, auto y) {
        if (x[1] == y[1])return stoi(x[2]) < stoi(y[2]);
        return stoi(x[1]) > stoi(y[1]);
        });
    int m;cin >> m;
    vector<array<string, 3>>b(m);
    for (int i = 0;i < m;i++) {
        cin >> b[i][0] >> b[i][1] >> b[i][2];mp[b[i][0]]++;
    }

    sort(b.begin(), b.end(), [](auto x, auto y) {
        if (x[1] == y[1])return stoi(x[2]) < stoi(y[2]);
        return stoi(x[1]) > stoi(y[1]);
        });
    int ra = -1, rb = -1;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0;i < n;i++) {
        if (a[i][0] == "lzr010506") {
            ra = i + 1;
            break;
        }
        if (mp[a[i][0]] == 2)cnt1++;
    }
    for (int i = 0;i < n;i++) {
        if (b[i][0] == "lzr010506") {
            rb = i + 1;
            break;
        }
        if (mp[b[i][0]] == 2)cnt2++;
    }
    cout << min(ra - cnt1, rb - cnt2) << '\n';
}

A A Bit Common

给定两个整数 $n$ 和 $m$ ，在所有包含小于 $2^{m}$ 的非负整数 $n$ 的序列中，你需要计算存在一个非空子序列 $A$ ，其中整数的位相 AND 为 $1$ 的这样的序列 $A$ 的个数。

由于答案可能非常大，请输出它的正整数模 $q$ 。

Solution

排列组合

//....

I Mirror Maze

有一个 $n \times m$ 镜子迷宫，每个格子上都有一面镜子。镜子有以下四种类型：

从上方或下方射来的光线会被反射回去，从左侧或右侧射来的光线会继续向前，不会被反射；
从左边或右边来的光会被反射回去，从上面或下面来的光会继续向前，不会被反射；
/''，来自左、右、上、下的光会分别被反射到上、下、左、右；
$∖$ ''，来自左、右、上、下的光会被反射，分别去往下、上、右、左。

现在有 $q$ 个光源。小 G 是光的信奉者，他想知道每种光源在足够的时间内，发出的光会被多少面不同的镜子反射。

Solution

超级麻烦的 BFS/图论