日常刷题

发表于 更新于 分类于 本文字数： 3.9k 阅读时长 ≈ 14 分钟

要开学了, 挣扎下. 17 号就要打 ICPC 的网络赛了, 到时候为了不太难看(队伍里有佬带飞qwq)就稍微做点题目.

如果进了区域赛, 那就得狠狠地锻炼了...

重复局面

出处

题意: n 个 8*8 的象棋棋盘, 统计每种局面的出现次数.

例如 ABA, 那么输出 1 1 2. 其中 A 代表

1
2
3
4
5
6
7
8
********
******pk
*****r*p
p*pQ****
********
**b*B*PP
****qP**
**R***K*

这样的一个模拟棋盘.

题解: 统计出现次数, 用一个简单的 Hash 解决. 一个棋盘就是一个 string(新的一行直接字符串拼接就行), 那么 unordered_map<string, int> 解决战斗.

垦田计划

导航

题意: 求 \(t_{总}=\max \{t_1, t_2, \dots, t_n\}\) 的最小值, 其中 \(t_i\) 可投入 \(p \cdot c_i\) 份的资源减少 \(p\) 时间(总资源有 \(m\) 份), 但是缩减后的时间必须 \(t_i' \geqslant k\), 其中 \(0 < k \leqslant \min \{t_1, t_2, \dots, t_n\}\).

题解: 水桶效应. 对时间枚举, 让最大值变成第二大, 一直到 \(k\). 每次判断剩余是否足够. 如果有盈余就输出 \(k\).

二分做法: 对答案时间枚举. 符合单调性: \(l = k, r= t_{max}\), 每次 check 答案所需资源是否大于 \(m\).

复习下二分板子

lower_bound:

[l, r] --> [l, mid] + [mid + 1, r]

1
2
3
4
5
6
7
8
while (l < r)
{
    int mid = l + r >> 1;
    if (check(mid))
        r = mid;
    else
        l = mid + 1;
}

upper_bound:

[l, r] ---> [l, mid - 1] + [mid, r]

1
2
3
4
5
6
7
8
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (check(mid))
        l = mid;
    else
        r = mid - 1;
}

CCC单词搜索

题意: 给定一个 \(R\times C\) 的字符矩阵, 搜索目标单词 \(W\), 合法的单词出现:

  • 出现在一条直线上, 可以水平或者竖直.
    • 可以正向, 可以反向.
    • 还可以出现在斜45度线段中.
  • 单词出现在两条相互垂直且存在公共端点的线段上.

数据量: \(2\leqslant|W|\leqslant 6\), \(1 \leqslant R, C \leqslant 100\)

样例:

1
2
3
4
5
6
7
8
9
NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E
示例

题解: DFS + 位运算

搜索方向, 用 dx, dy 两个数组存放偏移量.

偏移量

旋转操作可以用一个位运算的小技巧, 例如编号为 0 的方向旋转后的两个方向是 2 (010) 和 6 (110), 对应 0 ^ 2 以及 0 ^ 2 ^ 4.

实际上就是 0 + 2, 0 + 2 + 4, 但是对于例如 7 这样的数字会上溢, 位运算就免去了这个烦恼. 当然取模是可以获得相同的结果的.

枚举量: \(10000 \times 8 \times (5 \times 2 + 1)\) 大概是 1e6 的运算. 不用考虑 dp 优化.

我一直觉得 DFS 的代码很美观.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

const int N = 1e2 + 5, M = 7;
int T = 1;

char g[N][N], s[M];

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int r, c, len, res;

// x, y: 坐标
// d: 方向编号
// u: 深度
// cnt: 旋转次数
void dfs(int x, int y, int d, int u, int cnt)
{
    if (x < 0 || y < 0 || x >= r || y >= c || g[x][y] != s[u])
        return;
    if (u == len - 1)
        res ++;
    else
    {
        dfs(x + dx[d], y + dy[d], d, u + 1, cnt);
        if (!cnt && u)
        {
            dfs(x, y, d ^ 2, u, cnt + 1);
            dfs(x, y, d ^ 2 ^ 4, u, cnt + 1);
       }
    }
}

