A - Spoiler
Question
删除两个 |
之间的字符
Solution
按照题意模拟即可
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
string p1, p2;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '|') break;
p1.push_back(s[i]);
}
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] == '|') break;
p2.push_back(s[i]);
}
reverse(p2.begin(), p2.end());
cout << p1 + p2 << endl;
return 0;
}
B - Delimiter
Question
倒叙输出输入的数
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> p;
int x;
while (cin >> x) p.push_back(x);
reverse(p.begin(), p.end());
for (auto &x : p) cout << x << '\n';
return 0;
}
C - A+B+C
Question
给出三个集合 \(A,B,C\),每次询问给出一个 \(X\),问是否存在从 \(A,B,C\) 中挑出一个数字 \(a,b,c\),使得 \(a+b+c=X\)
Solution
由于集合大小很小,\(n^3\) 得预处理出 \(a+b+c\) 可能的所有值,最后 map 判断即可
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, l;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
cin >> m;
vector<int> b(m);
for (int i = 0; i < m; i++) cin >> b[i];
cin >> l;
vector<int> c(l);
for (int i = 0; i < l; i++) cin >> c[i];
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < l; k++)
mp[a[i] + b[j] + c[k]] = 1;
int q; cin >> q;
while (q--) {
int x; cin >> x;
cout << (mp.count(x) ? "Yes" : "No") << endl;
}
return 0;
}
D - String Bags
Question
初始时有一个空字符串 \(S\),此外有 \(1,2,\cdots,N\) 个袋子,每个袋子里面有装有一些字符串
袋子 \(i\) 里包含 \(A_i\) 个字符串,对于每个袋子,你可以选择两种操作中的一种:
- 支付 \(1\) 元,从袋子中选择一个字符串,将其连接到 \(S\) 的末尾
- 什么也不做
给定一个字符串 \(T\), 找到使最终 \(S=T\) 所需要的最小金额
Solution
一眼背包问题,定义 \(dp[i][j]\) 表示枚举到第 \(i\) 个袋子,前 \(i - 1\) 个袋子已经把 \(1\sim j\) 的字符串组成了的最小代价
对于每个袋子中的一个串 \(p\),如果 \(p=T[j,j+p.size-1]\) ,那么代表可以往后添加 \(p\) 字串,于是转移方程为:
\[dp[i][j+p.size-1]=\min\{dp[i-1][j]\} \]Code
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
string T; cin >> T; T = " " + T;
int n; cin >> n;
vector<vector<string> > a(n + 1);
for (int i = 1; i <= n; i++) {
int m; cin >> m;
for (int j = 0; j < m; j++) {
string s; cin >> s;
a[i].push_back(s);
}
}
vector<vector<int> > dp(n + 1, vector<int>(T.size(), INF));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < T.size(); j++) {
for (int k = 0; k < a[i].size(); k++) {
if (j + a[i][k].size() - 1 >= T.size()) continue;
if (T.substr(j, a[i][k].size()) == a[i][k])
dp[i][j + a[i][k].size() - 1] = min(dp[i][j + a[i][k].size() - 1], dp[i - 1][j - 1] + 1);
}
}
for (int j = 0; j < T.size(); j++)
dp[i][j] = min(dp[i][j], dp[i - 1][j]);
}
int ans = INF;
for (int i = 1; i <= n; i++)
ans = min(ans, dp[i][T.size() - 1]);
cout << (ans == INF ? -1 : ans) << endl;
return 0;
}
E - Insert or Erase
Question
给定长度为 \(N\) 的序列 \(A=(A_1,A_2,\cdots,A_N)\)。序列 \(A\) 的元素各不相同
按照给定序列的顺序处理 \(Q\) 个查询:
1 x y
:在 \(A\) 中元素 \(x\) 之后插入 \(y\)2 x
:从 \(A\) 中移除元素 \(x\)
输出处理完所有询问后的 \(A\)
Solution
这是一个非常好的题,如果 \(N\) 比较小的话,就是一个链表的典题,在一个元素后插入一个元素,删除一个元素
但是本题的 \(N\) 非常大,如果能在短时间内找到链表的 \(L[x],R[x]\) 就能快速解题了
而 C++ 的 map 就很好的做到了这一点,使用 map 看成数组记录链表的 \(L[x],R[x]\) 之后就是链表的正常操作了
Code
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
ios::sync_with_stdio(false);
int n; cin >> n;
unordered_map<int,int> right, left;
vector<int> a(n + 1, 0);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++) {
if (i != 1) left[a[i]] = a[i - 1];
if (i != n) right[a[i]] = a[i + 1];
}
left[a[1]] = -INF; right[a[n]] = INF;
left[INF] = a[n]; right[-INF] = a[1];
int q; cin >> q;
while (q--) {
int opt; cin >> opt;
if (opt == 1) {
int x, y; cin >> x >> y;
const int L = x, R = right[x];
left[y] = L; right[y] = R;
right[L] = y; left[R] = y;
}
if (opt == 2) {
int x; cin >> x;
const int L = left[x], R = right[x];
right[L] = R; left[R] = L;
left.erase(x); right.erase(x);
}
}
int x = right[-INF];
while (x != INF) {
cout << x << " ";
x = right[x];
}
return 0;
}
F - Earn to Advance
Question
有一个 \(N\times N\) 的网格,初始处于 \((1,1)\) ,金钱数为 \(0\)
当高桥处于 \((i,j)\) 时,可以在依次行动中执行以下操作之一:
- 留在原地并增加金钱 \(P_{i,j}\)
- 支付 \(R_{i,j}\) 移动到方格 \((i,j+1)\)
- 支付 \(D_{i,j}\) 移动到方格 \((i+1,j)\)
问高桥移动到 \((N,N)\) 的最小行动次数
Solution
高桥移动的过程肯定是移动到一个点,然后攒够足够的钱,然后尽量把一个现有的钱用完去移动到下一个点,然后再在下一个点攒钱
因为如果有两个点 \(A,B\) ,有 \(P_A < P_B\),那么高桥比起在 \(A\) 点攒钱,\(B\) 点攒钱肯定要划算一点,所以我们只需要在 \(A\) 点攒够足够的到 \(B\) 点的钱就好了
所以这样就可以定义 \(dp\) 了,定义 \(dp[x][y]\) 记录两个参数,第一个就是到 \(step\) 即到 \((x,y)\) 的最小步数,第二个是到 \(money\) 即到 \((x,y)\) 所剩下钱的最大值,其中要先保证步数最小,且需要在 \((x,y)\) 这点出攒钱
我们只需要枚举上一次攒钱的地方 \((x',y')\),需要额外的步数也就是是在 \((x',y')\) 处攒钱的步数为 \(dis/P_{x',y'}\) ,其中 \(dis\) 为 \((x,y)\) 到 \((x',y')\) 需要花费的钱的最小值
那么现在这个状态的步数和剩下的钱也就迎刃而解了
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pll;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int main() {
int n; cin >> n;
vector<vector<LL> > P(n + 1, vector<LL>(n + 1)), D(n + 1, vector<LL>(n + 1)), R(n + 1, vector<LL>(n + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> P[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j < n; j++)
cin >> R[i][j];
for (int i = 1; i < n; i++)
for (int j = 1; j <= n; j++)
cin >> D[i][j];
auto get_dis = [&](int x, int y) {
vector<vector<LL> > dis(n + 1, vector<LL>(n + 1, INF));
dis[x][y] = 0;
for (int px = n; px >= 1; px--)
for (int py = n; py >= 1; py--) {
if (px < x)
dis[px][py] = min(dis[px][py], dis[px + 1][py] + D[px][py]);
if (py < y)
dis[px][py] = min(dis[px][py], dis[px][py + 1] + R[px][py]);
}
return dis;
};
vector<vector<pll> > dp(n + 1, vector<pll>(n + 1, {INF,INF}));
dp[1][1] = {0,0};
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++) {
auto dis = get_dis(x,y);
for (int px = 1; px <= x; px++)
for (int py = 1; py <= y; py++){
auto [p_step, p_money] = dp[px][py];
LL ex_step = (dis[px][py] - p_money + P[px][py] - 1) / P[px][py]; ex_step = max(ex_step, 0LL);
LL now_step = p_step + ex_step + (x - px) + (y - py);
LL now_money = p_money + ex_step * P[px][py] - dis[px][py];
if (now_step < dp[x][y].first || (now_step == dp[x][y].first && now_money > dp[x][y].second))
dp[x][y] = {now_step, now_money};
}
}
cout << dp[n][n].first << endl;
return 0;
}
G - Points and Comparison
Question
在 \(xy\) 平面中有 \(N\) 个点 \((X_i,Y_i)\)
给出了 \(Q\) 对整数 \((A_j,B_j)\)
定义 \(f(A_j,B_j)\) 为满足 \(Y_i \ge A_j \times X_i + B_j\) 的 \(i\) 的数量
求 \(\sum\limits_{j=1}^Q f(A_j,B_j)\)
Solution
不妨设 \(k=A,b=B\) ,发现 \((A_j,B_j)\) 其实表示的是一条直线,而 \((X_i,Y_i)\) 表示的是平面上的一个点
观察 \(Y_i \ge k X_i+b\),就是点在直线上方或是刚在在直线上
由于 \(k,b\) 是固定的,移项 \(Y_i - kX_i \ge b\) ,也就是说,如果 \(Y_i-kX_i\) 是递增的,那么 \(b\) 就可以二分来找答案了
所以关键在于如何维护 \(Y_i-kX_i\) 递增,我们把这样的排列叫做排列 \(A\)
先考虑极端情况 \(k=-\infty\) ,那么 pair<int,int>
正好满足 \(A\) 排序
考虑 \(A\) 排序上的两个点 \((X_l,Y_l)\),\((X_r,Y_r)\) ,对于一个给定的 \(k\)
- 如果 \(X_l==X_r\),则排序还满足 \(Y_l,Y_r\) ,也就是说,\(l,r\) 的位置不变
- 如果 \(Y_l-kX_l > Y_r-kX_r\Longrightarrow \frac{Y_r-Y_l}{X_r-X_l} > k\) 也就是说,\(l,r\) 两点组成的斜率大于了 \(k\) ,则交换 \(l,r\)
考虑到没两个点至多只需要交换一次,所以把询问按照 \(k\) 从小到大排序,这样子对于每对关系,如果交换了一次,后面总是满足 \(A\) 排列的规则的
对于相邻的点 \((X_i,Y_i)\),\((X_{i+1},Y_{i+1})\) 的斜率值放到优先队列里面
如果说对于某一个 \(k\) 满足 \(k\) 大于其中的某个斜率了,就把对应的两个点交换,然后继续维护优先队列
当满足了对于一个 \(k\) 的排列 \(A\),就在 \(A\) 上面二分来找答案
对于时间复杂度分析,最多存在 \(N^2\) 对关系,所以交换操作最多操作 \(N^2\) 次,总时间复杂度为 \(O(Q(\log Q+\log N)+N^2\log N)\)
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pll;
const LL mod = (1ll << 31) - 1;
struct Line {
LL up, dn;
int pre, nxt; // 两者的编号
Line(LL _up, LL _dn, int _pre, int _nxt) {
if (dn < 0) up = -up, dn = -dn;
up = _up, dn = _dn, pre = _pre, nxt = _nxt;
}
bool operator < (const Line &rhs) const {
return up * rhs.dn > dn * rhs.up;
}
bool operator == (const Line &rhs) const {
return up == rhs.up && dn == rhs.dn && pre == rhs.pre && nxt == rhs.nxt;
}
};
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vector<pll> a(n + 1);
for (int i = 1; i <= n; i++) {
auto & [k, b] = a[i];
cin >> k >> b;
}
sort (a.begin() + 1, a.end());
int Q; cin >> Q;
int G0, Ra, Rb; cin >> G0 >> Ra >> Rb;
vector<pll> q(Q + 1); vector<LL> G(3 * Q + 1); G[0] = G0;
for (int i = 1; i <= 3 * Q; i++)
G[i] = (48271 * G[i - 1]) % mod;
for (int i = 1; i <= Q; i++) {
auto &[A, B] = q[i];
A = -Ra + (G[3 * i - 2] % (2 * Ra + 1));
B = -Rb + ((G[3 * i - 1] * mod + G[3 * i]) % (2 * Rb + 1));
}
sort (q.begin() + 1, q.end());
auto make_line = [&] (int i, int j) {
return Line(a[j].second - a[i].second, a[j].first - a[i].first, i, j);
};
priority_queue<Line> s;
for (int i = 1; i < n; i++)
if (a[i].first < a[i + 1].first)
s.push (make_line(i, i + 1));
LL ans = 0;
for (int i = 1; i <= Q; i++) {
auto [k, b] = q[i];
while (s.size() > 0) {
auto it = s.top();
int dn = it.dn, up = it.up, pre = it.pre, nxt = it.nxt;
if (!(make_line(pre, nxt) == it)) {s.pop(); continue;} // 说明这个线段已经被更新过了
if (k * dn < up) break; // 当 k > 两点的斜率时,交换
s.pop(); swap(a[pre], a[nxt]);
if (pre > 1 && a[pre - 1].first < a[pre].first) s.push(make_line(pre - 1, pre));
if (nxt < n && a[nxt].first < a[nxt + 1].first) s.push(make_line(nxt, nxt + 1));
}
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
auto [X, Y] = a[mid];
if ( -k * X + Y >= b) r = mid - 1;
else l = mid + 1;
}
ans += n - r;
}
cout << ans << endl;
return 0;
}
标签:AtCoder,int,题解,py,cin,344,vector,dp,dis
From: https://www.cnblogs.com/martian148/p/18068219