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

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

A 子弦

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

#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))$。

#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)$。

代码：

#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 告诉我合并方程就完事了…
太草了就不写了…感性理解下吧…