A - Maximum Increase
题意：给定一个 \(n\) 个整数组成的数组，找到给定数组中最长的递增子数组的长度。
Tag：DP，线段树，模拟。
象征性的写个 DP。
思路：设 \(dp_i\) 表示以 \(i\) 结尾的长度，显然，如果 \(a_i > a_{i-1}\)，就一定可以 \(dp_i = dp_{i-1} + 1\)，否则 \(dp_i = 1\)。
#include <bits/stdc++.h>using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define all(x) (x).begin(), (x).end()
#define inf (1 << 30)
#define lnf (1LL << 60)
typedef pair<int, int> PII;
constexpr int N = 1e5 + 7;
constexpr int P = 998244353;int n, a[N], f[N];int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}f[1] = 1;for (int i = 2; i <= n; i++) {if (a[i] > a[i - 1]) f[i] = f[i - 1] + 1;else f[i] = 1;}printf("%d\n", *max_element(f + 1, f + n + 1));return 0;
}
时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)
B - HonestOrUnkind2
题意：有 \(n\) 个人，每个人都不老实，有些人说谎，有些人没有，每个人会有 \(a_i\) 个名单，判断不矛盾的情况下，最多能有多少个老实人。
Tag：位运算，搜索，线段树。
思路：二进制枚举，判断有没有说谎，具体来说答案就是 __builtin_popcount。
#include <bits/stdc++.h>using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define all(x) (x).begin(), (x).end()
#define inf (1 << 30)
#define lnf (1LL << 60)
typedef pair<int, int> PII;
constexpr int N = 15 + 7;
constexpr int P = 998244353;int n, x[N][N], y[N][N], t[N]; int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &t[i]);for (int j = 1; j <= t[i]; j++) {scanf("%d%d", &x[i][j], &y[i][j]);}}int ans = 0;for (int S = 0; S < (1 << n); S++) {bool ok = true;vector<int> b(n + 1, -1);for (int i = 1; i <= n && ok; i++) {if (S & (1 << (i - 1))) {for (int j = 1; j <= t[i]; j++) {if (y[i][j]) {if (!(S & (1 << (x[i][j] - 1)))) {ok = false;// goto loop;break;}} else {if (S & (1 << (x[i][j] - 1))) {ok = false;// goto loop;break;}}b[x[i][j]] = y[i][j];}}}// loop: int cnt = 0;if (ok) {ans = max(ans, __builtin_popcount(S));// for (int i = 1; i <= n; i++) printf("%d ", b[i]);// puts("");// printf("%d\n", S);}}printf("%d\n", ans);return 0;
}
时间复杂度：\(O(2^n)\)
空间复杂度：\(O(n^2)\)
C - Ice Skating
题意：巴杰克正在学习滑冰。他是个初学者，唯一的移动方式就是从雪堆向北、东、南或西方向蹬冰滑行，直到撞上另一个雪堆。他发现通过这种方式，有些雪堆之间无法通过任何动作序列到达。现在他想堆砌一些额外的雪堆，使得他可以从任意雪堆到达其他所有雪堆。请你计算出需要创建的最少雪堆数量。
Tag：DSU，启发式合并，线段树
思路：显然，我们如果行相同或列相同，我们肯定不会新建，所以，看看有几个相同的，然后用 DSU 判断一下即可。
#include <bits/stdc++.h>using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define all(x) (x).begin(), (x).end()
#define inf (1 << 30)
#define lnf (1LL << 60)
typedef pair<int, int> PII;
constexpr int N = 100 + 7;
constexpr int P = 998244353;int n;
PII a[N];int fa[N];int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}void unite(int x, int y) {x = find(x), y = find(y);if (x != y)fa[y] = x;
}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d%d", &a[i].first, &a[i].second);fa[i] = i;} int res = 0;for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {if (a[i].first == a[j].first || a[i].second == a[j].second)unite(i, j);}}for (int i = 1; i <= n; i++) res += (fa[i] == i);printf("%d\n", res - 1);return 0;
}
时间复杂度：\(O(n^2k)\)（\(k\) 为不知名常数）
空间复杂度：\(O(n)\)。