ZJOI 2019 题解咕咕记

当年初赛没过,去混了 Day 1,30pt 实名丢人。

Codeforces Round #625

# 翻译

# A. Contest for Robots

给出长度为 1n1001\le n\le 100 的两个序列 r,br,b,且满足 ri,bi{0,1}r_i, b_i\in\{0, 1\},你需要确定 pip_ipi1p_i\ge 1)。

满足 i=1nripi>i=1nbipi\sum_{i=1}^n r_ip_i > \sum_{i=1}^n b_ip_i,并且最小化 maxi=1npi\max_{i=1}^n{p_i}

如果不可能,输出 1-1

# B. Journey Planning

给出长度为 1n21051\le n\le 2\cdot 10^5 的序列 bb1bi41051\le b_i\le 4\cdot 10^5

称合法序列为,c1,,ckc_1,\cdots,c_k,满足 ci<ci+1c_i<c_{i+1}ci+1ci=bci+1bcic_{i+1}-c_i = b_{c_{i+1}}-b_{c_i}k=1k=1 时也是合法的),定义其美丽值为 i=1kbci\sum_{i=1}^k b_{c_i}

求最大美丽值。

# C. Remove Adjacent

给出字符串 ss1s1001\le|s|\le100

定义一次变换为,选中第 ii 个字符移除,字符串长度减少 11,选中字符需要满足 si1,si+1s_{i-1},s_{i+1} 中至少有一个是 sis_i 的前驱。

求最多可进行几次操作。

# D. Navigation System

给出 2n21052\le n\le2\cdot 10^5 个节点,2m21052\le m\le2\cdot 10^5 条边的有向图,路径 p1,,pkp_1,\cdots,p_k,路径中没有重复元素,边 (pi,pi+1)(p_i,p_{i+1}) 总是存在。

定义 s=p1,t=pks=p_1,t=p_k

有一个导航系统,若当前在节点 uu,会构造一条从 uutt 的最短路径(这种路径可能不止一条,但导航系统只会选其中一条),设导航系统规划的下一个节点为 ww,实际行走的下一个节点为 vv

  • w=vw=v 不会触发重构。
  • wvw\neq v 会触发重构。

实际行走路线为 pp,求可能的最少重构次数和最多重构次数。

# E. World of Darkraft: Battle for Azathoth

nn 种武器,攻击力和价格分别为 ai,caia_i,ca_i

mm 种盔甲,防御力和价格分别为 bi,cbib_i,cb_i

caica_i 而不是 caic\cdot a_i

pp 个敌人,防御力、攻击力和掉落金币数为 xi,yi,zix_i,y_i,z_i

maxi,j{(xk<ai,yk<bjzk)caicbj} \max_{i,j}\left\{\left(\sum_{x_k<a_i,y_k<b_j} z_k\right) - ca_i - cb_j\right\}

# F. Reachable Strings

有零一串 tt,从 11 编号,t[lr]t[l\dots r] 代表 llrr 的字串(字串是连续的)。

有两种变换,011->110110->011 。若字符串 s1s_1 可经过若干次(可为 00)变换变成 s2s_2 则称 s1s_1 可到达 s2s_2

qq 个询问,给出 l1,l2,lenl_1,l_2,len,问 t[l1l1+len1]t[l_1\dots l_1+len-1] 是否可到达 t[l2l2+len1]t[l_2\cdots l_2+len-1]

# 题解

# A. Contest for Robots

对于 ri=bir_i=b_iri=0,bi=1r_i=0,b_i=1 肯定填 11

若没有 ri=1,bi=0r_i=1,b_i=0 则无解,

否则就是让这些 ri=1,bi=0r_i=1,b_i=0 凑出来。

ri=1,bi=0pi>ri=0,bi=11 \sum_{r_i=1,b_i=0} p_i > \sum_{r_i=0,b_i=1} 1
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii;

const int N = 200;

int r[N], b[N], p[N];

int main() {
std::ios::sync_with_stdio(false);
cout.tie(0);
int n; cin >> n;
rep(i, 1, n) cin >> r[i]; rep(i, 1, n) cin >> b[i];
int ge; bool flag = 0;
int x = 0, y = 0, z;
rep(i, 1, n){
if (r[i] == b[i]) { z++; continue; }
if (r[i] == 1) x++;
if (b[i] == 1) y++;
}
if (x == 0){ cout << -1; }
else {
if ((y+1)%x == 0) cout << (y+1)/x;
else cout << (y+1)/x + 1;
}
return 0;
}

# B. Journey Planning

移项可得 ci+1bci+1=cibcic_{i+1}-b_{c_{i+1}} = c_i-b_{c_i}

即对于 ii,定义 di=ibid_i=i-b_i

合法序列即为满足 dci==dckd_{c_i}=\cdots=d_{c_k}

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii;

const int N = 600010;

int b[N], a[N];
ll sum[N*2];

int main() {
std::ios::sync_with_stdio(false);
cout.tie(0);
int n; cin >> n;
ll ans = 0;
rep(i, 1, n){
cin >> b[i];
a[i] = N+i - b[i];
sum[a[i]] += b[i];
ans = std::max(ans, sum[a[i]]);
}
cout << ans;
return 0;
}

