【AtCoder】Tokio Marine Nichido Fire Insurance Programming Contest 2020

Marine Nichido Fire Insurance Programming Contest 2020"/>

【AtCoder】Tokio Marine Nichido Fire Insurance Programming Contest 2020

比赛链接

点击打开链接

官方题解

点击打开链接

Problem A. Nickname

输出 s 1 s 2 s 3 s_1s_2s_3 s1​s2​s3​ 即可。
时间复杂度 O ( ∣ S ∣ ) O(|S|) O(∣S∣) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {x = 0; int f = 1;char c = getchar();for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';x *= f;
}
char s[MAXN];
int main() {scanf("%s", s + 1), s[4] = 0;printf("%s\n", s + 1);return 0;
}

Problem B. Tag

判断 T × ( V − W ) T\times (V-W) T×(V−W) 与 ∣ A − B ∣ |A-B| ∣A−B∣ 的大小关系即可。
时间复杂度 O ( 1 ) O(1) O(1) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {x = 0; int f = 1;char c = getchar();for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';x *= f;
}
int main() {int a, v, b, w, t;read(a), read(v), read(b), read(w), read(t);int dist = abs(a - b);if (v > w && 1ll * t * (v - w) >= dist) puts("YES");else puts("NO");return 0;
}

Problem C. Lamps

考虑初始时 A i = 0 A_i=0 Ai​=0 的情况，则经过 O ( L o g N ) O(LogN) O(LogN) 次操作后，应当有 A i = N A_i=N Ai​=N 。
因此，有效操作的轮数不会超过 O ( L o g N ) O(LogN) O(LogN) 。模拟，直到 A i = N A_i=N Ai​=N 或是操作次数用尽即可。

时间复杂度 O ( N L o g N ) O(NLogN) O(NLogN) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {x = 0; int f = 1;char c = getchar();for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';x *= f;
}
int n, k, a[MAXN];
bool work() {static int s[MAXN];memset(s, 0, sizeof(s));for (int i = 1; i <= n; i++) {int l = max(1, i - a[i]), r = min(n, i + a[i]);s[l]++, s[r + 1]--;}bool res = false;for (int i = 1; i <= n; i++) {s[i] += s[i - 1];if (s[i] != a[i]) {res = true;a[i] = s[i];}}return res;
}
int main() {read(n), read(k);for (int i = 1; i <= n; i++)read(a[i]);for (int i = 1; i <= k; i++)if (!work()) break;for (int i = 1; i <= n; i++)printf("%d ", a[i]);printf("\n");return 0;
}

Problem D. Knapsack Queries on a tree

一种可行的暴力是记 d p i , j dp_{i,j} dpi