CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Stickers and Toys
#include <stdio.h>
int T, n, s, t;
int main()
{
for (scanf("%d", &T); T--; printf("%d\n", n - (s < t ? s : t) + 1))
scanf("%d%d%d", &n, &s, &t);
}
Letters Shop
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
vector<int> v[127];
char s[N];
int n, m;
int main()
{
scanf("%d%s%d", &n, &s, &m);
for (int i = 0; s[i]; ++i)
v[s[i]].push_back(i);
for (; m--; printf("%d\n", n + 1))
{
scanf("%s", s);
vector<int> p(127);
for (int i = n = 0; s[i]; ++i)
n = max(n, v[s[i]][p[s[i]]++]);
}
}
Vasya And Array
#include <bits/stdc++.h>
using namespace std;
const int N = 1023;
vector<pair<int, int>> v;
int n, m, ans[N], a[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0, t, l, r; i < m; ++i)
{
scanf("%d%d%d", &t, &l, &r);
if (t)
fill(a + l, a + r, 1);
else
v.emplace_back(l, r);
}
ans[1] = n;
for (int i = 1; i < n; ++i)
ans[i + 1] = a[i] ? ans[i] : ans[i] - 1;
for (auto p : v)
if (is_sorted(ans + p.first, ans + p.second + 1))
return printf("NO"), 0;
printf("YES\n");
for (int i = 1; i <= n; ++i)
printf("%d ", ans[i]);
}
Subarray Sorting
#include <bits/stdc++.h>
using namespace std;
struct Fenwick : vector<int>
{
Fenwick(int n) : vector<int>(n) {}
void upd(int x, int k)
{
for (; x < size(); x += x & -x)
at(x) = max(at(x), k);
}
int ask(int x)
{
int r = 0;
for (; x; x -= x & -x)
r = max(r, at(x));
return r;
}
};
int main()
{
int t, n, ans;
for (scanf("%d", &t); t--; puts(ans ? "YES" : "NO"))
{
scanf("%d", &n);
vector<int> a(n + 1);
vector<deque<int>> v(n + 1);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1, b; i <= n; ++i)
scanf("%d", &b), v[b].push_back(i);
Fenwick t(n + 9);
for (int i = ans = 1; i <= n; ++i)
{
if (v[a[i]].empty() || t.ask(a[i] - 1) > v[a[i]].front())
{
ans = 0;
break;
}
t.upd(a[i], v[a[i]].front());
v[a[i]].pop_front();
}
}
}
Tree Painting
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 9;
vector<int> g[N];
ll n, siz[N], sum[N];
void dfs(int u, int fa)
{
for (int to : g[u])
if (to != fa)
{
dfs(to, u);
siz[u] += siz[to];
sum[u] += sum[to];
}
sum[u] += ++siz[u];
}
void dfs2(int u, int fa)
{
if (fa)
sum[u] = (sum[fa] - siz[u]) + (n - siz[u]);
for (int to : g[u])
if (to != fa)
dfs2(to, u);
}
int main()
{
scanf("%lld", &n);
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);
dfs2(1, 0);
printf("%lld", *max_element(sum + 1, sum + n + 1));
}