A Medium Number

题意

三个数，输出中位数。

思路

排序

input

9
5 2 6
14 3 4
20 2 1
1 2 3
11 19 12
10 8 20
6 20 3
4 1 3
19 8 4

output

5
4
2
2
12
10
6
3
8

代码

int n, m;
int a[N];void solve() {n = 3;for (int i = 0; i < 3; i++) cin >> a[i];sort(a, a + 3);cout << a[1] << endl;
}

---

B Atilla’s Favorite Problem

题意

找到最大字符，对应如下输出：‘a’ -> 1；‘b’ -> 2；…；‘z’ -> 26；

思路

维护最大值

input

5
1
a
4
down
10
codeforces
3
bcf
5
zzzzz

output

1
23
19
6
26

代码

int n, m;
int a[N];void solve() {int n; cin >> n;string s; cin >> s;int mx = -1;for (auto c: s) {mx = max(mx, (int)(c - 'a') + 1);}cout << mx << endl;
}

---

C Advantage

题意

输出每个数 - 除自己之外的最大值。

思路

维护最大和次大，排序。

input

5
4
4 7 3 5
2
1 2
5
1 2 3 4 5
3
4 9 4
4
4 4 4 4

output

-3 2 -4 -2
-1 1
-4 -3 -2 -1 1
-5 5 -5
0 0 0 0

代码

int n, m;
int a[N], b[N];void solve() {int n; cin >> n;int x = -1, mx = -1;rep (i, 1, n) cin >> a[i], b[i] = a[i], x = max(x, a[i]);sort(b + 1, b + 1 + n);mx = b[n - 1];rep (i, 1, n) if(a[i] == x) cout << x - mx << ' '; else cout << a[i] - x << ' '; cout << endl;
}

---

D Challenging Valleys

题意

问是否仅存在一个子数组，满足：

• $a_l=a_{l+1}=...=a_r$
• $l=0$ 或者 $a_{l-1}>a_l$
• $r=n-1$ 或者 $a_{r+1}>a_r$

思路

如上条件，即一个 V 字型的尖尖，或者 _/ 的平段，或者 \_ 的平段。

统计这三种的个数，看是否最终为 1 即可。

便于统计，我们记数组 $1-n$，初始化 $a[0]=a[n+1]=INF$。

双指针，左端点固定，去移动右端点，直到这一段相等结束（条件1），判断上述 V 字型条件（条件2，3）即可。

input

6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10

output

YES
YES
NO
YES
YES
NO

代码

int n, m;
int a[N];
void solve() {cin >> n;rep (i, 1, n) cin >> a[i];int cnt = 0;a[0] = a[n + 1] = mod;int l = 1;for (int i = 2; i <= n + 1; i++) {while (i <= n && a[i] == a[l]) i++;if (a[l] < a[l - 1] && a[i - 1] < a[i]) cnt++;l = i;}if (cnt == 1 || n == 1) cout << "YES" << endl;else cout << "NO" << endl;
}

---

E Binary Inversions

题意

给你01字符串，问至多一次，反转一个字符（0-1,1-0），使得逆序对最大，输出最大个数。

思路

三种情况：

• 0次操作：

  • 直接统计逆序数即可，维护后缀0的数量，一次遍历，累加上位1的0的贡献。

• 1次操作：

  • 从前往后第一个0改1
  • 从后往前第一个1改0

input

5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1

output

3
7
1
13
2

代码

有点烂，不想改了，思路够清晰。

