T0
经典图片.jpg
T1
[1000/1000]
算法大师喜欢copy代码,有一天他照例抄了4份代码(1≤长度≤1e9)，由于没有处理好，导致代码长度一样。他将面临着被发现的风险。所以他要改动其中的几份代码使其长度变化，问最少要改几份代码才能使任意两份代码长度都不一样。
一眼过掉（然而并不是一眼），请注意初始化（我在初始化上面卡了5mins）
#include <bits/stdc++.h>
using namespace std;
void work() {
unordered_map<int, int> mp;
int res = 0;
for (int i = 1; i <= 4; i++) {
int x;
scanf("%d", &x);
if (mp[x])
res++;
mp[x]++;
}
printf("%d\n", res);
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
return 0;
}
T2
[390/1300]
以下流程可以得到一个数n的Y值，先把n的末尾的0去掉，得到数m，m的长度为a，如果m的最后一个位是5，则n的Y值为2a-1，否则为2a。给定给一个区间[L,R]，求哪个数的Y值最小。
第一次在B题上被hack了（悲），总体来说想到了思路，但是代码太过复杂最后导致自己没调出来。
值得一提的是，改题的时候还把快速幂打错从而又卡了10mins（悲）
#include <bits/stdc++.h>
using namespace std;
int l, r;
int Y(int x) {
while (!(x % 10)) x /= 10;
int cnt = 0, flag = 0;
if (x % 10 == 5)
flag = 1;
while (x) {
cnt++;
x /= 10;
}
return cnt * 2 - flag;
}
int Q(int x) {
int cnt = 0;
while (!(x % 10)) {
cnt++;
x /= 10;
}
return cnt;
}
int quick_power(int a, int b) {
int res = 1;
while (b) {
if (b & 1)
res *= a;
a *= a;
b >>= 1;
}
return res;
}
void work() {
scanf("%d%d", &l, &r);
int res = 0, tp = 20;
for (int i = l; i <= r;) {
int t = Y(i);
if (t < tp) {
res = i;
tp = t;
}
i += quick_power(10, Q(i));
}
printf("%d\n", res);
}
int main() {
int T;
scanf("%d", &T);
while (T--) work();
return 0;
}
T3
[1400/1400]
小岛又带领着幼儿园的小朋友们去春游了。这次有点不一样，这次他们要和其他的幼儿园一起。现在小朋友们排在一起，小岛这边的m个老师要安排看护哪些孩子。每个老师一定要看护K个连续的孩子，且至少有P个是小岛的学生。老师看护的孩子可以重叠，但是不能完全相同,不要求小岛的学生都被看护到。现在想知道，每个小朋友是不是一定会被老师看护到。
第一次看见C比B简单，这不赶紧秒了。
其实就是考察前缀和与差分，两个非常经典的基础算法。
用前缀和快速求出每一区间内这边幼儿园的人数，用差分求出每一个人的观察情况。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, size, p;
char s[N];
int sumQ[N], cnt[N], tot;
int main() {
scanf("%d%d%d%s", &m, &size, &p, s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++) sumQ[i] = sumQ[i - 1] + (s[i] == 'Q' ? 1 : 0);
for (int l = 1; l <= n; l++) {
int r = l + size - 1;
if (sumQ[r] - sumQ[l - 1] >= p) {
cnt[l]++;
cnt[r + 1]--;
tot++;
}
}
for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
for (int i = 1; i <= n; i++) {
if (cnt[i] >= tot - m + 1)
printf("+");
else if (cnt[i])
printf("?");
else
printf("-");
}
return 0;
}
T4
[800/1600]
魔板是一根长为L、宽度为1的木板，可以飞在空中。金块的宽度也是1，乐乐只能把金块横放在魔板上。
为了防止金块掉落，金块之间不能相互覆盖，而且金块的重心必须在魔板上(其中一种情况是大于等于一半的长度且为整数在魔板上)。
请你帮乐乐算算，最多可以运走多少重量的金块。
一眼看出DP，但是没有想出边界处理情况，于是DFS，喜提一半分数。
不过DP只需要增加一维就可以解决这个问题。
DP打法类似01背包问题。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, C = 4005;
int n, L, res, f[C][3];
int main() {
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; i++) {
int l, w;
scanf("%d%d", &l, &w);
res = max(res, w);
for (int j = L; j >= l / 2; j--) {
for (int k = 2; ~k; k--) {
if (j >= l)
f[j][k] = max(f[j][k], f[j - l][k] + w);
if (k >= 1)
f[j][k] = max(f[j][k], f[j - l / 2][k - 1] + w);
res = max(res, f[j][k]);
}
}
}
printf("%d", res);
return 0;
}
T5
[0/1800]
已知13张麻将，问接下来一张牌是哪些牌就可以胡了。胡牌的规则是：有一对牌，这两张牌要相同。还有4连牌，每连牌可以是三个相同的或者连续递增的。以上的相同和递增都是在同种类型的前提条件下。简化实际问题，现在只有三种类型的牌，分别为s,b,c,每种类型只有1-9。
每副麻将中相同的牌最多出现四个。
大模拟，但是要先进行一步离散化。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, C = 4005;
int flag = 1;
int t[N];
void dfs(int u) {
if (u > 4) {
flag = 0;
return;
}
for (int i = 1; i <= 27; i++) {
if (t[i] && t[i + 1] && t[i + 2]) {
t[i]--;
t[i + 1]--;
t[i + 2]--;
dfs(u + 1);
t[i]++;
t[i + 1]++;
t[i + 2]++;
}
if (!flag)
return;
}
for (int i = 1; i <= 29; i++) {
if (t[i] >= 3) {
t[i] -= 3;
dfs(u + 1);
t[i] += 3;
if (!flag)
return;
}
}
}
int main() {
int event = 0;
for (int i = 1; i <= 13; i++) {
char s[5];
scanf("%s", s);
if (s[1] == 's')
t[s[0] - '0']++;
if (s[1] == 'b')
t[s[0] - '0' + 10]++;
if (s[1] == 'c')
t[s[0] - '0' + 20]++;
}
for (int i = 1; i <= 29; i++) {
if (!(i % 10) || t[i] >= 4)
continue;
flag = 1;
t[i]++;
for (int j = 1; j <= 29; j++) {
if (!(j % 10))
continue;
if (t[j] >= 2) {
t[j] -= 2;
dfs(1);
t[j] += 2;
}
}
t[i]--;
if (!flag) {
if (i <= 10)
printf("%ds ", i % 10);
else if (i <= 20)
printf("%db ", i % 10);
else
printf("%dc ", i % 10);
event = 1;
}
}
if (!event)
puts("None");
return 0;
}
T6
[420/2100]
给定一棵 n 个节点的树，每个节点有一个商品的价格，可以进入买入或者卖出。
有 q 个询问，询问从一个节点到另一个节点，可以在路途中买入和卖出一次，求最大收益。
倍增求LCA，但是更快地方法是tarjan求LCA（但是要离线）
#include <bits/stdc++.h>
using namespace std;
const int N = 50005, M = N << 1;
int n, m, h[N], e[M], ne[M], idx, d[N], fa[N][20], w[N];
int down[N][20], up[N][20], Min[N][20], Max[N][20];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs(int u, int father) {
d[u] = d[father] + 1;
fa[u][0] = father;
Min[u][0] = min(w[father], w[u]);
Max[u][0] = max(w[father], w[u]);
up[u][0] = max(0, w[father] - w[u]);
down[u][0] = max(0, w[u] - w[father]);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == father)
continue;
dfs(j, u);
}
}
int lca(int a, int b) {
if (d[a] < d[b])
swap(a, b);
for (int k = 16; k >= 0; k--) {
if (d[fa[a][k]] >= d[b])
a = fa[a][k];
}
if (a == b)
return a;
for (int k = 16; k >= 0; k--) {
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
}
int get_max(int x, int y) {
int k = d[x] - d[y], res = w[x];
for (int i = 0; i <= 16; i++) {
if (k & (1 << i)) {
res = max(res, Max[x][i]);
x = fa[x][i];
}
}
return res;
}
int get_min(int x, int y) {
int k = d[x] - d[y], res = w[x];
for (int i = 0; i <= 16; i++) {
if (k & (1 << i)) {
res = min(res, Min[x][i]);
x = fa[x][i];
}
}
return res;
}
int get_sum_up(int x, int y) {
int k = d[x] - d[y], res = 0, mn = 1e9;
for (int i = 0; i <= 16; i++) {
if (k & (1 << i)) {
res = max(res, max(up[x][i], Max[x][i] - mn));
mn = min(mn, Min[x][i]);
x = fa[x][i];
}
}
return res;
}
int get_sum_down(int x, int y) {
int k = d[x] - d[y], res = 0, mx = 0;
for (int i = 0; i <= 16; i++) {
if (k & (1 << i)) {
res = max(res, max(down[x][i], mx - Min[x][i]));
mx = max(mx, Max[x][i]);
x = fa[x][i];
}
}
return res;
}
int main() {
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i < n; i++) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
dfs(1, 1);
for (int i = 1; i <= 16; i++) {
for (int j = 1; j <= n; j++) {
fa[j][i] = fa[fa[j][i - 1]][i - 1];
Min[j][i] = min(Min[j][i - 1], Min[fa[j][i - 1]][i - 1]);
Max[j][i] = max(Max[j][i - 1], Max[fa[j][i - 1]][i - 1]);
up[j][i] =
max(max(up[j][i - 1], up[fa[j][i - 1]][i - 1]), Max[fa[j][i - 1]][i - 1] - Min[j][i - 1]);
down[j][i] =
max(max(down[j][i - 1], down[fa[j][i - 1]][i - 1]), Max[j][i - 1] - Min[fa[j][i - 1]][i - 1]);
}
}
int q;
scanf("%d", &q);
while (q--) {
int x, y;
scanf("%d%d", &x, &y);
int par = lca(x, y);
int res = get_max(y, par) - get_min(x, par);
res = max(res, max(get_sum_up(x, par), get_sum_down(y, par)));
printf("%d\n", res);
}
return 0;
}