主要思路
这题细节真他妈多。
首先,看到 SCC 大小少于 \(100\) 就可以知道是 DAG DP + Tarjan + 高斯消元了,比较显然。然而实现起来非常麻烦。我们在反图上做 DP 的时候,从 queue 拿出顶点后先高斯消元一波,把环内的、SCC 之间的(也就是之前求出的 \(dp[u]\))一起放到方程组里进行消元即可。细节看代码吧,真的呕了。
这题细节真他妈多。
首先,看到 SCC 大小少于 \(100\) 就可以知道是 DAG DP + Tarjan + 高斯消元了,比较显然。然而实现起来非常麻烦。我们在反图上做 DP 的时候,从 queue 拿出顶点后先高斯消元一波,把环内的、SCC 之间的(也就是之前求出的 \(dp[u]\))一起放到方程组里进行消元即可。细节看代码吧,真的呕了。
这道题就是 DAG 求支配树裸题,过程是这样的:先做一遍拓扑排序,然后对于第\(i\)个点\(u\)而言,前\(i – 1\)个点已经完成,所以其支配树上的父亲就是入边起点的 LCA。稍稍处理一下即可。然后再在支配树上进行 DFS 求出每个子树的大小即可。
嗯,是我这种菜鸡不会的类型。
这个题主要的思路就是用离线莫队算法,这个算法是我本人第一次打,所以我会尝试一处一处讲清楚。首先大致分析一下,这道题的本质其实就是查询区间最大的加权众数。那么,根据题解上讲的,有一个这样的结论:
给定集合\(A,B\),则\(mode(A \cup B) \to mode(A) \cup B\)这两玩意本质一样。
所以就可以考虑进行区间增大的莫队了。首先,离散化后简单的分个块,把问答离线下来排个序搞一搞。针对每一个询问,如果可以从上个区间进行转移,就进行快速转移;否则,重新开始。
莫队算法的精髓就是:暴力的进行转移。
// A.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 1e6 + 2000; int n, m, arr[MAX_N], blockId[MAX_N]; int currentId[MAX_N], bucket[MAX_N]; ll cnt[MAX_N], leftBucket[MAX_N], answer, anses[MAX_N]; struct query { int l, r, id; bool operator<(const query &qu) const { return blockId[l] < blockId[qu.l] || (blockId[l] == blockId[qu.l] && r < qu.r); } } queries[MAX_N]; void update_left(int x) { leftBucket[currentId[x]]++; answer = max(answer, (leftBucket[currentId[x]] + cnt[currentId[x]]) * 1LL * arr[x]); } int main() { scanf("%d%d", &n, &m); int siz = sqrt(n * 1.0); for (int i = 1; i <= n; i++) scanf("%d", &arr[i]), bucket[i] = arr[i], blockId[i] = (i - 1) / siz + 1; sort(bucket + 1, bucket + 1 + n); int buckTot = unique(bucket + 1, bucket + 1 + n) - bucket; for (int i = 1; i <= n; i++) currentId[i] = lower_bound(bucket + 1, bucket + 1 + buckTot, arr[i]) - bucket; for (int i = 1; i <= m; i++) scanf("%d%d", &queries[i].l, &queries[i].r), queries[i].id = i; sort(queries + 1, queries + 1 + m); // Previous Information: int L = 1, R = 0, tmd; ll tmp = 0; answer = 0; queries[0].l = 0, blockId[0] = 0; for (int i = 1; i <= m; i++) { // Validiate if this interval is able to be calced by the previous one; if (blockId[queries[i - 1].l] != blockId[queries[i].l]) { memset(cnt, 0, sizeof(cnt)); R = tmd = blockId[queries[i].l] * siz; answer = tmp = 0; } L = min(tmd + 1, queries[i].r + 1); // Calc; while (L > queries[i].l) update_left(--L); while (R < queries[i].r) { R++; tmp = max((++cnt[currentId[R]]) * 1LL * arr[R], tmp); answer = max(answer, (cnt[currentId[R]] + leftBucket[currentId[R]]) * 1LL * arr[R]); } // Set the answer; anses[queries[i].id] = answer; // Set the bucket back; for (int j = L; j <= queries[i].r && j <= tmd; j++) leftBucket[currentId[j]]--; answer = tmp; } // Print the answer; for (int i = 1; i <= m; i++) printf("%lld\n", anses[i]); return 0; }
这是一道傻逼题,然后我强行搞了个拓扑序 DP 就 GG 了。现在想想非常后悔。
显然,把环全部缩成点就会形成一个 DAG (有向无环图),之后直接暴力 DP,然后再取出标记过的答案进行最大值比较即可。很傻逼的一道题。
哦,对了,记得开栈。(JZOJ 万年卡栈)
// B.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 602000; extern int theMain(void) __asm__("theMain"); int head[MAX_N << 1], current, n, m, dfn[MAX_N], low[MAX_N], aff[MAX_N]; int tot, stk[MAX_N], cur, afftot, indeg[MAX_N << 1], tmpx, tmpy, s; ll cnt[MAX_N << 1], dp[MAX_N << 1], answer; bool inst[MAX_N], mark[MAX_N]; struct edge { int to, nxt; } edges[MAX_N << 1]; void addpath(int src, int dst) { edges[current].to = dst; edges[current].nxt = head[src], head[src] = current++; } void tarjan(int u) { dfn[u] = low[u] = ++tot, stk[++cur] = u, inst[u] = true; for (int i = head[u]; i != -1; i = edges[i].nxt) if (dfn[edges[i].to] == 0) tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]); else if (inst[edges[i].to]) low[u] = min(low[u], dfn[edges[i].to]); if (low[u] == dfn[u]) { int j, nd = ++afftot; do { j = stk[cur], inst[j] = false; aff[j] = nd; } while (stk[cur--] != u); } } void toposort() { queue<int> q; q.push(aff[s]), dp[aff[s]] = cnt[aff[s]]; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = edges[i].nxt) { dp[edges[i].to] = max(dp[edges[i].to], dp[u] + cnt[edges[i].to]); q.push(edges[i].to); } } } int theMain() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy); afftot = n; for (int i = 1; i <= n; i++) if (aff[i] == 0) tarjan(i); for (int i = 1; i <= n; i++) scanf("%lld", &cnt[i]); for (int u = 1; u <= n; u++) { cnt[aff[u]] += cnt[u]; for (int i = head[u]; i != -1; i = edges[i].nxt) if (aff[u] != aff[edges[i].to]) addpath(aff[u], aff[edges[i].to]), indeg[aff[edges[i].to]]++; } scanf("%d%d", &s, &tmpx); for (int i = 1; i <= tmpx; i++) scanf("%d", &tmpy), mark[aff[tmpy]] = true; toposort(); for (int i = 1; i <= n; i++) if (mark[aff[i]]) answer = max(answer, dp[aff[i]]); printf("%lld", answer); return 0; } int main() { int size = 64 << 20; char *p = (char *)malloc(size) + size; __asm__ __volatile__("movq %0, %%rsp\n" "pushq $exit\n" "jmp theMain\n" ::"r"(p)); return 0; }
如题,然后秒切。
// C.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 101000; ll n, l, w, pos[MAX_N], prefix[MAX_N], answer; bool validiate(int l, int r) { int mid = (l + r) >> 1; ll ans = pos[mid] * (mid - l + 1) - (prefix[mid] - prefix[l - 1]) + (prefix[r] - prefix[mid]) - pos[mid] * (r - mid); return ans <= w; } int main() { scanf("%lld%lld%lld", &n, &l, &w); for (int i = 1; i <= n; i++) scanf("%lld", &pos[i]), prefix[i] = prefix[i - 1] + pos[i]; ll lcur = 1, rcur = 0; while (rcur < n && lcur <= n) { rcur++; while (lcur <= rcur && !validiate(lcur, rcur)) lcur++; answer = max(rcur - lcur + 1, answer); } printf("%lld", answer); return 0; }
好久没有写拓扑排序了。今天看到这题看了半天,由题解可知是拓扑序DP。原理根据拓扑序来进行DP。由于每个点在DAG是不会回路的,所以我们只需一头往下走就好,用dp[x]记录点x可到达的地方。使用拓扑排序就会让DP时不会出现影响其他已计算过的节点。
// P1137.cpp #include <iostream> #include <cstring> #include <queue> using namespace std; const int maxn = 100010; int points[maxn]; int to[2 * maxn]; int next[2 * maxn]; int indeg[maxn]; int res[maxn]; int dp[maxn]; int tot = 0; int current = 0; int n, m; void add_edge(int a, int b) { to[current] = b; next[current] = points[a]; points[a] = current++; } void toposort() { queue<int> waiting; for (int i = 1; i <= n; i++) if (indeg[i] == 0) waiting.push(i), res[tot++] = i; while (!waiting.empty()) { int curt = waiting.front(); waiting.pop(); for (int edge = points[curt]; edge != -1; edge = next[edge]) { indeg[to[edge]]--; if (indeg[to[edge]] == 0) waiting.push(to[edge]), res[tot++] = to[edge]; } } } void DP() { for (int i = 1; i <= n; i++) dp[i] = 1; for (int i = 0; i < n; i++) for (int edge = points[res[i]]; edge != -1; edge = next[edge]) dp[to[edge]] = max(dp[to[edge]], dp[res[i]] + 1); } int main() { memset(points, -1, sizeof(points)); memset(to, -1, sizeof(to)); memset(indeg, 0, sizeof(indeg)); cin >> n >> m; int a, b; for (int i = 0; i < m; i++) { cin >> a >> b, add_edge(a, b); indeg[b] += 1; } toposort(); DP(); for (int i = 1; i <= n; i++) cout << dp[i] << endl; return 0; }