void solve()
{
    cin >> s >> r >> c;
    len = strlen(s);

    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            cin >> g[i][j];

    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            for (int k = 0; k < 8; k++)
                dfs(i, j, k, 0, 0);

    cout << res << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // cin >> T;
    while (T--)
    {
        solve();
    }
    
    return 0;
}

对称山脉

传送

题意: \(n\) 座山, 每座山有 \(h_i\), 考虑一段连续区间 \([l, r]\), 定义不对称值 \(\displaystyle\sum_{0\leq i\leq\frac{r-l}2}\lvert h_{l+i}-h_{r-i}\rvert\), 求在某一区间长度下, 不对称值的最小值.

不对称值可以理解为: 连续区间对称位置之间的差值之和.

例如 1 2 3 4 5 这个例子, 当区间长为 3 时, 需要枚举 123 234 345.

  • 123 的例子: \(|h_1-h_3|+|h_2-h_2|=2\)
  • 234 的例子: \(|h_2-h_4|+|h_3-h_3|=2\)
  • ...

所以当区间长为 3 时最小值为 2.

数据范围: \(n\leqslant 5000\)

题解: 按照例子里的方法暴力枚举, 枚举区间长度, 枚举区间起点/终点, 计算差值求和, 时间复杂度为 \(O(n^3)\), 算上数据量是 1e11, 会爆. 需要优化为 \(O(n^2)\).

观察:

  • 计算大区间的不对称值, 一部分已经在小区间里计算了.
    • 例如 12345, 显然 234 已经在区间长为 3 的的时候过了计算了.
    • 它们的中心点都是 3.
  • 考虑枚举中心点, 然后逐层往外循环枚举.
    • 状态转移就是 \(f = f' + |h_l - h_r|\)
  • 答案取不对称值的最小值.
  • 奇偶分开讨论.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 5;
int T = 1;

int h[N], f[N];

void solve()
{
    memset(f, 0x3f, sizeof f);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> h[i];
    for (int i = 0; i < n; i++)
    {
        for (int l = i, r = i, s = 0; l >= 0 && r < n; l--, r++)
        {
            s += abs(h[l] - h[r]);
            f[r - l + 1] = min(f[r - l + 1], s);
        }
        for (int l = i, r = i + 1, s = 0; l >= 0 && r < n; l--, r++)
        {
            s += abs(h[l] - h[r]);
            f[r - l + 1] = min(f[r - l + 1], s);
        }
    }
    for (int i = 1; i <= n; i++)
        cout << f[i] << ' ';    
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // cin >> T;
    while (T--)
    {
        solve();
    }
    
    return 0;
}

二进制

出处

题意

题解: 简易版扫雷. 给的 k 字串数字和序列类似于扫雷里雷的数字. 因为给的序列是连续的滑动区间, 相邻最多差 1, 根据这个数字可以确定 1 在二进制串中出现的位置.

例如样例的 3 2 2 2, [1, 4] 中有 3 个 1, [2, 5] 有 2 个 1, [2, 4] 是公共部分, 1 的个数是相同的, 而 [1, 4] 多一个 1, 说明第一个位置是 1, 第五个位置是 0.

对于 [3, 6], 可以确定位置 6 和位置 2 是相同的. 最终可以确定二进制串是 1xyz0xy, 要确定的只有第一个区间里的 3 个位置, 还需要 2 个 1, 因此方案数为 \(\binom{2}{3}=3\) 个.

归纳可知

  • a[i] == a[i+1]: s[i] = s[i+k]
  • a[i] > a[i+1]: s[i] = 1, s[i+k] = 0
  • a[i] < a[i+1]: s[i] = 0, s[i+k] = 1

方案数 \(\binom{k-c_1-c_0}{a[0]-c_1}\), 其中 \(c_1\) 是第一个区间 1 的个数, \(c_0\) 是第一个区间 0 的个数.

相同值的位置可以用一个并查集维护.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

const int MOD = 1e6 + 3, N = 1e6 + 5;
int T = 1;

int n, k;

// a ^ b mod p
LL q_pow(int a, int b)
{
    LL res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        a = (LL) a * a % MOD;
        b >>= 1;
    }
    return res;
}