int n, m;
int a[N];void solve() {cin >> n;int res = 0;int zero = 0, one = 0;for (int i = 1; i <= n; i++) cin >> a[i], zero += 1 - a[i], one += a[i];int xx = zero;for (int i = 1; i <= n; i++) if (a[i] == 1) res += xx; else xx -= 1;int idx1 = 1;while (idx1 <= n && a[idx1] == 1) idx1++;if(idx1 <= n && a[idx1] == 0) a[idx1] = 1, zero -= 1, one += 1;int t = zero, res1 = 0;for (int j = 1; j <= n; j++) if (a[j] == 1) res1 += t; else t -= 1;if(idx1 <= n && a[idx1] == 1) a[idx1] = 0, zero += 1, one -= 1;int res2 = 0, idx = n;while (idx >= 1 && a[idx] == 0) idx--;if (idx >= 1 && a[idx] == 1) one -= 1, zero += 1, a[idx] = 0;t = zero;for (int j = 1; j <= n; j++) if (a[j] == 1) res2 += t; else t -= 1;cout << max({res, res1, res2}) << endl;

---

F Quests

题意

给定 $n，c，d$，表示任务数组大小 $n，d$ 天要赚至少 $c$ 元。每次工作了任务 $i$，那么接下来 $k$ 天，这个任务不可再做。问 $k$ 最大能是多少。

思路

最小的最大 ：二分答案

贪心的从大到小排序，维护前缀和。贪心的做任务获利高的任务，但每隔 $k$ 天才做下一次，所以一个周期做 $k+1$ 个任务（$d$ 很大则考虑这种写法，否则直接暴力 $d$ 天每次循环加上对应天下做的任务即可）。每次 $check$ 去判断，当前每个任务重做时间隔 $k$ 天，且在 $d$ 天内，能否获利 $c$ 元。

input

6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1

output

2
Infinity
Impossible
1
12
0

代码

• $check1$： 暴力加，循环节控制当天做的任务 $id$。
• $check$： $d$ 如果很大，则按周期加。

int n, m, c, d;
int a[N], s[N];bool check1(int x) {int res = 0;int now = 1;for (int i = 1; i <= d; i++) {if (now <= n) {res += a[now];now++;} if (i % (x + 1) == 0) {now = 1;}}return res >= c;
}bool check(int x) {x += 1;int pre = 0;if (x > n) pre = s[n];else pre = s[x];int now = 0, res = 0;while (now + x <= d) {res += pre;now += x;if (res >= c) return true;}for (int i = 1; i <= d - now && i <= n; i++) res += a[i];return res >= c;
}void solve() {cin >> n >> c >> d;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n, [=](int i, int j){ return i > j; });int z = 0; for (int i = 1; i <= min(n, d); i++) z += a[i];if (z >= c) { cout << "Infinity" << endl; return ; }if (d * a[1] < c) { cout << "Impossible" << endl; return ; }for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];int l = 0, r = 2e18;while (l < r) {int mid = (l + (r - l + 1) / 2);if (check(mid)) l = mid;else r = mid - 1;}cout << r << endl;
}

---

G SlavicG’s Favorite Problem

题意

$n$ 个点，$n-1$条边，边权 $w_i$。（每走一边，需要异或当前边权）。给定 $a,b$，问从 $a$ 出发，能否走往 $b$ 点。条件是仅当走到 $b$ 时，当前异或值为 $0$。并且，可以允许在路途中进行一次跳跃，即直接跳到任意除 $b$ 外的一点。

注意的是，但凡走到了 $b$ 就需要截止了（如果不为0，就走不到）。这意味着，从 $a$ 开始走，要想去往 $b$ 的子树下，仅能使用一次跳跃过去，而不能走过去。

思路

分别以 $a,b$ 为根节点，计算所有点到根节点的一个前缀异或值，记 $fa,fb$ 数组。（注意，这里 $a$ 为根节点的话，不能去往 $b$ 的子树）

对 $fa$ 数组，将所有可达点（$fa[i]!=-1$，包括 $a$ 本身【因为如果 $fb[a]=0$ 是直接可达的】，默认 $fa[a]=0$）统计进 $map$ 中。

对 $fb$ 数组，遍历所有点，判断如果当前点不是 $b$ 本身，且 $map$ 中存在 $fb[i]$ ，那么说明至多一次跳跃，可以让跳跃前异或值等于跳跃后异或值，走完到 $b$ 即异或为 $0$。

input

3
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5

output

YES
NO
YES

代码

int h[N], w[M], e[M], ne[M], idx; 
void add(int a, int b, int c = 1) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; 
} 
int n, a, b;
int fa[N], fb[N];
int root;
void dfs(int u, int f, int v) {if(root == a) fa[u] = v;else if(root == b) fb[u] = v;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (j == f) continue; if (root == a && j == b) continue; dfs(j, u, v ^ w[i]);}
}void solve() {memset(fa, -1, sizeof fa);memset(fb, -1, sizeof fb);memset(h, -1, sizeof h);cin >> n >> a >> b;for (int i = 0; i < n - 1;i ++) {int u, v, x; cin >> u >> v >> x;add(u, v, x), add(v, u, x);}root = a; fa[root] = 0;dfs(a, -1, 0);root = b; fb[root] = 0;dfs(b, -1, 0);map<int, int> mp;bool f = false;for (int i = 1; i <= n; i++) {if (i == b) continue; // 删掉也行吧，fa[b] == -1;else if(fa[i] != -1) mp[fa[i]] = 1;}for (int i = 1; i <= n; i++) {if (i == b) continue;else if (mp.count(fb[i])) f = true;}cout << (f ? "YES" : "NO") << endl;
}

---