A. 牛牛的方程式
题目描述
给定一个三元一次方程 \(ax+by+cz=d\)，求该方程是否存在整数解。
思路
由于若干个 \(a,b,c\) 只能凑出 \(\gcd (a,b,c)\) 的倍数，所以只需判断 \(d\) 是否为 \(\gcd(a,b,c)\) 的倍数即可。特别的，若 \(a,b,c\) 均为 \(0\)，则显然只有 \(d=0\) 时存在整数解。
时空复杂度均为 \(O(1)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;int t;
ll a, b, c, d;ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));
}void Solve() {cin >> a >> b >> c >> d;cout << (!a && !b && !c ? (!d ? "YES\n" : "NO\n") : (d % gcd(gcd(a, b), c) == 0 ? "YES\n" : "NO\n"));
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);for(cin >> t; t--; Solve()) {}return 0;
}
B. 牛牛的猜球游戏
题目描述
有一排 \(10\) 个球，依次编号 \(0-9\)，有 \(N\) 种操作，每次操作交换球 \(a,b\)。给定 \(M\) 次查询，每次求依次进行完 \(l\) 到 \(r\) 的操作后每个位置上球的编号。
思路
由于此题没有修改，所以考虑倍增。
令 \(f_{i,j}\) 表示从 \(i\) 开始，进行 \(2^j\) 次操作后每个球所处的位置。
我们很明显有以下转移：\(f_{i,j,_k}=f_{i+2^{j-1},j-1,f_{i,j-1,k}}\)。
查询时直接倍增求解即可。
空间复杂度 \(O(N\log N)\)，时间复杂度 \(O(N \log N + M\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 100001;int n, m, f[18][MAXN][11], res[11], ans[11];int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1, a, b; i <= n; ++i) {cin >> a >> b;a++, b++;for(int j = 1; j <= 10; ++j) {f[0][i][j] = j;}swap(f[0][i][a], f[0][i][b]);}for(int i = 1; i <= 17; ++i) {for(int j = 1; j <= n; ++j) {if(j + (1 << i) - 1 <= n) {for(int k = 1; k <= 10; ++k) {f[i][j][k] = f[i - 1][j + (1 << (i - 1))][f[i - 1][j][k]];}}}}for(int i = 1, l, r; i <= m; ++i) {cin >> l >> r;for(int j = 1; j <= 10; ++j) {res[j] = j;}int x = l;for(int j = 17; j >= 0; --j) {if(x + (1 << j) - 1 <= r) {for(int k = 1; k <= 10; ++k) {res[k] = f[j][x][res[k]];}x += (1 << j);}}for(int j = 1; j <= 10; ++j) {ans[res[j]] = j;}for(int j = 1; j <= 10; ++j) {cout << ans[j] - 1 << " \n"[j == 10];}}return 0;
}
C. 牛牛的凑数游戏
题目描述
对于一个多重集合 \(S\)，若 \(\exists S' \subseteq S\) 且 \(\sum \limits_{x\in S'} x = v\)，则我们说 \(S\) 可以表示 \(v\)。
给定一个长度为 \(N\) 的序列 \(A\) 和 \(M\) 次查询，每次查询若 \(S=\{A_l,A_{l+1},\dots,A_r\}\) 时 \(S\) 最小不能表示的非负整数。
思路
我们先考虑最暴力的一个 dp：
令 \(dp_i\) 表示考虑到第 \(i\) 个数，每个数是/否能表示出。
很明显有 \(dp_{i}=dp_{i-1} \operatorname{or} (dp_{i-1} \operatorname{lsh} A_i)\)，这里 \(\operatorname{or},\operatorname{lsh}\) 分别表示位或，左移运算。
由于转移的顺序不会改变结果，所以考虑将 \(A\) 排序。
假设此时 \(dp_i\) 二进制下是 \(X\dots X01\dots 1\)，这里令最低位的 \(0\) 在第 \(k\) 位。则在 \(0\) 到 \(k-1\) 位都是 \(1\)，所以此时最小不能表示的非负整数为 \(k\)。
现在考虑转移到 \(dp_{i+1}\)，此时只要 \(A_{i+1}>k\)，则永远也凑不出 \(k\) 了，因为此时左移会跳过 \(k\)，又因为 \(A\) 已被排序，所以之后也不会凑出来。此时答案就是 \(k\)。
只要此时没有 \(A_i > k\)，我们就能一直加下去。为了加快速度，每次我们让 \(k\leftarrow 小于等于 k 的数字之和\)，因为 \(k\) 可以加上所有 \(\le k 且 > lastk\) 的数，这里 \(lastk\) 是上一次的 \(k\)。
而如果 \(k=lastk\)，则代表加不下去了，也就是答案为 \(k\)。
但时间复杂度对不对呢？在这里每次至少加上 \(lastk+1\)，也就是 \(lastk\) 每次至少 \(\times 2\)，那么 \(k\) 也是如此，所以单次时间复杂度 \(O(\log^2 \max\{A_i\})\)。
每次求 \(\le k\) 的数字之和用可持久化 \(01\) 字典树即可。
空间复杂度 \(O(N\log \max \{A_i\})\)，时间复杂度 \(O(N\log \max\{A_i\}+M\log^2 \max\{A_i\})\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int MAXN = 100001;struct Persistent_01Trie {int tot = 0, ROOT[MAXN], son[2][62 * MAXN];ll cnt[62 * MAXN];void Insert(int x, int y, ll val) {ROOT[x] = ++tot;int u = ROOT[x], v = ROOT[y];for(int i = 60; i >= 0; --i) {son[(val >> i) & 1][u] = ++tot;son[!((val >> i) & 1)][u] = son[!((val >> i) & 1)][v];cnt[u] = cnt[v] + val;u = son[(val >> i) & 1][u], v = son[(val >> i) & 1][v];}cnt[u] = cnt[v] + val;}ll Getsum(int l, int r, ll val) {int u = ROOT[l - 1], v = ROOT[r];ll ans = 0;for(int i = 60; i >= 0; --i) {if((val >> i) & 1) {ans += cnt[son[0][v]] - cnt[son[0][u]], u = son[1][u], v = son[1][v];}else {u = son[0][u], v = son[0][v];}}return ans + cnt[v] - cnt[u];}
}tr;int n, m;int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1, x; i <= n; ++i) {cin >> x;tr.Insert(i, i - 1, x);}for(int i = 1, l, r; i <= m; ++i) {cin >> l >> r;ll x = 0;for(; ; ) {ll last = x;x = tr.Getsum(l, r, x + 1);if(x == last) {break;}} cout << x + 1 << "\n";}return 0;
}
D. 牛牛的 RPG 游戏
题目描述
给定一个 \(N\times M\) 的网格图，每个格子 \((i,j)\) 都有一个事件，每次事件如下：
- 获得 \(val(i,j)\) 的分数
- 接下来每走一步都会获得 \(buff(i,j)\) 的分数，直到触发下个事件前都有这个效果。
每遇到一个格子你都能选择是否触发事件，每次你只能往右/下走，求从 \((1,1)\) 开始到 \((N,M)\) 能获得的最大分数。
思路
首先考虑最暴力的 dp：
令 \(dp_{i,j}\) 表示从 \((1,1)\) 到达并触发 \((i,j)\) 的最大分数。
我们有 \(dp_{i,j}\leftarrow dp_{x,y}+(i-x+j-y)\cdot buff(x,y)+val(i,j)\)。
化简一下：\(dp_{i,j}\leftarrow dp_{x,y}-(x+y)\cdot buff(x,y)+(i+j)\cdot buff(x,y)+val(i,j)\)。
这里最难处理的地方就是 \((i+j)\cdot buff(x,y)\)，因为它既包含了 \(i,j\) 又包含了 \(x,y\)。
\(val(i,j)\) 可以在最后处理，主要考虑前面的部分。
前面的部分可以看作在平面直角坐标系中一条 \(y=kx+b\) 的直线，这里 \(k=buff(x,y),b=dp_{x,y}-(x+y)\cdot buff(x,y)\)，查询时就相当于查询在 \(x=i+j\) 处的最大 \(y\)，这个可以用李超线段树求解。
这里考虑分治 dp：
这样不断分治下去，直到只有一列，这样直接 dp，每列只会被访问 \(\log N\) 次，每次时间复杂度 \(O(\log (N+M))\)。
空间复杂度 \(O(NM)\)，时间复杂度 \(O(NM \log^2 (N+M))\)。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 200001, INF = (int)(2e9);struct line {int k, b;int Get(int x) const {return x * k + b;}
};struct Li_Segment_Tree {int tot;struct Node {int l, r, ls, rs;line Max;}t[MAXN * 16];void Clear(int l, int r) {t[tot = 1] = {l, r, 0, 0, line{0, -INF}};}void Insert(line l) {int u = 1;for(; t[u].l < t[u].r; ) {int mid = t[u].l + (t[u].r - t[u].l) / 2;if(l.Get(mid) > t[u].Max.Get(mid)) {swap(l, t[u].Max);}if(t[u].l + 1 == t[u].r || l.k == t[u].Max.k || l.b == -INF) {break;}if(l.k < t[u].Max.k) {if(!t[u].ls) {t[u].ls = ++tot, t[tot] = {t[u].l, mid, 0, 0, line{0, -INF}};}u = t[u].ls;}else {if(!t[u].rs) {t[u].rs = ++tot, t[tot] = {mid, t[u].r, 0, 0, line{0, -INF}};}u = t[u].rs;}}}int Getmax(int x) {int u = 1, l = 1, r = MAXN, ret = 0;for(; u && t[u].l < t[u].r; ) {int mid = l + (r - l) / 2;if(t[u].Max.Get(x) > ret) {ret = t[u].Max.Get(x);}if(t[u].l + 1 == t[u].r) {break;}(x < mid ? (u = t[u].ls, r = mid) : (u = t[u].rs, l = mid));}return ret;}
}tr;int n, m;
vector<int> b[MAXN], v[MAXN], dp[MAXN];void dfs(int l, int r) {if(l == r) {tr.Clear(1, MAXN);for(int i = 1; i <= n; ++i) {dp[i][l] = max(dp[i][l], tr.Getmax(i + l) + v[i][l]);tr.Insert(line{b[i][l], dp[i][l] - (i + l) * b[i][l]});}return;}int mid = (l + r) >> 1;dfs(l, mid);tr.Clear(1, MAXN);for(int i = 1; i <= n; ++i) {for(int j = l; j <= mid; ++j) {tr.Insert(line{b[i][j], dp[i][j] - (i + j) * b[i][j]});}for(int j = mid + 1; j <= r; ++j) {dp[i][j] = max(dp[i][j], tr.Getmax(i + j) + v[i][j]);}}dfs(mid + 1, r);
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; ++i) {b[i].resize(m + 1), v[i].resize(m + 1), dp[i].resize(m + 1);for(int j = 1; j <= m; ++j) {cin >> b[i][j];dp[i][j] = -INF;}}dp[1][1] = 0;for(int i = 1; i <= n; ++i) {for(int j = 1; j <= m; ++j) {cin >> v[i][j];}}dfs(1, m);cout << dp[n][m];return 0;
}
