校内模拟赛 · E2

校内模拟赛第二弹

$A$

$𝑁$座楼房,立于城中。第$𝑖$座楼,高度$ℎ_𝑖$。你需要一开始选择一座楼,开始跳楼。在第𝑖座楼准备跳楼需要$𝑐_𝑖$的花费。 每次可以跳到任何一个还没有跳过的楼上去。跳楼有代价,每次跳到另外一座楼的代价是两座楼高度的差的绝对值,最后一次从楼上跳到地面上不需要代价(只能跳到地上一次)。求在代价不超过𝑇的情况下,最多跳几次楼。

性质题,找不出来人似乎就没了233

考虑最优情况下肯定会是单调地跳,即要么单增地跳,要么单减地跳。这样就可以设计状态了$f_{i,j}$为跳到$i$,跳了$j$栋楼最小代价,然后枚举一遍状态即可。

$B$

小$c$切LuoguP5487这题,但是菜如小$c$,他写挂了。

小$c$开始了漫长的debug的阶段,2天过去了小$c$还是没有找到自己程序哪里写错了。于是他打印了自己所有函数的出入口的信息。对于小$c$写的第$i$个函数,他的入口会输出$+i$,他的出口会输出$-i$。

等到他把所有的输出打出来时,发现由于字符集的问题前面的符号消失了。但是他隐约记得某几个函数的出口的输出位置。现在小$c$想知道一个可能的打印序列,如果不存在输出NO

题解里面写这题可以倒着做,即从后向前扫,如果这个括号没有指定成右括号而且他是左括号合法,则标记为左括号;否则为右括号。跑完之后看看是否合法。思想大概就是诡异的贪心,因为左括号只会被“安排”,为了保证左/右平衡,故选择对左括号贪心。

