2022 CCPC 桂林 (22-10-30) B

2022 CCPC 桂林

2022 China Collegiate Programming Contest (CCPC) Guilin Site

B - Code With No Forces

prob. : 背景是在出题，有m份测试代码，n个样例（有序），每份代码对于每个测试点都有一个状态，格式是{verdict/max time/max memory}；每份代码跑完所有样例也会有一个状态，同样的格式，定义AC代码的max time是所有样例中花费最大的time，（memory同理），没有AC的代码是到第一个没有AC的点为止的最大的time和memory，verdict显示的是第一个没有AC的点的verdict（。现在给你n个样例和m份代码的状态，求在不改变每份代码的最终状态的情况下保留尽可能少的测试点（可以交换测试点的顺序），输出方案。

n 400， m 6， time memory 10000

ideas：

考虑状压dp

对于每份代码是否满足verdict、是否满足time、是否满足memory可以用3个位来表示状态，整个题目共$2^{3m}$个状态

感性地想一下，verdict 是否是AC的是需要分开考虑的，time和memory是独立且对称的

考虑依次接受测试点，对于每份代码来说的限制

对于一份代码来说，verdict为非AC的话，能接受的测试点的verdict为AC或同样的verdic；verdict为AC的话，能接受的测试点的verdict仅为AC。测试点的time和memory小于等于本身最终状态的time和memory。

对于一个测试点来说，状态{verdict/time/memory}

变成大分讨

• 测试点verdictAC，代码最终verdict也AC，满足verdict
  • 判断时间空间是否满足
  • 如果时间空间有超的，对于这份代码来说可以pass掉这个测试点、
  • 如果时间或空间有不足的，没有影响
• 测试点verdict非AC，代码最终verdict一致，满足verdict
  • 判断时间空间是否满足
  • 如果时间空间有超的，对于这份代码来说，需要在该测试点之前就满足所有的条件，以忽视这个测试点
  • 如果时间或空间有不足的，需要在该测试点之前就满足时间或空间条件
• 测试点verdictAC，代码最终verdict不一致
  • 判断时间空间是否满足
  • 如果时间空间有超的，对于这份代码来说，需要在该测试点之前就满足所有的条件，以忽视这个测试点
  • 如果时间或空间有不足的，没有影响
• 测试点verdict非AC，代码最终verdict不一致
  • 需要在该测试点之前就满足所有的条件，以忽视这个测试点

已经是穷举了，觉得太烦也可以看下官方std，感觉那个很简洁（。

然后感性地想一下类似最短路，源点是全0这个状态，终点是全1这个状态，每个测试点可以给一些点连有向边（？，由于是状态是有顺序的，可以直接状压dp

说实话写这个题写的我脑子有点混乱如果哪里说错了欢迎指正

code：

#include 

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;

int situation[10][4];
int test[500][20];
int sat[500], pre[500];
int dp[(1 << 18) + 10], pa[(1 << 18) + 10], edge[(1 << 18) + 10];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    auto getSituation = [&](string s) {
        int p1 = s.find(',');
        int p2 = s.find('/');
        string tmpt = s.substr(p1 + 1, p2 - p1 - 1);
        string tmpm = s.substr(p2 + 1);
        pair<int, pair<int, int> > res;
        if (s[0] == 'O') res.first = 0;
        if (s[0] == 'W') res.first = 1;
        if (s[0] == 'T') res.first = 2;
        if (s[0] == 'M') res.first = 3;
        if (s[0] == 'R') res.first = 4;
        res.second.first = atoi(tmpt.c_str());
        res.second.second = atoi(tmpm.c_str());
        return res;
    };

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            string s;
            cin >> s;
            auto vec = getSituation(s);
            test[i][j * 3] = vec.first;
            test[i][j * 3 + 1] = vec.second.first;
            test[i][j * 3 + 2] = vec.second.second;
            if (situation[j][0] != 0) continue;
            situation[j][0] = vec.first;
            situation[j][1] = max(situation[j][1], vec.second.first);
            situation[j][2] = max(situation[j][2], vec.second.second);
        }
    }

    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {

            if (test[i][j * 3] == 0) {
                if (test[i][j * 3] == situation[j][0]) {
                    if (test[i][j * 3 + 1] > situation[j][1] || test[i][j * 3 + 2] > situation[j][2])
                        continue;
                    sat[i] |= 1 << (3 * j);
                    if (test[i][j * 3 + 1] == situation[j][1]) sat[i] |= 1 << (3 * j + 1);
                    if (test[i][j * 3 + 2] == situation[j][2]) sat[i] |= 1 << (3 * j + 2);
                } else {
                    if (test[i][j * 3 + 1] == situation[j][1]) sat[i] |= 1 << (3 * j + 1);
                    if (test[i][j * 3 + 2] == situation[j][2]) sat[i] |= 1 << (3 * j + 2);
                    if (test[i][j * 3 + 1] > situation[j][1] || test[i][j * 3 + 2] > situation[j][2])
                        pre[i] |= 1 << (3 * j);
                }
            }
            else {
                if (test[i][j * 3] == situation[j][0]) {
                    sat[i] |= 1 << (3 * j);
                    if (test[i][j * 3 + 1] == situation[j][1]) sat[i] |= 1 << (3 * j + 1);
                    if (test[i][j * 3 + 2] == situation[j][2]) sat[i] |= 1 << (3 * j + 2);
                    if (test[i][j * 3 + 1] > situation[j][1] || test[i][j * 3 + 2] > situation[j][2])
                        pre[i] |= 1 << (3 * j);
                    if (test[i][j * 3 + 1] < situation[j][1]) pre[i] |= 1 << (3 * j + 1);
                    if (test[i][j * 3 + 2] < situation[j][2]) pre[i] |= 1 << (3 * j + 2);
                }
                else {
                    pre[i] |= 1 << (3 * j);
                }
            }

        }
    }

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int st = 0; st < (1 << (3 * m)); ++st) {
        if (dp[st] == inf) continue;
        for (int i = 0; i < n; ++i) {
            if ((st | sat[i]) == st) continue;
            if ((st & pre[i]) ^ pre[i]) continue;
            if (dp[st | sat[i]] > dp[st] + 1) {
                dp[st | sat[i]] = dp[st] + 1;
                pa[st | sat[i]] = st;
                edge[st | sat[i]] = i + 1;
            }
        }
    }

    vector<int> ans;

    int p = (1 << (3 * m)) - 1;
    while (p) {
        ans.push_back(edge[p]);
        p = pa[p];
    }
    reverse(ans.begin(), ans.end());

    cout << ans.size() << endl;
    for (auto x: ans) cout << x << " ";
}
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110