人均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

Categories: OI

0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *