Visits: 374

【LGR-067】洛谷 1 月月赛 II & CSGRound 3 Div.2

压岁钱

模拟。

封印的钱拿个数组记录就行了。

const int N = 1e6 + 7;
int n, o, x, y, ans;
ll c[N], now;

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) {
        now += c[i], rd(o), rd(x);
        switch (o) {
            case 1 : now += x; break;
            case 2 :
                if (now < x) ++ans;
                else now -= x;
                break;
            case 3 :
                now -= x, rd(y), c[y] += x;
        }
    }
    print(ans);
    return 0;
}

斗牛

选 $n-2$ 张牌相当于选两张牌，同时如果有解，答案一定是 $((\Sigma – 1) \bmod 10) + 1$。

开个大小为 $10$ 的桶即可。

const int N = 1e6 + 7;
int n, a[N], s, c[10];

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), a[i] %= 10, s += a[i];
    for (int i = 1; i <= n; i++) {
        int x = (s % 10 - a[i] + 10) % 10;
        if (c[x]) return print((s - 1) % 10 + 1), 0;
        c[a[i]%10] = 1;
    }
    print(0);
    return 0;
}

游戏

枚举先手取牌的张数，贪心出此时合法的 $X$ 的范围，差分即可。

贪心时二分可以做到 $\mathcal O(n \log n)$，双指针可以做到 $\mathcal O(n)$。

const int N = 1e6 + 7;
int n, k, c[N];
ll a[N];

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), a[i] += a[i-1];
    a[++n] = 1e18, rd(k);
    for (int i = 1, p = 2; i < n; i++) {
        while (a[p] < 2 * a[i]) ++p;
        if (a[i] <= k) ++c[a[i]];
        if (a[p] - a[i] <= k) --c[a[p]-a[i]];
    }
    vi ans;
    for (int i = 1; i <= k; i++)
        if ((c[i] += c[i-1])) ans.pb(i);
    print(ans.size());
    for (auto x : ans) print(x, ' ');
    return 0;
}

出游

套路题。

给定一张 $n$ 个点的有向图，一开始选择一些点，这些点每次走一步，问 $T$ 步后这些点可能在哪些位置。

类似这样的问题都可以用 bitset 优化矩阵乘法做到 $\mathcal O(\frac{n^3\log T}w)$，比如 CF576D Flights for Regular Customers。

我这题代码就是从那题的代码改的。

最终你会得到一个矩阵 $a$，$a_{i,j}$ 表示一开始如果 $i$ 被选择了，那么最终 $j$ 会被选。

那么 $j$ 最后不参加的概率就是所有 $a_{i,j} = 1$ 的 $i$ 一开始不参加的概率。

人数的期望就是所有人参加的概率之和。

const int N = 500;
int n, m;
modint p[N], ans;
#define bt bitset<N>
struct mt {
    bt a[N];
    inline friend mt operator * (mt x, mt y) {
        mt z;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (x.a[i][j]) z.a[i] |= y.a[j];
        return z;
    }
} a, b;

inline void ksm(mt x, int y, mt &z) {
    while (y) {
        if (y & 1) z = z * x;
        x = x * x, y >>= 1;
    }
}

int main() {
    rd(n), rd(m);
    for (int i = 0, k; i < n; i++) {
        rd(p[i]), rd(k);
        for (int j = 0, x; j < k; j++)
            rd(x), a.a[--x][i] = 1;
        b.a[i][i] = 1;
    }
    ksm(a, m, b);
    for (int i = 0; i < n; i++) {
        modint o = 1;
        for (int j = 0; j < n; j++)
            if (b.a[j][i]) o *= 1 - p[j];
        ans += 1 - o;
    }
    print(ans);
    return 0;
}