文章同载：https://www.luogu.com.cn/article/qd3i9xfj

前言

人物介绍：

• fyy，即 fp0cy1tz6mn4rd_。
• da_ke，即 。
• 「珂愛的我」，即 。

A

ke_ai_de_wo

B

珂愛的我按照形式化题意模拟，不然容易错。

ke_ai_de_wo

C

对于以 $i$ 结尾的子序列，其开头必然是与 $A_i$ 相同的最后一个数。对所有情况取最优。

ke_ai_de_wo

D

fyy 是一个珂愛的女孩子，有一天她购得 $N$ 只珂愛的 da_ke。

她初始将编号 $i$ 的 da_ke 放置在 $i$ 号笼子里。

随后，她进行 $Q$ 次操作，操作分为 $2$ 类

1. 将 $a$ 号 da_ke 放入 $b$ 号笼子
2. 将 $a$ 号笼子和 $b$ 号笼子里的所有 da_ke 互换。

fyy 可以在任意时刻问妳某个 da_ke 在哪个笼子里。

fyy 非常喜欢 da_ke，于是她买了很多只，于是妳要使用一种非常高效的算法来回答她的问题。

「珂愛的我」（下简记为我）想到，对于操作 $1$ 是容易的，经常刷题的朋友都知道，对于操作 $2$ 不容易单个处理，必须整体处理。

对于操作 $2$，我想到将笼子 $a$ 和笼子 $b$ 整体交换。但这将导致 $a$ 和 $b$ 的位置改变，da_ke 的位置也将改变，如何处理呢？

问题过于抽象，为了更加形象（笔者赛时也是这么想的），我将问题形象化。

将笼子和 da_ke 一起放在数轴上。为了语言描述，我常用「da_ke 本身」和「笼子本身」这两个短语。

• 对于所有操作 $1$，我们只需挪动 da_ke 本身的位置即可。
• 对于所有操作 $2$：
  • 保证 da_ke 本身的位置不变（解题的关键）。
  • 只交换笼子本身达到效果。
  • 更新笼子本身的位置。

以上是一些感性认识，我们现在将其转换为形式化语言。

记笼子 $i$ 的坐标位置为 $S_i$，坐标位置 $i$ 的笼子为 $E_i$，编号为 $i$ 的 da_ke 目前被关在坐标位置为 $H_i$ 的笼子里。

• 对于操作 $1$，$H_a\leftarrow S_b$。
• 对于操作 $2$：
  • $a$ 的位置将被 $b$ 占用，$b$ 同理，于是有 $E_{S_a}\leftarrow b,E_{S_b}\leftarrow a$。
  • 将 $a,b$ 的坐标位置互换，达到 $S_a^{\prime }=S_b,S_b^{\prime }=S_a$ 的效果。

代码是简单的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

int main()
{
    int N,Q;
    cin>>N>>Q;
    vector<int> st(N+1),ed(N+1),home(N+1); // st 为某个巢的坐标位置，ed 为某个坐标位置的巢。 
    rep(i,1,N) st[i]=i,ed[i]=i,home[i]=i;
    rep(i,1,Q)
    {
        int o;
        cin>>o;
        // 操作时应保证，鸽子是不动的。
        if(o==1)
        {
            int a,b;
            cin>>a>>b;
            home[a]=st[b];
        }
        /*
        .....a.....b....
        .....b.....a....
        */
        if(o==2)
        {
            int a,b;
            cin>>a>>b;
            ed[st[a]]=b,ed[st[b]]=a;
            swap(st[a],st[b]);
        }
        if(o==3)
        {
            int a;
            cin>>a;
            cout<<ed[home[a]]<<endl;
        }
    }
}

// 路虽远行则将至，事虽难做则必成。

AC 记录

E

fyy 行驶在小溪上，路线可以看作有向图。每条边的边权为 $1$。

因为「逆水行舟，不进则退」，fyy 要么沿着边的方向前进，要么逆着边的方向前进。顺、逆之间的转换需要代价 $X$。

fyy 想知道从 $1$ 到 $N$ 的最短代价是多少。

发现顺着和逆着似乎有着隔阂。这便是「层」。

• 将每个点 $i$ 拆成两个点 $i,i+N$。
  • 将 $(i,i+N),(i+N,i)$ 连接，边权皆为 $X$。
• 对于每个原来的边 $(u,v)$：
  • 连接 $(u,v)$ 和 $(v+N,u+N)$。这里体现顺、逆。

然后 Dijkstra 跑最短路即可。时间复杂度取决于 Dijkstra 的写法。

代码

終

本当の本当に終わり

「X - この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を」 解题报告

更快的更新渠道：https://www.luogu.com.cn/article/hmnoem6g

背景

故事性的背景：

このコンテストで潰そうという気になってくれた方に挑戦していただければと思います．コンテスト準備をしている段階から，本当にこんな問題を出題するのが許されるのかと大いに悩んでおりましたが，せっかくのネタ性に溢れるコンテストなので思い切って出題してみた次第です．お楽しみ頂ければ幸いです．

問題文 くぅ〜疲れましたｗ これにてコンテスト準備終了です！ 実は、ネタ問題を考えたらコンテストの話を持ちかけられたのが始まりでした 本当はボス問題のネタなかったのですが← ご厚意を無駄にするわけには行かないので一発ネタで挑んでみた所存ですｗ 以下、writer達のみんなへのメッセジをどぞ

きゅうり「みんな、解いてくれてありがとう ちょっとクソ問なところも見えちゃったけど・・・気にしないでね！」

JAPLJ「いやーありがと！ 問題の面白さは二十分に伝わったかな？」

KyuR1「解いてくれたのは嬉しいけどちょっとペナルティが多いね・・・」

じゃっぷる「解いてくれてありがとな！ 正直、問題文はほとんどがコピペ改変だよ！」

kyuridenamida「・・・ありがと」ｷｭﾘ
では、

きゅうり、JAPLJ、KyuR1、じゃっぷる、kyuridenamida、高橋「皆さんありがとうございました！」 終

きゅうり、JAPLJ、KyuR1、じゃっぷる、kyuridenamida「って、なんで高橋くんが！？ 改めまして、ありがとうございました！」

本当の本当に終わり

主要任务：识别字符画，计算表达式。

本题在 OI 史上享有「世界上最恐怖的题目」之美誉。10 多年来吸引大量 OIer 来此挑战。

思路

目前可以说主要有 4 种思路：

• 传统的随机化法
• 神经网络、深度学习法
• 特征矩阵法
• naive 的感性判断法（对于每个数字的特征详细的判断）

这题是真的恐怖如斯！

