Day1

见到了六年级大佬，感觉被单调队列了。通过讲座第一次知道 pku AI 好像比 thu 牛（？）。

试机赛怎么这么难，T2 一分没拿，好在 T1 勉强切了。

开打前就敲了一个头文件，其他蓝的敲，直接睡了。醒来后开的 T1，思考一下发现 $a>b+1$ 是不难的，其他情况大胆猜测 $\frac{(a+b)\times(a+b-1)-a\times(a-1)}{2}+1$，提交发现还过了 $a=2$ 的点，手推了下 $n=3$ 的情况，大胆猜测尽可能平均分成 $a-1$ 个完全图，过了。

然后开 T2，怎么是困难数据结构题，跳了，看 T3。T3 读懂题面后感觉很难，滚回去把 T2 24pts $O(n^2\log n)$ 的暴力跳lca+暴力去重的代码写了，继续想了一下后感觉一点不会，去开 T3，此时 1h30min。

T3 直接思考特殊性质，一番思索后无果。尝试写 $O(nmk)$ 暴力 dp，$dp_{i,j}$ 表示从第 $i$ 个点开始，从第 $r=j$ 时能否获胜，从它的所有可达节点转移，写了没过，此时 2h30min，非常恼火。

想了一下后突然发现要强连通分量缩点，然后就成了一个 DAG，然后注意到对于每个点它所有的可达节点所有可能获胜的 $r$，它的直接子结点一定一定包含所有这样的 $r$，强连通分量内的转移和孤点特判一下就可以做到 $O(mk)$。花 40min 写过了 20pts，感觉这就是最终得分了。

由于不会 T2 继续想 T3，于是发现特殊性质 B 只有最小能达到 $r$ 的是重要的，直接分讨一下好像就对完了。10min 写过了 50pts，又 10min 写过了 75pts，还有半小时尝试推正解，未果。

Day1：$100+24+75=199$

Day2

上午非常好讲座，和在大学听讲座一样（什）。

比赛先开的 T1，拼尽全力无法战胜，1h 了还是 0pts，这也太难了。看了眼 T2，我测怎么我连 $O(n^3)$ 都不会，就写了个 $c=1$ 的贪心跑路。T3 直接打 $O(nb\ln(n))$ 暴力 dp，7s 跑不过 $n\le 5\times 10^6，b\le 40$，只拿了 $n\le 10^6，b\le 40$ 的点，回来看 T1，此时 2h。

瞎构造了一番，我好像会 $4n$ 了，直接开写，这时还有 1h30min。

开写后发现这代码难写的跟什么一样，思路是随机选两个点（其实是 1 和 2），找到一个 离这两个点路径深度（距离）为 1 的点，然后利用这两个点找到与 离这两个点路径深度为 1 的点 的相邻的点，再找到离 离这两个点路径深度为 1 的点 和 离这两个点路径深度为 1 的点的相邻的点 的路径最远的点，再找到和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 的相邻的点，再找到离 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点的相邻的点 的最远的点，此时 离离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点和离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点的相邻的点的最远的点 和 离离这两个点路径深度为 1 的点和离这两个点路径深度为 1 的点的相邻的点的路径最远的点 即为所求（？）。

但是还需要特判 $n=1$、$n=2$、两个点相邻的情况、没有深度为 1 的点的情况、最远点深度为 1 的情况、最远点就是初始两点之一的情况等，最后还剩 30min 才把代码主体写好，加上交互库有 300 行。

过了样例一交，WA 0pts。

使用瞪眼法观察发现样例里点 $1$ 和 $2$ 一定相邻，于是手造了一个这个 case。

（这里应该有一张图片）

发现 ansWA 了，原来是没找到深度为 1 的点，原来深度算错了，交一发 WA0，继续手造 hack，又 hack 掉了。

（这里也应该有一张图片）

哦哦，特判深度为 1 的点为初始两点时特判错了，交一发，WA0，此时还剩 13min。

造了几个 hack 都过了，于是开始静态查错，发现最后一次找最远点时，如果恰好是初始两个点就错了，这时只剩 7min 了，只能尝试改成 $6n$ 或更劣的，改改改，改完了还剩 5min，再不过就要 day2t1 爆0了。

