Codeforces Round 869 (Div.1 & Div.2) 题解
2A. Politics
因为编号为 \(1\) 的人一定不会离开，那么最后留下的人一定要和编号为 \(1\) 的人的所有参数都一致，所以计数即可。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
int x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
return !f ? x : -x;
}
char s[105][105];
int n, k;
signed main () {
int _ = read ();
while (_ --) {
n = read (), k = read ();
for (int i = 1;i <= n; ++ i) scanf ("%s", s[i] + 1);
int ans = 1;
for (int i = 2;i <= n; ++ i) {
int ok = 1;
for (int j = 1;j <= k; ++ j) {
if (s[i][j] != s[1][j]) ok = 0;
}
ans += ok;
}
printf ("%d\n", ans);
}
return 0;
}
2B. Indivisible
我们可以写一个 \(O(n!)\) 的暴力打出表来，然后就发现无解条件是 \(n > 1\) 且 \(n \bmod 2 = 1\)。
然后分成两种情况：
-
如果 \(n = 1\)，那么答案为 \([1]\)。
-
否则答案为 \([2, 1, 4, 3, \dots, 2n, 2n - 1]\)。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
int x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
return !f ? x : -x;
}
int a[105], _, n, sum[105];
signed main () {
_ = read ();
while (_ --) {
n = read ();
if (n == 1) {
printf ("1\n");
continue;
}
if (n & 1) {
printf ("-1\n");
continue;
}
for (int i = 1, j = 2;i <= n; i += 2, j += 2) a[i] = j;
for (int i = 2;i <= n; i += 2) a[i] = a[i - 1] - 1;
for (int i = 1;i <= n; ++ i) printf ("%d ", a[i]);
printf ("\n");
}
return 0;
}
2C/1A. Almost Increasing Subsequence
我们首先考虑长度为 \(r - l + 1\) 不合法在哪里。
我们要把满足 \(a_{i} \geq a_{i + 1} \geq a_{i + 2}\) 全部删掉，只需要将把 \(l \leq i \leq r - 2\) 并且 \(a_{i} \geq a_{i + 1} \geq a_{i + 2}\) 的 \(i\) 全部删掉。
直接前缀和即可。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
int x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
return !f ? x : -x;
}
int n, q, a[200005], s[200005];
signed main () {
n = read (), q = read ();
for (int i = 1;i <= n; ++ i) a[i] = read ();
for (int i = 1;i <= n; ++ i) {
s[i] = s[i - 1];
if (a[i] >= a[i + 1] && a[i + 1] >= a[i + 2] && i + 2 <= n) s[i] ++;
}
while (q --) {
int l = read (), r = read (), ans = r - l + 1;
int L = l, R = r - 2;
if (L <= R) {
int d = s[R] - s[L - 1];
ans -= d;
}
printf ("%d\n", ans);
}
return 0;
}
2D/1B. Fish Graph
我们考虑将每一个连通块分开处理，对于每一个连通块，取出其中任意一个生成树，拎出来每一个返祖边，然后就构成了一个环，枚举每一个点（是点 \(u\)），判断是不是一个 Fish Garph 即可。
代码非常难写，有 114514 个细节，需要注意。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
int x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
return !f ? x : -x;
}
const int N = 2005;
struct LCAns {
struct edge {int to, nxt;} e[N << 1];
int head[N], eid;
inline void add_edge (int u, int v) {e[eid] = {v, head[u]}; head[u] = eid ++;}
int dp[N][17], d[N], lg[N];
int n, root;
inline void dfs (int u) {
for (int i = head[u]; ~i ; i = e[i].nxt) {
int v = e[i].to;
if (v == dp[u][0]) continue;
dp[v][0] = u; d[v] = d[u] + 1; dfs (v);
}
}
inline int LCA (int u, int v) {
if (d[u] < d[v]) swap (u, v);
for (int j = lg[d[u] - d[v]];j >= 0; -- j) {if (d[dp[u][j]] >= d[v]) u = dp[u][j];}
if (u == v) return u;
for (int j = lg[d[u]];j >= 0; -- j) {if (dp[u][j] != dp[v][j]) {u = dp[u][j], v = dp[v][j];}}
return dp[u][0];
}
inline void perf () {
for (int i = 0;i < N; ++ i) head[i] = -1;
eid = 0;
}
inline void pre () {
lg[0] = -1;
for (int i = 1;i <= n; ++ i) dp[i][0] = 0, d[i] = 0;
for (int i = 1;i <= n; ++ i) lg[i] = lg[i / 2] + 1;
d[root] = 1; dfs (root);
for (int j = 1; (1 << j) < n; ++ j) for (int i = 1;i <= n; ++ i) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
} tr;
int ed[N][2], n, m, vis[N], vis2[N], fl[N];
struct DSU {
int fa[N];
inline void init (int X) {
for (int i = 1;i <= X; ++ i) fa[i] = i;
}
inline int find (int x) {
return fa[x] == x ? x : fa[x] = find (fa[x]);
}
inline void merge (int x, int y) {
fa[find (x)] = find (y);
}
inline int query (int x, int y) {
return find (x) == find (y);
}
} awa, qwq;
vector < pair < int, int > > th;
vector < int > G2[N], G[N];
signed main () {
int _ = read ();
while (_ --) {
n = read (), m = read ();
for (int i = 1;i <= n; ++ i) vis[i] = 0;
for (int i = 1;i <= m; ++ i) vis2[i] = 0;
awa.init (n);
for (int i = 1;i <= m; ++ i) {
ed[i][0] = read (), ed[i][1] = read ();
awa.merge (ed[i][0], ed[i][1]);
G[ed[i][0]].push_back (ed[i][1]);
G[ed[i][1]].push_back (ed[i][0]);
}
int ok = 0;
for (int i = 1;i <= n; ++ i) {
if (vis[i]) continue;
tr.n = n, tr.root = i;
tr.perf ();
vector < int > _edge, ex;
_edge.clear ();
ex.clear ();
qwq.init (n);
for (int j = 1;j <= m; ++ j) {
if (!awa.query (i, ed[j][0]) || !awa.query (i, ed[j][1])) continue;
if (qwq.query (ed[j][0], ed[j][1])) {
ex.push_back (j);
continue;
}
tr.add_edge (ed[j][0], ed[j][1]);
tr.add_edge (ed[j][1], ed[j][0]);
G2[ed[j][0]].push_back (ed[j][1]);
G2[ed[j][1]].push_back (ed[j][0]);
vis2[j] = 1;
vis[ed[j][0]] = vis[ed[j][1]] = 1;
_edge.push_back (j);
qwq.merge (ed[j][0], ed[j][1]);
}
tr.pre ();
for (int E : ex) {
int U = ed[E][0], V = ed[E][1];
int Z = tr.LCA (U, V);
for (int j = 1;j <= n; ++ j) fl[j] = 1;
vector < int > vertex;
vertex.clear ();
int tot = 1;
for (int j = U; j != Z; j = tr.dp[j][0]) vertex.push_back (j), tot ++;
for (int j = V; j != Z; j = tr.dp[j][0]) vertex.push_back (j), tot ++;
vertex.push_back (Z);
for (int u : vertex) fl[u] = 0;
for (int u : vertex) {
th.clear ();
for (int v : G[u]) {
if (fl[v]) th.push_back (make_pair (u, v));
}
if (th.size () >= 2) {
tot += 2;
printf ("YES\n");
ok = 1;
printf ("%d\n", tot);
for (int j = U; j != Z; j = tr.dp[j][0]) printf ("%d %d\n", j, tr.dp[j][0]);
for (int j = V; j != Z; j = tr.dp[j][0]) printf ("%d %d\n", j, tr.dp[j][0]);
printf ("%d %d\n", U, V);
printf ("%d %d\n", th[0].first, th[0].second);
printf ("%d %d\n", th[1].first, th[1].second);
break;
}
}
if (ok) break;
}
for (int j = 1;j <= n; ++ j) G2[j].clear ();
if (ok) break;
}
if (!ok) printf ("NO\n");
for (int i = 1;i <= n; ++ i) G[i].clear ();
}
return 0;
}