「解题报告」洛谷九月月赛

今天怎么有一页阿克爷啊…..
怎么我还是啥都不会啊……

A 子弦

容易发现答案是出现次数最多的字母的出现次数。证明很简单:再扩展一位字符出去限制性也不会变弱。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
const int CN = 1e7 + 7; char ch[CN]; int tot[300], mx = 0;
int main()
{
ios :: sync_with_stdio(false); cin >> ch;
for(int i = 0; ch[i]; i++) tot[ ch[i] ]++;
for(int i = 'a'; i <= 'z'; i++) mx = max(mx, tot[i]);
printf("%d", mx);
}

B 雷雨

跑三遍 Dijkstra,枚举一个中间点拼起来就好了,复杂度 $O(nm(\log n + \log m))$。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

#define LL long long
const int CN = 1e3 + 3;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const LL INF = 0x3f3f3f3f3f3f3f3f;

class DJ {public: int x, y; LL v; bool operator < (const DJ & a) const {return v > a.v;}};
DJ mk(int a, int b, LL c) {DJ d; d.x = a, d.y = b, d.v = c; return d;}
priority_queue<DJ> Q;

bool vis[CN][CN];
void SP(int n, int m,int sx, int sy, LL d[][CN], LL dis[][CN]){
memset(vis, 0, sizeof(vis));
Q.push( mk(sx, sy, dis[sx][sy] = d[sx][sy]) );
while(!Q.empty()){
int x = Q.top().x, y = Q.top().y; Q.pop();
if(vis[x][y]) continue; vis[x][y] = true;
for(int k = 0; k < 4; k++){
int vx = x + dx[k], vy = y + dy[k];
if(!vx || !vy || vx > n || vy > m || vis[vx][vy]) continue;
if(dis[vx][vy] > dis[x][y] + d[vx][vy]){
dis[vx][vy] = dis[x][y] + d[vx][vy];
Q.push( mk(vx, vy, dis[vx][vy]) );
}
}
}
}

int n, m, a, b, c; LL d[CN][CN], da[CN][CN], db[CN][CN], dc[CN][CN];

int main()
{
n = read(), m = read(), a = read(), b = read(), c = read();
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) d[i][j] = read();

memset(da, 0x3f, sizeof(da)), SP(n, m, 1, a, d, da);
memset(db, 0x3f, sizeof(db)), SP(n, m, n, b, d, db);
memset(dc, 0x3f, sizeof(dc)), SP(n, m, n, c, d, dc);

LL ans = INF;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
ans = min(ans, da[i][j] + db[i][j] + dc[i][j] - 2ll * d[i][j]);
printf("%lld", ans);

return 0;
}

C 梦原

考虑如果给出一颗形态固定的树,我们应该怎样算答案?我们只需要把 $w[u]$ 变成 $w[ fa[u] ]-w[u]$(就是树上差分),然后把所有 $w[u]>0$ 的 $w[u]$ 加起来就可以了。也就是我们只考虑把多出来的那部分算到费用里面,容易发现这样一定是最优的。

然后考虑 $i$ 的父亲大概有 $\min i - 1,k$ 种可能,根据期望的线性性,只需对这些可能求个概率加权和就好了。设 $m=\min i-1, k$,得到答案是:
$$\sum\limits_{i=1}^n\sum\limits_{j=i-m}^{i-1}\frac{1}{m}[a_j<a_i](a_i-a_j)$$ 实际上就是个二维数点,由于区间是定长,因此直接拿个树状数组维护即可,复杂度 $O(n\log n)$。

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 1e6 + 6;
const int P = 998244353;

int qp(int a,int b) {int r = 1; while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;} return r;}

int n, m, a[CN], val[CN];

int id(int x) {return lower_bound(val + 1, val + val[0] + 1, x) - val;}

class BIT {
public: int d[CN], cnt[CN], n;
int lb(int x) {return x & (-x);}
void add(int p, int x) {while(p <= n) d[p] = (d[p] + x) % P, cnt[p]++, p += lb(p);}
void minus(int p, int x) {while(p <= n) d[p] = (d[p] - x + P) % P, cnt[p]--, p += lb(p);}
int qu(int p) {int r = 0; while(p) r = (r + d[p]) % P, p -= lb(p); return r;}
int quc(int p) {int r = 0; while(p) r += cnt[p], p -= lb(p); return r;}
} D;

int main()
{
D.n = n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read(), val[ ++val[0] ] = a[i];

sort(val + 1, val + val[0] + 1); int tmp = 1;
for(int i = 2; i <= val[0]; i++) if(val[i] ^ val[i - 1]) val[++tmp] = val[i]; val[0] = tmp;

int ans = a[1];
D.add(id(a[1]), a[1]);
for(int i = 2; i <= n; i++){
int k = qp(min(i - 1, m), P - 2), si = D.qu( id(a[i]) ), cnt = D.quc( id(a[i]) );
si = (1ll * cnt * a[i] % P - si + P) % P;
ans = (1ll * k * si % P + ans) % P;
D.add( id(a[i]) , a[i]);
if(i >= m + 1) D.minus( id(a[i - m]), a[i - m] );
}

printf("%d", ans);
}

D 线形生物

看上去今天只有我一个人不会这题的样子……
Subtask1, 10pts 交个cout<<(n<<1)上去就好了,因为对每一位都有 $E_i=\frac{1}{2}E_i+1$,解得 $E_i=2$,因此答案是 $2n$。
Subtask4, 40pts 看上去用高斯消元解方程就好了,考场上遇到了些哲学问题没调出来…
Subtask5…这就不会了啊。
事实上赛后红太阳 SSX 告诉我合并方程就完事了…
太草了就不写了…感性理解下吧…

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×