我们无疑使用传统方法。深度学习法我们搞不起，其他神仙方法更是学不会。

主要步骤

1. 降噪（这是所有方法的第一步）

2. 找到连通块（每一个字符隔离出来）

3. 识别字符（难点）

   • 尝试对每个原字体字符变换找出相似度最大的一个字符
     • 旋转
     • 缩小
     • 失真

4. 计算表达式

一些规划

那么这道题肯定不是能一下子写好的。我们得分步骤测试调试。

本人初二，学业压力略微有点，所以本题只能咕咕咕。

• 封装一些常量，计划在 2 月末 3 月初调试完毕。
• 降噪、找连通块，计划在 3 月初调试完毕。
• 3 月中下、4 月初实现一些基本的变换。
• 4、5 月实现字符识别。
• 后面再说吧。

代码目前非常困难，我习惯于在线 IDE，这回不得不启动 Vscode 了。

结语

本当の本当に終わり

沉痛悼念 @fp0cy1tz6mn4rd_

2 月 7 日的夜晚，一条犇犇打破了往日的平静。

打开 fyy 的主页，观察注册时间，发现和开始时间相近，而结束时间是昨天的日期。

我立刻反应过来：世界末日的到来。

我尝试劝说他三思，但我后悔了。尽管如何劝说都无法挽救 fyy 退役的事实。

我这几天晚上总用手机写斜率优化 DP。想着自己 4 级勾（菜死了）初二还在坚持，别人初一 5 级勾都放弃了，心里五味杂陈。

我倾听着内心沉重的音乐，像被阴霾覆盖着。目送着他渐行渐远，直到缥缈而空虚的远方。

慢慢的，眼看着 fyy 把所有的犇犇全部删了。主页上「昙花一现」4 个子显得无比扎眼。我准备给他发私信，祝他 whk 一切顺利，结果他的私信也关了，失望。

我失望的点开了他的专栏，留下了最后的留言。

唉，我突然感到「二十余年如一梦，此身虽在堪惊」，我们之间的往事一帧帧一幕幕地从脑海中划过。这晚我睡不着了。

珂愛的 fyy 就这样离我们而去了，我们能做的，只是 3 天不发犇犇祭奠他而已！

千言万语说不尽，祝他 whk 一切顺利！

本文含有大量珂学技术，请酌情阅读。

免责声明：da_ke 对使用本文说明的方法造成的一切后果概不负责。杀级域教室需谨慎！

小招·暴力篇

1

这是我刚用级域的一种杀法。

1. 5 下 Shift 引出粘滞键，然后发现你的 Win 任务栏出现了，趁机点击 Windows 图标，点击睡眠。

2. 不停敲击空格，知道电脑被唤醒。

3. 然后你发现逃脱了控制，仅有一分钟是逃离控制的。

4. 如果想解除一分钟到期。使用管理员 cmd，输入：

1

taskkill -f -im StudentMain.exe

优点：操作熟练可以很快操作，并可以很快返回老师界面。

缺点：老师查界面你就死了。

2

1. Win+L。
2. 睡眠。
3. 重启
4. 同上

优点：便捷；缺点：同上。

中招·解禁特权篇

可能你经常发现 Edge 显示该网页已被组织。

查询网络

终端管理员：

1
2

ping luogu.com.cn
ping github.com

如果找不到服务器，那就是老师拔网线了，后面的操作屁用没有。

解禁特权

如果还可以查到数据，

1
2
3

taskkill /f /im masterhelper.exe
NET stop tdnetfilter
sc stop tdfilefilter

最后一行是解禁 U 盘的。如果你有什么代码没写完的就可以带来写了（

大招·两全其美

资源管理器

1. 打开资源监视器( Win+R 运行 resmon)。

2. 找到 StudentMain.exe, 右击并单击结束进程

分屏大法好！

在老师没控制你的时候杀掉级域并新建桌面，然后老师来的时候退回桌面启动级域，然后再 Win+G 退回来。

方法不太稳定，有时会失败。

登录教师

当老师全屏控制时：

1．在全屏控制左上角点＂平移＂（找到后屏幕会缩小）

2．win + G，或者用最开始 Shift-Win 的方法。

3．右下角小箭头，找到极域并左键，其实就是任务列表。

5．设置，密码就写万能密码：mythware_super_password。

然后好办了。

https://blog.csdn.net/pyz258/article/details/130923638#:~:text=%E6%96%87%E7%AB%A0%E4%BB%8B%E7%BB%8D%E4%BA%86%E5%A6%82%E4%BD%95%E5%88%A9%E7%94%A8%E4%B8%87

使用珂学技术

https://github.com/imengyu/JiYuTrainer

用 U 盘带。U 盘解禁见上文。

前言

最难的 C。我的思路也很另类。

Stop learning other useless algorithms,go to solve problems,and learn how to use binary search. by Um_nik.

翻译

现在，有 $N$ 个敌人的按顺序排成一行，记他们的生命值为：$a_1,a_2,\dots ,a_N$，你有一个初始为 $0$ 的量 $T$。

不断进行如下操作：

记目前最前面的敌人生命值为 $a_i$，满足 $\mathrm{\forall }j\in [1,i),a_j<1$。

• 若 $T\equiv 0(mod3)$，让 $a_i$ 减 $3$。
• 否则，让 $a_i$ 减 $1$。

求让所有敌人生命值不大于 $0$ 的最小操作次数。

思路

暴力的方法的复杂度依赖于 $maxa$ 的大小，是因为因为这种方法不断去枚举 $T$ 导致的。

其实枚举 $T$ 是没必要的，因为很多操作是重复的。其实复杂度的瓶颈就是在于有些 $a_i$ 很大，你不断减 $1$ 很浪费时间。

所以可以在枚举 $i\in [1,n]$，考虑将每个敌人「杀死」，这么做是 $O(n)$ 的。但是个人觉得代码不太好写，我使用的是二分。

由于 $T$ 可以很大，事实上 $T\in [1,(maxa)\times N]$，考虑如下：

若存在一个最小的操作次数 $T_{min}$。则定 $\mathrm{\forall }T>T_{min}$，这些 $T$ 都多做了一些操作；$\mathrm{\forall }T<T_{min}$，这些 $T$ 都无法杀死所有敌人。

显然这道题符合二分的定义。

二分方法如下（会的直接跳过）

定义区间 $[L,R]$ 为查找区间，查找目的为 $L+1=R$。

• 如果 $M=\frac{L+R}{2}$，不足以杀死所有敌人，$T_{min}\in (M,R]$。
• 如果 $M=\frac{L+R}{2}$，能杀死所有敌人，是或不是最小次数（包含是最小次数的），$T_{min}\in [L,M]$。