LL C(int a, int b)
{
    LL fa = 1, fb = 1, fab = 1;
    // 只用算一次所以不用开 frac 数组了
    for (int i = 1; i <= a; i++)
        fa = fa * i % MOD;
    for (int i = 1; i <= b; i++)
        fb = fb * i % MOD;
    for (int i = 1; i <= a - b; i++)
        fab = fab * i % MOD;
    return fa * q_pow(fb, MOD - 2) % MOD * q_pow(fab, MOD - 2) % MOD;
}

// p: 并查集 父节点
// v: 值
int a[N], p[N], v[N];

int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

void solve()
{
    cin >> n >> k;
    for (int i = 0; i < n - k + 1; i++)
        cin >> a[i];
    
    for (int i = 0; i < n; i++)
        p[i] = i, v[i] = -1;
        
    for (int i = 0, j = k; j < n; i++, j++)
    {
        if(a[i] == a[i + 1])
            p[find(i)] = find(j);
        else if (a[i] < a[i + 1])
            v[find(i)] = 0, v[find(j)] = 1;
        else
            v[find(i)] = 1, v[find(j)] = 0;
    }
    
    int c0 = 0, c1 = 0;
    for (int i = 0; i < k; i++)
    {
        if (v[find(i)] == 1)
            c1 ++;
        else if (v[find(i)] == 0)
            c0 ++;
    }
    // cout << c0 << ' ' << c1 << endl;
    cout << C(k - c1 - c0, a[0] - c1) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // cin >> T;
    while (T--)
    {
        solve();
    }
    
    return 0;
}

并查集/数学板子

并查集: 路径压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int p[N];
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return x;
}

void merge(int a, int b)
{
    p[find(a)] = find(b);
}

bool equal(int a, int b)
{
    return find(a) == find(b);
}

快速幂:

1
2
3
4
5
6
7
8
9
10
11
12
13
// a^b mod p
int fpow(int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = (LL) res * a % p;
        a = (LL) a * a % p;
        b >>= 1;
    }
    return res;
}

求阶乘: 逆元求法

原理

\[\binom{n}{m} = \frac{m!}{n!(n-m)!}\]

在模 \(p\) 意义下, 那么

\[\binom{n}{m} \equiv m!(n!)^{-1}((n-m)!)^{-1} (\bmod p)\]

那么我们只用计算阶乘的乘法逆元即可.

\[(n!)^{-1}=((n-1)!n)^{-1}=((n-1)!)^{-1}n^{-1} (\bmod p)\]

\(p\) 是大质数, 利用费马小定理

\[n\equiv n^{p} (\bmod p)\Rightarrow n^{-1}\equiv n^{p-2} (\bmod p)\]

于是

\[(n!)^{-1}=((n-1)!)^{-1}\cdot n^{p-2}\]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int fpow(int x, int t = mod - 2) {
    int res = 1;
    for (; t; t >>= 1, x = 1ll * x * x % mod)
        if (t & 1) res = 1ll * res * x % mod;
    return res;
}

int fac[N], ifac[N];