# C. Remove Adjacent

举例来说,对于 c,只有 b 对 c 有影响,删除 d, e, f,… 要么不会影响,要么使 b 更加靠近 c,让 c 能被删除。

总的来说,就是进行多次扫描,每一次扫描,删除可删除的最大字符。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii;

const int N = 1000;

char s[N], prev[N], next[N];

bool tag[N];

int main() {
std::ios::sync_with_stdio(false);
cout.tie(0);
int n; cin >> n;
cin >> s+1;
rep(i, 1, n){
cin >> s[i];
}
rep(i, 0, n+1) prev[i] = i-1, next[i] = i+1;
int ans = 0;
while(1){
int add = 0, targ = 0;
rep(i, 1, n){
if (tag[i]) continue;
if (s[prev[i]] - s[i] == -1 || s[next[i]] - s[i] == -1){
targ = std::max(targ, int(s[i]));
}
}
rep(i, 1, n){
if (tag[i]) continue;
if (s[i] == targ && (s[prev[i]] - s[i] == -1 || s[next[i]] - s[i] == -1)){
prev[next[i]] = prev[i];
next[prev[i]] = next[i];
add++;
tag[i] = 1;
}
}
if (add == 0) break;
ans += add;
}
cout << ans;
return 0;
}

# D. Navigation System

若当前在节点 uu,设导航系统可能规划的下一个节点为 w1,,wxw_1,\cdots,w_x,实际行走的下一个节点为 vv

d(u)d(u)uutt 距离。

  • d(w)<d(v)d(w)<d(v) 那么一定会重构。
  • d(w)=d(v)d(w)=d(v) 那么可能会重构。

d(u)d(u) 构建反图求即可。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii;

namespace graph {
const int INF = 2147483647;
template <int N, int M>
struct graph {
struct edge {
int v, w;
edge *nxt;
edge() : v(0), w(0), nxt(NULL) {}
edge(int _v, int _w, edge *_nxt) : v(_v), w(_w), nxt(_nxt) {}
};
edge e[M];
edge *head[N];
int cnt, n;
inline void addedge(const int &u, const int &v, const int w) {
e[cnt] = edge(v, w, head[u]);
head[u] = &e[cnt];
++cnt;
}
graph() {
std::memset(head, 0, sizeof(head));
cnt = 0;
}
void dijkstra(int s, int dis[]) {
for (int i = 0; i <= n; ++i) {
dis[i] = INF;
}
std::priority_queue<pii, std::vector<pii>, std::greater<pii>> q;
dis[s] = 0;
q.push(std::make_pair(0, s));
while (!q.empty()) {
pii cur = q.top();
q.pop();
if (cur.first > dis[cur.second]) continue;
for (edge *i = head[cur.second]; i != NULL; i = i->nxt) {
if (dis[i->v] > cur.first + i->w) {
dis[i->v] = cur.first + i->w;
q.push(std::make_pair(dis[i->v], i->v));
}
}
}
}
};
} // namespace graph

const int N = 2e5+100, M = 2e5+100;

graph::graph<N, M> f, g;

int p[N], dis[N];

int main() {
std::ios::sync_with_stdio(false);
cout.tie(0);
int n, m; cin >> n >> m;
f.n = g.n = n;
rep(i, 1, m){
int u, v;
cin >> u >> v;
f.addedge(u, v, 1);
g.addedge(v, u, 1);
}

int k; cin >> k;
rep(i, 1, k) cin >> p[i];

g.dijkstra(p[k], dis);
int min = 0, max = 0;
rep(qaq, 1, k-1){
int less = 0, eq = 0;
int u = p[qaq];
int s = dis[p[qaq+1]];
for(auto i = f.head[u]; i ; i = i->nxt){
if (i->v == p[qaq+1]) continue;
if (dis[i->v] < s) less++;
if (dis[i->v] == s) eq++;
}
if (less) min++;
if (less || eq) max++;
}
cout << min << ' ' << max;
return 0;
}

# E. World of Darkraft: Battle for Azathoth

是一个简单扫描线。

构造线段树,支持区间加,总体最大。

按武器的攻击力(或者说敌人的防御力)扫描,线段树维护盔甲的防御力(或者说敌人的攻击力),线段树中不是盔甲防御力的值的地方赋成 -\infin,其余地方赋成 cb-cb

具体看代码吧。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int, int> pii;

const int N = 1e6+10;
ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m; ll c;

