A – 迷宫
这道题挺好的,让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路,大概的维护方法非常像 Floyd。也没啥好说的,看代码吧。
这道题挺好的,让我知道了线段树还有这样的操作。
考虑线段树维护一段区间行入口到行出口的最短路,大概的维护方法非常像 Floyd。也没啥好说的,看代码吧。
这道题看了题解之后发现就是一道 sb 题。
考虑将每一列看成一个数,发现如果忽略掉列的操作,这些数仍然满足等差的条件,所以我们只要暴力算完第一列就可以进行等差了。如果考虑列的操作,那么我们就大力暴力就行了,时间复杂度是\(O(n + m)\)。
今天被各路神仙吊打,顺利 gg。
在考场上我推了个有后效性的 DP,还以为是高斯消元,然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。
首先,对一个概率为\(p\)的事件,它的期望次数是\(\frac{1}{p}\)(参见这里)。然后,考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。
考虑\(dp[1]\)的求法,首先需要两个级别为\(0\)的武器,然后发现无论失败与否都可以保证至少又一个\(0\)级武器,所以我们只需要注意另外一个武器的花费就可以了:
\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]
首先,强烈推荐阅读这篇文章。(看懂了就不用来了)
Miller-Robin 算法包括两个部分,一个是费马测试,还有一个就是二次探测。这两个东西听上去非常的玄学(的确也是),我来讲清楚,并附上代码。我们现在要进行测试的数是\(p\)。
对,这道题是毒瘤题。首先,我们可以判定出,这些序列一定会在\(60s\)内全部从头开始,因为\(1,2,3,4,5,6\)的最大公倍数为\(60\)。之后,我们可以考虑把这些操作放入操作矩阵之中。操作矩阵的长宽都为\(n*m\)。具体的操作对应如下:
然后算出\(p=\lfloor \frac{m}{60} \rfloor, q = m \mod 60\),进行矩阵快速幂和连续乘法即可。
好毒瘤,建议不要写。
// CH3401.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 70; ll N, M, t, act; char opt[MAX_N][MAX_N]; string opts[MAX_N]; struct matrix { ll mat[MAX_N][MAX_N], n, m; matrix() { memset(mat, 0, sizeof(mat)); } matrix(int n, int m) { this->n = n, this->m = m; for (int i = 1; i <= max(n, m); i++) mat[i][i] = 1; } matrix operator*(const matrix &tar) const { matrix ans = matrix(); ans.n = n, ans.m = tar.m; for (int i = 0; i <= n; i++) for (int j = 0; j <= tar.m; j++) for (int k = 0; k <= m; k++) ans.mat[i][j] += mat[i][k] * tar.mat[k][j]; return ans; } matrix operator^(const int &tim) const { int ti = tim; matrix ans, bas = *this; for (int i = 0; i <= max(n, m); i++) ans.mat[i][i] = 1; ans.n = n, ans.m = m; while (ti) { if (ti & 1) ans = ans * bas; bas = bas * bas; ti >>= 1; } return ans; } } P, Q, mats[70]; ll getPos(ll x, ll y) { return (x - 1) * M + y; } int main() { scanf("%lld%lld%lld%lld", &N, &M, &t, &act); for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) cin >> opt[i][j], opt[i][j] -= '0'; for (int i = 0; i < act; i++) cin >> opts[i]; int p = t / 60, q = t % 60; matrix F; F.n = 0, F.m = getPos(N, M), F.mat[0][0] = 1; for (int tim = 1; tim <= 60; tim++) { matrix current; current.n = getPos(N, M), current.m = getPos(N, M); current.mat[0][0] = 1; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) { int pos = (tim - 1) % (opts[opt[i][j]].size()); char op = opts[opt[i][j]][pos]; switch (op) { case 'N': if (i > 1) current.mat[getPos(i, j)][getPos(i - 1, j)] = 1; break; case 'S': if (i < N) current.mat[getPos(i, j)][getPos(i + 1, j)] = 1; break; case 'E': if (j < M) current.mat[getPos(i, j)][getPos(i, j + 1)] = 1; break; case 'W': if (j > 1) current.mat[getPos(i, j)][getPos(i, j - 1)] = 1; break; case 'D': break; default: current.mat[0][getPos(i, j)] = op - '0'; current.mat[getPos(i, j)][getPos(i, j)] = 1; break; } } mats[tim] = current; } P = mats[1]; for (int i = 2; i <= 60; i++) P = P * mats[i]; P = P ^ p; Q = q == 0 ? matrix(getPos(N, M), getPos(N, M)) : mats[1]; for (int i = 2; i <= q; i++) Q = Q * mats[i]; F = F * P * Q; ll ans = 0; for (int i = 1; i <= getPos(N, M); i++) ans = max(ans, F.mat[0][i]); printf("%lld", ans); return 0; }
这道题算是非常的毒瘤了。
首先我们来看第一问,根据 XG 巨佬的话,是非常明显的。我们在序列读入时减去元素自己的序号,找 LIS 长度即可。代码:
scanf("%lld", &n); for (ll i = 1; i <= n; i++) scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF; dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF; for (ll i = 2; i <= n; i++) { ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst; len = max(len, addr); dp[i] = addr; dst[addr] = min(dst[addr], arr[i]); } printf("%lld\n", n - dp[n]);
第二问我们引出一个小的结论:如果要把区间\([l\dots r]\)之间变得“好看”,那么这个子区间内一定分为两段:高度为\(arr[l]\)的一段和高度\(arr[r]\)的一段。注意,此时\(arr[]\)内的元素已经剪去了元素编号。
所以这第二问就是一道区间 DP,时间复杂度为\(O(n^3)\)。不过好在序列随机,且我们可以使用邻接表预先存好那些可以处理的区间,然后进行 DP。
// P2501.cpp #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define ll long long using namespace std; const ll MX_N = 35020, INF = 0x3f3f3f3f; ll head[MX_N], arr[MX_N], n, len, dst[MX_N], dp[MX_N], M_curt, f[MX_N], sum1[MX_N], sum2[MX_N]; struct edge { ll to, nxt; } edges[MX_N << 1]; void addpath(ll src, ll dst) { edges[M_curt].to = dst, edges[M_curt].nxt = head[src]; head[src] = M_curt++; } int main() { memset(head, -1, sizeof(head)); scanf("%lld", &n); for (ll i = 1; i <= n; i++) scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF; dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF; for (ll i = 2; i <= n; i++) { ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst; len = max(len, addr); dp[i] = addr; dst[addr] = min(dst[addr], arr[i]); } printf("%lld\n", n - dp[n]); for (ll i = n; i >= 0; i--) addpath(dp[i], i), f[i] = INF; f[0] = 0; for (ll i = 1; i <= n; i++) for (ll e = head[dp[i] - 1]; e != -1; e = edges[e].nxt) { ll v = edges[e].to; if (v > i) break; if (arr[v] > arr[i]) continue; for (ll k = v; k <= i; k++) sum1[k] = abs(arr[k] - arr[v]), sum2[k] = abs(arr[k] - arr[i]); for (ll k = v + 1; k <= i; k++) sum1[k] += sum1[k - 1], sum2[k] += sum2[k - 1]; for (ll k = v; k <= i - 1; k++) f[i] = min(f[i], f[v] + sum1[k] - sum1[v] + sum2[i] - sum2[k]); } printf("%lld", f[n]); return 0; }