牛客IOI周赛21-提高组

2024-02-10 18:48:10

难得周六晚上有比赛打，于是就报了下，结果竟然锕氪了 极度舒适

T1 序列问题

先开的这题。

一眼看这个数据范围，应该是要推式子了，先分个类。

  • \(q >= n\) ：不用说了，肯定没方案。

  • \(0 <= q < n\)

    发现只用考虑 \(\mathrm{B}\) 集合的最小值 \(-\) \(\mathrm{A}\) 集合的最大值 即可，考虑枚举，先枚举 \(\mathrm{B}\) 再枚举 \(\mathrm{A}\) ，设总的方案数为 \(ans\) ，可得到：

    \[\begin{aligned} ans &= \sum_{i = q + 1}^{n} 2^{n - i} \sum_{j = 1}^{i - q} 2^{j - 1} \\ &= \sum_{i = q + 1}^{n} 2^{n - i} \times (2^{i-q}-1) \\ &= \sum_{i = q + 1}^{n} 2^{n - q} - 2^{n - i} \\ &= 2^{n - q} \times (n - q) - (2 ^ {n - q} - 1) \end{aligned}\]

    然后就能做到 \(\log n\) 了。

  • \(-n < q < 0\)

    还是考虑枚举，先令 \(q = -q\) 变为正数，现在考虑的限制就是 \(\mathrm{A}\) 集合的最大值 \(-\) \(\mathrm{B}\) 集合的最小值 \(<= q\) 。

    可以只枚举 \(\mathrm{A}\) ，然后就能确定 \(\mathrm{B}\) 集合可以取的数的个数，则：

    \[ans = \sum_{i = 1}^{n} 2^{i - 1} \times (2^{n - \max(0, i - q - 1)} - 1) \]

    有个取 \(\max\) 的很烦，考虑分类来算：

    \[\begin{aligned} ans1 &= \sum_{i = 1}^{q + 1} 2^{i - 1} \times (2^n - 1) \\ &= (2^{q + 1} - 1) \times 2^n - \sum_{i = 1}^{q + 1} 2^i \\ ans2 &= \sum_{i = q + 2}^{n} 2^{i - 1} \times (2^{n - (i - q - 1)} - 1) \\ &= \sum_{i = q + 2}^{n} 2^{n + q} - 2^{i - 1} \\ &= 2^{n + q} \times (n - q - 1) - \sum_{i = q + 2}^{n} 2^i \end{aligned}\]

    整合 \(ans1\) 与 \(ans2\) 得：

    \[\begin{aligned} ans &= (2^{q + 1} - 1) \times 2^n + 2^{n + q} \times (n - q - 1) - \sum_{i = 1}^n 2^{i - 1} \\ &= (2^{q + 1} - 1) \times 2^n + 2^{n + q} \times (n - q - 1) - (2^n - 1) \end{aligned}\]

    然后就能做到 \(\log n\) 了。

  • \(q <= -n\) : 很明显怎么选都可以，直接输出总方案 \((2^n - 1) ^ 2\) 即可。

\(code:\)

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL read() {
	char ch = getchar();
	LL x = 0, pd = 0;
	while (ch < '0' || ch > '9')
		pd ^= ch == '-', ch = getchar();
	while ('0' <= ch && ch <= '9')
		x = x*10+(ch^48), ch = getchar();
	return pd ? -x : x;
}
const int mod = 998244353;
int Add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
int Mul(LL x, LL y) { x %= mod, y %= mod; return 1ll * x * y % mod; }
int fastpow(int x, LL y) {
    int res = 1;
    for (; y; x = Mul(x, x), y >>= 1)
        if (y & 1) res = Mul(res, x);
    return res;
}
int main() {
	#ifdef LOCAL
	freopen("data.in", "r", stdin);
	freopen("pro.out", "w", stdout);
	#endif
    int T = read();
    while (T--) {
        LL n = read(), q = read();
        if (q >= 0) {
            if (q < n) printf("%d\n", Mul(fastpow(2, n - q), n - q - 1) + 1);
            else puts("0");
        }
        else {
            q = -q;
            if (q < n - 1)
                printf("%d\n", Add(Add(Mul(fastpow(2, q + 1) - 1, fastpow(2, n)), Mul(fastpow(2, n + q), n - q - 1)), mod - fastpow(2, n) + 1));
            else printf("%d\n", Mul(fastpow(2, n) - 1, fastpow(2, n) - 1));
        }
    }
	return 0;
}

T2 俄罗斯方块

最后10min才写出来 ...

想了dp啊啥的感觉都没有思路，看到数据范围只有 \(10\) 个方块，方块就 \(3\) 种，棋盘只有 \(7 \times 6\) ，而且行消除了就真的没了，相当于棋盘在缩小，试着暴搜看能不能过吧。