struct Seg{
struct Node{
int l, r;
ll sum, tag, max;
} T[N*4];
#define s T[c]
#define ls (c<<1)
#define rs ((c<<1)|1)
#define ln T[ls]
#define rn T[rs]
inline void upd(int c){
s.sum = ln.sum + rn.sum;
s.max = std::max(ln.max, rn.max);
}
inline void pushdown(int c){
ln.tag += s.tag, rn.tag += s.tag;
ln.sum += (ln.r-ln.l+1)*s.tag, rn.sum += (rn.r-rn.l+1)*s.tag;
ln.max += s.tag, rn.max += s.tag;
s.tag = 0;
}
void build(int c, int l, int r){
s.l = l, s.r = r;
if (l == r){ s.sum = s.max = -inf; return; }
int mid = (l+r)/2;
build(ls, l, mid);
build(rs, mid+1, r);
upd(c);
}
void init(int n){ build(1, 1, n); }
int P, L, R; ll X;
void _add(int c){
if (L <= s.l && s.r <= R){ s.tag += X; s.max += X; s.sum += (s.r-s.l+1)*X; return; }
if (s.r < L || R < s.l) return;
pushdown(c); _add(ls); _add(rs); upd(c);
}
void add(int pos, ll x){ L = R = pos, X = x; _add(1); }
void add(int l, int r, ll x){ L = l, R = r, X = x; _add(1); }
ll _query(int c){
if (L <= s.l && s.r <= R) return s.sum;
if (s.r < L || R < s.l) return 0;
pushdown(c); return _query(ls) + _query(rs);
}
ll _query_max(int c){
if (L <= s.l && s.r <= R) return s.max;
if (s.r < L || R < s.l) return -inf;
pushdown(c);
return std::max(_query_max(ls), _query_max(rs));
}
ll query_max(int l, int r){ L=l, R=r; return _query_max(1); }
ll query_sum(int l, int r){ L=l, R=r; return _query(1); }
void print(int c){
cerr << s.l << ' ' << s.r << ' ' << s.max << endl;
if (s.l == s.r){ return; }
pushdown(c);
print(ls); print(rs);
}
#undef s
#undef ls
#undef rs
#undef ln
#undef rn
} ds;

struct W{
int a;
ll c;
bool operator== (const W& rhs){
return a == rhs.a;
}
} w[N], a[N];
bool cmp(const W&a, const W& b){
return a.a == b.a ? a.c < b.c : a.a < b.a;
}
struct X
{
int x, y, z;
} mos[N];
bool cmp_x(const X&a, const X&b){
return a.x < b.x;
}

int main() {
std::ios::sync_with_stdio(false);
cout.tie(0);
int n, m, p; cin >> n >> m >> p;
rep(i, 1, n) cin >> w[i].a >> w[i].c;
rep(i, 1, m) cin >> a[i].a >> a[i].c;
std::sort(w+1, w+1+n, cmp);
n = std::unique(w+1, w+1+n) - (w+1);
std::sort(a+1, a+1+m, cmp);
m = std::unique(a+1, a+1+m) - (a+1);
// cerr << n << ' ' << m << endl;
rep(i, 1, p) cin >> mos[i].x >> mos[i].y >> mos[i].z;
std::sort(mos+1, mos+1+p, cmp_x);
int M = 1e6+10;
ds.init(M);
rep(i, 1, m){
ds.add(a[i].a, inf-a[i].c);
}
// ds.print(1);

ll ans = -inf;
int j = 1;
rep(i, 1, n){
for(; j <= p && mos[j].x < w[i].a; ++j) ds.add(mos[j].y+1, M, mos[j].z);
ans = std::max(ans, ds.query_max(1, M) - w[i].c);
}
cout << ans;
return 0;
}

# F. Reachable Strings

雅礼集训瞎做

pixiv link, author: Alcxome

# 2017

# 「雅礼集训 2017 Day1」市场

支持区间减,区间整除,区间最小查询,区间和查询。

线段树,考虑一个区间的最大值 aa 和最小值 bb

k=aa/d=bb/dk=a-\lfloor a/d \rfloor = b-\lfloor b/d \rfloor, 则对于 a<c<ba<c<bcc/d=kc-\lfloor c/d\rfloor=k

事实上满足上述的只有 a=ba=ba=b+1a=b+1

证明可令 a=αk+p1,b=βk+p2a=\alpha k+p_1,b=\beta k+p_2 具体略

云服务器上乱七八糟的应用

pixiv link, author: catzz

域名备案批下来了,服务器是阿里云的 9.5r/mon

用这个搭了一些小服务,全程使用 docker。所有 password/key/secretQAQ 替代

用 nginx 进行反向代理

「牛客 1103B」路径计数机

是道好题

可惜卡常数

Comet OJ - 模拟赛测试 Day2

感觉题目出得不是很难,部分分给得很足

Codeforces Round #599 (Div. 1)

sto God Song orz

Being teached again

Educational Codeforces Round 75

又被 God Song 教育了

牛客 CSP-S 提高组赛前集训营 1 题解

体验还是比较好的 230 只有 100 名差评,没有享受到大样例x

# 比赛实录

6:30:看 T1,这个博弈我好像推不出来SG,这是 ICG 吗?

滚去看 T2,理解题意 5min ,这个乘积怎么维护啊。。。

DP式子推推搞搞搞

「USACO 2007 Dec. Gold」Sightseeing Cows

给定一张 n1000n\le1000 个点、m5000m\le5000 条边的有向图

每个点都有一个权值 fif_i ,每条边都有一个权值 tit_i

求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大