比赛回顾

国庆放假前一天晚上的一场 div3 比赛，题目全是模拟只是难度分布不太正常开局卡了好一会儿，还好当时头脑清醒，手速快罚时少最终也是成功小涨了一波分数 😁，突破 1500 分大关

赛后个人总结：

  • 复杂度分析不明白导致前几道模拟题一直不敢动手写，下次直接莽

  • E2 在最后两分钟才过的，自己的离散化板子竟然还是不支持去重的数组版本，坑了自己好久

A.Casimir’s String Solitaire—签到

题意：判断字符串中字符 B 的数量是否和 字符 A、C的数量相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void test_case() {
    string s;
    cin >> s;
    int a = 0, b = 0, c = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'A')
            ++a;
        else if (s[i] == 'B')
            ++b;
        else
            ++c;
    }
    if (a + c == b)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B.Shifting Sort—贪心+模拟

题意：给出一个乱序的数组长度为 n，每次操作可以选择一个子区间 [l,r] 然后让里面的数循环左移 d 个位置，必须满足 1<d<r−l1<d<r-l 。找出一个操作次数不多余 n 次的方法使数组有序

思路：提示很明显，贪心就每次操作让一个最乱序中的最大数放在有序数列中，这样 n 次操作正好使数组有序，因为数据范围很小 55 所以每次操作就模拟循环复制

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
const int maxn = 55;
 
int a[maxn], b[maxn];
 
struct node {
    int l, r, d;
    node(int l, int r, int d) : l(l), r(r), d(d) {}
};
 
vector<node> ans;
void test_case() {
    ans.clear();
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    for (int i = n; i >= 1; --i) {
        int now = b[i];
        for (int j = 1; j <= i; ++j) {
            if (a[j] == now && j != i) {
                ans.push_back(node(1, i, j));
                int c[maxn] = {};
                for (int k = 1; k <= i - j; ++k) c[k] = a[k + j];
                for (int k = 1; k <= j; ++k) c[k + i - j] = a[k];
                for (int k = 1; k <= i; ++k) a[k] = c[k];
                break;
            }
        }
    }
    cout << ans.size() << endl;
    if (ans.size())
        for (auto e : ans) cout << e.l << ' ' << e.r << ' ' << e.d << endl;
}

C.Ticks—贪心+DFS搜索

题意：在 n∗mn*m 的棋盘上有些方块是图上黑色的，已知涂色时需要满足选择一个中心点位置涂黑，然后分别向左上、右上两侧延伸涂色 d 块（d 需要不小于给出的 k），现在给出已经涂完色的棋盘请判断在给定条件下可否涂成棋盘的样子

思路：贪心的考虑，每个点都可能作为涂色的中心点，然后如果两边确实对称成 V 形而且两侧延伸长度确实大于 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
const int maxn = 25;
 
string mz[maxn];
bool vis[maxn][maxn];
int n, m, d;
 
int check(int i, int j) {
    int k = 1;
    while (1) {
        int lx = i - k, ly = j - k, rx = i - k, ry = j + k;
        if (lx < 1 || ly < 1 || rx < 1 || ry > m) break;
        if (mz[lx][ly] != '*' || mz[rx][ry] != '*') break;
        ++k;
    }
    return k - 1;
}
 
void paint(int i, int j, int cnt) {
    vis[i][j] = 1;
    for (int k = 1; k <= cnt; ++k) {
        int lx = i - k, ly = j - k, rx = i - k, ry = j + k;
        vis[lx][ly] = vis[rx][ry] = 1;
    }
}
 
void test_case() {
    memset(vis, 0, sizeof vis);
    cin >> n >> m >> d;
    for (int i = 1; i <= n; ++i) {
        cin >> mz[i];
        mz[i] = " " + mz[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (mz[i][j] == '.') continue;
            int tmp = check(i, j);
            if (tmp < d) continue;
            paint(i, j, tmp);
        }
    }
    bool flag = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (mz[i][j] == '*' && !vis[i][j]) {
                flag = 0;
                break;
            }
        }
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

D.Productive Meeting—贪心+优先队列

题意：有 n 个人来开会，第 i 个人有 ai 次谈话次数，在所有谈话次数后就离场。开会时每两个人进行一次谈话求整个会场能进行的最大谈话次数。

思路：每次选两个拥有最大谈话次数的人进行一次谈话最优，用优先队列模拟即可

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
typedef pair<int, int> pii;
 
vector<pii> ans;
priority_queue<pii> que;
 
void test_case() {
    int n;
    cin >> n;
    ans.clear();
    while (que.size()) que.pop();
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (x == 0) continue;
        que.push(pii(x, i));
    }
    while (que.size() >= 2) {
        auto top1 = que.top();
        que.pop();
        auto top2 = que.top();
        que.pop();
        ans.push_back(pii(top1.second, top2.second));
        --top1.first, --top2.first;
        if (top1.first) que.push(top1);
        if (top2.first) que.push(top2);
    }
    cout << ans.size() << endl;
    if (ans.size())
        for (auto e : ans) cout << e.first << ' ' << e.second << endl;
}

E1.Permutation Minimization by Deque—贪心+双端队列

题意：依次给出 n 个正整数用来生成一个数列，你每次可以将该数放在已经生成的数列最左侧或者最右侧，请输出可以生成的最小字典序数列