觉得写递归回溯太麻烦了，用了类似 \(\mathrm{BFS}\) 的方法，开了两个存所有可能的棋盘状态的 \(\mathrm{vector}\) ，交替更新。

第一种方块旋转共有两个不同的形状，第二种就一个，第三种有六个（写的时候还漏了像镰刀形状的情况.....）

然后就是枚举插入在什么地方，判断合法性，然后插完之后判断消除，总之就是码码码......

码了150多行终于过了。

\(code:\)

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int read() {
	char ch = getchar();
	int x = 0, pd = 0;
	while (ch < '0' || ch > '9')
		pd ^= ch == '-', ch = getchar();
	while ('0' <= ch && ch <= '9')
		x = x*10+(ch^48), ch = getchar();
	return pd ? -x : x;
}
int n, ans = 7;
struct R {
    int n;
    int s[7];
} t;
vector<R>v[2];
R check(R x) {
    for (int i = x.n - 1; i >= 0; i--)
        if (x.s[i] == 63) {
            for (int j = i; j < x.n - 1; j++) x.s[j] = x.s[j + 1];
            --x.n;
        }
    ans = min(ans, x.n);
    return x;
}
int main() {
	#ifdef LOCAL
	freopen("data.in", "r", stdin);
	freopen("pro.out", "w", stdout);
	#endif
    n = read();
    t.n = 7;
    v[1].push_back(t);
    for (int i = 1; i <= n; i++) {
        int x = read(), len = v[i & 1].size();
        v[i & 1 ^ 1].clear();
        if (x == 1) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k < v[i & 1][j].n; k++)
                    for (int l = 0; l < 3; l++) {
                        int now = 15 << l;
                        if (!k || (now & v[i & 1][j].s[k - 1])) {
                            bool ok = 1;
                            for (int kk = k; ok && kk < v[i & 1][j].n; kk++)
                                ok = !(v[i & 1][j].s[kk] & now);
                            if (!ok) continue;
                            t = v[i & 1][j];
                            t.s[k] |= now;
                            v[i & 1 ^ 1].push_back(check(t));
                        }
                    }
                for (int k = 0; k + 3 < v[i & 1][j].n; k++)
                    for (int l = 0; l < 6; l++) {
                        if (k && !(1 << l & v[i & 1][j].s[k - 1])) continue;
                        t = v[i & 1][j];
                        bool ok = 1;
                        for (int kk = k; ok && kk < v[i & 1][j].n; kk++)
                            ok = !(1 << l & v[i & 1][j].s[kk]);
                        if (!ok) continue;
                        t.s[k] |= 1 << l, t.s[k + 1] |= 1 << l, t.s[k + 2] |= 1 << l, t.s[k + 3] |= 1 << l;
                        v[i & 1 ^ 1].push_back(check(t));
                    }
            }
        }
        if (x == 2) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k + 1 < v[i & 1][j].n; k++)
                    for (int l = 0; l < 5; l++) {
                        int now = 3 << l;
                        if (!k || (now & v[i & 1][j].s[k - 1])) {
                            bool ok = 1;
                            for (int kk = k; ok && kk < v[i & 1][j].n; kk++)
                                ok = !(v[i & 1][j].s[kk] & now);
                            if (!ok) continue;
                            t = v[i & 1][j];
                            t.s[k] |= now, t.s[k + 1] |= now;
                            v[i & 1 ^ 1].push_back(check(t));
                        }
                    }
            }
            
        }
        if (x == 3) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k + 2 < v[i & 1][j].n; k++)
                    for (int l = 0; l < 5; l++) {
                        int now = 3 << l;
                        if (!k || (now & v[i & 1][j].s[k - 1])) {
                            bool ok = 1;
                            for (int kk = k; ok && kk < v[i & 1][j].n; kk++)
                                ok = !(v[i & 1][j].s[kk] & now);
                            if (!ok) continue;
                            t = v[i & 1][j];
                            t.s[k] |= now, t.s[k + 1] |= 1 << l, t.s[k + 2] |= 1 << l;
                            v[i & 1 ^ 1].push_back(check(t));
                            t = v[i & 1][j];
                            t.s[k] |= now, t.s[k + 1] |= 1 << (l + 1), t.s[k + 2] |= 1 << (l + 1);
                            v[i & 1 ^ 1].push_back(check(t));
                        }
                    }
                for (int k = 0; k + 1 < v[i & 1][j].n; k++)
                    for (int l = 0; l < 4; l++) {
                        int now = 7 << l;
                        if (!k || (now & v[i & 1][j].s[k - 1])) {
                            bool ok = 1;
                            for (int kk = k; ok && kk < v[i & 1][j].n; kk++)
                                ok = !(v[i & 1][j].s[kk] & now);
                            if (!ok) continue;
                            t = v[i & 1][j];
                            t.s[k] |= now, t.s[k + 1] |= 1 << l;
                            v[i & 1 ^ 1].push_back(check(t));
                            t = v[i & 1][j];
                            t.s[k] |= now, t.s[k + 1] |= 1 << (l + 2);
                            v[i & 1 ^ 1].push_back(check(t));
                        }
                    }
                for (int k = 0; k + 2 < v[i & 1][j].n; k++)
                    for (int l = 0; l < 5; l++) {
                        int now = 3 << l;
                        if (!k || (1 << l & v[i & 1][j].s[k - 1])) {
                            bool ok = 1;
                            for (int kk = k; ok && kk < v[i & 1][j].n; kk++)
                                ok = !(1 << l & v[i & 1][j].s[kk]);
                            for (int kk = k + 2; ok && kk < v[i & 1][j].n; kk++)
                                ok = !(1 << (l + 1) & v[i & 1][j].s[kk]);
                            if (!ok) continue;
                            t = v[i & 1][j];
                            t.s[k + 2] |= now, t.s[k + 1] |= 1 << l, t.s[k] |= 1 << l;
                            v[i & 1 ^ 1].push_back(check(t));
                        }
                        if (!k || (1 << (l + 1) & v[i & 1][j].s[k - 1])) {
                            bool ok = 1;
                            for (int kk = k; ok && kk < v[i & 1][j].n; kk++)
                                ok = !(1 << (l + 1) & v[i & 1][j].s[kk]);
                            for (int kk = k + 2; ok && kk < v[i & 1][j].n; kk++)
                                ok = !(1 << l & v[i & 1][j].s[kk]);
                            if (!ok) continue;
                            t = v[i & 1][j];
                            t.s[k + 2] |= now, t.s[k + 1] |= 1 << (l + 1), t.s[k] |= 1 << (l + 1);
                            v[i & 1 ^ 1].push_back(check(t));
                        }
                    }
            }
        }
    }
    printf("%d\n", 7 - ans);
	return 0;
}