判断是否杀死的方法：

定义 $x$ 为当前消耗的 $T$ 值。

对于 $i\in [1,n]$，记 $y=a_i$。

• 定义 $m=3-(xmod3)$

  • 如果 $y<m$，令 $x$ 为 $x+y$。

  • 如果 $y\ge m$，令 $y$ 为 $y-m-2$，$x$ 为 $x+m$。这里为了更好描述敌人的损耗。这是若 $y\ge 0$，则 $i$ 已经死了。否则：设每轮 $3$ 此共 $5$ 伤害值的轮数 $r=\lfloor \frac{x}{5}\rfloor$，计算出 $y$ 经过 $r$ 轮伤害后的 $y_1$，同时更新 $x$。

    • 如果 $y_1\in \{1,2\}$，则 $x$ 增加 $y_1$。
    • 否则，$x$ 增加 $3$。

具体思想是循环问题，每 $5$ 个伤害为一轮，可仔细体会。

运用上面的方法，判断 $i$ 次后是否满足 $x\le T$ 即可。

以上就是数学的描述，下面就是代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

// #define EXT
#include <bits/stdc++.h>
#ifdef EXT
    #include <bits/extc++.h>
#endif

//define
#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>

using namespace std;

// type define
typedef long long ll;
typedef double db;
typedef __int128 i128;
#ifdef EXT
    typedef unsigned int ui;
    typedef unsigned long long ull;
    typedef long double ldb;
#endif

// const integer
const int INF=1<<29;
const ll INFL=1ll<59;
const int N=2e5+3;

int n;
ll a[N],sum[N];

bool check(ll t)
{
    ll x=0;
    rep(i,1,n)
    {
        ll m=3-x%3;
        ll y=a[i];
        if(y<m) x+=y;
        if(y>=m)
        {
            // remaining : 3
            // x=0,1,2,3 m=3
            y=y-m-2,x+=m;
            if(y<=0) continue;
            // remaining : 7
            // x=0,1,2,3 m=3
            // y=2;
            ll r=y/5;x+=3*r;
            ll r0=y-5*r;
            if(r0<=2) x+=r0;
            else x+=3;
        }
    }
    return x<=t;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    rep(i,1,n) cin>>a[i],sum[i]=sum[i-1]+a[i];
    ll l=0,r=N*1e9+23;
    while(l+1<r)
    {
        ll mid=l+((r-l)>>1);
        if(check(mid))
            r=mid;
        else l=mid;
    }
    cout<<r;
}

代码中穿插了我写代码是举的例子，可仔细体会。

总结

我觉得这次很难。

广告：安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。

最后 60 天

每天晚上 23:00 左右更新，其实就是下线前更新。

缺省源：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// Written by da_ke
// Website: https://mahaoming2022.github.io

#include <bits/stdc++.h>

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    
}

// hope to debug successfully

之前的日志

• NOIP/提高组题单
• ABC题 https://www.luogu.com.cn/problem/list?type=AT&keyword=ABC&orderBy=pid&order=asc&page=1
• latest https://www.luogu.com.cn/problem/list?type=AT&keyword=ABC&orderBy=pid&order=asc&page=42
• https://www.luogu.com.cn/problem/list?type=AT&keyword=ABC&orderBy=pid&order=asc&page=30

undo:

• https://www.luogu.com.cn/problem/AT_abc266_c
• https://www.luogu.com.cn/problem/AT_abc264_c
• https://www.luogu.com.cn/problem/AT_abc278_e

todo:

• CSP-S 2020 https://www.luogu.com.cn/problem/P7076
• https://www.luogu.com.cn/problem/AT_abc258_g
• 大模拟·鸭棋 https://www.luogu.com.cn/problem/P5380
• 贪心https://www.luogu.com.cn/problem/P10569
• https://www.luogu.com.cn/problem/AT_abc257_f
• https://www.luogu.com.cn/problem/AT_abc260_e
• https://www.luogu.com.cn/problem/AT_abc261_f
• https://www.luogu.com.cn/problem/AT_abc264_f
• https://www.luogu.com.cn/problem/AT_abc265_e
• https://www.luogu.com.cn/problem/solution/AT_abc267_e
• https://www.luogu.com.cn/problem/AT_abc271_e
• https://www.luogu.com.cn/problem/AT_abc188_f
• https://www.luogu.com.cn/problem/P1879

什么嘛，我想要留下美好的回忆有什么错！在自己消失之前，心怀上不像消失的愿望，希望让某个人记住我，希望留下羁绊。我这么希望着，又有什么不可以吗！——珂朵莉

最后 60 天，不管好坏都得退役了。也就是，CSP 结束的那一刻，可以和我说 GoodBye 了。

但是即使这样，我也想拼尽全力，不留遗憾。

Day 0 / 20240825

其实呃呃呃。

今天颓了，跟小学生完了你画我猜，水了一黄就下了。

Day 1 / 20240826

MO 自然是小蓝本。组合数学难，但有规律可循。

很不幸的是我过敏了，原因未知。手极度的酸，连代码都打不动。

下面说说晚上。

发现：https://www.luogu.com.cn/problem/AT_abc278_f 可做，刚学过状压。丢到几天后做。

竟然犇犇现场开导神犇：@Yun_Mengxi 这么强都得退役了，那我是啥？

AT_abc279_e，很难。

我糖了，b[a[i]+1] 写成 b[a[i]]+1，原因：显然。

写一下这题思路：实际上，不操作某个操作的结果：

• 在操作前是后一个，那么看前面一个最后在哪里。
• 在操作前是前一个，那么看后面一个最后在哪里。
• 如果第 $i$ 次操作不关于 $1$，那么不用管他。

根据题解理解，感谢 dl。

立马换 F，并查集板子（？）偷偷看题解确认一下。

你说的对，但怎么清空 $y$ 的桶？！

开始看题解。21:52 懂了。思路是换点。

但是被 ub 搞到 22:43。还准备在写一题！

总结：数组太不安全，越界了连 RE 没有，我要学扶苏用 vector。

这个 abc280 C 太简单了，秒。

D 会，但是分解质因数应该有的。

Day 2 / 20240827

【有关 MO】【OI 无关】：其实组合数学是有必要先囫囵吞枣的，但很多人认为没意义。

狂补作业ing，damn 读书记录，各种 sb 表。

没控制住，玩你画我猜到 20:00。

D，分解质因数，有公式：

对于 $k$ 的因子 $p$，$N!$ 有 $N!/p^1+N!/p^2+\cdots +N!/p^k$

牢记。

同时因为不开 long long 调了很久，因为最后有一个很大的因子。

