A. Alice's Adventures in "Chess"
题意：你从(0, 0)出发，重复固定的移动路径，问能不能经过(a, b)。
直接跑一百次就行，因为ab都很小（其实只要跑20次）。
点击查看代码
void solve() {
int n, a, b;
std::cin >> n >> a >> b;
int x = 0, y = 0;
std::string s;
std::cin >> s;
std::vector<std::pair<int, int> > c;
for (auto & ch : s) {
if (ch == 'N') {
++ y;
} else if (ch == 'E') {
++ x;
} else if (ch == 'S') {
-- y;
} else {
-- x;
}
c.push_back({x, y});
}
for (int i = 0; i <= 100; ++ i) {
for (auto & it : c) {
if (it.first == a && it.second == b) {
std::cout << "YES\n";
return;
}
it.first += x; it.second += y;
}
}
std::cout << "NO\n";
}
B. Alice's Adventures in Permuting
题意：给你一个数组的生成式：\(a_i\)=(i-1)*b+c，每次把最大的数变成mex，问需要多少次可以变成0到n-1的排列。
自己写几个样例发现，如果全部数都小于n，那么b=1,c=0的情况是0次操作，b=0的话，c>=n是n次操作，c>=n-2是n-1次操作，其他都是-1。
对于数组里有大于等于n的数的情况，那么每次会把一个大于等于n的数变成mex，如果有m个大于等于n的数，就会操作m次，我是用二分找的这个m。
点击查看代码
void solve() {
using i128 = __int128;
i64 n, b, c;
std::cin >> n >> b >> c;
if (b == 0 && c >= n) {
std::cout << n << "\n";
return;
}
if (b == 0 && c >= n - 2) {
std::cout << n - 1 << "\n";
return;
}
if ((i128)(n - 1) * (i128)b + c == n - 1) {
std::cout << 0 << "\n";
return;
}
if ((i128)(n - 1) * (i128)b + c < n - 1) {
std::cout << -1 << "\n";
return;
}
i64 l = 1, r = n;
while (l < r) {
i64 mid = l + r >> 1;
if ((i128)(mid - 1) * (i128)b + c >= n) {
r = mid;
} else {
l = mid + 1;
}
}
std::cout << n - l + 1 << "\n";
}
C. Alice's Adventures in Cutting Cake
题意：你要把一个数组分成m+1组，每一组都由连续的元素组成，其中m组每组总和要大于等于v，要让剩下属于我们的一组在满足这些条件下的总和最大。
如果我们以i开始，那么前面i-1个应该正好分成满足条件的几组，不然我们的开始位置可以往前移。那么我们可以从前往后枚举前面分几组，那么我们这组能取到后面哪个位置呢？为了让后面的组对我们的影响最小，应该从最后开始分给他们，那就预处理从后面开始到第i个可以取满几个组，那么如果我们前面有了k组，那么可以二分后面分成m-k组的最大下标，那么中间的数就都属于我们。
点击查看代码
void solve() {
int n, m;
i64 v;
std::cin >> n >> m >> v;
std::vector<i64> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::vector<i64> sum(n + 1);
for (int i = 0; i < n; ++ i) {
sum[i + 1] = sum[i] + a[i];
}
std::vector<int> cnt(n + 2);
for (int i = n; i >= 1; -- i) {
int j = i;
while (j && sum[i] - sum[j - 1] < v) {
-- j;
}
if (j) {
cnt[j] = cnt[i + 1] + 1;
}
i = j;
}
for (int i = n; i >= 1; -- i) {
cnt[i] = std::max(cnt[i], cnt[i + 1]);
}
if (cnt[1] < m) {
std::cout << -1 << "\n";
return;
};
i64 ans = 0;
for (int i = 1, k = m; i <= n; ++ i, -- k) {
int l = i + 1, r = n + 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (cnt[mid] >= k) {
l = mid;
} else {
r = mid - 1;
}
}
if (cnt[l] >= k) {
ans = std::max(ans, sum[l - 1] - sum[i - 1]);
}
int j = i;
while (j <= n && sum[j] - sum[i - 1] < v) {
++ j;
}
i = j;
}
std::cout << ans << "\n";
}
D. Alice's Adventures in Cards
题意：我们手里有一个1，希望它变到n，我们可以和三个人交换，每个人对i都有一个重视值，如果第i个数重视值大于第j个数，那么我们可以用j换i。我们只可以换比手里更大的数。要求给定一个操作序列。
正解好像是dp，我写了个差不多搜索的东西。
三个set存分别存{\(a_i\), i}, {\(b_i\), i}, {\(c_i\), i}。
开始我们把1入队，用优先队列每次出最小的数。然后把还没进队的比当前数小的数从三个set里都删了。然后三个set分别lower_bound一下枚举比当前数值小的数，求个最短路记录转移，最后把新入队的数统一从三个set里删了。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n + 1), b(n + 1), c(n + 1);
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
}
for (int i = 1; i <= n; ++ i) {
std::cin >> b[i];
}
for (int i = 1; i <= n; ++ i) {
std::cin >> c[i];
}
std::vector<int> pre(n + 1);
std::vector<std::string> op(n + 1);
std::priority_queue<int, std::vector<int>, std::greater<int> > q;
q.push(1);
std::set<int> s;
std::set<std::pair<int, int> > sa, sb, sc;
for (int i = 2; i <= n; ++ i) {
s.insert(i);
sa.insert({a[i], i});
sb.insert({b[i], i});
sc.insert({c[i], i});
}
while (q.size()) {
int u = q.top(); q.pop();
while (s.size() && *s.begin() < u) {
int id = *s.begin();
sa.erase({a[id], id});
sb.erase({b[id], id});
sc.erase({c[id], id});
s.erase(s.begin());
}
std::vector<int> del;
auto ia = sa.lower_bound({a[u], 0});
while (ia != sa.begin()) {
-- ia;
int v = ia->second;
if (op[v].empty()) {
pre[v] = u;
op[v] = "Q";
q.push(v);
del.push_back(v);
}
}
auto ib = sb.lower_bound({b[u], 0});
while (ib != sb.begin()) {
-- ib;
int v = ib->second;
if (op[v].empty()) {
pre[v] = u;
op[v] = "K";
q.push(v);
del.push_back(v);
}
}
auto ic = sc.lower_bound({c[u], 0});
while (ic != sc.begin()) {
-- ic;
int v = ic->second;
if (op[v].empty()) {
pre[v] = u;
op[v] = "J";
q.push(v);
del.push_back(v);
}
}
for (auto & id : del) {
sa.erase({a[id], id});
sb.erase({b[id], id});
sc.erase({c[id], id});
s.erase(id);
}
}
if (s.count(n)) {
std::cout << "NO\n";
} else {
std::cout << "YES\n";
std::vector<std::string> ans;
int i = n;
while (i > 1) {
ans.push_back(op[i] + " " + std::to_string(i));
i = pre[i];
}
std::reverse(ans.begin(), ans.end());
std::cout << ans.size() << "\n";
for (auto & s : ans) {
std::cout << s << "\n";
}
}
}