我测，还是 WA0，这下真完蛋了。

这下盲猜错在了 1 与 2 相邻上，先来随便造个 hack。

（这里本来有一张图片）

怎么过了，再造一个。

（这里应该还有一张图片）

我测，ansWa 了。我测，我求出来的最远的点有什么作用吗，烧烤一下确实没作用，那路径上的最小值有作用吗，也没用到啊，那我再跑一遍是为啥，我测，原来敲错变量名了，赶紧改，改完了，我看着电脑上的 17:00 陷入了浅浅的沉思。

我电脑时间快 1 分半啊，交一发，怎么评测怎么慢。

最后还是 WA0 了，D2T1 一分没得。

但这是我的想象，最后过了 50+pts，评测完时间是 $16$:$59$:$07$ 左右，我非常激动所以直接不小心把窗口全叉了。

然后我忘记我每题具体得多少分了。

如果有好心人记得的话可以告诉一下。

Day2 最后应该是 56+11+24=91。

noip 去的是南外的考场，考前不太清醒，上场敲了个平常用的头文件和线段树板子就摆了。

下发的密码打不开文件，于是继续摆。

过了一会能打开 pdf 了，开始看题。

T1 看起来是个很显然的贪心啊，大胆假设是从前往后尽可能匹配，20min 左右过了大样例，去写 T2。

看到 T2 的数据范围就想到了考前模拟赛的矩阵光速幂，正着推了一会有点乱，于是容斥一下发现很对，甚至只需要快速幂，在 40+min 时过了 T2 的大样例。

看到 T3 一眼就认定了这道题很可做，直接尝试推正解，推正解的过程中把链和菊花的特殊性质写了，推了 2h（？） 发现不太对，于是去看了眼 T4，把 $O(n^2)$ 暴力写了，回来继续搞 T3，未果，最后只补写了个 $k=1$ 的点。

出考场后发现 T1 难度是蓝，我场上以为 T1 最多黄，很慌，T3、T4 都是紫，那还行。

最后 $100+100+40+32=272$，比大众分还低的大众分，不过至少没挂分。

直接从到赛场开始说了。

去的是南外新校区的赛场，大厅挺好看的就是比较漏雨。

到了考场把头文件敲了敲，还写了一个对拍板子和线段树板子，想写 fread 和 fwrite 但怕出事，遂未写，摆摆摆直到发试题。

收到了下发的试题，手滑把它给删了，去要试题，然后在二次下发之前在 trash 里找到了，希望不要怀疑我是来找茬的（。

先开的 T1，看上去很难，读了半天没读懂，近 15+min 才写出来个按题意模拟的代码，感觉很对过大样例了就跳了。

T2 题目有点长，听说 j 组 T2 是大模拟，直接开 T3。

T3 看起来很典，把题意转化一下就是求（选择（一个区间最多交一次的）线段集合的）最大权值和，直接写一个理论上能得 50pts 的 $O(n^2)$ dp 扔上去，过了大样例就弃了，此时 30min。

回来看 T2，怎么是数学公式题，感觉很不会，但还是写了。直接大分讨上去，一顿操作用了 30min，然后又调了 30min，过了大样例，这时才过去 1.5h，感觉还是挺良好的。

然后去写 T4 了，T4 看起来很抽象，但是一般来说题面越抽象题目越简单（什）。推了推，感觉很可做，于是尝试写正解，结果越推越不对，这时已经过去很久了（可能 2h？），感觉不对遂写 40pts $O(n^2\log_2n)$ 暴力，结果暴力也写了很久（可能 40min？），而且不超过 5000 的大样例跑了 0.996s，写完后只剩 20min 了。

回来 T3 的 $n\le200000,a_i\le 10$ 的点还没写，写完就只剩 10min。

看了一会发现 T4 的特殊性质 A 来不及写了，最后 3min 检查代码时发现 T4 void 函数写成 int 函数了，差点挂完了。