赛后别人提交的代码，我靠，就两三个跟我一样正正经经的码正解，其他人都是面向数据编程（打表），毕竟可以无限次提交，然后还能看到分数，感觉这样做好没意义啊。（所以应该就只有两三个人ak了hahaha）

T3 旅行没有商问题

避开T2大毒瘤先做了这题，事实证明也是明智的。

观察到数据范围很小，马上想到容斥+矩乘，算了下时间能过。

就是强制不能经过哪些点，然后剩下的问题就是随便走，就是一个很简单的图上dp了，矩阵加速一下就好。

感觉这题是这场比赛最简单的一道

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
int read() {
	char ch = getchar();
	int x = 0, pd = 0;
	while (ch < '0' || ch > '9')
		pd ^= ch == '-', ch = getchar();
	while ('0' <= ch && ch <= '9')
		x = x*10+(ch^48), ch = getchar();
	return pd ? -x : x;
}
const int mod = 1000000007;
int Add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
int Mul(int x, int y) { return 1ll * x * y % mod; }
int n, m, p, q, ans;
int nd[25];
int mp[25][25];
int a[25], b[25][25], t[25][25];
void Mul() {
    for (int j = 1; j <= n; j++) t[1][j] = 0;
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= n; k++)
            t[1][j] = Add(t[1][j], Mul(a[k], b[k][j]));
    for (int j = 1; j <= n; j++) a[j] = t[1][j];
}
void MulSelf() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) t[i][j] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                t[i][j] = Add(t[i][j], Mul(b[i][k], b[k][j]));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) b[i][j] = t[i][j];
}
int main() {
	#ifdef LOCAL
	freopen("data.in", "r", stdin);
	freopen("pro.out", "w", stdout);
	#endif
    n = read(), m = read(), p = read(), q = read();
    for (int i = 0; i < q; i++) nd[i] = read();
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read();
        mp[x][y] = mp[y][x] = 1;
    }
    for (int i = 0; i < (1 << q); i++) {
        for (int j = 1; j <= n; j++) {
            a[j] = 1;
            for (int k = 1; k <= n; k++) b[j][k] = mp[j][k];
        }
        int cnt = 0;
        for (int j = 0; j < q; j++)
            if (1 << j & i) {
                a[nd[j]] = 0;
                for (int k = 1; k <= n; k++) b[k][nd[j]] = b[nd[j]][k] = 0;
                ++cnt;
            }
        int N = p - 1;
        while (N) {
            if (N & 1) Mul();
            MulSelf(), N >>= 1;
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) sum = Add(sum, a[i]);
        if (cnt & 1) ans = Add(ans, mod - sum);
        else ans = Add(ans, sum);
    }
    printf("%d\n", ans);
	return 0;
}
上一篇：数据结构——B-树


下一篇：Python & Matplotlib: Monte Carlos Method