Codeforces Round 870 (Div. 2)题解（5/6)_piifog

作者：知新_RL | 2024-05-01 13:41:21

踩

piifog

A.Trust Nobody

题意：
$n$ 个人，有人说谎，有人说真话，每个人都告诉你至少有 $l_i$ 个人说谎，问是否矛盾，否则输出可能的说谎的人数。

思路：
暴力枚举说谎人数，判断有多少个人说谎即可。

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()


int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            int x;
            cin >> x;
            a[x]++;
        }
        for (int i = 1; i <= n; ++i) {
            a[i] +=  a[i - 1];
        }
        bool f = 0;
        for (int i = 0; i <= n; ++i) {
            if (i == n - a[i]) {
                f = 1;
                cout << i << "\n";
                break;
            }
        }
        if (!f) {
            cout << -1 << '\n';
        }
    }
    return 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

B.Lunatic Never Content

题意：
$f (a, x) = (a 1 m o d x .... anm o d x)$ ，问最大的x使得成回文。

思路：考虑 $am o d x = bm o d x$ ，且 $x$ 属于 $[a, b]$ ,不难推出 $t x = ab s (a - b)$ , 所以每个限制等于告诉你我都要是 $ab s (a - b)$ 的约数，做 $g c d$ 即可。

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()


int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 2);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        int ans = 0;
        for (int i = 1, j = n; i <= j; i++, j--) {
            ans = __gcd(ans, abs(a[i] - a[j]));
        }
        cout << ans << '\n';
    }
    return 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

C.Dreaming of Freedom

题意： $n$ 个人投票，给 $m$ 个人，问是否存在永远平局的情况。

思路：
$n <= m$ , 显然可以，除了 $n == 1$ ,
否则枚举 $n$ 的约数a看 $m >= a$ 是否成立即可

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()


int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n == 1) {
            cout << "YES\n";
        } else if (n <= m) {
            cout << "NO\n";
        } else {
            bool f = 0;
            for (int i = 2; i * i <= n; ++i) {
                if (n % i == 0) {
                    if (m >= i) {
                       f = 1;
                       break; 
                    }
                }
            }
            cout << (f ? "NO\n" : "YES\n");
        }
    }
    return 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

D.Dreaming of Freedom

题意:
定义 $f (l, r)$ = (区间最大的三个值 - $(r - l))$ ，问最大的 $f (l, r)$
思路：

显然区间的左右端点必选，所以左右端点贡献分别为 $a [i] + i$ , $a [i] - i$ ,暴力枚举中间端点分别对这两个贡献数组做前后缀最大值即可。
考虑类似银川 $B$ 的 $t r i c k$ , 由于值的数量很少，我们暴力dp出其贡献，具体来说就是 $d p [i] [0/1/2/3]$ , 表示当前区间选了前三个数/or不选的最大值，左右端点的贡献为 $a [i] + / - i$ , 暴力转移即可。

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()


int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> b(n + 2), sum1(n + 2), sum2(n + 2);
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
            sum1[i] = b[i] + i;
            sum2[i] = b[i] - i;
        }
        for (int i = 2; i <= n; ++i) {
            sum1[i] = max(sum1[i - 1], sum1[i]);
        }
        for (int i = n - 1; i >= 1; --i) {
            sum2[i] = max(sum2[i + 1], sum2[i]);
        }
        int ans = 0;
        for (int i = 2; i + 1 <= n; ++i) {
            ans = max(ans, b[i] + sum1[i - 1] + sum2[i + 1]);
        }
        cout << ans << '\n';
    }
    return 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

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()

const int maxn = 1e5 + 5;
int dp[maxn][4];

int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1, x; i <= n; ++i) {
            cin >> x;
            for (int j = 0; j <= 3; ++j)
                dp[i][j] = dp[i - 1][j];
            dp[i][1] = max(dp[i][1], dp[i - 1][0] + x + i);
            dp[i][2] = max(dp[i][2], dp[i - 1][1] + x);
            dp[i][3] = max(dp[i][3], dp[i - 1][2] + x - i);
        }
        cout << dp[n][3] << '\n';
    }
    return 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

E.Dreaming of Freedom

题意: $m$ 场演出， $n$ 个模特，每个模特一个费用， $m$ 场演出每个模特有不同的rank, 要求选出模特的子集后重排列使得 $m$ 场演出的rank严格递增，且费用最大。

思路：
显然有个 $n^2$ 的 $d p$ , $d p [i]$ 表示最后结尾的是 $i$ 这个模特的最大值，如果知道每个模特后面能跟谁，就相当于在一个dag上 $d p$ , $O(n^2)$ 即可，这个每个模特后面能跟谁也显然有个 $O(n^2 m)$ 的做法，两两枚举 $n$ ，但是这样无法优化。我们发现这个关系 $a < b ， b < c 则 a < c$ , 满足偏序关系，所以排序后一定是dag图，那么我们考虑对每一个 $m$ 做倒序排序， $f [i] [j]$ 表示 $i$ 后面能跟谁，我们在这个 $d a g$ 图上转移是 $O (n)$ 的，我们可以通过dag图上转移使得一次转移第二维的所有位数，第二维 $bi t se t$ 优化即可做到O(n/64), 最后按拓扑序再 $d p$ 一下即可。
时间复杂度 $O(n ^ 2m/64)$ ，好久没 $bi t se t$ vp的时候差点没写完，该找时间写些 $bi t se t$ 的题了

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()

const int maxn = 5005;
bitset<5000> dp[maxn];
PII a[maxn];

vector<int> G[maxn];
int deg[maxn];

int main() {
    IOS
    int m, n;
    cin >> m >> n;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                dp[i].set(j);
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            a[j].second = j - 1;
            cin >> a[j].first;
        }
        sort(a + 1, a + 1 + n, [&](PII x, PII y) {
            return x.first > y.first;
        });
        bitset<5000> b;
        vector<int> tmp;
        for (int j = 1; j <= n; ++j) {
            tmp.emplace_back(a[j].second);
            if (j == n || a[j].first != a[j + 1].first) {
                for (auto &x : tmp) {
                    dp[x] &= b;
                }
                for (auto &x : tmp) {
                    b.set(x);
                }
                tmp.clear();
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = dp[i]._Find_first(); j < n; j = dp[i]._Find_next(j)) { 
                G[i].emplace_back(j);
                deg[j]++;
        }
    }
    queue<int> q;
    vector<ll> f(n + 2, 0);
    for (int i = 0; i < n; ++i) {
        if (!deg[i]) {
            f[i] = p[i  + 1];
            q.push(i);
        }
    }
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (auto u : G[x]) {
            f[u] = max(f[u], f[x] + p[u + 1]);
            if (--deg[u] == 0) {
                q.push(u);
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

F.Fading into Fog

待补

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/519127