VP 五十八分钟苏童流体。好耶
A
#define GLIBCXX_DEBUG
#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long
const int N = 500100;
std::string s[N];
signed main() {
int n, cnt = 1;
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
std::cin >> s[i];
for (int i = 2; i < n; ++i) {
if (s[i] == "sweet" && s[i - 1] == "sweet") {
printf("No\n");
return 0;
}
}
puts("Yes");
return 0;
}
B
直接模拟即可。
#define GLIBCXX_DEBUG
#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long
const int N = 500100;
char s[510][510];
signed main() {
int n, m;
scanf("%lld%lld", &n, &m);
int x, y;
scanf("%lld%lld", &x, &y);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
std::cin >> s[i][j];
std::string xx;
std::cin >> xx;
for (auto &v : xx) {
if (v == 'U') {
if (x > 1 && s[x - 1][y] == '.')
--x;
} else if (v == 'D') {
if (x < n && s[x + 1][y] == '.')
++x;
} else if (v == 'L') {
if (y > 1 && s[x][y - 1] == '.')
--y;
} else {
if (y < m && s[x][y + 1] == '.')
++y;
}
}
std::cout << x << ' ' << y << '\n';
return 0;
}
C
简单贪心。容易发现甜度和咸度互相独立，因此分类甜度最少多少次，咸度最少多少次即可。排一下序就可以求出答案。
时间复杂度为 \(O(n\log n)\)。
#define GLIBCXX_DEBUG
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define int long long
const int N = 500100;
int a[N], b[N];
signed main() {
int n, x, y;
std::cin >> n >> x >> y;
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 1; i <= n; ++i)
std::cin >> b[i];
std::sort(a + 1, a + n + 1, std::greater<>());
std::sort(b + 1, b + n + 1, std::greater<>());
int c1 = 0, c2 = 0, s1 = 0, s2 = 0;
for (int i = 1; i <= n; ++i) {
s1 += a[i];
++c1;
if (s1 > x) break;
}
for (int i = 1; i <= n; ++i) {
s2 += b[i];
++c2;
if (s2 > y) break;
}
std::cout << std::min(c1, c2) << '\n';
return 0;
}
D
二分套二分板子。考虑对于每一个询问二分距离，然后两个二分分别二分出左边和右边最多可以选择多少个点，判断选择的点数是否超过了 \(k\) 即可。稍微有一点点细节。时间复杂度为 \(O(n\log^2n)\)。不知道有没有单 \(\log\) 做法。
#define GLIBCXX_DEBUG
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define int long long
const int N = 500100;
int a[N], b[N];
signed main() {
int n, x, y;
std::cin >> n >> x >> y;
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 1; i <= n; ++i)
std::cin >> b[i];
std::sort(a + 1, a + n + 1, std::greater<>());
std::sort(b + 1, b + n + 1, std::greater<>());
int c1 = 0, c2 = 0, s1 = 0, s2 = 0;
for (int i = 1; i <= n; ++i) {
s1 += a[i];
++c1;
if (s1 > x) break;
}
for (int i = 1; i <= n; ++i) {
s2 += b[i];
++c2;
if (s2 > y) break;
}
std::cout << std::min(c1, c2) << '\n';
return 0;
}
E
这不 AT_dp_e。最简单的思路是 \(f_{i,j,k}\) 表示当前选择前 \(i\) 个菜肴，甜度为 \(j\)，咸度为 \(k\) 最多可以选择多少个菜肴。但是显然过不去。考虑交换状态。设 \(f_{i,j,k}\) 表示当前选择前 \(i\) 个菜肴，选了 \(j\) 个菜肴，当前甜度为 \(k\) 的最小咸度为多少。式子显然。
时间复杂度为 \(O(n^2\min(X,Y))\)。
#define GLIBCXX_DEBUG
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
// #define int long long
const int N = 500100;
int a[N], b[N], f[83][83][10010];
signed main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
int n, x, y;
std::cin >> n >> x >> y;
for (int i = 1; i <= n; ++i)
std::cin >> a[i] >> b[i];
memset(f, 0x3f, sizeof f);
f[0][0][0] = 0;
// f[i][j][k] 表示当前吃了前 i 个菜肴，选择 j 个菜肴，当前甜度为 k 的最小咸度
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
for (int k = a[i]; k <= x; ++k)
for (int p = 0; p < i; ++p)
f[i][j][k] = std::min(f[i][j][k], f[p][j - 1][k - a[i]] + b[i]);
int res = 0;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= x; ++k)
if (f[i][j][k] <= y)
res = std::max(res, j);
if (res != n)
++res;
std::cout << res << '\n';
return 0;
}
F
首先把所有的边离线下来按照代价从小到大排序。
然后对于每一条边 \(l\sim r\)，若其前面的所有的边都已经加入最小生成树中，则可以考虑维护任意相邻的两个点 \(i,i+1\) 之间的连通性。每一次操作完毕之后一定贪心的让 \(l\sim r\) 中所有的点都连通，也就是说 \(l\sim r-1\) 之间的边全部删除。
直接暴力枚举显然不可行。因此考虑用一个 set 来维护答案，每一次用 lower_bound 找到其下一次要删除的边并将其刹删除。很明显每一条边最多只会被删除 \(1\) 次。因此时间复杂度为 \(O(n\log n)\) 可以通过。
#define GLIBCXX_DEBUG
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#define int long long
const int N = 2000100;
struct awa {
int a, b, c;
} wx[N];
bool operator<(const awa &l, const awa &r) {
return l.c < r.c;
}
int la[N];
signed main() {
int n, q;
scanf("%lld%lld", &n, &q);
for (int i = 1; i <= q; ++i)
scanf("%lld%lld%lld", &wx[i].a, &wx[i].b, &wx[i].c);
std::sort(wx + 1, wx + q + 1);
std::set<int> se;
for (int i = 1; i <= n; ++i)
se.insert(i), la[i] = i;
int cost = 0;
for (int i = 1; i <= q; ++i) {
auto it = se.lower_bound(wx[i].a);
int pos = la[*it], cnt = 0, tm;
for (; it != se.end() && wx[i].b >= la[*it]; se.erase(tm))
tm = *it, ++it, ++cnt;
se.insert(tm), la[tm] = pos;
cost += cnt * wx[i].c;
}
if (se.size() == 1)
printf("%lld\n", cost);
else
puts("-1");
}