目录
Contest InfoSolutions A. runD. monreyG. transformH. travelI. carJ. farmPractice Link
SolvedABCDEFGHIJK6/10Ø..Ø..ØØØØ. O 在比赛中通过Ø 赛后通过! 尝试了但是失败了. 没有尝试题意： 白云每次可以移动\(1\)米或者\(k\)米，询问移动的米数在\([L, R]\)范围内的方案数有多少。
思路：\(dp[i][0/1]\)表示到第\(i\)米，是通过\(1\)米的方式过来的还是\(k\)米的方式过来的，递推即可。
代码：
#include <bits/stdc++.h> using namespace std; #define N 100010 const int p = 1e9 + 7; int f[N][2], g[N]; int q, k, l, r; void add(int &x, int y) { x += y; if (x >= p) { x -= p; } } int main() { scanf("%d%d", &q, &k); memset(f, 0, sizeof f); f[0][0] = 1; for (int i = 0; i <= 100000; ++i) { add(f[i + 1][0], (f[i][0] + f[i][1]) % p); if (i + k <= 100000) { add(f[i + k][1], f[i][0]); } } memset(g, 0, sizeof g); for (int i = 1; i <= 100000; ++i) { g[i] = g[i - 1]; add(g[i], f[i][0]); add(g[i], f[i][1]); } while (q--) { scanf("%d%d", &l, &r); printf("%d\n", (g[r] - g[l - 1] + p) % p); } return 0; }题意： 有\(n\)个物品，从\(1\)到\(n\)的顺序去访问，身上最多只能携带一个物品，每次可以买进或者卖出物品，身上有无限的钱，问最后获得的利润最多是多少。
思路： 考虑将买入和卖出合并成一种操作，买入就是减去收益，卖出是增加收益，维护两个堆，遍历\(i\)个物品。
如果当次是买入，那么去找之前收益最高的一个卖出操作，或者直接买入。如果当次是卖出，那么取找之前收益最高的一个买入操作。代码:
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 100010 int n, a[N]; struct node { ll tot; int cnt; node() {} node (ll tot, int cnt) : tot(tot), cnt(cnt) {} bool operator < (const node &other) const { if (tot == other.tot) { return cnt > other.cnt; } return tot < other.tot; } }; int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } //0表示上一次操作是买入 //1表示上一次操作是卖出 priority_queue <node> pq[2]; node res = node(0, 0); pq[0].push(node(-a[1], 1)); node t1, t2; for (int i = 2; i <= n; ++i) { pq[0].push(node(-a[i], 1)); if (!pq[0].empty()) { t1 = pq[0].top(); pq[1].push(node(t1.tot + a[i], t1.cnt + 1)); } if (!pq[1].empty()) { t2 = pq[1].top(); pq[0].push(node(t2.tot - a[i], t2.cnt + 1)); } if (!pq[1].empty()) { res = max(res, pq[1].top()); } } printf("%lld %d\n", res.tot, res.cnt); } return 0; }题意： 一维坐标系上，在\(x_i\)有\(a_i\)个物品，每次移动一个物品的代价为\(2 \cdot abs(x_u - x_v)\)，现在有\(T\)元钱，问在不超过\(T\)的代价下，移动物品使得 在同一个位置上的物品最多。
思路： 显然可以二分物品数量，check的时候枚举左端点，双指针维护右端点，多余的部分从右端回退。 再枚举右端点，反着搞一遍。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 500010 int n, x[N], a[N]; ll sum[N], cost[N]; ll T, L, R, need; int u; ll cost_l(int i) { //将L+1~i的物品移动到i的费用 ll a = (sum[i] - sum[L]) * x[i] - (cost[i] - cost[L]); //将i+1~R的物品移动到i的费用 ll b = (cost[R] - cost[i]) - x[i] * (sum[R] - sum[i]); //将多余的物品从R移动到i的费用 ll c = (sum[R] - sum[L] - need) * (x[R] - x[i]); return a + b - c; } ll cost_r(int i) { //将L+1~i的物品移动到i的费用 ll a = (sum[i] - sum[L]) * x[i] - (cost[i] - cost[L]); //将i+1~R的物品移动到i的费用 ll b = (cost[R] - cost[i]) - x[i] * (sum[R] - sum[i]); //将多余的物品从L移动到i的费用 ll c = (sum[R] - sum[L] - need) * (x[i] - x[L + 1]); return a + b - c; } bool check(ll x) { need = x; L = 0, R = 1, u = 0; while (1) { while (R < n && sum[R] - sum[L] < x) ++R; if (sum[R] - sum[L] < x) break; while (u < L) ++u; while (u < R && cost_l(u) > cost_l(u + 1)) ++u; if (cost_l(u) <= T) return 1; ++L; } L = n - 1, R = n, u = n; while (1) { while (L > 0 && sum[R] - sum[L] < x) --L; if (sum[R] - sum[L] < x) break; while (u > R) --u; while (u > L && cost_r(u) > cost_r(u - 1)) --u; if (cost_r(u) <= T) return 1; --R; } return 0; } int main() { while (scanf("%d%lld", &n, &T) != EOF) { T /= 2; for (int i = 1; i <= n; ++i) { scanf("%d", x + i); } for (int i = 1; i <= n; ++i) { scanf("%d", a + i); sum[i] = sum[i - 1] + a[i]; cost[i] = cost[i - 1] + 1ll * a[i] * x[i]; } ll l = 0, r = sum[n], res = -1; while (r - l >= 0) { ll mid = (l + r) >> 1; if (check(mid)) { l = mid + 1; res = mid; } else { r = mid - 1; } } printf("%lld\n", res); } return 0; }题意： 询问一棵树上三条不相交路径的最大点权和。
思路：\(f[u][x][y]\)表示以\(u\)为根的子树中，\(u\)的状态为\(x\)，已经选了\(y\)条树链的最大点权和是多少。 三种状态：
当前点不选当前点是链的一端当前点是链的拐点，即两条链的交界处考虑转移：
对于\(y\)的转移可以枚举\(y\)和\(i\)，可以推出\(j\)注意\(y\)和\(i\)的枚举要降序枚举。对于当前点是拐点，转移过来的可以是链+链，也可以是拐点+不选对于当前点是链，可以是当前点是空，转移过来是链，也可以是当前点是链，转移过来的是空对于当前点不选，那么可以是任何状态转移过来，但是当前点不要选。最后答案是\(f[1][0][3]\)代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 400010 int n, a[N]; vector <vector<int>> G; // 0 表示当前点不选 // 1 表示当前点链的一端 // 2 表示当前点是拐点 // 第三维表示已经选了0, 1, 2, 3条链 ll f[N][3][4]; void Max(ll &x, ll y) { if (x < y) x = y; } void DFS(int u, int fa) { f[u][1][0] = a[u]; for (auto v : G[u]) if (v != fa) { DFS(v, u); //转移2状态 for (int k = 2; ~k; --k) { for (int i = k, j; ~i; --i) { j = k - i; //链+链 Max(f[u][2][k], f[u][1][i] + f[v][1][j]); //拐点+空 Max(f[u][2][k], f[u][2][i] + f[v][0][j]); } } //转移1状态 for (int k = 2; ~k; --k) { for (int i = k, j; ~i; --i) { j = k - i; Max(f[u][1][k], f[u][0][i] + a[u] + f[v][1][j]); Max(f[u][1][k], f[u][1][i] + f[v][0][j]); } } //转移0状态 for (int k = 3; ~k; --k) { for (int i = k, j; ~i; --i) { j = k - i; f[u][0][k] = max(f[u][0][k], f[u][0][i] + f[v][0][j]); if (j) { f[u][0][k] = max(f[u][0][k], f[u][0][i] + f[v][1][j - 1]); f[u][0][k] = max(f[u][0][k], f[u][0][i] + f[v][2][j - 1]); } } } } for (int k = 3; k; --k) { Max(f[u][0][k], f[u][1][k - 1]); Max(f[u][0][k], f[u][2][k - 1]); } } int main() { while (scanf("%d", &n) != EOF) { memset(f, 0, sizeof f); G.clear(); G.resize(n + 1); for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } for (int i = 1, u, v; i < n; ++i) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } DFS(1, 0); printf("%lld\n", f[1][0][3]); } return 0; }题意： 在一个\(n \cdot n\)的二维平面上，要放置尽量多的小车，使得每一俩小车都要直行到它的对面边界，其中有一些障碍物，小车行驶的时候不能相撞，也不能碰到障碍物， 问最多放多少辆小车。
思路：
显然每一行每一列最多放一辆小车。假设\(a[x][y]\)有障碍物，那么第\(x\)行第\(y\)列都不能有小车。如果\(n\)是奇数，那么第\(\frac{n + 1}{2}\)行，第\(\frac{n + 1}{2}\)只能放一辆小车。代码：
#include <bits/stdc++.h> using namespace std; #define N 100010 int n, m; int vis[N][2]; int main() { while (scanf("%d%d", &n, &m) != EOF) { memset(vis, 0, sizeof vis); for (int i = 1, x, y; i <= m; ++i) { scanf("%d%d", &x, &y); vis[x][0] = 1; vis[y][1] = 1; } int ans = 0; if (n & 1) { if (vis[n / 2 + 1][0] == 0 && vis[n / 2 + 1][1] == 0) { ++ans; vis[n / 2 + 1][0] = 1; vis[n / 2 + 1][1] = 1; } } for (int i = 1; i <= n; ++i) { for (int j = 0; j < 2; ++j) { ans += (vis[i][j] == 0); } } printf("%d\n", ans); } return 0; }题意： 在\(n \cdot m\)的农田上，有\(n \cdot m\)棵植物，每棵植物只能施放第\(a[i][j]\)种肥料，有\(T\)次操作，每次操作时将\(x_1, y_1, x_2, y_2\)矩形内的作物都施上第\(k_i\)种肥料， 一旦作物被施上不是第\(a[i][j]\)种肥料，它就会立刻死亡。 问最后死亡的作物数目.
思路一： 考虑： 作物的施肥次数 = 第\(a[i][j]\)种肥料的施肥次数+其他种类肥料的施肥次数。 我们先二维差分求出所有作物的总的施肥次数。 然后将操作按\(k_i\)分类，用二维BIT维护二维前缀和，表示\(k_i\)操作下作物的施肥次数。 然后再枚举初始值为\(k_i\)的所有作物，判断它总的施肥次数以及第\(k_i\)种肥料的施肥次数是否相等，不相等就挂了。 时间复杂度：\(\mathcal{O}(nm + T \cdot log(n) \cdot log(m))\)
代码一：
#include <bits/stdc++.h> using namespace std; #define N 1000010 #define pii pair <int, int> #define fi first #define se second int n, m, q; struct node { int x[2], y[2]; node() {} node(int x1, int y1, int x2, int y2) { x[0] = x1; x[1] = x2; y[0] = y1; y[1] = y2; } }; vector < vector <pii> > a; vector < vector <node> > b; struct BIT { vector < vector <int> > a; void init() { a.clear(); a.resize(n + 1); for (int i = 0; i < n + 1; ++i) { a[i].resize(m + 1); } } void update(int x, int y, int v) { for (int i = x; i <= n; i += i & -i) { for (int j = y; j <= m; j += j & -j) { a[i][j] += v; } } } void update(int x1, int y1, int x2, int y2, int v) { update(x1, y1, v); update(x2 + 1, y2 + 1, v); update(x1, y2 + 1, -v); update(x2 + 1, y1, -v); } int query(int x, int y) { int res = 0; for (int i = x; i > 0; i -= i & -i) { for (int j = y; j > 0; j -= j & -j) { res += a[i][j]; } } return res; } }bit; void read(int &x) { x = 0; char ch; while (!isdigit(ch = getchar())); while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } } int main() { while (scanf("%d%d%d", &n, &m, &q) != EOF) { a.clear(); a.resize(n * m + 1); b.clear(); b.resize(n * m + 1); bit.init(); for (int i = 1; i <= n; ++i) { for (int j = 1, x; j <= m; ++j) { read(x); a[x].emplace_back(i, j); } } for (int i = 1, k, x1, y1, x2, y2; i <= q; ++i) { read(x1); read(y1); read(x2); read(y2); read(k); b[k].push_back(node(x1, y1, x2, y2)); bit.update(x1, y1, x2, y2, 1); } int res = 0; for (int i = 1; i <= n * m; ++i) { for (auto it : b[i]) { bit.update(it.x[0], it.y[0], it.x[1], it.y[1], -1); } for (auto it : a[i]) { if (bit.query(it.fi, it.se) != 0) { ++res; } } for (auto it : b[i]) { bit.update(it.x[0], it.y[0], it.x[1], it.y[1], 1); } } printf("%d\n", res); } return 0; }思路二： 考虑每次施肥的时候加上的是\(k_i\)而不是1，那么最终如果作物没有死，那么它的值应该是\(a[i][j] \cdot 施肥次数\)。 但是这样容易被卡，将权值映射成素数即可。 时间复杂度：\(\mathcal{O}(n + m + 10^7)\)
代码二：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 15500010 int prime[1000010], tot; bool check[N]; void init() { tot = 0; memset(check, 0, sizeof check); for (int i = 2; i < N; ++i) { if (!check[i]) { prime[++tot] = i; if (tot >= 1000000) break; } for (int j = 1; j <= tot; ++j) { if (1ll * i * prime[j] >= N) break; check[i * prime[j]] = 1; if (i % prime[j] == 0) { break; } } } } int n, m, q; vector <vector<int>> a, c; vector <vector<ll>> b; template <class T> void up(vector <vector<T>> &vec, int x1, int y1, int x2, int y2, int v) { vec[x1][y1] += v; vec[x2 + 1][y2 + 1] += v; vec[x1][y2 + 1] -= v; vec[x2 + 1][y1] -= v; } template <class T> void work(vector <vector<T>> &vec) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { vec[i][j] += vec[i - 1][j] + vec[i][j - 1] - vec[i - 1][j - 1]; } } } int main() { init(); random_shuffle(prime + 1, prime + 1 + tot); while (scanf("%d%d%d", &n, &m, &q) != EOF) { a.clear(); a.resize(n + 2, vector <int> (m + 2, 0)); b.clear(); b.resize(n + 2, vector <ll> (m + 2, 0)); c.clear(); c.resize(n + 2, vector <int> (m + 2, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &a[i][j]); } } int x[2], y[2], k; while (q--) { scanf("%d%d%d%d%d", x, y, x + 1, y + 1, &k); up(b, x[0], y[0], x[1], y[1], prime[k]); up(c, x[0], y[0], x[1], y[1], 1); } work(b); work(c); int res = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (b[i][j] != c[i][j] * prime[a[i][j]]) { ++res; } } } printf("%d\n", res); } return 0; }思路三： 依据：\[ \begin{eqnarray*} 2c &=& a + b\\ 2c^2 &=& a^2 + b^2 \\ \end{eqnarray*} \] 当且仅当\(a = b = c\)时成立。 增加一个平方验证。
代码三：
#include <bits/stdc++.h> using namespace std; #define ll long long int n, m, q; vector <vector<int>> a, c; vector <vector<ll>> b; template <class T> void up(vector <vector<T>> &vec, int x1, int y1, int x2, int y2, int v) { vec[x1][y1] += v; vec[x2 + 1][y2 + 1] += v; vec[x1][y2 + 1] -= v; vec[x2 + 1][y1] -= v; } template <class T> void work(vector <vector<T>> &vec) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { vec[i][j] += vec[i - 1][j] + vec[i][j - 1] - vec[i - 1][j - 1]; } } } void read(int &x) { x = 0; char ch; while (!isdigit(ch = getchar())); while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } } int main() { while (scanf("%d%d%d", &n, &m, &q) != EOF) { a.clear(); a.resize(n + 2, v ector <int> (m + 2, 0)); b.clear(); b.resize(n + 2, vector <ll> (m + 2, 0)); c.clear(); c.resize(n + 2, vector <int> (m + 2, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { read(a[i][j]); } } int x[2], y[2], k; while (q--) { read(x[0]); read(y[0]); read(x[1]); read(y[1]); read(k); up(b, x[0], y[0], x[1], y[1], 1ll * k); up(c, x[0], y[0], x[1], y[1], 1); } work(b); work(c); int res = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (b[i][j] != c[i][j] * a[i][j]) { ++res; } } } printf("%d\n", res); } return 0; }思路四： 考虑两个数不同，那么它们的二进制位至少有一位是不同的。 那么考虑枚举二进制位，当每次操作的\(k_i\)的当前二进制上为一时那么施肥。 然后枚举每个作物：
如果当前作物的\(a[i][j]\)的二进制位上为\(1\)，如果施肥总次数与当次总次数不同，那么它挂了如果当前作物的\(a[i][j]\)的二进制位上为\(0\)，如果存在施肥次数，那么它挂了实现的时候开一维数组然后映射二维坐标就过了，开二维vector就T了。。
代码四：
#include <bits/stdc++.h> using namespace std; #define N 4000010 #define y1 y_1 int x1[N], y1[N], x2[N], y2[N], k[N]; int n, m, q; int a[N], b[N], c[N]; bool die[N]; int id(int x, int y) { return (x - 1) * (m + 2) + y; } void up(int *f, int x1, int y1, int x2, int y2, int v) { f[id(x1, y1)] += v; f[id(x2 + 1, y2 + 1)] += v; f[id(x1, y2 + 1)] -= v; f[id(x2 + 1, y1)] -= v; } void work(int *f) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { f[id(i, j)] += f[id(i - 1, j)] + f[id(i, j - 1)] - f[id(i - 1, j - 1)]; } } } int main() { while (scanf("%d%d%d", &n, &m, &q) != EOF) { memset(b, 0, sizeof b); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &a[id(i, j)]); } } for (int i = 1; i <= q; ++i) { scanf("%d%d%d%d%d", x1 + i, y1 + i, x2 + i, y2 + i, k + i); up(b, x1[i], y1[i], x2[i], y2[i], 1); } work(b); for (int i = 15; i >= 0; --i) { for (int _i = 1; _i <= n; ++_i) { for (int _j = 1; _j <= m; ++_j) { c[id(_i, _j)] = 0; } } for (int j = 1; j <= q; ++j) { if (k[j] >> i & 1) { up(c, x1[j], y1[j], x2[j], y2[j], 1); } } work(c); for (int _i = 1; _i <= n; ++_i) { for (int _j = 1; _j <= m; ++_j) { if (a[id(_i, _j)] >> i & 1) { if (b[id(_i, _j)] != c[id(_i, _j)]) { die[id(_i, _j)] = 1; } } else if (c[id(_i, _j)]) { die[id(_i, _j)] = 1; } } } } int res = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { res += die[id(i, j)]; } } printf("%d\n", res); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11108613.html
