intminimumDeletions(vector < int > a){ // Complete this function if (a.size() <= 2) return0; int ans = 0; int flag = a[1] > a[0], st = 0, ed = 1; for (int i = 2; i < a.size(); ++i) { if (flag) { if (a[i] > a[i - 1]) ed = i; else { flag = 0; ans += max(0, ed - st + 1 - 2); st = i - 1, ed = i; } } else { if (a[i] < a[i - 1]) ed = i; else { flag = 1; ans += max(0, ed - st + 1 - 2); st = i - 1, ed = i; } } } ans += max(0, ed - st + 1 - 2); return ans; }

intmain(){ int n; cin >> n; vector<int> a(n); for(int a_i = 0; a_i < n; a_i++)cin >> a[a_i]; int result = minimumDeletions(a); cout << result << endl; return0; }

Maximal AND Subsequences

Given an arry with $n\leq 10^5$ long integers $A_{i}\leq 10^{18}$, try to find all the $k$-element subsequences of $A$ where the bitwise AND of the subsequence’s elements is maximal.

This problem is very common actually, and I lost my mind during that time.

We can use a greedy strategy, due to the truth that: $$ 2^{i} > 2^{i-1}+2^{i-2}+\cdots + 2^{0} $$

We consider the bits in number two system from high to low. For each bit, we calculate the number of elements whose expression at the bit is 1. If the number is larger than or equal to $k$, then we need to delete all other elements whose expression at the bit is 0. That means the maximal AND value must result from those bit-1 elements. The elements left last make up a set from which we can choose $k$ elements.

I choose the data structure multiset to support the delete operation. But vector, list and so on are optional.

#include<bits/stdc++.h> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); usingnamespacestd; typedeflonglong ll; #define mp make_pair #define fi first #define se second #define pb push_back

voidinit(){ ans[1][1] = 1; for (int i = 2; i < MAX_N; ++i) { for (int j = 1; j <= i; ++j) { if (j * 2 - 1 <= i) upd(ans[i][j], 2 * j * ans[i - 1][j]); int t = i - 2 * j; if ((j + 1) * 2 - 1 <= i && t > 0) upd(ans[i][j + 1], t * ans[i - 1][j]); } }

for (int i = 1; i < MAX_N; ++i) { for (int j = 1; j <= i; ++j) { upd(ans[i][j], ans[i][j - 1]); } } }

intmain(){ init(); int Q, n, K; cin >> Q; while (Q--) { cin >> n >> K; cout << ans[n][n - K] << endl; } return0; }

Maximum Disjoint Subtree Product

This is a tree-dp problem with two times dfs. Be in a clear mind while coding this problem. I spent nearly two hours finishing it, and got accepted at the second sumbit (the first submit failed because I forgot to add one line code for dfs2() function).

intmain(){ cin >> n; for (int i = 1; i <= n; ++i) cin >> val[i]; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; G[u].pb(v); G[v].pb(u); } dfs1(1, 0); ans = 0;

To be honest this is a old problem as it is the same meaning with CF196 C. I have seen it about one month before. So copy and paste may be a good choice. 23333.

#include<bits/stdc++.h> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); usingnamespacestd; typedeflonglong ll; #define mp make_pair #define fi first #define se second #define pb push_back

voiddfs(int u, int p){ sz[u] = 1; for (int v: G[u]) if (v != p) { dfs(v, u); sz[u] += sz[v]; } }

voiddfs2(int u, int p, int st, int ed){ int leftCorner = st; ori.fi = ori.se = INF; for (int i = st; i <= ed; ++i) { if (P[i].x < ori.fi || (P[i].x == ori.fi && P[i].y < ori.se)) { leftCorner = i; ori.fi = P[i].x, ori.se = P[i].y; } }

swap(P[st], P[leftCorner]); sort(P + st + 1, P + ed + 1); // ans[P[st].id] = u; ans[u] = P[st].id;

int count = 0; for (int v: G[u]) if (v != p) { dfs2(v, u, st + count + 1, st + count + sz[v]); count += sz[v]; } }

intmain(){ cin >> n; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; G[u].pb(v); G[v].pb(u); } for (int i = 0; i < n; ++i) cin >> P[i].x >> P[i].y, P[i].id = i + 1; dfs(1, -1); dfs2(1, -1, 0, n - 1); for (int i = 1; i <= n; ++i) { cout << ans[i] << (i == n ? '\n' : ' '); } return0; }