感觉错失了上分机会
A – Takahashi san (abc325 A)
题目大意
给定姓和名，输出尊称，即姓+san。
解题思路
按照题意模拟即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
cout B – World Meeting (abc325 B)
题目大意
给定(n)个地区的公司人数和对应的时区，规定上班时间为 (9:00-18:00)，现召开一小时会议，上班期间的公司可以参加。问订个时间，能参与的人数的最大值。
解题思路
枚举开会的时间，然后依次判断每个公司能否参加，累计参加人数，取最大值即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector> a(n);
for (auto& i : a)
cin >> i[0] >> i[1];
int ans = 0;
auto is_work_time = [](int time) { return time >= 9 && time C – Sensors (abc325 C)
题目大意
给定二维平面，有#和.。每个#可以与周围八个格子连成一整体。
问有多少个整体。
解题思路
用BFS或者并查集判断一下连通性，最后数连通块即可。
神奇的代码
#include
using namespace std;
using LL = long long;
class dsu {
public:
vector p;
vector sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
sz.resize(n);
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
dsu d(h * w);
auto two2one = [&](int x, int y) { return x * w + y; };
vector s(h);
for (int i = 0; i > s[i];
for (int j = 1; j 0 && s[i - 1][j - 1] == '#' && s[i][j] == '#') {
d.unite(two2one(i - 1, j - 1), two2one(i, j));
}
if (j + 1 D – Printing Machine (abc325 D)
题目大意
给定(n)个物品的出现时间和消失时间。拿一个物品花费 (1)的时间。
问最多能拿多少个物品。
解题思路
对于某一时刻，我肯定拿出现的物品中，最早消失的物品。
由此贪心拿即可。
注意每拿完一个物品后要考虑是否有新物品出现。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector> a(n);
for (auto& i : a)
cin >> i[0] >> i[1];
vector id(n);
iota(id.begin(), id.end(), 0);
ranges::sort(id, [&](int x, int y) {
if (a[x][0] != a[y][0])
return a[x][0] item;
LL time = 0;
int ans = 0;
auto it = id.begin();
while (!item.empty() || it != id.end()) {
if (item.empty())
time = a[*it][0];
while (it != id.end() && a[*it][0] = time) {
++ans;
++time;
item.pop();
}
}
cout E – Our clients, please wait a moment (abc325 E)
题目大意
给定一张完全图，从(1)号点到 (n)号点，一开始打车，在某点可转成坐火车，但不能转回来。
从一个点到另一个点，打车和火车的耗时不同。
问最少耗时。
解题思路
注意到我们肯定是在某一点(a)转乘火车，那从(1)号点到 (n)号点就分成了两部分：
- 先打车到(a)号点（可以看成从(a)号点打车到 (1)号点）
- 再乘火车到 (n)号点
因此我们可以预处理出，每个点打车到(1)号点和坐火车到 (n)号点的最短耗时。然后两者的和的最小值就是答案。
而求每个点到 (1)号点的耗时和到 (n)号点的耗时，相当于分别从 (1)号点出发到每个点的耗时，以及从 (n)号点出发到每个点的耗时，两次 最短路即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, a, b, c;
cin >> n >> a >> b >> c;
vector> tu(n, vector(n));
for (auto& i : tu)
for (auto& j : i)
cin >> j;
LL ans = numeric_limits::max();
auto dijkstra = [&](int st, function E, vector& dis) {
dis[st] = 0;
priority_queue> team;
team.push({0, st});
while (!team.empty()) {
auto [expect, u] = team.top();
team.pop();
if (dis[u] != -expect)
continue;
for (int v = 0; v dis[u] + E(tu[u][v])) {
dis[v] = dis[u] + E(tu[u][v]);
team.push({-dis[v], v});
}
}
}
};
vector dis0(n, numeric_limits::max());
auto dis1 = dis0;
dijkstra(
0, [&](int w) { return 1ll * w * a; }, dis0);
dijkstra(
n - 1, [&](int w) { return 1ll * w * b + c; }, dis1);
for (int i = 0; i F – Sensor Optimization Dilemma (abc325 F)
题目大意
给定(n)个区间长度，有两种操作，
- 操作一，区间长度减 (a_1)，成本 (c_1)，最多用 (k_1)次
- 操作二，区间长度减 (a_2)，成本 (c_2)，最多用 (k_2)次
问将每个区间长度减成非正的最小成本。
解题思路
考虑搜索的状态，就是当前的区间，操作一的使用次数，操作二的使用次数，然后枚举当前区间使用的操作一的次数，复杂度是(O(nk^3))。
上述搜索转换成 (dp)的形式就是 (dp[i][j][k])表示前(i) 个区间，操作一用了(j)次，操作二用了 (k)次，这一状态是否合法（即 bool型，成本从两个操作次数就能算出来），这难免过于浪费，我们可以把一个状态放到(dp)的值里。
即设 (dp[i][j])表示前 (i)个区间，操作一用了 (j)次时，操作二使用的最小次数（换句话说就是最小成本），转移同样是枚举当前区间的操作一的次数，时间复杂度是 (O(nk^2))。
神奇的代码
#include
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector d(n);
for (auto& i : d)
cin >> i;
array l{}, c{}, k{};
for (int i = 0; i > l[i] >> c[i] >> k[i];
vector dp(k[0] + 1, inf);
dp[0] = 0;
for (auto& i : d) {
vector dp2(k[0] + 1, inf);
for (int j = 0; j ::max();
for (int i = 0; i ::max())
ans = -1;
cout G – offence (abc325 G)
题目大意
给定一个字符串(s)和一个数 (k)，每次可以将 of连带后面的最多(k)个字符删除。
问字符串剩余的最小长度。
解题思路
依次考虑每个前缀，设(dp[i])表示 (s[1..i])经过操作后的最小长度，则 (dp[i] = min(dp[i – 1] + 1, dp[j – 1]))，其中 (j)是满足(s[j..i])能完全被删除的。
从中我们发现需要求一个(del[i][j])表示 (s[i..j])能否被完全删除，这是一个常见的区间(dp)。考虑转移，分两种情况
- 一个就是常规的转移，即(del[i][j] |= del[i][l] & del[l+1][j])
- 另一个是考虑进行一次操作，即(s[i]=o)，找到(s[l]=f)的地方，(s[l+1..j])的进行操作后的最短长度 (leq k)，这样就可以通过一次操作就把 (del[i][j])完全删除。
设(s[i..j])的进行操作后的最短长度为(mink[i][j])，其转移就两种：
- 一个就是常规的转移，即(mink[i][j] = min(mink[i][l] + mink[l+1][j]))
- 另一个就是当(del[i][j]=true)时， (mink[i][j]=0)
这样 (dp)数组就可以转移求答案了。
其实最后发现 (mink[0][n-1])就是答案。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
int k;
cin >> s >> k;
vector> dp(s.size() + 1, vector(s.size() + 1, 0));
vector> mink(s.size() + 1, vector(s.size() + 1, 0));
for (int i = 0; i = 0; --i) {
mink[i][j] = j - i + 1;
for (int l = i; l dp2(s.size(), 0);
dp2[0] = 1;
for (int i = 1; i 可以发现这是一道区间(dp)，从它操作结果可以合并可以感受出来。即设 (dp[l][r])表示子串 (s[l..r])经过操作后的最小长度。
其中一个转移就是(dp[l][r] = min(dp[l][i] + dp[i + 1][r]))，就是两个区间的合并。
还有一个转移就是经过操作的转移，可以发现这类转移都可以归到(s[l]=o)的情况，因为如果 (s[l] neq o)的话，其实可以归成上面这种情况。如果 (s[l]=o)，那么就找一个 (s[i]=f)，如果 (dp[l+1][i-1] = 0)，即完全删除，可以拼接出一个新的 (of)，那么 (dp[l][r] = max(dp[i + 1][r] – k, 0))，即一个前缀被删除了，剩下的字符最多可再减去(k)个字符。
时间复杂度都是(O(n^3))。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
int k;
cin >> s >> k;
vector> dp(s.size() + 1, vector(s.size() + 1, 0));
for (int r = 0; r = 0; --l) {
dp[l][r] = r - l + 1;
for (int m = l; m 机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