过。

存一道题：https://www.luogu.com.cn/problem/AT_abc280_e

秒 ABC281 C。

9:00 刚开 D，看一下觉得爆搜？搜完 dp 就行，不知可不可行。

题解怎么比我想的复杂！！

我觉得有点像背包，写出来看假不假。

然后写废了，没调。

Day 3 / 20240828

【OI 无关】贴一道组合数徐：

甲乙两人从 $1,2,4,\cdots ,2^{2024}$ 选数，甲先选。每选一个数，就将其减 $1$。如果哪个人操作后有负数，此人告负。问：谁必胜？

答案：甲必胜。原因：搞不懂。来源：《小蓝本》第 7 本，第 4 章习题 8。

大佬会的私信我。

感谢 Zelotz 的耐心查看，发现 1LL<<59 写成 1LL<59，警钟长鸣。

Zelotz 列为 Special Thanks。

随后 A 了。

写点闲话，我跟 cq_zry 什么关系。

这里 cq_zry 现在是 @CQ_Bob & @harmis_yz。

实际上，我们认识的日子就是 WOT 的生日。当时，cq_zry 回答了我的一个帖子，使得我关注他。然后我向他宣团，就是现在的 WOT，他加入了。

第二天，他问我团队里 【Wuhu 2002】飞行棋 他代码的问题，是用记忆化搜索的，我自然没看出来。

当时我很弱，非常菜，但是 cq_zry 不仅没有瞧不起我，还耐心地指导我。我们努力出了愚人节赛（T1 模拟，T2 博弈，T3 dp）。

他对我很耐心，他也很谦虚，我觉得这才是真正的大佬。相比最近一些嘲讽我的「dl」来说【】。

也是因为他，我才学习了 dp，而且相当一段时间，我做的题都是 dp。我也喜欢用记忆化搜索，直到今天也在用。

在我们努力下，我们又出了五一赛（T1 模拟，T2 贪心，T3 忘了 T4 随机 T5 数位 dp T6 卡常背包）

那个暑假发生了很多事。后来因为著名的联合公开赛，cq_zry 被封了（被小 L 盗号导致的），从此我跟他很长一段时间没有交往，后来 WOT 也解散了。

这是后来我重建 WOT 的时候，我去再次邀请他，他竟然出乎意料的回到了 WOT

后来我又拜他为师，他耐心地帮我调了很多代码。

其实 cq_zry 一直是我心目中最巨的大佬，不仅仅是因为他的学术水平强悍……

这里搞笑放一段 cq_zry 写的：

YT: 也许曾经喜欢过，但已不存在了。那时的我们，一起笑过，哭过，陪过。和妳一起的时光很短，分别的时光很长。就像一场龙卷风，在不经意的瞬间，卷走了妳，和我。分开的时候，是迷茫的，是沉默的。我好像并没有感情，又好像，只是没有说出来。就这样我们在那不知意的情况下，默默地、慢慢地分别。在梦里，在脑海里，在心里，都牵挂着妳。多少次莫名地心酸，多少次悄悄地哭泣，不知道，终是为何。是雨天，是晴雨天，是看不见的雨天。它倾盆地毫无保留地泼下来，淋湿了我，毫无遮挡的脸庞……

Bye,if you remember me...

cq_zry

2023.2.10

这里祝 @cq_zry NOI Au。

言归正传，19:00 准时开始做题，不准颓废！

存一道题：https://www.luogu.com.cn/problem/AT_abc281_e

ABC282 B 竟然橙 orz。看了一会儿，很简单，没写。

C 红，orz。随便写一下。

很好写的模拟题，19:18 写好了。

D 绿，orz。二分图？我还没学过呢！

https://oi-wiki.org ：节点集合由两个集合组成，且两个集合内部没有边的图，称为二分图。

呃这个，还是看不懂。Thus，题解！

虽然但是用 DeepL：

什么是二分图？当且仅当我们可以将每个顶点涂成黑色或白色以满足以下条件时，一个无向图被称为二分图。

• 没有边连接涂成相同颜色的顶点。

这场 ABC 是不是 shaber 场？要是我参加肯定掉大分。我是唐诗。

运用组合数学中染色的思想，我们将图而染色（不妨黑白）。

若一条还没有添加的边，满足两边颜色不同，可加。

枚举每个连通块，记黑白分别为 $c_0,c_1$，根据乘法原理共 $c_0{c}_1$，同时也可以和别的连通块中的点连，故 $\sum c_0{c}_1+\sum (c_0+c_1)(N-c_0-c_1)/2$

最后减去连边即可。

写了但是：https://atcoder.jp/contests/abc282/submissions/57205175

检查公式，发现加减写错，sb。

话说这样例也不能水这种程度？

然后又 WA：https://atcoder.jp/contests/abc282/submissions/57205323

先不调了，去切 Water 场。

ABC283 保卫战！

C，第一眼 dp，数据范围爆了。马上贪心，正确！但是即使这么简单也不妨碍我 sb 交了很多次。

D，只有橙吗？晕了，我竟然不太会。但是括号层数记一下，被标记层数记一下就做完了吧。由于字母只有 $26$ 个故该条件应该是突破点。

更：ABC282D 开 long long，少错 2 个点。感谢 @baibaieee

水了犇，放松了一下，同时也获得了前面组合题的证明。感谢 @Ravener。

回来写题。大雾，为啥初值 x=1。A：原因是为访问过与第一层访问是有区别的。

E，是 dp 吗，数据这么诡异，不大不小。就算是也不会，太菜。

题解。

大概看了一下，是 dp，但暴力程度无法想象qwq。wssb。

可能丢一半明天写。

Day 4 /20240829

快开学了，先把 sb 表口胡了，还剩一个三结合，明天胡。

MO 颓了，悟净没颓。写点运动笔记

【高一物理】运动

先定义标量：只有大小而没有方向的量；矢量（数学中译作向量）：既有大小又有方向的量。

• 路程：质点通过的长度之和。符号：$s$，是标量。
• 位移：质点运动前后位置的变化。符号：$x$，是矢量。

举例：如一物体沿 $(x-1{)}^2+y^2=1$ 这个圆走，从 $(0,0)$ 沿圆周走大 $(2,0)$。其路程为 $\pi$，位移为 $(2,0)$。这里用向量的方式表示矢量。

• 时刻：时间的节点。符号 $t$，是标量。

• 时间：两个时刻之间的部分（通俗）。符号：$\mathrm{\Delta }t$，有时也即 $t$，是标量。

• 速度：符号为 $v$，$v={\displaystyle \frac{\mathrm{\Delta }x}{\mathrm{\Delta }t}}$，是矢量。方向与位移方向一致。

