A. False Alarm
从第一次需要开门统计，看 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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
bool flag = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 1 && m <=0) {
cout << "NO\n";
return;
}
if(!flag && a[i] == 1) {
flag = 1;
}
if (flag) m--;
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
B. Shrink
显然低的放两侧，高的在中间
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
deque<int> q;
for (int i = n;i > 0; i--) {
if(i&1) {
q.push_front(i);
} else {
q.push_back(i);
}
}
for (auto x : q) cout << x << " ";
cout << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
C. Cool Partition
贪心，前一段所有数在当前段中出现过后，就切一刀
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 2e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> a(n), lst(n + 10, -1);
for (int i = 0; i < n; i++) {
cin >> a[i];
lst[a[i]] = i;
}
unordered_set<int> s;
int pos = 0, ans = 0;
while (pos < n) {
unordered_set<int> cur, tmp = s;
int cha = tmp.size();
int mn = n + 1;
int i = 0;
for (i = pos; i < n; i++) {
int v = a[i];
if (cur.insert(v).second) mn = min(mn, lst[v]);
if (tmp.erase(v)) --cha;
if(cha == 0 && mn > i) {
++ans;
s.swap(cur);
pos = i + 1;
break;
}
}
if (i >= n) {
ans++;
break;
}
}
cout << ans <<endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
D. Retaliation
观察到两种操作，如果同时使用，每一位都会减去 n + 1, 所以差异出现在单独使用某种操作的次数。
假设多使用的是操作一，可以发现，如果要使最终数组都为 0，那么一定是单调递增数列。
反之，一定是单调递减数列。
每次操作一，都会使相邻两个数差值减少 1，操作的次数就是这个差值的大小。
同时，第一项要能进行 n 次操作。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> a(n + 10);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int d = a[2] - a[1];
for (int i = 2; i < n; i++) {
if (a[i + 1] - a[i] != d) {
cout << "NO\n";
return;
}
}
ll tmp = a[1] + 1ll * n * d;
int t = n + 1;
if (tmp % t) {
cout << "NO\n";
return;
}
int x = tmp / t, y = x - d;
if(x >= 0 && y >= 0) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
E. Lost Soul
糖了，看半天没看出来写 F 去了。
如果 $a_i=b_i$，那么二者前方的所有元素都可以转化相等。
如果 $a_i=a_j$，不管 j - i 是奇还是偶，都能通过一次删除操作使相差为奇，通过操作使得 $a_i=b_i$。
如果 $a_i=b_j$，可按照上面的操作转移为 $a_i=b_i$，但要注意 i + 1 != j。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
map<int,int> ca, cb;
for (int i = 0; i < n; i++) {
cin >> a[i];
ca[a[i]]++;
}
for (int i = 0; i < n; i++) {
cin >> b[i];
cb[b[i]]++;
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) ans = max(ans, i + 1);
ca[a[i]]--;
if (ca[a[i]] > 0) {
ans = max(ans, i + 1);
}
cb[b[i]]--;
if (cb[b[i]] > 0) {
ans = max(ans, i + 1);
}
}
for (int i = 0; i < n; i++) {
ca[a[i]]++;
cb[b[i]]++;
}
for (int i = 0; i < n - 1; i++) {
ca[a[i]]--;
cb[b[i]]--;
if (cb[a[i]] > 0 && b[i + 1] != a[i] || cb[a[i]] > 1) ans = max(ans, i + 1);
if (ca[b[i]] > 0 && a[i + 1] != b[i] || ca[b[i]] > 1) ans = max(ans, i + 1);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
F. Wildflower
注意到，每个点只可能为 1 或 2，如果叶子节点数量大于 2，就会有重复。
所以叶子节点数量只能是 1 或 2。
这两种情况都可视作一整条链，为 1 时，是根为 1 的一条链，反之，在中间某一点处断开。
叶子节点数量为 1 时，每个点任意取，即为 $2^n$。
叶子节点数量为 2 时，LCA 上方任意取 $2^k$;
下方先找两条链的长度 l1, l2，
两条链同时从下方开始看，记 $t_i$ 为长度为 i 时的两侧子树和的差值，那么 $t_{i+1} = t_i + (x-y)$，同时要求 t != 0;
手玩可以得到这种情况可能有 4 种，如果长度不相等，避免上方撞回 0，则只有 3 种，
所以此时答案为 $F(l_1,l_2)= \begin{cases} 4, l_1=l_2 \ 3 \cdot2^d, d=|l_1-l_2|>0 & \end{cases}$
再乘上前面的即可
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void solve() {
int n;
cin >> n;
vector<int> g[n + 1];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> dep(n + 1, 0), fa(n + 1, 0);
deque<int> q;
q.push_back(1);
fa[1] = 0;
dep[1] = 0;
while (!q.empty()) {
int u =q.front();
q.pop_front();
for (auto v : g[u]) {
if (v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
q.push_back(v);
}
}
vector<int> tmp;
for (int i = 2; i <= n; i++) {
if(g[i].size() == 1) tmp.push_back(i);
}
if (tmp.size() >= 3) {
cout << "0\n";
return;
}
if (tmp.size() == 1) {
cout << qpow(2, n) << endl;
return;
}
int a = tmp[0], b = tmp[1];
int u = a, v = b;
while (dep[u] > dep[v]) {
u = fa[u];
}
while (dep[v] > dep[u]) {
v = fa[v];
}
while (u != v) {
u = fa[u];
v = fa[v];
}
int k = dep[u];
int l1 = dep[a] - k;
int l2 = dep[b] - k;
int d = abs(l1 - l2);
ll t;
if (d == 0) {
t = 4;
} else t = 3 * qpow(2, d) % mod;
cout << t * qpow(2, k) % mod <<endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
G. Omg Graph
dijkstra 变换解决，最短路储存的当前路径上的最长边。
以 1 和 n 各为起点跑一次，再遍历边，假设当前边是 min，max 一定出现在 mx1, mxn, w 三者之中。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, m;
cin >> n >> m;
vector<pair<ll,ll>> g[n + 1];
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
auto dijkstra = [&](int st) {
vector<ll> mx(n+1, 1e18 + 10), vis(n+1, 0);
mx[st] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, st});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto [v, w] : g[u]) {
if (mx[v] > max(d, w)) {
mx[v] = max(d, w);
pq.push({mx[v], v});
}
}
}
return mx;
};
vector<ll> mx1 = dijkstra(1);
vector<ll> mx2 = dijkstra(n);
ll ans = 1e18 + 10;
for (int i = 1; i <= n; i++) {
for (auto [v, w] : g[i]) {
ans = min(ans, max({mx1[i], mx2[v], w}) + w);
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|