虽然没参加，但是还是记录一下。
没时间写代码，只是瞟了一眼题目想了一下思路而已。
CCF出题真的长啊，读题就花了我好久...
T1 假期计划
第一眼感觉是 $O(kn^2)$ 的 dp，但好像消除不了后效性
考虑暴力：Floyd+全排列 $O((k+2)n^2+n^4)$. 或许40pts?
又发现k=0，再加30pts?
正解是折半搜索+剪枝?
T2 策略游戏
一开始还以为是博弈论，结果只是简单的分类讨论+线段树
鉴定为 "水"
|
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 |
#include <iostream> // 100pts #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; typedef long long LL; // 千万别忘记开longlong const int N = 1e5 + 10, INF = 2e9; int a[N], b[N]; template<typename T> void read(T &x) { char ch = getchar(); bool flag = 0; x = 0; for (; ch < '0' || ch > '9'; ch = getchar()) flag |= (ch == '-'); for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; if (flag) x = -x; } struct node { int l, r; int maxPval = -INF, minPval = INF; int maxNval = -INF, minNval = INF; }; struct choice { int x, y; LL val() { return 1ll * x * y; } }; struct segmentTree { // 开8个线段树太夸张了其实2个就够了 #define rs(x) (x << 1 | 1) #define ls(x) (x << 1) #define p tr[u] #define pl tr[ls(u)] #define pr tr[rs(u)] node tr[N << 2]; void pushup(int u) { p.maxPval = max(pl.maxPval, pr.maxPval); p.minPval = min(pl.minPval, pr.minPval); p.maxNval = max(pl.maxNval, pr.maxNval); p.minNval = min(pl.minNval, pr.minNval); } void build(int u, int l, int r, int *a) { p.l = l, p.r = r; if (l == r) { // 规定0既是正数也是负数 if (a[l] >= 0) p.maxPval = p.minPval = a[l]; if (a[l] <= 0) p.maxNval = p.minNval = a[l]; } else { int mid = l + r >> 1; build(ls(u), l, mid, a), build(rs(u), mid + 1, r, a); pushup(u); } } void updata(node &a, node b) { #define toMax(x, y) (x < y ? x = y: 0) #define toMin(x, y) (x > y ? x = y: 0) toMax(a.maxPval, b.maxPval); toMax(a.maxNval, b.maxNval); toMin(a.minPval, b.minPval); toMin(a.minNval, b.minNval); } node query(int u, int l, int r) { if (p.l >= l && p.r <= r) return p; int mid = p.l + p.r >> 1; node res; if (l <= mid) updata(res, query(ls(u), l, r)); if (r > mid) updata(res, query(rs(u), l, r)); return res; } } trA, trB; int main() { #ifdef noi freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); #endif int n, m, q; read(n), read(m), read(q); for (int i = 1; i <= n; ++ i) read(a[i]); for (int i = 1; i <= m; ++ i) read(b[i]); trA.build(1, 1, n, a); // 千万别忘记建树 trB.build(1, 1, m, b); while (q --) { int l1, r1, l2, r2; read(l1), read(r1), read(l2), read(r2); node qa = trA.query(1, l1, r1); node qb = trB.query(1, l2, r2); // x要满足 min(x*B) 最大 // 假设小L选正数,小Q一定会选最小的负数(Q有负数且L要选最小正数)或最小的正数(Q无负数且L要选最大正数) choice c1 = {-INF, INF}; if (qa.minPval != INF) { if (qb.minNval != INF) c1 = {qa.minPval, qb.minNval}; else c1 = {qa.maxPval, qb.minPval}; } // 假设小L选负数,小Q一定会选最大的正数(Q有正数且L要选最大负数)或最大的负数(Q无正数且L要选最小负数) choice c2 = {-INF, INF}; if (qa.minNval != INF) { if (qb.minPval != INF) c2 = {qa.maxNval, qb.maxPval}; else c2 = {qa.minNval, qb.maxNval}; } // 比较两种选择孰优 printf("%lld\n", max(c1.val(), c2.val())); } } |
T3 星战
大意好像是有n个点m条单向边，u的入边称为u的虫洞
打击方式有两种 1.边 2.u&u的虫洞
反攻条件 1.缩点后只有一个强连通分量 2.每个u都只有一个出边
只想的到暴力：每次询问把修改的点标记一下，跑一次tarjan $O((n+m)q)$
或许能拿 40pts?
T4 数据传输
建图时将能直接连接的点加一条边
然后每次询问都跑一遍最短路?
$O(Qnlog_2n)$ 44pts?
今年的题还是很好拿分的?(还是我的错觉?)
发表回复