NOIP2024 游记

Day -1

模拟赛 T4 MLE 了，70->0。原来是自己 C++ 测样例脚本 ulimit 使用不对。

Day 0

早上去上 whk。下午找 M 大神求助测样例脚本，经测试后 ulimit -s ;ulimit -v;time ./ 三句话连在一起才能启动 ulimit。然后加了点功能：显示 RE 和 WA 的点。（然而他用的是 .sh，ulimit 不用放一起也可以启动）

晚上到家已经快 21:00 了，一个板子也没打就睡觉了。

Day 1(2024.11.30) 13:00 前

和同学一起进杭师大，我在机房 302。

我的座位紧贴背对窗户。在我那一排和签到名单上看到了 zys 大神和“转投他校”的黄姓同学 hhy0613，快一年没见到 hhy 了，上一次还是在 PKUWC 的酒店里见到的（当时他已经转投他校两星期了）。感觉那一排应该是初中 Linux 区，显示器是长方形的，比 CSPS 时 Windows 区的正方形显示器大多了也舒服多了（不过那里还有正方形显示器，系统一眼扫过去都是 Windows）。左前方有 ZJ-0001 sfl 和 ZJ-0002 fsz，可以看到他们的屏幕。左方有 yyf，远处可见 czk,zcr,zjx。左边是杨添盛。

8:30 开，先（理解性）默写了测样例脚本。

看 T1，不会，猜个贪心，再想想怎么 O(n) 实现，直接记录每段可用的 0/1 的个数即可，过了大样例。此时快 9:00，不赢不输。没想到反例就不管贪心正确性了。

看 T2，显然每段独立，最开始题意没看清，当成要考虑 x，没过去样例。又花了一点时间推式子。9:30 多过大样例，小输。

看 T3，k=1 显然。按照模拟赛的经验先跳了：如果不能秒掉 T3，就先去看 T4，不深入思考 T3，搞好 T4 基础的部分分再看 T3。

看 T4，感觉部分分很多的样子。一开始脑子很晕，把 \max 当成 \sum 了，O(n^2+qn) 显然，但是要写两个 ST 表（一个欧拉序求 LCA，另一个维护区间 LCA）。没过样例成功激活了自己，改改过了，B 性质暴力即可，过了对应的大样例，此时 10:00。

分析 A 性质很快想到统一二分+离线一起处理（类似整体二分，不过不用管撤销的细节）O(n\log^2n)，试图冲 O(n\log n) 失败。试图把链转到树也失败，开码，11:00 多过了对应的大样例，1e5 1.5s，随 5e5 发现要 17s，只有 48pts，输，看 T3。

回去看 T3，很快想到了容斥 O(2^kn)。看性质，A 输出 1 送的，B 性质不用枚举子集，考虑容斥 1/2 条边即可。大概 11:40 过了对应的大样例，64pts。

想带容斥系数 -1 的 DP 失败，又去想 T4 A 的 O(n\log n)，失败（虽然平时模拟赛 T4 不容二想，打完应拿的部分分必须放弃，但是感觉这次 T4 很有前途啊），没想出来。

快 11:30，突然感觉 T3 很可做，有了大概思路，但是感觉 30min 不够了！先匆忙的从部分分代码复制了读入和初始化，然后想 DP 细节，最后也没想清楚，心里已经知道自己要输了。最后 15 分钟建子文件夹放代码，填字节数表。

感觉身边的同学都会 T3，因为夏令营讲过带容斥系数 -1 的 DP，几道题同学都写了。这下大家都过 123，T4 的 32 分很好写。

估分：100+100+64+48=312。估计垫底了。

今年最后 80min 分数没有任何进展，然而去年只有 40min。

Day 1 13:00 后

出来见到认识的同学就问会不会 T3。杨添盛说显然不会。在前往机房门口的路上碰到了 jzc 和 wxy，wxy 说会，jzc 说会但是没调出来。糟糕，这下估计大家都会 T3 了，慌了！在 1 楼平台碰到了 cyq,ljm,yyf，cyq 和 yyf 说不会。ljm 说没调出来。没碰到 byc。

在门口的时候看到 fsz 给别人讲题，感觉 fsz AK 了。

拍合照。

往杭师大门口走的路上问 fsz 关于 wmy 的分数，他说 wmy 应该 AK 了。

虽然问了一些同学说不会 T3，但是我还是很慌，感觉一车 348 的。

Day >1

考完之后我家长看某些地方得到的结论：T4 比 T3 简单。但赛后会了 T3 不会 T4。看云斗发现 ZJ T3 30AC T4 24AC，可能因为题目顺序导致大家都冲 T3 导致的，如果 T4 放前面估计更多人过。当然暑假也学了带容斥系数 -1 的 DP 对 T3 指数复杂度变多项式复杂度有一定帮助。

