statement:https://codeforces.com/gym/102452
赛中过题: B D G (有一说一差点偷鸡出线)
C. Constructing Ranches
给一棵树，点带权，问有多少条路径的点权能构成一个严格(指有面积)的多边形。
结论：充要条件为
考虑点分治, 处理出当前分治子树下所有点到分治点的路径中的权值和以及权值最大值.
然后按权值最大值排序，用树状数组计数，复杂度为.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> pil;
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
const int N = 200010;
vector<int> E[N];
vector<pil> info;
int sz[N], a[N];
bool vis[N];
void prepare(int u, int fa) {
sz[u] = 1;
for(auto &v : E[u]) {
if(v == fa || vis[v]) continue;
prepare(v, u);
sz[u] += sz[v];
}
}
void getroot(int u, int fa, int &m, int &root) {
if(sz[u] * 2 < m) return;
if(sz[u] < sz[root]) root = u;
for(auto &v : E[u]) {
if(v == fa || vis[v]) continue;
getroot(v, u, m, root);
}
}
void getinfo(vector<pil> &info, int u, int fa, int nowmx, ll nowsum) {
nowmx = max(nowmx, a[u]), nowsum = nowsum + a[u];
for(auto &v : E[u]) {
if(v == fa || vis[v]) continue;
getinfo(info, v, u, nowmx, nowsum);
}
info.emplace_back(nowmx, nowsum);
}
ll calc(int u, int root) {
info.clear();
int _mx = u == root ? 0 : a[root], _a = _mx;
getinfo(info, u, 0, _mx, _a);
// info.pop_back();
vector<ll> dec(info.size());
for(int i = 0; i < (int)info.size(); i++) {
dec[i] = info[i].se - a[root];
}
sort(all(dec)); dec.erase(unique(all(dec)), dec.end());
vector<int> bit(dec.size() + 1, 0);
int L = dec.size();
auto add = [&](int x) { for(; x <= L; x += x&-x) bit[x]++;};
auto sum = [&](int x) { int ret = 0; for(; x; x -= x&-x) ret += bit[x]; return ret;};
sort(all(info), greater<pil>());
ll ret = 0;
for(auto &e : info) {
ret += sum(upper_bound(all(dec),e.se-a[root])-dec.begin());
int idx = upper_bound(all(dec),2*e.fi-e.se)-dec.begin()+1;
if(idx <= L) add(idx);
}
return ret;
}
ll divide(int u) {
prepare(u, 0);
int m = sz[u], root = u;
getroot(u, 0, m, root);
ll ret = calc(root, root); vis[root] = 1;
// cout << root << ' ' << ret << '\n';
// for(auto &e : info) cout << e.fi << ' ' << e.se << endl;
for(auto &v : E[root]) {
if(vis[v]) continue;
ret -= calc(v, root);
ret += divide(v);
}
return ret;
}
void solve(int cas) {
int n; cin >> n;
for(int i = 1; i <= n; i++) E[i].clear(), vis[i] = 0;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
E[u].emplace_back(v);
E[v].emplace_back(u);
}
cout << divide(1) << '\n';
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _; cin >> _;
for(int i = 1; i <= _; i++) solve(i);
return 0;
}
E. Erasing Numbers
给一个到
的排列，保证
一定是奇数.
每次你可以选择连续的三个数，并将三个数中的最大值和最小值删掉，删到只有最后一个数为止，
问第个数能否留在最后.
考虑比第个数大的数的个数和小的数的个数，如果能删到让两种数的个数相等，则第
个数可以留到最后。
贪心删个数多的一边即可，复杂度。
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 5010;
int a[N], n;
int go(int l, int r, int p) {
if(l > r) return 0;
int num1 = a[p] - 1, num2 = n - a[p];
int ret = 0, sz = 0;
if(num1 < num2) {
for(int i = l; i <= r; i++) {
if(a[i] > a[p]) {
if(++sz == 3) sz -= 2, ret++;
} else if(--sz == -1) sz = 0;
}
} else {
for(int i = l; i <= r; i++) {
if(a[i] < a[p]) {
if(++sz == 3) sz -= 2, ret++;
} else if(--sz == -1) sz = 0;
}
}
return ret;
}
void solve(int cas) {
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) {
int c1 = go(0, i - 1, i);
int c2 = go(i + 1, n - 1, i);
int c3 = abs(n + 1 - 2 * a[i]) / 2;
if(c1 + c2 >= c3) cout << "1";
else cout << "0";
}
cout << '\n';
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _; cin >> _;
for(int i = 0; i < _; i++) solve(i);
return 0;
} H. Hold the Line
两种操作：
1.在位置插入一个
;
2.查询区间中离
近的
,输出
.
线段树套的在线做法常数过大，考虑
分治，线段树套单调栈等离线做法.
加快读勉强卡过去.
#include<bits/stdc++.h>
using namespace std;
const int N = 1 << 19 | 7;
const int inf = 0x3f3f3f3f;
struct seg_t {
#define ls o << 1
#define rs o<<1|1
static int n;
static void set_n(int _n) { n = _n;}
struct node_t {
int val;
node_t() {}
node_t(int _val):val(_val) {}
operator int() { return val;}
void init(int _val) { val = _val;}
node_t operator + (const node_t &rhs) {
return node_t(max(val, rhs.val));
}
} node[N << 1];
void init() {
build();
}
void build(int o = 1, int l = 1, int r = n) {
if(!node[o].val) return;
node[o].val = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
// node[o] = node[ls] + node[rs];
}
void update(int x, int v, int o = 1, int l = 1, int r = n) {
if(l == r) return node[o].init(v);
int mid = (l + r) >> 1;
if(mid >= x) update(x, v, ls, l, mid);
else update(x, v, rs, mid + 1, r);
node[o] = node[ls] + node[rs];
}
node_t query(int ql, int qr, int o = 1, int l = 1, int r = n) {
if(ql <= l && r <= qr) return node[o];
node_t ret = 0; int mid = (l + r) >> 1;
if(ql <= mid) ret = ret + query(ql, qr, ls, l, mid);
if(qr > mid) ret = ret + query(ql, qr, rs, mid + 1, r);
return ret;
}
} tree;
int seg_t::n;
int ans[N * 2];
struct event {
int ty, l, r, h, id;
bool operator < (const event&rhs)const {
if(h != rhs.h) return h < rhs.h;
return ty < rhs.ty;
}
} E[N * 2], tE[N * 2];
void work(int l, int r) {
if(l == r) return;
if(r - l < 200) {
for(int i = l; i <= r; i++) if(E[i].ty) {
for(int j = l; j < i; j++) if(!E[j].ty && E[j].h <= E[i].h) {
if(E[i].l <= E[j].l && E[j].l <= E[i].r)
ans[E[i].id] = min(ans[E[i].id], E[i].h - E[j].h);
}
}
sort(E + l, E + r + 1);
return;
}
int mid = (l + r) >> 1;
work(l, mid); work(mid + 1, r);
int p = l, q = mid + 1, c = l;
while(q <= r) {
if(p <= mid && E[p] < E[q]) {
if(!E[p].ty) tree.update(E[p].l, E[p].h);
tE[c++] = E[p++];
} else {
if(E[q].ty) {
int t = tree.query(E[q].l, E[q].r);
if(t) ans[E[q].id] = min(ans[E[q].id], E[q].h - t);
}
tE[c++] = E[q++];
}
}
while(p <= mid) tE[c++] = E[p++];
for(int i = l; i <= r; i++) E[i] = tE[i];
tree.init();
}
inline char nc() {
#define SZ 1000000
static char buf[SZ], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, SZ, stdin), p1 == p2) ? EOF : *p1++;
#undef SZ
}
int scan(int &x) {
char c;
while(!isdigit(c = nc()) && c != EOF);
if(c == EOF) return c;
for(x = 0; isdigit(c); c = nc())
x = x * 10 + (c ^ 48);
return 1;
}
template<typename ...Args>
int scan(int &x, Args&...args) {
return scan(x), scan(args...);
}
void print(int x) {
static char buf[21], *p2;
if(x < 0) putchar('-'), print(-x);
else {
*(p2 = buf + 20) = '\0';
if(!x) *--p2 = 48;
while(x) *--p2 = x % 10 ^ 48, x /= 10;
puts(p2);
}
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
int _; scan(_);
while(_--) {
int n, q; scan(n, q);
for(int i = 0; i < q; i++) {
ans[i] = inf;
scan(E[i].ty);
if(E[i].ty) scan(E[i].l, E[i].r, E[i].h);
else scan(E[i].l, E[i].h), E[i].r = E[i].l;
E[i].id = i;
}
seg_t::set_n(n);
work(0, q - 1);
for(int i = 0; i < q; i++) tE[E[i].id] = E[i];
for(int i = 0; i < q; i++) E[i] = tE[i];
for(int i = 0; i < q; i++) E[i].h = 1e9 + 1 - E[i].h;
work(0, q - 1);
for(int i = 0; i < q; i++) tE[E[i].id] = E[i];
for(int i = 0; i < q; i++) E[i] = tE[i];
for(int i = 0; i < q; i++) {
if(E[i].ty) {
if(ans[i] == inf) ans[i] = -1;
print(ans[i]);
}
}
}
return 0;
} I. Incoming Asteroids
两种操作:
- 在
个容器里插入一个值为y的元素，当这个值y在一个容器改变时，它在其他容器的值也会改变。
- 将第
个容器的值全部减
，若有元素的值小于
，则按插入顺序输出他们，并从容器中删除。
两种操作均强制在线。
据CJB所说，这个idea来自2018年毛营.
将分成
份，分别插入到各个容器中，若
在某个容器中的值小于
则从其他容器中取出y，然后分成
份，重新插入到各个容器中，
每个容器用堆维护最小值，这样每次取出，
都会至少减小原来的
。均摊复杂度为
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int N = 200010;
int tot = 0;
vector<int> ans;
vector<int> p[N];
vector<ll> g[N];
ll del[N];
int val[N], vis[N];
struct event {
ll v;
int t, id;
event() {}
event(ll _v, int _t, int _id) { v = _v, t = _t, id = _id;}
bool operator < (const event &r)const {
return v > r.v;
}
};
priority_queue<event> A[N];
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, q; cin >> n >> q;
while(q--) {
int op; cin >> op;
if(op == 1) {
int id = ++tot;
int y, k; cin >> y >> k; y ^= ans.size();
val[id] = y;
p[id].resize(k);
g[id].resize(k);
y = (y + k - 1) / k;
for(int i = 0; i < k; i++) {
int x; cin >> x; x ^= ans.size();
A[x].emplace(del[x] + y, vis[id], id);
p[id][i] = x;
g[id][i] = del[x];
}
} else {
int x, y; cin >> x >> y;
x ^= ans.size(), y ^= ans.size();
ans.clear();
del[x] += y;
while(!A[x].empty() && A[x].top().v <= del[x]) {
event temp = A[x].top(); A[x].pop();
if(temp.t != vis[temp.id]) continue;
vis[temp.id]++;
ll tt = 0;
for(int i = 0; i < (int) p[temp.id].size(); i++) {
int x = p[temp.id][i];
tt += del[x] - g[temp.id][i];
}
if(tt >= val[temp.id]) ans.push_back(temp.id);
else {
val[temp.id] -= tt;
int y = (val[temp.id] + p[temp.id].size() - 1) / p[temp.id].size();
for(int i = 0; i < (int) p[temp.id].size(); i++) {
int x = p[temp.id][i];
A[x].emplace(del[x] + y, vis[temp.id], temp.id);
g[temp.id][i] = del[x];
}
}
}
cout << ans.size();
sort(all(ans));
for(auto &e : ans) cout << ' ' << e; cout << '\n';
}
}
return 0;
} J. Junior Mathematician
数位出线题（逃）
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 5010;
char s1[N], s2[N];
int dp[N][60][60], num[N], pw10[N], n, m;
int dfs(int p, int dt, int prf, bool limit) {
if(p == -1) return dt == 0;
if(!limit && dp[p][dt][prf] != -1) return dp[p][dt][prf];
int up = limit ? num[p] : 9, res = 0;
for(int i = 0; i <= up; i++)
res=(res+dfs(p-1,(dt+i*pw10[p]-i*prf%m+m)%m,(prf+i)%m,limit&&(i==up)))%mod;
if(!limit) dp[p][dt][prf] = res;
return res;
}
bool check(char *s) {
int n = strlen(s), x = 0, sum = 0, prf = 0;
for(int i = 0; i < n; i++) {
x = (x * 10 + s[i] - '0') % m;
sum = (sum + (s[i] - '0') * prf) % m;
prf = (prf + s[i] - '0') % m;
}
return x == sum;
}
int solve(char *s) {
int n = strlen(s);
reverse(s, s + n);
for(int i = 0; i < n; i++) num[i] = s[i] - '0';
return dfs(n - 1, 0, 0, 1);
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int _; cin >> _; pw10[0] = 1;
while(_--) {
cin >> s1 >> s2 >> m;
int n = strlen(s2);
memset(dp, -1, sizeof(dp[0]) * n);
for(int i = 1; i <= n; i++) {
pw10[i] = pw10[i - 1] * 10 % m;
}
int res = check(s1);
res = (res + solve(s2)) % mod;
res = (res + mod - solve(s1)) % mod;
cout << res << '\n';
}
return 0;
}
京公网安备 11010502036488号