重庆 CCPC 游记

· · 生活·游记

审流：过题数 6 题，但罚时 1237min。

Day -?：

知道了初二只有我一个去重庆 CCPC 的坏消息，所以我就是躺赢狗。

Day -2：

发现比赛当天是半期的体考，直接爽翻了。

Day 0：

8:30 左右（记不得了）：到了重大；

8:40-9:50：签到，顺便拿了个包和一件衣服；

10:00：开题。

三个人一个从前面开，一个从后面开，一个从中间开。 拿到 L，思考了一下，等 yzc 把 F 秒了就开始写。
第一遍：写了一个栈，交了发现段错误，推了一下发现如果不复制栈里面的元素，只将答案乘 2 的话可能会删完。
第二遍：写了一个 vector，交了一遍发现答案错误，下面是重现的赛时代码（大概吧）：

#include<bits/stdc++.h>
using namespace std;
vector<int>vec;
int ans=0;
const int MOD=998244353;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        if(s=="Push"){
            int x;
            cin>>x;
            vec.push_back(x);
            ans+=x;
            ans%=MOD;
            cout<<ans<<endl;
        }else if(s=="Pop"){
            ans-=vec.back();
            vec.pop_back();
            ans%=MOD;
            cout<<ans<<endl;
        }else{
            if(vec.size()<=n/2+1){
                vec.insert(vec.end(), vec.begin(), vec.end());
            }
            ans*=2;
            ans%=MOD;
            cout<<ans<<endl;
        }
        for(int i=0;i<vec.size();i++){
            cout<<vec[i]<<' ';
        }cout<<endl;
    }
    return 0;
}

看起来没什么问题，但还是 WA；
于是……第三遍：
jch 认为可能是 vector 的问题，于是就改成了普通数组，但是还是 WA；
最后经过一堆自己造的大样例的测试，发现：

ans-=vec.back();
vec.pop_back();
ans%=MOD;

可能是负数！
于是：

ans=(ans-vec.back())%MOD+MOD;
vec.pop_back();
ans%=MOD;

然后过了，但是 3:36^{+10}； 荣获逆天罚时，此时是 13:36（我成千古罪人了？）。

11:05：切掉了 C；

12:06：我在旁边手写 L 代码，然后听到了 jch 和 yzc 在激烈的讨论 A，然后写完代码，WA。

jch：打个暴力试试？

12:27：

评测机：AC。

后来……
yzc：貌似暴力的时间复杂度比我们第一个代码要小……

13:09：干掉 H；

13:36：终于搞完 L；

13:40：开始看 B：

我一开始是看了 B 的，读完题就想到了网络流（为什么呢？），然后一看时间复杂度 n\le 5\times 10^6,m\le 10^3（大概吧，反正网络流不可能）……
然后想到贪心或者 DP，思考了一下后发现貌似 DP 不行，然后跟 jch 讨论了一下，想到用单调优先队列，简单设计了一下就开始打代码。
测完样例直接交，然后不出意料的 WA。
然后开始调代码，发现了一些细节错误，改完之后还是 WA，然后我开始造样例，然后造出来一个 1 1 1 的逆天样例，虽然数据范围表示不可能，但是程序输出了 2，接着添加了出入站口必须不同的判断，一发还是 WA，然后 jch 直接删掉了所有的判断特殊情况的语句，然后 AC 了（本躺赢狗还是不知道为什么能 A）。

此时 14:56，想到了 D 的思路但是没打完。

6 道题，罚时 1237，荣获 6 题倒一，遗憾退场。
排行榜，队名“罚坐三人组”，rk51（有分队伍 rk34 的下面），打星队伍。

杂项：

其他两个队伍一个 rk25（3 分钟 A 两题，B 和 D，还是太强势了，Orz），一个 rk73。
开始后 1 小时，三支队伍都只 A 了一道，带队老师看外榜时想跳河。