• 速率：瞬间速度。符号 $v$，矢量。

• 加速度：匀变速直线运动中，速度-时间函数的斜率。

下面介绍这些的关系：

记时间为 $t$，开始速度为 $v_0$，加速度为 $a$。

• $v=v_0+at$

• 位移的大小是速度-时间函数图像下方面积（通俗的讲是：开始时间的垂线、停止时间的垂线，函数图像，坐标系横轴所围成的面积）。

证明：这里记函数为 $f(x)$ 将函数曲线分割成无限小长方形。每个长方形在横坐标轴上，其在横坐标轴上的边长为 $\mathrm{d}x$，其面积为 $f(x)\mathrm{d}x$，就是表示的是这个瞬间通过的位移大小。

由上面的结论我们可以推出一个推论：

• $x=v_{0}t+a{t}^2$。面积公式可证。

如果我们用 $v$ 表示结束时的速度，那么又有：

• $v^2-v_0^2=2ax$。由上式变换可得。

下面介绍函数关系：

由公式 $x=v_{0}t+a{t}^2$ 和 $v=v_0+at$，很难不发现，$v=x^{\prime }$。

实际上，速度的变化实际上就是位移的瞬间变化率，这符合导函数的定义。

实际上，速度-时间函数是位移-时间函数的导函数，加速度-时间函数是速度-时间函数的导函数。

下面介绍考法：

实际上，各种问题，我们都可以将 $v-t$ 图像转为 $x-t$ 图像（积分）。这样我们就可以解决各种考题。

本人初学，有错私信。

写笔记写到 19:30，准备开始 OI。

今天可能需要补一些前面的题。

一上，https://lglg.top/913738 这个也能违规，这是人吗？！你谷现在 xxs 泛滥，天天讨论低质量内容，怎么来板块漂移就是 btd？？你谷真的是蒸蒸日上啊！

你谷 xxs tm 真可怕！我真的服了。其实我现在基本不用讨论区了，真的跟小学生对线对怕了！他们一个个号称比我强几百倍！说我 CTJ，说我菜，说我是 xxs。真的好想笑啊。其实你谷绿名是菜，xxs 很多都是绿名，但绿名只是是 xxs 的必要条件！不是充要条件！实际上也不是必要条件，因为橙名也有小学生。所以很多人看到我都以为是那种 xxs，都不看我主页都跟我对线，引战。

其实真正的大佬不是你们这些伪大佬的姿态的。可怕。xxs 一般具有几个特征：

• 主页冗长，含有滥用 $LATEX$ 的垃圾内容、传送带图片、火柴人图片、你谷笑梗、游戏、iostream=100、各种打油诗等等垃圾内容。而大佬的主页都是什么 AtC Rating，CF Rating 之类的。

• 小学生你跟他说 ABC 都不知道是啥。他们没有 AT，CF。

• 小学生可以随便在求助帖里发诸如「666」「你调不出来就睡觉」之类的劝退的语气。

主要还是看主页。正如一位蓝勾巨佬跟我说的：主页就可以准确的看出一个人的年龄。

致远星了，看了 kkk 发的帖，sb，6 h 老铁，那我题目总版岂不是直接沉海！你谷讨论区密度小，而神贴密度比他更小，但学术帖密度很大，这是因为他又知识！！！那些 xxs 帖你觉得他又什么意义吗？这不是鼓励发水贴吗？

我去 LOJ 捞了（？），其实我是很反对各种规定的。实际上规定并不能约束人的思想。洛谷不是明明规定不能抄题解不还有人吗？他们难道不知道没有这条规定吗？这简直就是谬论！

惩罚实际上是一种比较低级的约束方式。虽然但是，LOJ 没有严格的规定也没有小学生嘛！

要么就严格要求。像 Codeforces，你去发个 qp 都不行。这强迫我们讨论学术内容。然而现在学术贴 1 年都没有一条回复，这是洛谷的初衷吗？？？！！

如今小学生泛滥的洛谷我觉得是无可救药了，自从 xht 搞毛，小粉兔休假以后就是密度一天比一天小，让知识都埋没在深处了。

洛谷就像一个大海，总是密度小的水贴上浮，显眼，甚至神贴永垂不朽；而密度大的求助帖下沉，还不给捞。

如果你认为我说的不对，别喷。只会喷人的人不是好人。

虽然但是如果你发帖缅怀李政道都是违规的，但是我看看管理员有没有胆量把他删了。

https://www.luogu.com.cn/discuss/880769

我觉得那些风纪志愿者也得停停停了，洛谷现状无法挽回。

开始看题了，边写边写点日记

sb dp，写了很久才写好。

sb AT，上了好久上不上去！

样例没过 #1

感谢 @ran_qwq 指出 AT_abc282_d 我取整的错误，orz。因边会在别的连通块中遍历到，所以不慌除以二。

发现问题：tm 又把 i,j,k 搞反，警钟长鸣。但是这竟然过了 16 组数据！

这次也算终于 A 了：https://www.luogu.com.cn/record/175306046

写一下想法：

$dp(i,j,k,l)=min\{dp(i-1,k,l,0)+dp(i-1,k,l,1)\}+j$

然后在 AT 的自带 IDE 上随便打了一道 C，直接交，没测样例，竟然直接 A。

Day 5 / 20240830

明天开学报道了。

初一电脑班在 9 班，准备面积 ps。

谈谈大招在中考的应用：

图：天津 2024 中考，填空倒数第二题。

实际上这道题就是个裸体。

无需作任何辅助线的，但答案作了。

在 $\mathrm{△}AED$ 中应用余弦定理，$D{E}^2=A{E}^2+A{D}^2-2AE\cdot DE\cdot \cos \mathrm{\angle }DAE=34$。

然后应用斯特瓦尔特定理的特殊情况中线长定理，$A{F}^2=\frac{1}{2}A{E}^2+\frac{1}{2}A{D}^2-\frac{1}{4}D{E}^2=\frac{\sqrt{10}}{2}$。然后就结束了。

天津出题人脑瘫辣！

天津第 18 题一样脑瘫，但是有一个细节注意到：$AE$ 是圆的直径。就结束了（应用小蓝本第 4 本「三角形内接三角形」中的结论即证）。

所以这里放几个大招：

余弦定理：

$c^2=a^2+b^2-2ab\cos C$，具体前提翻高中数学必修第二册。

正弦定理：

$a/\sin A=b/\sin B=c/\sin C$

斯特瓦尔特定理：

$P$ 是 $\mathrm{△}ABC$ 边 $BC$ 上的点：