签完名直接走，怎么我成第一个出来的了，第二个怎么隔那么久才出来，怀疑我漏了什么步骤。

重写一遍代码然后在 luogu 测，怎么只有：
100+90+65+32
我 T2 还可能会挂完。
T4 为了卡常数组开小了，结果 luogu 上只跑 400ms。
希望不要出来后爆0。

真实代码下来后在 luogu 没挂分。
100+100+65+40
我重写写错了（悲）。
在另一个什么榜上面也是305。
而且我好像是唯一这个分数的人（？）。
主要是 T3 没写正解去写 T4 暴力还只拿了 40pts 的人太少了导致的（大悲）。

首先，知周所众，willpam 把他的洛谷号密码放在了首页。

我在洛谷上用他的号打了 abc模拟赛|A Passing Contest 001，并在比赛期间拿到了rank30 左右。

但是他的密码仍然放在首页（悲）。

然后现在他的洛谷号成了这个样子 luogu.com.cn/user/708860。

望恕罪望恕罪望恕罪望恕罪望恕罪望恕罪望恕罪望恕罪。

有谁能告诉我489这题数据范围明明是

任意时刻 0<ai≤10^6。

而给的数据到了

6,429,675

8,196,736

2,574,707

这合理吗？？？？？

不知道用的是什么方法（可能是深搜和dp???） 代码...写的很乱 希望你能看懂，还有别在意奇怪的变量名。 对了，问下，scanf怎么用？？？（数组的3001可以改成1001）

思路:每次从0到1就增加一次，直到终点，但搜索超时，所以保存一下从每个点到终点所需要的次数（最少）

#include<bits/stdc++.h>
using namespace std;
int a[3001][3001];
int u[3001][3001];
bool awsl[3001][3001];
bool ee;
int f(int c,int k,int s,int x,int y,bool p) {
    if(awsl[x][y]) {
        int rrrr=0;
        if(ee==false&&a[x][y]==1) {
            rrrr=1;
        }
        return s+u[x][y]+rrrr;
    }
    long long g=1919810114514,d=1919810114514;
    bool e=false;
    bool ahelp=false;
    bool bhelp=false;
    ee=p;
    if(x==k&&y==c) {
        awsl[x][y]=true;
        return s;
    }
    if((x+1)<=k) {
        if(a[x+1][y]!=p) {
            p=!p;
            e=true;
        }
        if(a[x+1][y]==1&&e) {
            g=f(c,k,s+1,x+1,y,p);
            ahelp=true;
        } else {
            g=f(c,k,s,x+1,y,p);
        }
    }
    if(e) {
        e=!e;
        p=!p;
    }
    if((y+1)<=c) {
        if(a[x][y+1]!=p) {
            p=!p;
            e=true;
        }
        if(a[x][y+1]==1&&e) {
            d=f(c,k,s+1,x,y+1,p);
            bhelp=true;
        } else {
            d=f(c,k,s,x,y+1,p);
        }
    }
    if(d>=g) {
        u[x][y]= u[x+1][y];
        if(ahelp)
        {
            u[x][y]++;
        }
        awsl[x][y]=true;
        return g;

    } else {

        u[x][y]=u[x][y+1];
        if(bhelp)
        {
            u[x][y]++;
        }
        awsl[x][y]=true;
        return d;

    }
}
int main() {
    int n,i,c,k,j,t;
    cin>>n;
    int g[n+1];
    for(i=1; i<=n; i++) {
        scanf("%d%d",&c,&k);
        g[i]=0;
        for(j=1; j<=k; j++) {
            for(t=1; t<=c; t++) {
                scanf("%d",&a[j][t]);
                u[j][t]=0;
                awsl[j][t]=false;
            }
        }
        if(a[1][1]==1) {
            g[i]++;
            g[i]+=f(c,k,0,1,1,1);
        } else {
            g[i]+=f(c,k,0,1,1,0);
        }
    }
    for(i=1; i<=n; i++) {
        printf("%d\n",g[i]);
    }
    return 0;
}

（感觉写的很奇怪，算了，不管了） (感觉没用的东西好多呀，等哪个人来改改吧）