int C(int n, int m) {
    if (n < m) return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int main()
{
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[N - 1] = fpow(fac[N - 1]);
    for (int i = N - 2; i; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
    // ...
}

所有三角形

导航

模拟铺瓷砖. 每一个三角形对答案贡献 3, 但是有相连的情况对答案贡献 -2, 注意上下相连的情况如果是顶点相接则不会有影响.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve()
{
    cin >> n;
    int res = 0;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < n; j++)
        {
            cin >> w[i][j];
            if (w[i][j])
                res += 3;
            if (j && w[i][j] && w[i][j - 1])
                res -= 2;
            if (i && j % 2 == 0 && w[i - 1][j])
                res -= 2;
        }
    cout << res << endl;
}

分组

导航

题意: 有 \(x\) 对人希望分在同一组, \(y\) 对人希望分在不同组, 现在有 \(3G\) 个人分成 \(G\) 组, 判断有多少意愿没有被满足.

题解: 哈希表存放 名字->组 的一个映射, 然后逐个判断每个意愿即可. 例如希望同组的, 就判断 mp[a] != mp[b], 同理希望不同组的判断是否相同即可. 时间复杂度为 \(O(n)\).

注意记得关闭 cin 同步或者采用 scanf.

正方形泳池

导航

题意: \(N \times N\) 的矩阵, 有 \(T\) 棵树, 找到一个最大边长的正方形子矩阵, 使得内部不包含树.

题解: \(N\) 太大, 转而枚举树, 理论上把 \(\binom{4}{t}\) 的方案全部枚举, 然后求上下边界和左右边界距离的最小值即可. 复杂度是 \(O(T^4)\).

如果问题变为 hard version, 也就是 T 的范围变到 \(10^3\) 那就不好办了. 这时候考虑优化.

我们考虑只枚举左右边界, 然后逐步缩小上下边界, 求出一个 \(d\). 然后再枚举上下边界, 缩小左右边界得到 \(d'\). 那么答案是 \(\max\{d, d'\}\).

上下边界和右边树的位置相关 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 105;
int T = 1;

int n, t;

PII tr[N];

int work()
{
    int res = 0;
    sort(tr, tr + t);
    for (int i = 0; i < t; i++)
    {
        int up = n + 1, down = 0;
        for (int j = i + 1; j < t; j++)
        {
            if (tr[i].x == tr[j].x)
                continue;
            if (tr[j].x - tr[i].x > up - down)
                break;
            res = max(res, tr[j].x - tr[i].x - 1);
            if (tr[j].y >= tr[i].y)
                up = min(up, tr[j].y);
            if (tr[j].y <= tr[i].y)
                down = max(down, tr[j].y);
        }
    }
    return res;
}