$A{B}^2\cdot PC+A{C}^2\cdot PB=A{P}^2\cdot BC+PB\cdot PC\cdot BC$

Menelaus 定理，塞瓦定理，托勒密定理。直接 bdfs 吧，这里不展开举例说明了。

堪称经典。

。。。。

今天没有日记，因为我去墨鱼了。

写了 E：LCM on the whiteboard。有一点没明白，故不写思路。

感谢 @枫原千叶 解答了我 4 个月的问题。

谷冥看法：https://www.luogu.com.cn/discuss/915331

投票:你如何看待姜萍事件(点击选项进行投票):
我支持姜萍。我认为她是一个自学成才的天才，她的成绩是真实的。
我不支持姜萍。我认为她是一个数学盲，她成绩可能是假的

Day 6 / 20240831

今天入学。讲废话。乐子。

然后 ABC 事后诸葛亮了。赛时竟然只做了 A、B。赛后话好长时间做 C，但 D 秒了。qwq，掉大分！！！

wssb。

Day 7 / 20240901

https://www.luogu.com.cn/discuss/916871 出题人是不是来吃饭的？！

这里讲一下 D 的做法（其实是个人就会。

一个暴力 dp：$dp(i,j)=v(i)+max\{dp(i,j),dp(i+1,dp(j+1))\}$，其中 $v(i)$ 是第 $i$ 个所获价值。

其实我们并不关心 $j$ 是多少，只关心奇偶性，故 $$dp(i,j)=v(i)+max\{dp(i,j),dp(i+1,dp((j+1)mod2))\}$$

然后你发现你就秒了。记忆化搜索即可，比 C 简单吧。

糖丸指数达 200，不水乐。

写了 ABC260 E，看官方题解的，一看马上秒懂，orz。

wssb。

Day 8 / 20240902 ~ Day 12 / 20240906

先讲一点故事。其中【】不宜的内容，用【色，删】代替，自行领悟。

da_ke 准备和 public_sickle 面积。

众所周知，da_ke 的同桌是 lzx cp。

插叙：lzx 之前跟 da_ke 说过，说她有一个学弟，是 OIer，说 personality 非常像 da_ke。

插叙：cyh 跟 da_ke 说过，lzx 有一个小学 ng。

为下文做铺垫。

开端：

周一不引人注意，da_ke 去 709 问 fyy 谁无果。

周二不引人注意，同理。

发展：

事情在周三迅速发酵，因 da_ke 当 cyh 面给 public_sickle 写东西，引起注意。经多方商议、研究，确定路线，准备集体面积 public_sickle。同日，这件事被 lzx 知道了，因 da_ke 写信泄露到 lzx，悲。

cyh & lzx 每天都会传 QS（a letter to show love），周三 lzx 写的 QS 上有：

我 ng 就是 fyy （大意），他拉着【色，删】。

还有她的问题（以 lzx 的口吻，QS 原话）：

1. 我这个没学过 C艹 的能明白妳怎么认识 fyy 的吗？
2. 什么是一【色，删】多【色，删】？

我帮 cyh 在 QS 上写了问题 1。

高潮：

周四上午，cyh & da_ke & 两位好心的保卫员，前往 709 面积 public_sickle。

保卫员和 cyh 大胆的询问到 ps，而 da_ke 却因为设死躲起来。

public_sickle 好帅！

da_ke 说了几句话就 go die 了。

结局：

既是高潮又是结局。

回来后，我发癫了：

我喜欢妳傅元一！

Day 13 / 20240907

上午黄皮卷有一道题：

$\mathrm{△}BDP,\mathrm{△}CPE$ 和四边形 $ADPE$ 面积相等，求 $CP/DP$。

da_ke 向来不喜欢用正规方法解题。

对 $\mathrm{△}BDP,\mathrm{△}BAE$ 应用 共角比例定理，

$${\displaystyle \frac{BC\cdot BP}{BA\cdot BE}}={\displaystyle \frac{1}{2}}$$

同理：

$${\displaystyle \frac{CP\cdot CE}{CD\cdot AC}}={\displaystyle \frac{1}{2}}$$

对 $\mathrm{△}ADC$ 及截线 $BPE$ 应用梅涅劳斯定理，

$${\displaystyle \frac{AC}{CE}}\cdot {\displaystyle \frac{EP}{BP}}\cdot {\displaystyle \frac{BD}{AD}}=1$$

综合三式易得：

$${\displaystyle \frac{CP}{DP}}=3$$

就是这么简单。

这是无脑做法，正规做法是连接 $AP$ 设未知数，然后用类似于共边比例定理之类的也能得出结果。

但是思维难度大。

其实我做这种题的套路是：

1. 面积比 -> 线段比例
2. 比例 -> 截线比（应用梅涅劳斯定理）
3. 截线比 -> 面积比

按照这种套路你就无敌了。

OI：2023 S1 52 太菜。

无

Day 14 / 202409008

累。没人理解我。

wssb。

纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。

唉。成人机了。

21:00 才上。

乐子。

A ABC 265 E，简单到爆。

略。

调试代码的好处

发现和修复错误：调试是找出并修复代码中错误的关键步骤。通过调试，开发者可以逐步跟踪代码执行过程，定位问题的根本原因，并及时修复这些错误，确保代码的正确性和可靠性。

提高代码质量：调试有助于发现代码中的逻辑错误、潜在的错误或者代码不规范的地方。通过逐行调试代码，开发者可以更加深入地理解代码的运行机制和细节，以及找出代码中的问题并进行修正，从而提高代码质量。

加快开发速度：调试可以帮助开发者快速定位问题，减少排查错误的时间，从而提高开发速度。通过调试，开发者可以逐步分析代码执行过程，并逐步排除错误，减少调试时间，加快代码开发的进度。

增强开发技能：经过长时间的调试实践，开发者可以积累大量的经验和技巧。不仅可以提高开发者的调试能力，还可以提高他们解决问题的能力和创新能力。

怎么样，是不是心动了，快试试吧！

0 分求调！

发帖用的（乐子。

Day 15 / 20240909

无

Day 16 / 20240910

只讲一下发生的重大事件呃。

在最后一节课前，当 cyh 去音乐教室时，我偷翻他的 QS，而且边看边笑，最后实在绷不住了。

被发现了qwq，cyh 要我道歉。

但是要求我向 lzx 3 鞠躬，还要叫她 mother。我强把后面一条删了，他也同意。

放学我见到 lzx 非常设死，并很不情愿的【】，然后迅速逃跑。瞟一眼，lzx 诡异笑容真可怕（

Day 17 / 20240911

