Q1
给定等长数组 $a_n, b_n$,判断是否能给 $a_n$ 的一个连续区间的元素加上非负整数 $k$,使得 $a_n$ 变成 $b_n$。
分析:
- 因为 $k \ge 0$, 那么显然有 $a_i \leq b_i$。
- 作用范围是连续的。
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
| #include "bits/stdc++.h"
int a[100000]; int b[100000];
inline int getInt(){ int t = 0; bool neg = false;
char c = getchar(); while (c == ' ' || c == '\n') c = getchar();
if (c == '-') { neg = true; c = getchar(); } while (c != ' ') { if (c == '\n') break; t = t * 10 + (c - '0');
c = getchar(); } return neg ? -t : t; }
int main() { int T; scanf("%d", &T); int n; for (int i = 0; i < T; ++i) { scanf("%d", &n); getchar(); for (int j = 0; j < n; ++j) a[j] = getInt(); for (int j = 0; j < n; ++j) b[j] = getInt(); int d = 0; bool bad = false; bool had = false; for (int j = 0; j < n; ++j){ if (a[j] != b[j]) { if (a[j] - b[j] > 0) { bad = true; break; } if (had) { if (a[j-1] == b[j-1]) { bad = true; break; } } else { had = true; } if (d == 0) d = a[j] - b[j]; else { if (d != a[j] - b[j]) { bad = true; break; } } } } if (bad) printf("NO\n"); else printf("YES\n"); } return 0; }
|
Q2
给定 $n$ 根木棍,你需要依次掰断他们,使他们构成一个单调不递减的序列。
分析:
- 木棍的相对顺序不变。
- 木棍只能折断为整数。
- 单调不递减,即 $a_i \leq a_{i+1}$
WA 了。
Q3
这题是个背包题,给定 $n$ 张可以重复使用的优惠券,$m$ 个商品,问你最少要花多少钱。
不会写。
Q4
给定 $n$ 个数字的序列,求对于每个元素,从它自己开始,统计向两侧方向的连续范围内小于等于它的元素个数。
分析:这题逻辑很清晰,暴力可以过 71% 的测试点。但是剩下的测试点无论是从输入、输出,或是循环边界上优化都过不去,显然测试数据中肯定掺入了大量的连续重复数据段。我最后选择开一个数组统计当前元素的副本数,但是交上去 WA 了不少测试点。交卷后的那一刻才突然意识到还需要对每个副本都单独输出一次结果。
原版暴力
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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
| #include "bits/stdc++.h"
inline int getInt() { int t = 0; bool neg = false;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ') { if (c == '\n') break; t = t * 10 + (c - '0');
c = getchar(); }
return t; } int crr[6]; inline void putInt(int t) { if (t == 0) { putchar('0'); putchar(' '); return; }
int j = 0; while (t != 0) { crr[j] = '0' + t % 10; ++j; t /= 10; }
--j; while (j != -1) { putchar(crr[j]); --j; } putchar(' '); }
int arr[100010]; int brr[100010]; int main() { int T; scanf("%d", &T);
int n; int j; for (int c = 0; c < T; ++c) { scanf("%d", &n); for (int i = 0; i < n; ++i) arr[i] = getInt(); memset(brr, 0, n * 4); for (int i = 0; i < n; ++i) { j = i - 1; while (j != -1) { if (arr[j] == arr[j + 1] || arr[j] <= arr[i]) { ++brr[i]; --j; } else { break; } } j = i + 1; while (j != n) { if (arr[j] == arr[j - 1] || arr[j] <= arr[i]) { ++brr[i]; ++j; } else { break; } } } for (int i = 0; i < n - 1; ++i) { putInt(brr[i]); } printf("%d\n", brr[n - 1]); } return 0; } }
|
应该是正解
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 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
| #include "bits/stdc++.h"
inline int getInt() { int t = 0; bool neg = false;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ') { if (c == '\n') break; t = t * 10 + (c - '0');
c = getchar(); }
return t; } int crr[6]; inline void putInt(int t) { if (t == 0) { putchar('0'); putchar(' '); return; }
int j = 0; while (t != 0) { crr[j] = '0' + t % 10; ++j; t /= 10; }
--j; while (j != -1) { putchar(crr[j]); --j; } putchar(' '); }
int arr[100010]; int brr[100010]; int drr[100010]; int main() { int T; scanf("%d", &T);
int n; int j; for (int c = 0; c < T; ++c) { scanf("%d", &n); memset(drr, 0, sizeof(drr)); for (int i = 0; i < n; ++i) { arr[i] = getInt(); if (i != 0 && arr[i] == arr[i - 1]) { ++drr[i - 1]; --n; --i; } else { drr[i] = 1; } } memset(brr, 0, n * 4); for (int i = 0; i < n; ++i) { j = i - 1; while (j != -1) { if (arr[j] == arr[j + 1] || arr[j] <= arr[i]) { brr[i] += drr[j]; --j; } else { break; } } j = i + 1; while (j != n) { if (arr[j] == arr[j - 1] || arr[j] <= arr[i]) { brr[i] += drr[j]; ++j; } else { break; } } brr[i] += drr[i] - 1; } for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < drr[i]; ++j) { putInt(brr[i]); } }
for (int j = 0; j < drr[n - 1] - 1; ++j) putInt(brr[n - 1]); printf("%d\n", brr[n - 1]); } return 0; }
|