＃ A
就是找最短区间存在这10个字母呗， O（n）
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> void clear(T &a) { T().swap(a); }
const int N = 1e5 + 5;
int n, m, _, k;
char s[N], t[] = "puleyaknoi";
int v[10];
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> s + 1; int cnt = 0, ans = 1e9;
rep (i, 0, 9) v[i] = 0;
for (int i = 1; s[i]; ++i) {
rep (j, 0, 9)
if (s[i] == t[j]) { cnt += !v[j], v[j] = i; break; }
if (cnt == 10) {
int mi = 1e9, mx = 0;
rep (j, 0, 9) umin(mi, v[j]), umax(mx, v[j]);
umin(ans, mx - mi + 1);
}
}
if (ans == 1e9) cout << "-1
";
else cout << ans << '
';
}
return 0;
}
B
二分呗, 提前记录 字母 'p' 出现的位置作为二分判定的起点
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> void clear(T &a) { T().swap(a); }
const int N = 1e5 + 5;
int n, m, _, k;
char s[N], t[] = "puleyaknoi";
VI c;
bool check(int mid) {
for (int &a : c) {
int cnt = 0;
for (int i = a; t[cnt] && i - a + 1 <= mid && s[i]; ++i)
if (s[i] == t[cnt]) ++cnt;
if (cnt == 10) return 1;
}
return 0;
}
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> s; clear(c);
for (int i = 0; s[i]; ++i) if (s[i] == 'p') c.pb(i);
int l = 10, r = 1e5 + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (r == 1e5 + 1) cout << "-1
";
else cout << r << '
';
}
return 0;
}
C
存在 两个节点的环, 找一下就好了, 就两个系节点的环
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }
template<class T> void clear(T& a) { T().swap(a); }
const int N = 1e7 + 10;
int n, m, _, k;
int prime[N], miu[N], tot;
bool v[N];
void init(int n) {
miu[1] = 1;
rep (i, 2, n) {
if (!v[i]) prime[++tot] = i, miu[i] = -1;
for (int j = 1; prime[j] <= n / i && j <= tot; ++j) {
v[prime[j] * i] = 1;
if(i % prime[j] == 0) { miu[i * prime[j]] = 0; break; }
else miu[i * prime[j]] = -miu[i];
}
}
}
int main() {
IOS; init(1e7);
for (cin >> _; _; --_) {
ll m; cin >> n >> m;
bool f1 = 0, f2 = 0;
for (int c = 0; miu[n] != 0 && m; --m) {
if (f1 && f2) {
if (m & 1) n += c;
break;
}
if (miu[n] == 1) f1 = 1, c = -1;
else f2 = 1, c = 1;
n += miu[n];
}
cout << n << '
';
}
return 0;
}
D
用不着离散化, 也不用存谁连谁, 用map存下 哪个节点连了几条边就好了, 用 set存边 (min(u, v), max(u,v)) 存这条就行
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }
template<class T> void clear(T& a) { T().swap(a); }
const int N = 1e5 + 5;
int n, m, _, k;
unordered_map<int, int> st;
set<PII> s;
int main() {
IOS; cin >> n;
rep(i, 1, n) {
cin >> m;
if (m == 3) cout << k << '
';
else if (m == 1) {
int u, v; cin >> u >> v;
if (u > v) swap(u, v);
if (s.count({ u, v })) continue;
int a = ++st[u], b = ++st[v];
if (a == 1 && b == 1) ++k;
else if (min(a, b) > 1) --k;
s.insert({ u, v });
}
else {
int u, v; cin >> u >> v;
if (u > v) swap(u, v);
if (!s.count({ u, v })) continue;
int a = --st[u], b = --st[v];
if (!a && !b) --k;
else if (a && b) ++k;
s.erase({ u, v });
}
}
return 0;
}
F
区间操作, 求的是区间和绝对值最小, 那先求一下前缀和呗
那么对于 (l, r) 就是求 [l - 1, r - 1] 中谁和 sum[r] 差值最小呗
我们卡着 r, 求出对于 i ∈ [1, r - 1], abs(sum[r] - sum[i]) 最小, 离线回答就好了
这不是明显的线段树吗, 然后我就不会了
我是真没想到, 还能在每个节点存下 sum[l] ~ sum[r] 的
而且这道题 tag 是不能叠加的, 必须一次 push_down 到底, 那么必然超时
所以我们在 change 的时候 先处理右区间并记录最小的 abs, 那么在递归回来求左区间的时候, 一旦 大于 最小值 直接 return
答案对于从右向左是单调的, 最小值出现在靠近 r 的点上, 谁还管远处的点?
这每个节点存sum[l]~sum[r], 和 根据单调贪心减小复杂度 是真的秀
#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;
template<class T1, class T2> bool umin(T1& a, T2 b) { return a > b ? (a = b, true) : false; }
template<class T1, class T2> bool umax(T1& a, T2 b) { return a < b ? (a = b, true) : false; }
template<class T> void clear(T& a) { T().swap(a); }
const int N = 1e5 + 5, M = 3e5 + 5;
int n, m, _, k;
ll a[N], ans[M], mi;
struct tree {
struct node {
int l, r;
ll val = 2e18;
vector<ll> c;
} tr[N << 2];
void push_up(int rt) {
umin(tr[rt].val, min(tr[rt << 1].val, tr[rt << 1 | 1].val));
}
void build(int rt, int l, int r) {
tr[rt].l = l; tr[rt].r = r; tr[rt].c.resize(r - l + 1);
rep(i, l, r) tr[rt].c[i - l] = a[i];
sort(all(tr[rt].c));
if (l == r) return;
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
}
bool solve(int rt, ll k) {
auto it = upper_bound(all(tr[rt].c), k);
if (it != tr[rt].c.begin()) umin(tr[rt].val, k - *(it - 1));
if (it != tr[rt].c.end()) umin(tr[rt].val, *it - k);
if (mi <= tr[rt].val) return 1;
if (tr[rt].l == tr[rt].r) { umin(mi, tr[rt].val); return 1; }
return 0;
}
void change(int rt, int p, ll k) {
if (tr[rt].r <= p) { if (solve(rt, k)) return; }
int mid = tr[rt].l + tr[rt].r >> 1;
if (mid < p) change(rt << 1 | 1, p, k);
change(rt << 1, p, k);
push_up(rt);
mi = min(mi, tr[rt].val);
}
ll ask(int rt, int l, int r) {
if (tr[rt].l >= l && tr[rt].r <= r) return tr[rt].val;
int mid = tr[rt].l + tr[rt].r >> 1;
if (mid >= r) return ask(rt << 1, l, r);
else if (mid < l) return ask(rt << 1 | 1, l, r);
else return min(ask(rt << 1, l, r), ask(rt << 1 | 1, l, r));
}
} bit;
pair<int, PII> q[M];
int main() {
IOS; cin >> n >> m; ++n;
rep(i, 2, n) cin >> a[i];
rep(i, 2, n) a[i] += a[i - 1];
bit.build(1, 1, n);
rep(i, 1, m) {
cin >> q[i].se.fi >> q[i].fi;
q[i].se.se = i; ++q[i].fi;
}
sort(q + 1, q + 1 + m);
for (int i = 2, j = 1; i <= n; ++i) {
mi = 2e18;
bit.change(1, i - 1, a[i]);
while (j <= m && q[j].fi <= i) ans[q[j].se.se] = bit.ask(1, q[j].se.fi, i), ++j;
}
rep(i, 1, m) cout << ans[i] << '
';
return 0;
}