void solve()
{
    cin >> n >> t;
    for (int i = 0; i < t; i++)
        cin >> tr[i].x >> tr[i].y;

    tr[t++] = {0, 0};
    tr[t++] = {0, n + 1};
    tr[t++] = {n + 1, n + 1};
    tr[t++] = {n + 1, 0};

    int ans = work();
    for (int i = 0; i < t; i++)
        swap(tr[i].x, tr[i].y);

    cout << max(ans, work()) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

好四和好五

来源

题意: 求 \(4x+5y=N\) 的所有解的数量.

题解: 不定方程的一个特解 \(x_0=-N, y_0=N\), 通解 \(x=x_0+5k\), \(y=y_0-4k\), \(k\) 最小为 \(\lfloor \frac{N}{5} \rfloor\), 最大 \(\lceil \frac{N}{4} \rceil\).

1
2
3
4
5
6
7
void solve()
{
    int n;
    cin >> n;
    int ans = n / 4 - (n + 4) / 5 + 1;
    cout << ans << endl;
}

街灯

导航

差分板子

差分: 给 [l, r] 区间的每个数加上 c

1
2
3
4
5
6
int a[N], b[N];
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

ICPC 2022 网络赛 I

出处

C Delete the Tree

题意: 删除一棵树, 有两种操作:

  • 删除: 选择一个点, 删除该节点以及它连着的边.
  • 收缩: 选择一个度数为 2 的节点, 假设它是 \(x\), 连着 \(u,v\), 那么该操作将 \(x, (u,x), (x,v)\) 删去, 新建边 \((u,v)\).

求删除树的最小删除操作的次数.

题解: 观察到收缩操作可以将图中全部度数为 2 的节点删除, 剩下的要么是叶子, 要么是内部度数大于 2 的节点.

对于度数大于 2 的节点, 可以考虑先将与它相连的叶子删去, 使其度数转为 2, 然后通过收缩操作将其删去.

要进行删除的点只有叶子, 也就是度数为 1 的节点.

坑点:

  • 记得特判 \(n = 1\) 的情况.
  • 为什么 memset 会 T.

D Find the Number

1
2
3
4
5
6
7
8
9
10
void solve()
{
    int ans = 0;
    for (int i = 1; i <= 1e9; i++)
    {
        if (__builtin_ctz(i) == __popcount(i))
            ans ++;
    }
    cout << ans << endl;
}

暴力打表可知这样好的数的个数一共约有 5e5 个. 如果我们知道了这些数, 然后放到一个集合里, 二分判断每次的查询就行了.

当然你不能暴力求这个"好数"的集合, 肯定会 TLE 的.

考虑枚举尾导零的个数, 例如 4, 最后五位是 10000, 剩下的 32 - 5 位就全排列, 这个可以用 next_permutation 枚举出来, 近似常数的.

这道题还可以数位DP + DFS 做, 但我不会.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

const int M = 1e9;
int T = 1;

set<int> st;
vector<int> t;

int to_bit(vector<int>& a, int i)
{
    int res = 0;
    vector<int> aa = a;
    reverse(aa.begin(), aa.end());
    for (int j = 0; j < aa.size(); j++)
        res += (aa[j] << j);
    res <<= (i + 1);
    return res;
}

void solve()
{
    int l, r;
    cin >> l >> r;
    auto it = st.lower_bound(l);
    if (it == st.end())
    {
        cout << -1 << endl;
        return;
    }
    int x = *it;
    if (l <= x && x <= r)
        cout << x << endl;
    else
        cout << -1 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 枚举尾导零的个数
    for (int i = 1; i <= 15; i++)
    {
        t.clear();
        vector<int> a;
        for (int j = 0; j < 30 - 2 * i; j++)
            a.push_back(0);
        for (int j = 0; j < i - 1; j++)
            a.push_back(1);
        // 全排列前面 30 - i - 1 个位置
        do
        {
            int num = to_bit(a, i) + (1 << i);
            if (num <= M)
                st.insert(num);
        } while (next_permutation(a.begin(), a.end()));
    }

    cin >> T;
    while (T--)
    {
        solve();
    }
    
    return 0;
}

A 01 Sequence

题意: 给定 0-1 循环串(表示首位和末尾是相邻的), 可以进行两种操作

  • 删除: 如果 \(|S|\geqslant 3\), 那么选择 \(S_i = 1\) 的第 \(i\) 位以及其相邻的位进行删除.
  • 翻转: 将第 \(i\) 位的 1 变为 0, 0 变为 1.

定义 如果 \(S\) 可以通过删除操作置空, 则 \(S\) 为好串.

定义 \(f(S)\) 为令 \(S\) 为好串的最小翻转操作数.

给定 0-1 串 \(a\) 以及 \(q\) 个询问, 每个询问会给出 \(l_i, r_i\), 任务是回答 0-1 串的一个字串 \(a_{l_i...r_i}\) 的 \(f(a_{l_i...r_i})\).

样例:

1
2
3
4
5
6
7
8
9
10
11
12
20 10
00001000100000010000
18 20
14 16
7 12
2 10
16 18
6 20
8 10
13 15
1 6
1 12
1
2
3
4
5
6
7
8
9
10
1
0
1
1
0
3
0
1
1
2

前缀和 + 思维.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int T = 1;

int n, m, s[N], suf[N], pre[N];
char a[N];

int calc(int l, int r)
{
    int ll = l + pre[l], rr = r - suf[r];
    if (ll >= rr)
        return (r - l + 1) >> 1;
    return s[rr] - s[ll - 1] + (pre[l] + suf[r] + 1) / 2;
}

void solve()
{
    int l, r;
    cin >> l >> r;
    int len = r - l + 1;
    cout << max(0, len / 3 - calc(l, r)) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n >> T;

    a[0] = '#';
    cin >> a + 1;

    // 1 区间的个数
    int last = -1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == '1')
        {
            if (last != i - 1)
                s[i] = 1, last = i;
            else
                last = -1;
        }
        s[i] += s[i - 1];
    }

    // 左边数起 结尾为 i 连续 1 的个数
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == '1')
            suf[i] = suf[i - 1] + 1;
        else
            suf[i] = 0;
    }

    for (int i = n; i >= 1; i--)
    {
        if (a[i] == '1')
            pre[i] = pre[i + 1] + 1;
    }

    while (T--)
    {
        solve();
    }
    
    return 0;
}