T1 合格的机器
- 基本思路
- 由于操作次数无限制，所以先【劫掠】所有的人，给他们留一个代币就完了
- 然后考虑如何分配当前的钱数 sum
- 如果钱数不足 n，那么答案就是 sum
- 如果钱数足够，那么先给所有人分一个代币，再把剩下代币给到第一个人就完了
- 如果 sum-n 是奇数，答案为 n-1
- 否则，答案为 n
T2 小灰灰的火焰星球2
- 基本思路
- 可以发现，小灰灰只能够在一段后缀中寻找答案
- 那么预处理后缀的最大和次大值
- 然后对于每次询问，二分后缀在哪就可以查询答案了
- 总时间复杂度：
- 注意细节
- 可能后缀中只有 1 或者 0 个数
T3 盲目自大的小灰灰
- 基本思路
- 我们发现，在题目给出的 m 个关键点处，小灰灰的位置状态是确定的
- 那么我们只需要考虑从前一个关键点到后一个关键点的过程中小灰灰在如何移动即可
- 本题询问的是某种分数能否达到，那么对于两个关键点中间的段：
- 小灰灰一定是在不死的情况下，进行一些 +2 分数的往返跳跃
- 这些往返跳跃是可选可不选的，所以直接统计最多能够进行多少次这样的往返跳即可
- 注意最后一段，即最后一个关键点到 n 位置这一段：
- 这一段中没有往返跳的限制，因为在 n 处是没有陷阱的（除非最后一个陷阱在 n 位置处）
- 所以这里就是可以进行一些 +1 的随意跳跃
- 最后对于每个询问，我们需要考虑的就是：
- 能否利用【最少跳跃次数】和上面的 +2 +1 情况将答案拼出来
- 这里直接分类讨论即可
- 时间复杂度：
T4 手动机
- 基本思路
- 本题不能二分，因为无法 check
- 其实本题就是经典的两种权重的最短路问题，要求我们在最小化权重 1 的情况下再去最小化权重 2
- 思路 1
- 先利用指令串对位置进行扩散，求出所有能到点的最短时间
- 然后进行一轮扩散，这里是用手动操作，扩散目标是那些访问不到的，且和当前已经访问过点相邻的点
- 最后扩散的次数就是第一问的答案，第二问的答案可以顺手求出来
- 时间复杂度：
- 思路 2
- 两种权重可以同时维护，然后对于一个点来说其最短距离就是最小化权重 1，如果权重 1 相等就最小化权重 2
- 这样和普通最短路没有区别，只是权重多了一个关键字
- trick
- 将两个权重压缩为 1 个
- 把更重要的权重 1 的权值设为远超于权重 2 的权值，那么最短路自然就会优先保证权重 1 较小
- 注意，这里权重 2 总权值很大，可能是：
的，所以权重 1 不应该小于
- 时间复杂度：
T5 小机器人
- 基本思路
- 考虑到
故本题应当用
的做法来完成，而非
- 我们需要分析单次操作的性质，尝试从中找到某些特性用于优化算法
- 考虑到
- 思路 1
- 回想一下暴力怎么做？
- 分为三个步骤：
- 每次把区间排序
- 然后机器人一定是把排序后的“阶梯状”柱状图的一个前缀给抹平
- 然后把剩余的额外操作在抹平段选出下标较小的几个数进行 +1 操作
- 上面三个操作中
- 排序操作，时间为
- 抹平操作，时间为
- 额外挑选 +1 操作，利用桶标记下标可以做到
- 排序操作，时间为
- 可以发现，主要的引入
的瓶颈是排序步骤
- 这里用到一个小 trick
- 需要观察到这个阶梯状柱状图进行完上面三步操作后，其仍然是一个近似有序的状态
- 为什么说“近似有序”呢
- 抹平后，序列仍旧有序
- 但是额外挑选 +1 后序列有序性被破坏，但是被破坏的这一部分其实是下标相对顺序不再正确
- 也就是说，只要能够把下标顺序还原就可以了
- 而下标取值范围是
的，所以这里可以用桶统计来
- 那么我们会发现，这个区间中元素在操作进行结束后，其仍然是有序的
- 于是我们可以考虑把排序从“每次操作都排序”修改为“每次操作都从一个长有序序列中分离区间中的元素”
- 具体来说，我们可以先对整个数组排序
- 然后对于单次操作，我们分离整个有序序列，分为操作区间内子有序数组，和操作区间外子有序数组
- 然后我们对操作区间内子有序数组进行“抹平”和“额外 +1”操作，并用桶统计修复数组有序性
- 然后再把这个有序数组和操作区间外子有序数组合并，得到整个数组修改后的有序结构
- 这样上面的单次操作中每一步操作都是
- 需要观察到这个阶梯状柱状图进行完上面三步操作后，其仍然是一个近似有序的状态
- 至此，算法总时间复杂度为
的
- 思路 2
- 特别鸣谢验题人 @Health0_0
- 注意到这个“抹平”操作会使得数组中出现一些相同的元素
- 下面我们描述一个看似暴力，实则是基于区间中不同元素种类的做法
- 对于每个操作请求，我们反复执行下面的做法，直到 k 值为 0
- 选出区间中的最小值，以及最小值出现的所有坐标集
- 找出区间中的次小值，若次小值不存在（区间中元素全相等）将其设为极大值 inf
- 若剩余 k 值能够把所有的最小值都推平到次小值，那就推平，同时 k 减少对应值
- 否则，将最小值推平，然后把剩余的操作次数分给前面若干个最小值，k 变 0
- 上述操作单次的时间复杂度最坏为
乘【区间中元素种类】的
- 但我们观察整体，对于这个 n 长的数组，其内部只有最多 n 个不同元素
- 而每次操作最多只能生成 1 种新元素
- 故在整个算法中，不同元素个数是
的
- 所以整个算法的时间复杂度为：
T6 独特的方格
- 基本思路
- 本题没有太好的基本思路，主要靠运气吧
- 注意到
- 有经验的同学可以想到，一个常见的时间复杂度
这里有
（如果不成立，那我们转置整个数组，就成立了）
- 但至此，仍旧没有太好的突破点
- 思考下，如何统计矩阵的个数问题，一般有下面两个角度
- 枚举矩阵的上下边界，然后扫描行
- 这里遇到的主要问题是，扫描行的做法难以避开上下边界的范围
- 不过 @Anoth3r 想到了利用 bitset 优化的方式，从内测情况来看，效率不错
- 枚举矩阵的右下角，然后观察左上角的取值可行域
- 这个做法初看很寄
- 但可以细想一下，对于每个右下角，其左上角可行域必然组成了一个阶梯状的东西
-
- 然后我们会发现，这东西好像可以递推
-
- 利用 X 和 Y 的信息可以推导出 Z 的阶梯状可行域
- 这样最后的答案就是所有右下角点可行域的面积和
- 那么如何推导这个东西呢
- 假设我们需要求解 Z 的第 k 列可行的左上角点范围
-
- 那么其可行域受到 X 的第 k 列和 Y 的第 k 列取值的限制
- 然后可以发现，在满足了上面两个限制后，只有下面两个点还有额外限制要被满足
- 点
<i, j>在第 k 列所能够向上延伸的最远距离 - 点
<i, k>在第 j 列所能够向上延伸的最远距离
- 点
- 这里我们对每一列生成一个从上往下的，每种数值的上一次出现位置就可以求得这两个额外限制的解了
- 故本题整体来说可以递推，为了保证向左的阶梯状可行区域不长，所以我们使得 列小于行 然后做这个算法就可以了
- 时间复杂度：
这里 n 代表行，m 代表列，且
- 假设我们需要求解 Z 的第 k 列可行的左上角点范围
-
- 枚举矩阵的上下边界，然后扫描行
Code
-
T1
-
#include <bits/stdc++.h> using namespace std; #define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++) #define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --) #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); void solved() { int n; cin >> n; int sum = 0; _for(i, 1, n) { int x; cin >> x; sum += x - 1; } if(sum < n) cout << sum; else if(sum - n & 1) cout << n - 1; else cout << n; return ; } signed main() { IOS // int ttx; cin >> ttx; _for(i, 1, ttx) solved(); return 0; }
-
-
T2
-
#include <bits/stdc++.h> using namespace std; #define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++) #define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --) #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); const int N = 1e5 + 9; int a[N], b[N]; int mx[N][2]; void solved() { int n, m; cin >> n >> m; _for(i, 1, n) cin >> a[i]; _for(i, 1, n) cin >> b[i]; _rep(i, n, 1) { mx[i][0] = mx[i + 1][0]; mx[i][1] = mx[i + 1][1]; if(b[i] > mx[i][1]) mx[i][1] = b[i]; if(mx[i][0] < mx[i][1]) swap(mx[i][0], mx[i][1]); } ll ans = 0; _for(i, 1, m) { int x; cin >> x; int l = 1, r = n + 1; while(l < r) { int mid = l + r >> 1; if(a[mid] < x) r = mid; else l = mid + 1; } ans += mx[l][0] + mx[l][1]; } cout << ans; return ; } signed main() { IOS // int ttx; cin >> ttx; _for(i, 1, ttx) solved(); return 0; }
-
-
T3
-
#include <bits/stdc++.h> using namespace std; #define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++) #define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --) #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define endl '\n' const int N = 1e5 + 9; int a[N], b[N]; int mx[N][2]; void solved() { int n, m; cin >> n >> m; int now = 0, gt = 0, s = 0, cnt = 0; _for(i, 1, m) { int t, c; cin >> t >> c; if(c != gt) { // 不需要额外跳跃调整不死 s += (t - now) / 2; } else { // 需要额外跳跃调整不死 s += (t - now - 1) / 2; cnt ++; } now = t, gt = !c; } int d = n - now; // 计算最后一段的 +1 的最多次数 cin >> m; _for(i, 1, m) { int x; cin >> x; bool ans = true; if(x < cnt) ans = false; x -= cnt; x -= min(x / 2, s) * 2; x -= min(x, d); if(x != 0) ans = false; if(ans) cout << "Yes" << endl; else cout << "No" << endl; } } signed main() { IOS // int ttx; cin >> ttx; _for(i, 1, ttx) solved(); return 0; }
-
-
T4
-
思路 2
-
#include <bits/stdc++.h> using namespace std; #define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++) #define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --) #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); using ll = long long; const int N = 1e3 + 9, M = 1e5 + 9; char a[N][N]; ll nex[M << 1][4]; int xx[] = {0, 1, 0, -1, 0}; // 右、下、左、上 ll dis[N][N]; void solved() { int n, m; cin >> n >> m; string s; cin >> s; int len = s.size(); _for(i, 0, 3) nex[2 * len][i] = (1ll << 40) + 1; _rep(i, 2 * len - 1, 0) { _for(j, 0, 3) nex[i][j] = min(nex[i + 1][j] + 1, (1ll << 40) + 1); if(s[i % len] == 'R') nex[i][0] = 1; if(s[i % len] == 'D') nex[i][1] = 1; if(s[i % len] == 'L') nex[i][2] = 1; if(s[i % len] == 'U') nex[i][3] = 1; } _for(i, 1, n) _for(j, 1, m) cin >> a[i][j]; _for(i, 1, n) _for(j, 1, m) dis[i][j] = INF; dis[1][1] = 0; using ll3 = array<ll, 3>; priority_queue<ll3> pq; pq.push({-dis[1][1], 1, 1}); while(!pq.empty()) { ll3 p = pq.top(); pq.pop(); int x = p[1], y = p[2]; ll w = -p[0]; if(w != dis[x][y]) continue; _for(i, 1, 4) { int fx = x + xx[i - 1], fy = y + xx[i]; if(fx < 1 || fy < 1 || fx > n || fy > m) continue; ll d = w + nex[(w & (1ll << 40) - 1) % len][i - 1]; if(a[fx][fy] == '#' || d >= dis[fx][fy]) continue; dis[fx][fy] = d; pq.push({-d, fx, fy}); } } ll ans = dis[n][m]; cout << (ans >> 40) << ' ' << (ans & (1ll << 40) - 1); return ; } signed main() { IOS // int ttx; cin >> ttx; _for(i, 1, ttx) solved(); return 0; }
-
-
T5
-
思路 1
-
#include <bits/stdc++.h> using namespace std; #define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++) #define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --) #define endl '\n' #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); using ll = long long; const int N = 8e3 + 9; ll a[N]; int c[N], n; int b1[N], b2[N], t1, t2; bool vis[N]; int d[N]; void work() { int l, r, k; cin >> l >> r >> k; t1 = t2 = 0; _for(i, 1, n) { // 分离区间内和区间外的数 if(c[i] < l || c[i] > r) b1[++ t1] = c[i]; else b2[++ t2] = c[i]; } ll mx, len; _for(i, 1, t2) { // 找到变化值的最大值 len = i; ll dt = a[b2[i + 1]] - a[b2[i]]; if(dt * i >= k || i == t2) { mx = a[b2[i]] + k / i; k %= i; break; } k -= dt * i; } // while(len < t2 && a[b2[len + 1]] == mx) len ++; // 可以不管，后续不会错 _for(i, 1, len) a[b2[i]] = mx, vis[b2[i]] = true; // 调整提升值，桶标记 int tp = 1; _for(i, 1, n) if(vis[i]) { // 在桶中对前 k 个数进行添加 tp = i; if(k == 0) break; a[i] ++, k --; } int ft = 1; _for(i, tp, n) if(vis[i]) b2[ft ++] = i, vis[i] = false; // 后面的数先追加 _for(i, 1, tp - 1) if(vis[i]) b2[ft ++] = i, vis[i] = false; // 前面的数因为 +1 后追加 int fl = 1, fr = 1; _for(i, 1, n) { // 归并 if(fl > t1) c[i] = b2[fr ++]; else if(fr > t2) c[i] = b1[fl ++]; else if(a[b1[fl]] < a[b2[fr]] || a[b1[fl]] == a[b2[fr]] && b1[fl] < b2[fr]) c[i] = b1[fl ++]; else c[i] = b2[fr ++]; } } void solved() { cin >> n; _for(i, 1, n) cin >> a[i]; _for(i, 1, n) c[i] = i; sort(c + 1, c + 1 + n, [&](int x, int y) -> bool { if(a[x] == a[y]) return x < y; return a[x] < a[y]; }); int m; cin >> m; _for(i, 1, m) work(); _for(i, 1, n) cout << a[i] << ' '; return ; } int main() { IOS // int ttx; cin >> ttx; while(ttx --) solved(); return 0; } -
思路 2
-
#include <bits/stdc++.h> using namespace std; #define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++) #define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --) #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); using ll = long long; const ll INF = 1.1e18; const int N = 8e3 + 9; ll a[N]; int n, m; void work() { int l, r, k; cin >> l >> r >> k; while(k) { vector<int> ve; ve.push_back(l); _for(i, l + 1, r) { if(a[i] > a[ve[0]]) continue; if(a[i] < a[ve[0]]) ve.clear(); ve.push_back(i); } ll mn = INF; _for(i, l, r) if(a[i] != a[ve[0]]) mn = min(mn, a[i]); ll dt = mn - a[ve[0]]; int len = ve.size(), d = min((ll)k / len, dt); bool flag = d < dt; k -= len * d; for(int x: ve) { if(k == 0) flag = false; a[x] += d + flag; k -= flag; } } } void solved() { cin >> n; _for(i, 1, n) cin >> a[i]; cin >> m; _for(i, 1, m) work(); _for(i, 1, n) cout << a[i] << ' '; return ; } signed main() { IOS // int ttx; cin >> ttx; _for(i, 1, ttx) solved(); return 0; }
-
-
T6
-
递推
-
#include <bits/stdc++.h> using namespace std; #define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++) #define _rep(i, a, b) for(int i = a, IM = b; i >= IM; i --) #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define endl '\n' const int N = 1e5 + 9, M = 317 + 9; int a[N][M]; int b[N][M]; // b[i][j] 表示第 i 个元素往左到第 j 列的最上方位置 int c[M][N]; // c[i][j] 表示第 i 列中第 j 个元素出现的最早行号 int n, m; int ask(int x, int y) { if(x == 0 || y == 0) return 0; return (x - 1) * m + y; } void solved() { cin >> n >> m; if(n > m) { _for(i, 1, n) _for(j, 1, m) cin >> a[i][j]; } else { swap(n, m); _for(j, 1, m) _for(i, 1, n) cin >> a[i][j]; } ll ans = 0; _for(i, 1, n) _for(j, 1, m) { int now = ask(i, j), u = ask(i - 1, j), l = ask(i, j - 1); _rep(k, j, 1) { b[now][k] = max({c[k][a[i][j]], c[j][a[i][k]], b[u][k]}); if(k != j) b[now][k] = max({b[now][k], b[now][k + 1], b[l][k]}); ans += i - b[now][k]; } c[j][a[i][j]] = i; } cout << ans << endl; _for(i, 1, n) _for(j, 1, m) c[j][a[i][j]] = 0; return ; } signed main() { IOS PCS(6) int ttx; cin >> ttx; _for(i, 1, ttx) solved(); return 0; }
-
--- end ---
京公网安备 11010502036488号