我也是贪心做的,不过是正着做的。没有限制时,如果上一个是(,那我这一个就安排成)就好了,但算上限制时,出问题的就是会把一些左括号限制为右括号,即“强制嵌套”。那么如果原本是()(这样,第三个括号被强制为右括号,就顺便把前一个右括号改成(,即变为((),留着去跟后面的匹配。合不合法最后再$check$一遍就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
cin >> N ; int i, j ;
for (i = 1 ; i <= N ; ++ i) base[i] = qr() ;
for (cin >> M, i = 1 ; i <= M ; ++ i) ok[qr()] = 1 ;
for (i = 1 ; i <= N ; ++ i){
if (ok[i] && !stk[base[i]].size()){
ans[i] = 1 ;
stk[base[i]].pb(mat[buc[base[i]]]) ;
ans[i] = 1, ans[mat[buc[base[i]]]] = ans[buc[base[i]]] = 0 ;
mat[i] = buc[base[i]], mat[buc[base[i]]] = i ; buc[base[i]] = i ;
}
else if (!stk[base[i]].size()) stk[base[i]].pb(i), ans[i] = 0 ;
else mat[i] = stk[base[i]].back(), ans[i] = 1,
mat[stk[base[i]].back()] = i, stk[base[i]].pop_back(), buc[base[i]] = i ;
}
for (i = 1 ; i <= N ; ++ i)
if (!ans[i]) stack[++ t] = i ;
else if (!t) return puts("NO"), 0 ;
else stack[t --] = 0 ;
if (t) return puts("NO"), 0 ;
for (i = 1 ; i <= N ; ++ i){
printf("%c%d ", ans[i] ? '-' : '+', base[i]) ;
}

$C$

给定$n\leq 1,000$。求最少需要多少不同的$a_i\in[1,n]$,使得$\forall x, 1\leq x\leq n$,总可以选出某个${a}$的子集来凑出$x$。同时,求最小$|{a}|$下凑出所有$x$的方案总数。

第一问是个贪心……贪心……就是二进制分解的思路,$n$的二进制位数就是答案。感觉如果要证明,证明起来其实是挺自然的。考虑首先二进制划分一定是合法的,同时如果将其中的$>1$个换出去,那么一定凑不出$1$~$n$的所有数。

第二问据说是一个经典的$dp$。考虑状态$f_{i,j,k}$表示带了$i$枚金币,和为$j$,最大值为$k$的方案数。然而对我来说状态并不是很容易定义……emmm。转移的话采用刷表法比较简单,考虑对于一个状态$f_{i,j,k}$,枚举比$k$大的$o$,那么就有$f_{i,j,k}\to f_{i+1,\min(j+o,n),l}$ .

$D$

已知C国有n个城市,城市间有m条双向道路,每条路有限重。JD公司想修建一些仓库来实现对C国所有城市的配送,仓库必须修建在某个城市。送达每个城市的货物可以由任意一个仓库发出,不过在运输途中必须满足限重的要求。

JD公司想让你设计一个程序来帮助高管决策,q次询问,每次询问计算如果想配送重量为w的物品,至少需要建多少个仓库。

质疑题面在恰饭

一个比较显然的思想就是建出最大生成树来。然后比较常规的做法就是边建树边飞询问,考虑加完第一条载重为$val$边之前,现在的连通块个数就是重量为$val-1$的询问的答案,于是离线下来飞就可以了。

然后这东西也可不离线下来再去飞询问。观察性质可以发现假设现在询问的重量为$w_q$,那么对于所有限重$w_o<w_q$的边,一定会分成两个连通块。于是可以直接把最大生成树的边排一个序,然后二分出$<w_q$的个数即为答案。

$E$

给定一个字符串,每次询问一个子串中$A$的个数和$B$的个数的比值为$x:y$的子串的最长长度。

$n,q\leq 100,000$

一开始我是真没想写这题……但是想了个线段树发现自己假了,然后就被迫入坑。。

考虑推式子
$$
\frac{A_r-A_{l-1}}{B_r-B_{l-1}}=\frac{x}{y}\\
x\cdot (B_r-B_{l-1})=y\cdot (A_r-A_{l-1})\\
y \cdot A_r-x \cdot B_r=y \cdot A_{l-1}-x \cdot B_{l-1}
$$
然后如果我们令$val_i=y\cdot A_i-x \cdot B_i$,那么求的就是区间内相同的数相隔的最长距离。天真的我以为这题可以线段树,然后就很开心地想做……去uoj群里问了一圈发现这个被lxl规约到了$n \sqrt n$的问题上面……

然后就觉得,大概可以莫队吧。于是就想上莫队,结果发现这东西似乎并不是很好统计……于是写了半天之后毅然决然地写了一个线段树。最终在luogu上二分这个题的时限,卡到了100ms~6500ms这个范围……然后最终复杂度就应该是$n\sqrt q \log n$。

然后莫队确实可以卡常,大概就是不要傻傻地真把$Q$分成$\sqrt Q$块,因为常数因子导致均值不等式搞出来的结果没有那么对;然后莫队的cmp可以这么写:

1
2
3
4
il bool cmp(qrs a, qrs b) {
return (blg[a.l] ^ blg[b.l]) ?
blg[a.l] < blg[b.l] : ((blg[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

奇数块正着排,偶数块倒着排,就会快好多。

然后最后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//写了一下午QAQ
char s[MAXN] ;
struct qrs{
int l, r, id ;
}q[MAXN] ; int l, r, buc[MAXM], val[MAXN] ;
int blg[MAXN], T[MAXM << 2], ans[MAXN], Pre[MAXN], Nxt[MAXN] ;
int N, X, Y, M, S, U, base[MAXN], cnt[2][MAXM], pre[MAXN][2], res, res2 ;

il int qr(){
char c = getchar() ; int res = 0 ;
while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;
return res ;
}
il bool comp(qrs a, qrs b) {
return blg[a.l] == blg[b.l] ? a.r < b.r : blg[a.l] < blg[b.l] ;
}
il bool cmp(qrs a, qrs b) {
return (blg[a.l] ^ blg[b.l]) ? blg[a.l] < blg[b.l] : ((blg[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
void update(int rt, int L, int R, int p, int v){
int mid = (L + R) >> 1 ;
if (L == R) return T[rt] = v, void() ;
if (p <= mid) update(rt << 1, L, mid, p, v) ;
else update(rt << 1 | 1, mid + 1, R, p, v) ;
T[rt] = max(T[rt << 1], T[rt << 1 | 1]) ;
}
void del(int p){
// cout << p << " : " << cnt[0][val[p]] << " " << cnt[1][val[p]] << " " << val[p] << endl ;
if (p == cnt[0][val[p]]) cnt[0][val[p]] = Nxt[p] ;
if (p == cnt[1][val[p]]) cnt[1][val[p]] = Pre[p] ;
// cout << p << " : " << cnt[0][val[p]] << " " << cnt[1][val[p]] << " " << val[p] << endl ;
update(1, 0, MAXM, val[p], cnt[1][val[p]] - cnt[0][val[p]]) ;
res = T[1] ;// cout << T[1] << endl ;
// cout << p << " : " << cnt[0][val[p]] << " " << cnt[1][val[p]] << " " << val[p] << endl ;
}
void upd(int p){
cnt[0][val[p]] = min(cnt[0][val[p]], p) ;
cnt[1][val[p]] = max(cnt[1][val[p]], p) ;
update(1, 0, MAXM, val[p], cnt[1][val[p]] - cnt[0][val[p]]) ;
res = T[1] ;
// cout << p << " : " << cnt[0][val[p]] << " " << cnt[1][val[p]] << " " << val[p] << endl ;
}
int main(){
cin >> N >> X >> Y ; int i, j ;
for (scanf("%s", s + 1), i = 1 ; i <= N ; ++ i)
base[i] = s[i] - 'A',
pre[i][base[i]] = pre[i - 1][base[i]] + 1,
pre[i][base[i] ^ 1] = pre[i - 1][base[i] ^ 1] ;
for (i = 0 ; i <= N ; ++ i) val[i] = MAXN + Y * pre[i][0] - X * pre[i][1] ;
memset(buc, -1, sizeof(buc)) ;
for (i = 0 ; i <= N ; ++ i) Pre[i] = buc[val[i]], buc[val[i]] = i ;
memset(buc, 0, sizeof(buc)) ;
for (i = N ; i >= 0 ; -- i) Nxt[i] = buc[val[i]] ? buc[val[i]] : N + 1, buc[val[i]] = i ;
M = qr() ; S = pow(M, 0.5832) ; U = ceil((double)M / S) ;
memset(cnt[0], 63, sizeof(cnt[0])) ;
memset(cnt[1], -1, sizeof(cnt[1])) ;
for (i = 1 ; i <= U ; ++ i)
for (j = (i - 1) * S + 1 ; j <= i * S ; ++ j) blg[j] = i ;
for (i = 1 ; i <= M ; ++ i) q[i].l = qr() - 1, q[i].r = qr(), q[i].id = i ;
sort(q + 1, q + M + 1, comp) ; l = 0, r = -1 ;
for (i = 1 ; i <= M ; ++ i){
while (r < q[i].r) upd(++ r) ;
while (l < q[i].l) del(l ++) ;
while (l > q[i].l) upd(-- l) ;
while (r > q[i].r) del(r --) ;
ans[q[i].id] = res ;
}
for (i = 1 ; i <= M ; ++ i) printf("%d\n", ans[i]) ;
return 0 ;
}

不知道为啥rqy写的莫队套线段树加了个看不太透的优化比我快了一倍,迷乱233

$F$

你的花田一共由$n-2$片花田组成,编号从$1$到$n-2$。

算上你的家和花店,一共有$n$个地点,其中你的家编号为$0$,花店编号为$n-1$。即,家、花田、花店都属于地点,且它们都有一个唯一的$0$~$n-1$的编号。有$m$条双向道路连接这些地点。保证所有地点间都是直接或间接连通的。

你需要从家里出发,经过所有的花田进行收获,再到达花店,再从花店出发经过所有花田进行播种,最后重新回到家中。当你经过一片花田的时候,你可以选择收获、播种或者什么事都不做,也就是说你经过一片未收割的花田时可以不立即收割它,播种亦然。然而,播种必须发生在你完成了所有收获并到花店交货之后。在完成最后一个花田的收获后,你必须在到达花店后才能开始播种。也就是说,在你没有收获完所有花田并到花店交货前,即使你已经经过了花店,你也不能进行播种。(啰嗦了这么多但愿讲明白了)

然而还有一个问题。在收割完花朵后,花田会变得光秃秃的,此时土地里的水分会迅速蒸发。考虑到这个问题,更早被收割的花田也理应更早地被播种。具体来说,你必须保证前$\lfloor \frac{n-2}{2}\rfloor$个被收割的花田也是前$\lfloor \frac{n-2}{2}\rfloor$个被播种的,其中符号$\lfloor \rfloor$表示向下取整。你不需要保证这些花田收割和播种的顺序完全一致,而只需要保证前$\lfloor \frac{n-2}{2}\rfloor$名的集合不变即可。

现在,你需要求出完成上述一系列动作走过的最短路程。

$n \leq 20$

一眼看出状压$dp$,第二眼看出应该从头和尾分别$dp$,然后没看第三眼就开始写……发现不太对??有个限制,要求前$\lfloor \frac{n-2}{2}\rfloor$必须相同。然后我就寻思着要压一下顺序?有点难写;寻思着记录一下路径?但是发现变更不对了,因为可能最后的状态根本不重合,然后就没有然后了QAQ。

然后瞅了一眼题解发现很妙。大概就是枚举$size$为$\frac{n}{2}$的状态,将整张地图分为两半。之前预处理一个floyd,然后每次的代价就是

$$
\mathsf{\min _{x\in S,y\in T}(f_{S,x}+dis_{x,y}+g_{T,y})+\min _{x\in S,y\in T}(g_{S,x}+dis_{x,y}+f_{T,y}})
$$

然后枚举$\mathsf {S,T,x,y}$就完了,复杂度$O(2^{n}+\binom{n}{\lfloor\frac{n}{2}\rfloor}\cdot n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int g[MAXS][MAXN], pre[MAXS][2], sz[MAXS], ans ;
int A[MAXN][MAXN], dis[MAXN][MAXN], N, M, E, f[MAXS][MAXN], stk[MAXN], cnt ;

int main(){
cin >> N >> E ;
int i, j, k, o ;
M = (1 << N) - 1, ans = Inf ;
memset(dis, 63, sizeof(dis)) ;
memset(f, 63, sizeof (f)) ; f[1][0] = 0 ;
for (i = 1 ; i <= N ; ++ i) dis[i][i] = 0 ;
for (i = 1 ; i <= E ; ++ i)
cin >> j >> k >> o,
A[j][k] = A[k][j] = o,
dis[j][k] = dis[k][j] = o ;
for (k = 0 ; k < N ; ++ k)
for (i = 0 ; i < N ; ++ i)
for (j = 0 ; j < N ; ++ j)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]) ;
if (N == 3) return printf("%d\n", 2 * (dis[0][1] + dis[1][2])), 0 ;
for (i = 1 ; i <= M ; ++ i) sz[i] = sz[i - (i & (-i))] + 1 ;
for (i = 2 ; i <= M ; ++ i){
for (j = 0 ; j < N ; ++ j)
if (1 << j & i) stk[++ cnt] = j ;
for (j = 1 ; j <= cnt ; ++ j){
int now = stk[j] ;
for (k = 1 ; k <= cnt ; ++ k)
if (!(stk[k] ^ now)) continue ;
else f[i][now] = min(f[i][now], f[i ^ (1 << now)][stk[k]] + dis[stk[k]][now]) ;
}
cnt = 0 ;
}
memset(g, 63, sizeof(g)) ; g[1 << (N - 1)][N - 1] = 0 ;
for (i = (1 << (N - 1)) + 1 ; i <= M ; ++ i){
for (j = 0 ; j < N ; ++ j)
if (1 << j & i) stk[++ cnt] = j ;
for (j = 1 ; j <= cnt ; ++ j){
int now = stk[j] ;
for (k = 1 ; k <= cnt ; ++ k)
if (!(stk[k] ^ now)) continue ;
else g[i][now] = min(g[i][now], g[i ^ (1 << now)][stk[k]] + dis[stk[k]][now]) ;
}
cnt = 0 ;
}
// cout << g[M][1] << endl ;
for (i = 1 ; i <= M ; ++ i){
if (sz[i] != N / 2) continue ;
int stA = i, stB = (~i & M), res = Inf, fg = 0 ;
for (int j = 1 ; j < N ; ++ j)
if (1 << j & stA)
for (int k = 1 ; k < N ; ++ k)
if (1 << k & stB)
res = min(res, f[stA][j] + dis[j][k] + g[stB][k]), fg = 1 ;
// if (!fg) res = 0 ;
stB ^= (1 << N - 1), stB |= 1 ;
stA ^= 1, stA |= (1 << N - 1) ;
for (int j = 1 ; j < N ; ++ j)
if (1 << j & stB)
for (int k = 1 ; k < N ; ++ k)
if (1 << k & stA) ans = min(ans, res + f[stB][j] + dis[j][k] + g[stA][k]) ;
// if (!fg) ans *= 2 ;
}
cout << ans << endl ;
}