树想不到相邻 LCA，链不会 O(n\log n)。两个都没想到看来自己确实只配拿 48。总之，我树和 DS 都太菜了！！！

感觉但凡实力强一点 T1T2 就可以省 20min，T4 就可以省 30min，就有冲 T3 的希望了，348 还算一个不错的分数？但是赛后想通 T3 的容斥 DP 后写+调总共用了 90min（不算想的时间），鉴定为组合计数功底太差，不过省个 50min+不去冲 T4 O(n\log n) 应该够了。总之自己太菜了，没有什么好抱怨的。附自己很蠢的容斥 DP 做法。

查分，100+100+64+48=312，一分没挂。问 wxy，他说他 T4 挂成 20，反正我比他低。fsz 和 wmy 都 AK 了，别的同学暂时不太清楚。

本来以为考得非常一般，没想到云斗的成绩表显示卡在高中生 3 倍队线？神秘。总算拿到了非大众分，开心。

哈哈哈，云斗测 ZJ 高中生显示没有 312，T3 也没有 64 的。应该就我会 T3 O(2^kn) 不会 O(n\text{poly}(k))！（当然现在也不会非 O(n) 的 O(n\text{poly}(k))）我是 Joker！我真的太菜了！

老师要到了我们学校初中生的代码，挂一下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char s1[N], s2[N], t1[N], t2[N];
int b1[N], b2[N], c1[N][2], c2[N][2];

int Main()
{
    int n, i, ans = 0;
    scanf("%d%s%s%s%s", &n, s1+1, s2+1, t1+1, t2+1);
    memset(c1,0,sizeof c1);memset(c2,0,sizeof c2);
    int x1 = 0, x2 = 0;
    for(i=1;i<=n;i++)
    {
        if(i==1||t1[i-1]=='0'||t1[i]=='0') x1++;
        if(i==1||t2[i-1]=='0'||t2[i]=='0') x2++;
        b1[i] = x1, b2[i] = x2;
        c1[x1][s1[i]-'0']++, c2[x2][s2[i]-'0']++;
    }
    for(i=1;i<=n;i++)
    {
        if(c1[b1[i]][0]&&c2[b2[i]][0])
        {
            c1[b1[i]][0]--, c2[b2[i]][0]--;
            ans++;
            continue;
        }
        if(c1[b1[i]][1]&&c2[b2[i]][1])
        {
            c1[b1[i]][1]--, c2[b2[i]][1]--;
            ans++;
            continue;
        }
        if(c1[b1[i]][0]) c1[b1[i]][0]--;
        if(c1[b1[i]][1]) c1[b1[i]][1]--;
        if(c2[b2[i]][0]) c2[b2[i]][0]--;
        if(c2[b2[i]][1]) c2[b2[i]][1]--;
    }
    printf("%d\n", ans);
    return 0;
}