老胡发试卷故意拖延说废话和作业，害得 da_ke 和 cyh 直接犯癫痫，口念《临江仙·滚滚长江东逝水》，前面人以为我们要死了。结果试卷下确实死了。

老【】天天说要换座位，然后说今天必调（课后拖堂）。

老【】来过后，da_ke 非常【数据删除】，唱起了《送别》。

长亭外，古道边，芳草碧连天。晚风拂柳笛声残，夕阳山外山。天之涯，地之角，知交半零落。一壶浊酒尽余欢，今宵别梦寒。

感情深厚，虽然天天矛盾。但是没掉。

相信老【】调座位的就跟相信国足的一样。

崩。

Day 18 / 20240912

下午我和 cyh 一人一张中考卷（由好心的 cyh 提供，从万维里面撕），他青海，我兰州。TM！

巨，然后我做到几何突然半角公式忘了，当场十分尴尬，然而他非常快的做完了，毕竟是青海，没难度。

$\tan 2\alpha =(2\tan \alpha )/(1-{\tan }^2\alpha )$。

牢记。

遇到一点有趣的几何，用正弦定理边角转化即可，再加上三角恒，应该就杀了。

Day 19 / 20240914

无，记在明天。

Day 20 / 20240914

我眼神有点不好，没看见你们，sorry~

关于

非常帅

呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃………………………………………………………………………………………………………………

其实我都是睁一只眼闭一只眼，没逮任何人哦！

感谢！

下午没上课（喜）！

ABC 废了，ABD 一眼秒，唯独不知道 C 在说什么。上一丢丢分。

wssb。

我tm有邪恶微笑（（（（（））））））））））））））））

Day 21 / 20240915

做题将题目一般化得到了点旋转公式：

$$X=x\cos \theta -y\sin \theta ,Y=x\sin \theta +y\cos \theta$$

，很强。

ABC264F 非常好做的 DP，很经典，做了很多遍，我们用记忆化秒。

一遍过。

Day 22 / 20240916

大雨，台风，晕。昨天晚上聊到好晚。

历险记

这几天一直发现有：

「您的 Windows 内部版本将于 XXXX 过期……………………」

一查发现，这玩也叫做「时间弹炸」。

介绍：是 Windows 8 以后内部版本安全性组成，其内部版本过期后将隔 2 个小时重启电脑，时间间隔不断减小，直至电脑报废。

我慌得一批，赶快 $\mathtt{\text{bing}}$ fs + luogu 提问。便去重装系统，想着 2 h 后电脑就要报废了，quick！！！！！！！！！！！！

镜像慢的要死，慌死了~

但是看到一篇救命博客，删掉 $\mathtt{\text{System32/LicensingUI.exe}}$ 即可，立即行动，发现寄了。需要 TrustedInstaller 权限。

真是长知识了，将我删除的经验写一下：

• 属性-》安全高级-》更改权限，把 Users 改成完全控制即可。

哇！！！！！！！！！！！！！！！！！！！！！有惊无险！！！！！！！！！！！！！！！！！！！！！

足足耗了我 1.h 服了。

后来说也不会重启了，自从 Windows 11，想想微软还是挺野蛮的啊。

https://www.luogu.com.cn/training/601675#problems

https://www.luogu.com.cn/discuss/927871

乐子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <bits/stdc++.h>

#define i64 long long
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define fdn(i,r,l) for(int i=(r);i>=(l);i--)
#define pii pair<int,int>
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 i128;

ll f(string s)
{
    ll cnt=0,ans=0;
    for(auto i:s)
    {
        if(i=='X') cnt++;
        else ans+=cnt*(i-'0');
    }
    return ans;
}

bool cmp(string s1,string s2)
{
    return f(s1+s2)>f(s2+s1);
}

int main()
{
#ifndef ONLINE_JUDGE 
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n;
    cin>>n;
    vector<string> s(n);
    rep(i,0,n-1) cin>>s[i];
    sort(s.begin(),s.end(),cmp);
    string o="";
    for(auto& i:s) o+=i;
    cout<<f(o)<<endl;
}

乐子-》原：这份代码揭晓 Windows 和 Linux 有多大的区别。

然后发现我唐氏然后在 out.out 中间加了空格，警钟长鸣。

AC。

ABC275：

$$dp(i,j)=min\{dp(i-1,j-a_i),f(j)+1\}$$

$$f(j)=min\{k\in [1,i)|dp(k,j)\}$$

夜阑卧听风吹雨，【】。

风大，很吓人，但是我很快睡着了。

Day 23 / 20240917

一年一中秋，一家一平安，一心一思念，一人一祝福。中秋将至，祝福独一无二的你，事事顺心又如意，天天无忧又无虑。

https://www.luogu.com/paste/y19v3sta

您真的把自己当谁了？！

A 了 CSP J 2024 T4

Day 27 / 20240921

昨天水了犇，加油。

J 组 1h 写完了，不想看了。结果民间 80.5。

看到各位都是 90+，慌得 ybdz，发了不少贴，听 Fly_in_the_Wind 说了分母的事情就稍微放心点。

S 就是 sb，但我吧选择题认真做了，后面凭感觉，二分也稍微看看。觉得 45 分还是有的。

S 民间 46.5（加分，只会少不会多，即 $S>46.5$）。

珂爱的赵校长来陪考，我和 TA 走到楼下，我说这雕像是钟家庆先生？然后我说要不要 Orz。结果赵校长直接跪地给钟家庆先生 orz 3 下，我在旁边也膜拜了几下。

Day 20240928

我逐渐忘了是多少天了，也不需要知道了。

3年啊，似乎挺长，但现在却突然结束了...他几乎贯穿了过去三年的每一天，陪我过去了多少事情，回忆过往，不仅是OI，许多平常遇到的各种事情也随着时间线浮现出来...初学的好奇、期待、兴奋再到如今，过往的事情一瞬间挤满了我的脑海，如今却画上了句号。

https://www.luogu.com.cn/problem/list?type=AT&keyword=ABC&orderBy=pid&order=asc&page=43

从今日起 Github 的 lib/ATCoder 代码暂时停更，要代码直接去 AT 查。

Special Thanks

• @harmis_yz

• @Zelotz

• @baibaieee

• @Ravener

• @ran_qwq

• @枫原千叶

• @_A__

后记

本当の本当に終わり。

但是你看我像退役了吗？

CSP 2024 游记

CSP 4202 J/S 1

初赛巨难。但是应该能过吧。

答案：

1
2
3
4
5
6

J: AACCA BBDDB DDCCD
FFFCC/FTTABB/TTTABC
ABCDA BCDAB
S: DDBBD CCAAC AABBA
TTTAA/TTTBBB/TTFCCD
DACBD DBCAD