思路：字典序只需要保证靠前的位置越小越好，所有贪心考虑当前的数如果比生成数列最左侧的数还小就放在最左侧，否则就放在最右侧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void test_case() {
    int n;
    cin >> n;
    deque<int> que;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (i == 1) {
            que.push_back(x);
            continue;
        }
        if (x <= que.front())
            que.push_front(x);
        else
            que.push_back(x);
    }
    for (auto e : que) cout << e << ' ';
    cout << endl;
}

E2.Array Optimization by Deque—树状数组求逆序数+思维

题意：和 E1 题给数方法一样，但是需要你生成一个逆序数对最少的数列

思路：整体的考虑对于当前需要放置的数插在已经生成数列的前后对后续的操作贡献没有影响，我们只需要保证当前数插入时新增加的逆序对数最少即可。所以用树状数组维护逆序数，插在前面新增的贡献就是生成数列中比当前数小的数的数量，插在后面新增的贡献就是生成数列中比当前大的数的数量，哪边贡献少插哪边

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
const int maxn = 2e5 + 5;
 
int n;
int a[maxn], b[maxn];  //离散化后的数组
int c[maxn];           //树状数组
 
struct node {
    int val, id;
} in[maxn];
 
int lowbit(int i) {
    return i & (-i);
}
 
void update(int i, int k) {
    while (i <= n) {
        c[i] += k;
        i += lowbit(i);
    }
}
 
int getsum(int i) {
    int res = 0;
    while (i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}
 
void test_case() {
    cin >> n;
    //存值
    for (int i = 1; i <= n; i++) {
        cin >> a[i];  //a[]到时候还得用来索引
        b[i] = a[i];  //生成a[]的副本
    }
    //排序
    sort(b + 1, b + 1 + n);
    //去重
    int len = unique(b + 1, b + 1 + n) - b - 1;  //len为去重后的数组长度
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;  //赋给离散的值
 
    int maxx = 0;
    for (int i = 1; i <= n; ++i)
        maxx = max(maxx, a[i]);
    //树状数组求逆序
    memset(c, 0, sizeof(c));
    long long ans = 0;  //要是处理很多数，即使离散化了也很可能超出int范围
    for (int i = 1; i <= n; i++) {
        update(a[i], 1);  //1代表该位置数存在
        ans += min(i - getsum(a[i]), getsum(a[i] - 1));
    }
    cout << ans << endl;
}

F.Array Stabilization (AND version)—贪心+BFS搜索

题意：给定一个循环 01 数组下标从 0 到 n-1，每次操作是让各个位置上的数和往后循环的第 d 个位置上的数做并运算并放在后者位置上，需要几次操作才能让整个数组只有 0

思路：之前做过一个 GCD 版本的是用 ST 表和二分，这题同理先寻找隐藏性质。如果某个位置是 0 那么这个位置永远是 0，同时它会每次在循环移动时将遇到的 1 变为 0。所以我们模拟上述过程，从每个位置初始为 0 的位置开始模拟每重循环移动的操作（中间遇到 0 不考虑，遇到 1 就 变为 0 并将产生的新 0 往后模拟）直至结束，用 BFS + 优先队列维护每次取步数最小的下标向后循环移动，每个点最多进入一次队列所以时间复杂度 O(nlogn) 可行

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
const int maxn = 1e6 + 5;
 
int n, d;
int a[maxn];
 
void test_case() {
    cin >> n >> d;
    for (int i = 0; i <= n - 1; ++i) cin >> a[i];
    int res = 0;
    priority_queue<pii, vector<pii>, greater<pii> > que;  //大顶堆每次选择循环次数最小的
    for (int i = 0; i <= n - 1; ++i)
        if (!a[i]) que.push({0, i});  //循环次数和0的位置
 
    while (que.size()) {
        auto now = que.top();
        que.pop();
 
        int nex = (now.second + d) % n;
        if (!a[nex])
            continue;
        else {
            a[nex] = 0;
            que.push({now.first + 1, nex});
            res = max(res, now.first + 1);
        }
    }
 
    bool flag = true;
    for (int i = 0; i <= n - 1; ++i)
        if (a[i]) {
            flag = false;
            break;
        }
    if (flag)
        cout << res << endl;
    else
        cout << -1 << endl;
}

G.Minimal Coverage—bitset+DP

题意：依次给出 n 个跳跃长度，第一次跳跃已知从 x 轴的 0 下标向右跳，以后的每次跳跃从上次跳跃的落点选择向左或者向右跳，请问跳跃过程中最左端和最右端距离的最小值是多少

思路：显然答案线段具有二分性质，我们每二分一次线段判断是否可行。记布尔类型 dp[i][j] 表示第 i 次跳跃是否能到达线段最左端点的 j 处，那么转移方程就是 dp[i][j]=dp[i-1][j-a[i-1]]|dp[i-1][j+a[i]]，第一次跳跃可以在这个线段任意位置所以初始化 dp[][] 为全 1，为了防止跳出该线段我们每次更新后的数组和上次数组做一个并操作，同时利用 bitset 滚动降维。

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
int n, a[maxn];

bool check(int x) {
    bitset<2005> dp, tmp;
    for (int i = 0; i <= x; ++i) dp[i] = 1;
    tmp = dp;                       //记录当前轮情况
    for (int i = 1; i <= n; ++i) {  //滚动数组求下一轮情况
        dp = (dp << a[i]) | (dp >> a[i]);
        dp &= tmp;  //防止跳出界用上一轮限制一下
    }
    return dp.any();
}

void test_case() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int l = 0, r = 2001;
    while (l < r) { //找下界
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
}