int main()
{
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    int t;scanf("%d", &t);
    while(t--) Main();
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7;

struct cd{int c,d;}a[N];
int c[N], d[N];

int power(int a, int b)
{
    a %= mod;
    int c = 1;
    while(b)
    {
        if(b&1) c = c * a % mod;
        b >>= 1, a = a * a % mod;
    }
    return c;
}

int Main()
{
    int n, m, v, i, ans = 1;
    scanf("%lld%lld%lld", &n, &m, &v);
    for(i=1;i<=m;i++) scanf("%lld%lld", &a[i].c, &a[i].d);
    sort(&a[1],&a[m]+1,[](cd a,cd b){if(a.c!=b.c)return a.c<b.c;return a.d<b.d;});
    for(i=1;i<m;i++) if(a[i].c==a[i+1].c&&a[i].d!=a[i+1].d) ans = 0;
    for(i=1;i<m;i++) if(a[i].c!=a[i+1].c)
    {
        int x = a[i+1].c - a[i].c;
        int y = (power(v,x*2)-power(v,x)+power(v,x-1)) % mod;
        ans = ans * y % mod;
    }
    ans = ans * power(v*v,a[1].c-1+(n-a[m].c)) % mod;
    printf("%lld\n", (ans+mod)%mod);
    return 0;
}

signed main()
{
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout);
    int t;scanf("%lld", &t);
    while(t--) Main();
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7;

namespace test12
{
int dep[N], u[N], v[N], d[N], e[N], fac[N], sz[N], ca, res;
vector<int>g[N];

void dfs(int x, int f)
{
    dep[x] = dep[f] + 1;
    for(auto j:g[x]) if(j!=f) dfs(j,x);
}

void dp(int x, int f)
{
    int c = 0;
    int a = sz[x];
    for(auto j:g[x]) if(j!=f)
    {
        dp(j,x), sz[x] += sz[j];
        if(sz[j]) c++;
    }
    if(sz[x]<ca||a) c++;
    int deg = g[x].size();
    if(c==1) res = res * fac[deg-1] % mod;
    if(c==2) res = res * fac[deg-2] % mod;
    if(c>=3) res = 0;
}

int Main()
{
    int n, k, i, j, ans = 0;
    scanf("%lld%lld", &n, &k);
    for(i=1;i<n;i++) scanf("%lld%lld", &u[i], &v[i]), g[u[i]].emplace_back(v[i]), g[v[i]].emplace_back(u[i]);
    dfs(1,0);
    for(i=1;i<n;i++) if(dep[u[i]]<dep[v[i]]) d[i] = v[i];else d[i] = u[i];
    for(i=1;i<=k;i++) scanf("%lld", &e[i]);
    for(i=1;i<(1<<k);i++)
    {
        ca = 0, res = 1;
        for(j=1;j<=n;j++) sz[j] = 0;
        for(j=0;j<k;j++) if((i>>j)&1) ca++, sz[d[e[j+1]]] = 1;
        dp(1,0);
        if(ca&1) ans = (ans + res) % mod;
        else ans = (ans - res) % mod;
    }
    printf("%lld\n", (ans+mod)%mod);
    for(i=1;i<=n;i++) g[i].clear();
    return 0;
}
int main()
{
    int t, i;scanf("%lld", &t);
    fac[0] = 1;
    for(i=1;i<=N-10;i++) fac[i] = fac[i-1] * i % mod;
    while(t--) Main();
    return 0;
}
}

namespace test18
{
int main()
{
    int t;scanf("%lld", &t);
    while(t--) printf("1\n");
    return 0;
}
}

namespace test21
{
int fac[N];
int Main()
{
    int n, k, i, a, b;
    scanf("%lld%lld", &n, &k);
    for(i=1;i<n;i++) scanf("%lld%lld", &a, &b);
    for(i=1;i<=k;i++) scanf("%lld", &a);
    if(k==1) printf("%lld\n", fac[n-2]);
    else
    {
        int a = k * fac[n-2] % mod - k * (k - 1) / 2 % mod * fac[n-3] % mod;
        printf("%lld\n", (a%mod+mod)%mod);
    }
    return 0;
}
int main()
{
    int t, i;scanf("%lld", &t);
    fac[0] = 1;
    for(i=1;i<=N-10;i++) fac[i] = fac[i-1] * i % mod;
    while(t--) Main();
    return 0;
}
}

signed main()
{
    freopen("traverse.in","r",stdin);
    freopen("traverse.out","w",stdout);
    int c;
    scanf("%lld", &c);
    if(c<=12) return test12::main(), 0;
    if(c==18) return test18::main(), 0;
    if(19<=c&&c<=21) return test21::main(), 0;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, q;
bool Mbe;
vector<int>g[N];
int ee[20][N*2], lc[19][N], cur, dep[N], l2[N*2], pos[N];
bool Med;

int sm(int a, int b){return (dep[a]<=dep[b])?a:b;}

int LCA(int a, int b)
{
    a = pos[a], b = pos[b];
    if(a>b) swap(a,b);
    int c = l2[b-a+1];
    return sm(ee[c][a],ee[c][b-(1<<c)+1]);
}

int rlca(int l, int r)
{
    int z = l2[r-l+1];
    return LCA(lc[z][l],lc[z][r-(1<<z)+1]);
}

void dfs(int x, int f)
{
    ee[0][pos[x]=++cur] = x, dep[x] = dep[f] + 1;
    for(auto j:g[x]) if(j!=f) dfs(j,x), ee[0][++cur] = x;
}

namespace chain
{
int ans[N];
struct qq{int l,r,k,L,R,mid,id;}qu[N];
set<int>S;
int mx[N*4], lz[N*4], r[N];
void jia(int p, int x){mx[p]+=x,lz[p]+=x;}
void spd(int p){if(lz[p])jia(p*2,lz[p]),jia(p*2+1,lz[p]),lz[p]=0;}
void build(int p, int L, int R)
{
    lz[p] = 0;
    if(L==R) return mx[p] = n - L + 1, void();
    int mid = (L + R) >> 1;
    build(p*2,L,mid), build(p*2+1,mid+1,R);
    mx[p] = max(mx[p*2],mx[p*2+1]);
}
void add(int p, int l, int r, int L, int R, int x)
{
    if(L==R) return jia(p,x), void();
    int mid = (L + R) >> 1;spd(p);
    if(l<=mid) add(p*2,l,r,L,mid,x);
    if(mid<r) add(p*2+1,l,r,mid+1,R,x);
    mx[p] = max(mx[p*2],mx[p*2+1]);
}
int ask(int p, int l, int r, int L, int R)
{
    if(l<=L&&R<=r) return mx[p];
    int mid = (L + R) >> 1;spd(p);
    if(l>mid) return ask(p*2+1,l,r,mid+1,R);
    if(mid>=r) return ask(p*2,l,r,L,mid);
    return max(ask(p*2,l,r,L,mid),ask(p*2+1,l,r,mid+1,R));
}
int main()
{
    scanf("%d", &q);
    int i;
    for(i=1;i<=n;i++) r[dep[i]] = i;
    for(i=1;i<=q;i++) scanf("%d%d%d", &qu[i].l, &qu[i].r, &qu[i].k), qu[i].L = 1, qu[i].R = n, qu[i].id = i;
    while(true)
    {
        for(i=1;i<=q;i++) qu[i].mid = (qu[i].L + qu[i].R + 1) >> 1;
        sort(&qu[1],&qu[q]+1,[](qq a,qq b){return a.mid<b.mid;});
        int j = 1;
        S.clear(), S.insert(0), S.insert(n+1);
        build(1,1,n);
        for(i=1;i<=q;i++)
        {
            while(j<qu[i].mid)
            {
                auto it = S.lower_bound(r[j]);
                int R = *it, l = *(prev(it));
                add(1,l+1,r[j],1,n,r[j]-R);
                assert(ask(1,r[j],r[j],1,n)==0);
                S.insert(r[j]), j++;
            }
            if(ask(1,qu[i].l,qu[i].r-qu[i].k+1,1,n)>=qu[i].k) qu[i].L = qu[i].mid;
            else qu[i].R = qu[i].mid - 1;
        }
        for(i=1;i<=q;i++) if(qu[i].L!=qu[i].R) break;
        if(i>q) break;
    }
    for(i=1;i<=q;i++) ans[qu[i].id] = qu[i].L;
    for(i=1;i<=q;i++) printf("%d\n", ans[i]);
    return 0;
}
}

signed main()
{
    freopen("query.in","r",stdin);
    freopen("query.out","w",stdout);
    int i, j, a, b;
    scanf("%d", &n);
    for(i=1;i<n;i++) scanf("%d%d", &a, &b), g[a].emplace_back(b), g[b].emplace_back(a);
    dfs(1,0);
    for(i=1;i<=n;i++) if(dep[i]==n) break;
    if(i<=n)
    {
        chain::main();
        return 0;
    }
    for(i=2;i<=cur;i++) l2[i] = l2[i>>1] + 1;
    for(i=1;(1<<i)<=cur;i++) for(j=1;j+(1<<i)-1<=cur;j++) ee[i][j] = sm(ee[i-1][j],ee[i-1][j+(1<<(i-1))]);
    for(i=1;i<=n;i++) lc[0][i] = i;
    for(i=1;(1<<i)<=n;i++) for(j=1;j+(1<<i)-1<=n;j++) lc[i][j] = LCA(lc[i-1][j],lc[i-1][j+(1<<(i-1))]);
    scanf("%d", &q);
    while(q--)
    {
        int l, r, k, ans = 0;
        scanf("%d%d%d", &l, &r, &k);
        for(i=l+k-1;i<=r;i++) ans = max(ans,dep[rlca(i-k+1,i)]);
        printf("%d\n", ans);
    }
    return 0;
}

以及我场上写的 Linux 测样例脚本，直接改 T,M,file,code,tests,testt 就可以启动了！（testt 是 abcd 后缀的文件名，用于手造样例，运行时间需要自己看）

#include<bits/stdc++.h>
using namespace std;
int T = 1000, M = 512, tests = 2, testt = 1;
string re = "", wa = "", file = "edit", code = "A";

void run(string s)
{
    cout<<"Running "<<s<<"\n";
    string mem = "";
    int x = M * 1024;
    while(x) mem = (char)('0'+(x%10)) + mem, x /= 10;
    system(("cp "+file+s+".in "+file+".in").c_str());
    if(system(("ulimit -v "+mem+";ulimit -s "+mem+";time ./"+code).c_str())) return re += s + " ", void();
    if(system(("diff "+file+".out "+file+s+".ans -BZ").c_str())) wa += s + " ";
}

int main()
{
    int i;
    for(i=1;i<=tests;i++)
    {
        string s = "";
        int j = i;
        while(j) s = (char)('0'+(j%10)) + s, j /= 10;
        run(s);
    }
    for(i=0;i<testt;i++) run((string)""+(char)('a'+i));
    cout<<"RE: "<<re<<"\n";
    cout<<"WA: "<<wa<<"\n";
    cout<<"Time Limit: "<<T;
    return 0;
}