都过了。

CSP 4202 J/S 2

这是我 OI 生涯的最后一场比赛，甚至游记都写不了就得退役了，故在考场上写。

密码公布了是：$\mathtt{\text{Yi2Meng0Wei2Ma4}}$

上午 J 第一题很难，去看 T2。T2 是个线性 dp，对于我来说秒了。5 min 写好过了大样例。此时过去了 10 min。

回去看 T1，其实发现一些非常巧秒的东西。但只能得 70 pts。算了，去 T3。

T3 nortan 大模拟，叫我模拟某谷的积分功能，cao。直接宝马开干。

写了 1h，调了 30 min tm 终于搞完了。此时过去 2h。

T4 图论。竟然是个偏板子+暴力（？），不确定但写了。过了样例。

回看 T1，直接打了 70 pts。

估分：$70+100+100(?)+50$。

中午和 $\mathtt{\text{color{red}{public\_sickle}}}$ 打了一会三国杀。

S 密码：$\mathtt{\text{Bu4Fu2Shao0Hua2}}$

下午 S 更服。T1 类似于去年是思维题，虽然但是 0.5 h 终究想出来了部分分。

T2 算简单，但只会 40 pts。写完 T1 T2 过去 1h。

T3 大模拟，愤怒。爆肝了，调了很久，但过了样例，感觉会炸。因为样例强度太低。

T4 不可以总司令，希望可以通过 CCF 的脚造数据。

打完了还剩 30 min，我啥都不干了。因为这是我 OI 的最后 1800 秒。我检查 IO，并深度放松，尽情享受 OI 的最后 1800 s。

估分：$30+40+50(?)+10=130$

晚上看了解密。

出分了，但是退役了。

J：290，S: 120，都挂了。

祝我 Whk 顺利。正如密码所告诉我们的，以梦为马，不负韶华。

后记

你可能以为是真的了，实际上这是假的，也许比这个好，也许比这个惨，但这的的确确是我ＯＩ的最后一场比赛了。

写本文章的目的是，我赛后真的没有游记了，于是用一个假的冒充一下，证明一下我也曾是一名 OIer。

希望在役的各位 OIer 珍惜每一天。

题解：AT_abc367_d [ABC367D] Pedometer

前言

赛时被整懵了，赛后题解。

AtCoder Problem

更好的阅读体验？

翻译

注意：一定是顺时针走。

正文

记 $i,j$ 的距离为 $d(i,j)$

暴力的做法是，枚举 ${\displaystyle \frac{d(i,j)}{M}}$，二分查找满足条件的点。

显然过不了，其瓶颈在于倍数的枚举。

不妨破环，记数组 $a$ 为 $a_1,a_2,\dots ,a_{2N-1}$，且使用前缀和。

事实上，$d(i,j)\equiv 0(modM)$ 的充要条件是 $\sum _{k=1}^i{a}_k\equiv \sum _{k=1}^j{a}_k(modM)$。

故对所有前缀和对 $M$ 取模，若模相同，则满足题目要求。

但是考虑到一定是顺时针走，我们统计是只从前往后看的。换句话说就是，前面的只会看后面的，不会再往前看。这里的前后指的是下标的大小。

具体的，现有点 $i,j$。要从 $i$ 走到 $j$。

• 若 $i<j$，相当于判别 $\sum _{k=1}^i{a}_k$ 和 $\sum _{k=1}^j{a}_k$ 模相同。
• 若 $i>j$，相当于判别 $\sum _{k=1}^i{a}_k$ 和 $\sum _{k=1}^{j+N}{a}_k$ 模相同。

我们看到第 $i$ 个的时候只会向后看到第 $i+N-1$ 个。因为这样我们才能保证我们即是方向正确的，又是两点的最短路径。

代码实现，我们采用了桶装的方法，因为对 $M$ 取模的余数一定小于 $M$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)

using namespace std;
typedef long long ll;

const int N=2e5+23;
int n,m;
int a[2*N],sum[2*N];
unordered_map<int,int> cnt;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>n>>m;
    rep(i,1,n) cin>>sum[i],sum[i+n]=sum[i];
    rep(i,1,2*n) sum[i]+=sum[i-1],sum[i]%=m;
    rep(i,1,n) cnt[sum[i]]++;  
    ll ans=0;
    rep(i,1,n)
    {
        cnt[sum[i]]--; // 弃用
        ans+=cnt[sum[i]]; // 统计
        cnt[sum[i+n]]++; // 启用
    }
    cout<<ans;
}

AC 记录

总结

我觉得这个放在 D 虽然代码不长，但是有一定难度的。

参考资料：

• https://atcoder.jp/contests/abc367/submissions/56794653
• https://atcoder.jp/contests/abc367/editorial/10706

广告：安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。

题解：AT_abc366_c [ABC366C]

前言

题目已经翻译好了，故不提供翻译解释。

正解

需注意：编号为 $x$ 的球可以有很多个，赛场上因此痛吃罚时。

考虑到 $x\in [1,{10}^6]$，数据范围较小，故开一个桶：$s_x$ 记录 $x$ 出现的次数。

同时维护一个集合，记录目前还存在的球种类。考虑到我们只关心球种类的数量，故可将集合变为一个计数器。

代码很容易写出来。

时间复杂度 $O(Q)$，空间复杂度 $O(maxx)$。

加强版

但是如果 $1\le x\le {10}^{18}$，那 $x$ 肯定无法用桶去装了。这是因为数组一定是连续的，而事实证明根本不需要连续，因为很多数是没有出现过的。

但是 C++ 中的 STL 恰恰有这么一个非连续的数据结构 map。其使用方法与数组类似。

注意：map 在没有修改的键值对应值默认是 0，这里只举整数类型为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)

using namespace std;
typedef long long ll;
typedef double db;

int Q,cnt=0;
map<ll,ll> s;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>Q;
    while(Q--)
    {
        int o;ll x;
        cin>>o;
        if(o==1)
        {
            cin>>x;
            if(s[x]==0) cnt++;
            s[x]++;
        }
        if(o==2)
        {
            cin>>x;
            s[x]--;
            if(s[x]==0) cnt--;
        }
        if(o==3)
            cout<<cnt<<endl;
    }
}

时间复杂度为 $O(Q\log Q)$。因为 map 一次查询的复杂度是 $O(Q\log Q)$ 的，且最多有 $Q$ 个球会加入袋子。

空间复杂度 $O(Q)$，理由同上。

总结

这道题作为 C 还是很水的，而且不必用 STL。

AC：https://atcoder.jp/contests/abc366/submissions/56635007

广告

安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。