比赛地址:https://ac.nowcoder.com/acm/contest/8564
出题人题解:https://ac.nowcoder.com/discuss/564880
A-进攻
知识点:前缀最大值
战机按破坏力从小到大排序、基地按防御值从小到大排序并维护价值的前缀最大值。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 1e9 + 7; const double eps = 1e-8; const int MAXN = 1e6 + 117; const int MAXM = 1e6 + 117; int n, m; int a[MAXN]; struct node { int d; int v; } b[MAXN]; bool cmp(node x, node y) { if(x.d != y.d) return x.d < y.d; return x.v > y.v; } int main() { scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) scanf("%d", &a[i]); for(int i = 1; i <= m; i++) scanf("%d", &b[i].d); for(int i = 1; i <= m; i++) scanf("%d", &b[i].v); sort(a, a + n); sort(b + 1, b + 1 + m, cmp); b[0].v = 0; for(int i = 1; i <= m; i++) b[i].v = max(b[i].v, b[i - 1].v); LL ans = 0; for(int i = 0, j = 0; i < n; i++) { while(j < m && b[j + 1].d < a[i]) j++; ans += b[j].v; } printf("%lld\n", ans); return 0; }
B-二进制
知识点:二进制枚举
题意:求一个不超过5次的操作序列,满足对于任意的经过已知的操作序列后和经过ans操作序列后所得的结果相同。
枚举每一位经过次操作后的结果,再运用位运算的性质选择合适的操作。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 1e9 + 7; const double eps = 1e-8; const int MAXN = 1e6 + 117; const int MAXM = 1e6 + 117; int n; int op[MAXN], a[MAXN]; int one, two, three; int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d%d", &op[i], &a[i]); for(int i = 0; i < 20; i++) { int x = 0, y = 1 << i; for(int j = 0; j < n; j++) { if(op[j] == 1) x &= a[j], y &= a[j]; if(op[j] == 2) x |= a[j], y |= a[j]; if(op[j] == 3) x ^= a[j], y ^= a[j]; } x = (x >> i) & 1, y = (y >> i) & 1; if(x == 1 || y == 1) one += 1 << i; if(x == 1 && y == 1) two += 1 << i; if(x == 1 && y == 0) three += 1 << i; } printf("3\n1 %d\n2 %d\n3 %d\n", one, two, three); return 0; }
C-积木
知识点:构造
易证当为奇数时无解,当为偶数时分解成若干个2阶立方体即可。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 1e9 + 7; const double eps = 1e-8; const int MAXN = 1e6 + 117; const int MAXM = 1e6 + 117; int n; int main() { scanf("%d", &n); if(n & 1) puts("-1"); else { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { for(int k = 0; k < n; k++) { int num = (j / 2 + k / 2) & 1; printf("%d ", num ^ (i & 1)); } putchar(10); } } } return 0; }
D-种树
知识点:dfs
只能取到深度小于等于操作次数的点的子树的最小值。
注:出题人题解给出了二分的做法。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 1e9 + 7; const double eps = 1e-8; const int MAXN = 5e5 + 117; const int MAXM = 1e6 + 117; int n; int a[MAXN], ans; int l[MAXN], r[MAXN]; void dfs(int i, int high) { if(l[i]) { dfs(l[i], high + 1); dfs(r[i], high + 1); a[i] = min(a[l[i]], a[r[i]]); } if(high <= n / 2 / 2) ans = max(ans, a[i]); } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d%d", &l[i], &r[i]); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); ans = -INF; dfs(1, 0); printf("%d\n", ans); return 0; }
E-考试
知识点:贪心
尽量相同的为对,不同的为错。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 998244353 ; const double eps = 1e-8; const int MAXN = 1e6 + 117; const int MAXM = 1e6 + 117; int n, k; int a[MAXN], b[MAXN]; int yes, no; int main() { scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) scanf("%d", &a[i]); for(int i = 0; i < n; i++) { scanf("%d", &b[i]); if(a[i] == b[i]) yes++; else no++; } if(k <= no) printf("%d\n", n - (no - k)); else printf("%d\n", n - (k - no)); return 0; }
F-项链
知识点:模拟
双向链表模拟题。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 1e9 + 7; const double eps = 1e-8; const int MAXN = 5e5 + 117; const int MAXM = 1e6 + 117; int n, m; int f; int l[MAXN], r[MAXN]; void pr() { int x = 1; if(f) { do { printf("%d ", x); x = l[x]; } while(x != 1); } else { do { printf("%d ", x); x = r[x]; } while(x != 1); } putchar(10); } void del(int i) { int ll = l[i], rr = r[i]; r[ll] = rr; l[rr] = ll; } void add(int x, int i) { int rr = r[i]; r[i] = x; l[x] = i; r[x] = rr; l[rr] = x; } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { if(i == 1) l[i] = n; else l[i] = i - 1; if(i == n) r[i] = 1; else r[i] = i + 1; } int op, x, y; while(m--) { scanf("%d", &op); if(op == 1) { scanf("%d%d", &x, &y); del(x); if(f) add(x, l[y]); else add(x, y); } else if(op == 2) { scanf("%d%d", &x, &y); del(x); if(f) add(x, y); else add(x, l[y]); } else if(op == 3) { f ^= 1; } else pr(); } return 0; }
G-涂色
知识点:数学
可以,但易求答案为。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 998244353 ; const double eps = 1e-8; const int MAXN = 1e6 + 117; const int MAXM = 1e6 + 117; int n; int main() { cin >> n; cout << n + 1 << endl; return 0; }
H-圆
知识点:几何
圆心距与两圆半径判交点。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 1e9 + 7; const double eps = 1e-8; const int MAXN = 1e6 + 117; const int MAXM = 1e6 + 117; int T; int main() { double x1, y1, r1; double x2, y2, r2; cin >> T; while(T--) { cin >> x1 >> y1 >> r1; cin >> x2 >> y2 >> r2; double dist = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); if(dist > r1 + r2 || dist < fabs(r1 - r2)) puts("NO"); else puts("YES"); } return 0; }
I-修改
知识点:最小生成树
数列问题转化成图论问题的神奇操作:
- 数列值全为0-->差分数组值全为0。
- 选择区间进行修改-->差分数组和发生修改。
- 对点和点建边后,对任意数列满足的充要条件为:每个点都可以通过某些边到达点。
- 最小代价为最小生成树的大小。
总结的不好,建议看出题人的题解。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 1e9 + 7; const double eps = 1e-8; const int MAXN = 1e5 + 117; const int MAXM = 4e5 + 117; int n, m; int tot; int F[MAXN]; struct Edge { int u, v, w; } edge[MAXM]; void addedge(int u, int v, int w) { edge[tot].u = u; edge[tot].v = v; edge[tot++].w = w; } bool cmp(Edge a, Edge b) { return a.w < b.w; } int find(int x) { if(F[x] == x) return x; return F[x] = find(F[x]); } LL kruskal(int n) { for(int i = 0; i <= n; i++) F[i] = i; sort(edge, edge + tot, cmp); int cnt = 0; LL ans = 0; for(int i = 0; i < tot; i++) { int u = edge[i].u; int v = edge[i].v; int w = edge[i].w; int t1 = find(u); int t2 = find(v); if(t1 != t2) { ans += w; F[t1] = t2; cnt++; } if(cnt == n - 1) return ans; } return -1; } int main() { scanf("%d%d", &n, &m); int l, r, w; while(m--) { scanf("%d%d%d", &l, &r, &w); addedge(l, r + 1, w); } printf("%lld\n", kruskal(n + 1)); return 0; }
J-克隆
知识点:欧拉序
欧拉序:https://www.cnblogs.com/stxy-ferryman/p/7741970.html
个人能经过的点数总和不少于,欧拉序列长度为。
#include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const double pi = acos(-1); const LL mod = 1e9 + 7; const double eps = 1e-8; const int MAXN = 1e5 + 117; const int MAXM = 4e5 + 117; int n, m, k; int head[MAXN]; int edge[MAXM], ne[MAXM], tot; bool vis[MAXN]; int ans[MAXM], cnt; void addedge(int u, int v) { edge[tot] = v; ne[tot] = head[u]; head[u] = tot++; } void dfs(int i) { ans[cnt++] = i; vis[i] = true; for(int j = head[i]; j != -1; j = ne[j]) { int v = edge[j]; if(!vis[v]) { dfs(v); ans[cnt++] = i; } } } int main() { tot = cnt = 0; memset(head, -1, sizeof(head)); scanf("%d%d%d", &n, &m, &k); int u, v; while(m--) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } dfs(1); puts("YES"); int num = (2 * n + k - 1) / k; for(int i = 0; i < cnt; i += num) { if(i + num < cnt) printf("%d", num); else printf("%d", cnt - i); for(int j = 0; j < num && i + j < cnt; j++) printf(" %d", ans[i + j]); putchar(10); } return 0; }