洛谷 ⑨ 月月赛 I & Cnoi2020作战日志

人均AK，被吊打，没有人权 /kk

14:00

开赛。直接开 T1，“出现次数最多的非空子串的出现次数”，显然是个模拟。发现数据不大，果断暴力。

int main() {
    char ch;
    while ((ch = getchar()) != EOF) ++cnt[ch - 'a'];
    for (int i = 0; i < 26; ++i)
        ans = max(ans, cnt[i]);
    printf("%d\n", ans);
    return 0;
}

感觉人均AC，开T2。

14:30

感觉平淡。看着题面感觉没什么思路，但是图片提示了搜索有关思想。感觉就是个搜索。

首先，如果中间有分流然后合起来的情况（环），走一边肯定更优。然后一个块就不会走多次了。这道题就是从一个点到其余三个点的最短路之和了。DFS裸题。

火速切。

inline void dfs(int x,int y,int t){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            Len[i][j]=INF;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            vis[i][j]=false;
    register int i,j;
    Len[x][y]=0;
    PQ.push(Node(x,y,0));
    register Node p;
    register int X,Y,XX,YY;
    while(!PQ.empty()){
        p=PQ.top();PQ.pop();X=p.x,Y=p.y;
        if(vis[X][Y])   continue;
        vis[X][Y]=true;
        for(i=0;i<4;i++){
            XX=X+fang[i][0],YY=Y+fang[i][1];
            if(XX<1 || XX>N || YY<1 || YY>M || Len[XX][YY]<=Len[X][Y]+MP[X][Y])
                continue;
            Len[XX][YY]=Len[X][Y]+MP[X][Y];
            PQ.push(Node(XX,YY,Len[XX][YY]));
        }
    }
    for(i=1;i<=N;i++)
        for(j=1;j<=M;j++)
            anss[i][j]+=Len[i][j];
}

结果常数有些大，只好加上一个快读，交了好几发勉强卡进 2000ms（实测 1900+ms） /kk

15:40

前两题 AC，果断开 T3。《梦  原》出题人  你  梦  没  了。

闻到了数学的气息。但是想想发现这棵树好像符合那么一点小根堆的性质。每个点只会加在前面的点后面，好像可以从前往后 DP。

具体来讲就是：在枚举到一个点 x 的时候，假设它的父亲是 fa，那么删父亲的果子的时候带上这个点最优（毕竟这个点往外的通路也就只有父亲了）。最后花点时间暴力删除该节点的果子，那么总答案就是：

f_x=\dfrac{\sum\limits_{fa\in[x-k,x-1]\cap N^+}f_{x-1}+\operatorname{max}(a_x-a_{fa},0)}{\sum\limits_{fa\in[x-k,x-1]\cap N^+}1}
于是暴力失败，40pts。

改成初始化以后没法卡常，于是只好 std::sort / std::unique，结果还是有点炸。

17:40

T4 终场都没想出正解，感觉人均 AK。/fad 只是两题期望不太友好。

总分：100 + 100 + 70 + 10 = 280。