CSP-S 2025

咋这么快就 csp 了。

10-26

加训！

让 deepseek 给我生成了一个看起来可以使用的 self-eval 状物。

# test.ps1 - 单个题目的测试脚本
param(
    [string]$ProblemName = "problem1",
    [string]$SourceFile = "main.cpp",
    [string]$TestCasesDir = "test_cases"
)

Write-Host "正在测试题目: $ProblemName" -ForegroundColor Green

# 编译源代码
Write-Host "编译 $SourceFile ..." -ForegroundColor Yellow
$executable = "$ProblemName.exe"
g++ -O2 -std=c++14 -Wall -o $executable $SourceFile

if ($LASTEXITCODE -ne 0) {
    Write-Host "编译失败!" -ForegroundColor Red
    exit 1
}

Write-Host "编译成功!" -ForegroundColor Green

# 运行测试用例
$testCases = Get-ChildItem "$TestCasesDir/$ProblemName" -Filter "*.in"
$passed = 0
$total = $testCases.Count

foreach ($testCase in $testCases) {
    $inputFile = $testCase.FullName
    $outputFile = $inputFile -replace '\.in$', '.out'
    $myOutput = "temp_output.txt"
    $testName = $testCase.BaseName
    
    Write-Host "测试 $testName ..." -NoNewline
    
    # 运行程序并计时
    $sw = [System.Diagnostics.Stopwatch]::StartNew()
    Get-Content $inputFile | .\$executable > $myOutput
    $sw.Stop()
    
    # 比较输出
    $expected = Get-Content $outputFile
    $actual = Get-Content $myOutput
    
    if ($expected -eq $actual) {
        Write-Host " 通过! " -NoNewline -ForegroundColor Green
        Write-Host "($($sw.ElapsedMilliseconds)ms)" -ForegroundColor Gray
        $passed++
    } else {
        Write-Host " 失败! " -NoNewline -ForegroundColor Red
        Write-Host "($($sw.ElapsedMilliseconds)ms)" -ForegroundColor Gray
        Write-Host "期望输出:" -ForegroundColor Yellow
        $expected
        Write-Host "实际输出:" -ForegroundColor Yellow
        $actual
    }
    
    Remove-Item $myOutput -ErrorAction SilentlyContinue
}

Write-Host "`n测试结果: $passed/$total 通过" -ForegroundColor $(if ($passed -eq $total) { "Green" } else { "Red" })

# 清理
Remove-Item $executable -ErrorAction SilentlyContinue

upd:
自己写了个像个人样的。

param($id)

$name = "mst"

$cpp = $name + ".cpp"
$exe = $name + ".exe"

g++-15 $cpp -o "$exe" -std=c++14

Write-Host "Compile finsihed"

if ($?) {
    $in = ".\" + $name + $id + ".in"
    $out = ".\" + $name + $id + ".out"
    $ans = ".\" + $name + $id + ".ans"

    (Get-Content $in) | &.\$exe > $out

    if ($?) {
        if ((Get-Content $out) -ne (Get-Content $ans)) {
            Write-Host "WA on "$id -ForegroundColor Red
        } else {
            Write-Host "AC" -ForegroundColor Green
        }
    }
}

打了 MX-S8，好多分！

100 + 90 + 0 + 25

虽然我也不知道为啥 T2 不是只有 70pts。

AI hints 提示词，太强大。

这是一道信息学竞赛中题目以及其题解：

---------- 题目内容开始 ----------
题面
---------- 题面内容结束 ----------

---------- 第 xxx 篇题解开始 ----------
题解内容
---------- 第 xxx 篇题解结束 ----------
        
现在请你根据上述内容，将题解内容概括成 5 个思维难度层层递进的步骤，然后整理成提示，以引导做题人一步步想到题目正确的解法。

要求：
1. 提示的程度从浅到深。
2. 提示的内容不能过度简单或平凡，例如题意的复述无需写在提示内。可以是题目中的某个关键性质或是需要使用某算法的思路等。
3. 前三条提示思路，后两条直接给出正解做法。
4. 提示可以较为详细，字数控制在 50 字内即可。
5. 关键要求：输出格式必须满足一行一个提示，格式为 “提示xxx：xxx”，每个提示只占单独一行，两两提示间由一个空行隔开。不需要多余的内容。

10-27

萌熊模拟赛。

咋坠机了。

想了一场都不会 T2。

实际上场上是考察性质的时候只考察了区间的子集和超集的性质，没有发现他的长度也有说法。

10-28

组合对象和组合结构

记录一点常见的组合对象和组合结构的考察方法。

集合

子集
超集
补集
大小

排列

线头 dp
置换环

区间

弱于集合。

嵌套集和子树
长度
画到平面上！

最值

笛卡尔树

从小到大加入
运算存在单调性
维护位置

单调栈。

连续段

连通
求和

mex

运算存在单调性
连续段

逆序对

判定性

基于已知序列。

二维偏序。

构造性

单调加入。

数颜色

维护前驱后继。

完全图

归纳
平均

算法思想

独立性

分别计算。

拆贡献

这和交换求和顺序 / 反演之类的是一类技巧。

下标 - 值域转换

值域数据结构。

把询问挂在值域上。

最优化 - 判定转换

有单调性的时候二分。

没单调性的时候可以尝试构造单调性，如答案恰好为不能做但是答案是否能不小于使可做的。

判定 - 计数转换

水 u 群遇到的鬼技巧。

原集 - 补集转换

容斥。

代表元

代表元 / 支配对 / 最小表示法。

很多东西是没有用的。

操作的复合/取逆

更清楚的考察操作的性质。

必要性探路

破题。

充分性假设

假装能做。

注意及时回头。

复杂度均摊

所有连通块的
颜色段均摊。每个颜色被处理一次后将立即被删除。
求 border 时的势能分析

不等式方法

放缩组合对象的某项性质。

个数和为，
dsu on tree
，则最大使中，这被称为值域倍增。
小清新线段树
seg-beats

复杂度平衡

其实也可以是认为是一种不等式方法。只是这里研究的是复杂度何时取最小值。

根号分治
Meet in the Middle

离线

枚举

从紧到松处理限制

考察答案的形态

11-03

求求你了给我个省一吧/ll/ll

11-08

求求你了给我个懒狗吧/ll/ll

CF2156 (div 2)

CF2155 (div 2)

CF2156C

考虑整除关系时在模意义下考虑会更容易。

CF2160D CF2156D

做交互的时候考虑通过先前获取过的信息是否还有用。有些时候先前获取的信息可以刻画当前的状态。

CF2155D CF2156C

鸽巢原理。组合极值思想。考虑不等关系的放缩。考虑取等条件等。

CF2155F

有些难以的题可以开始想根号相关的做法或者之类的做法。根号和根号可能可以拼在一起，造出这种神秘复杂度。

考虑均摊。考虑势能。

CF2136B

密集区间限制考虑相邻项做差引出的单点的性质。

CF2155B

出度入度都为的结构被称为置换环。出度为的结构是内向基环森林。

考虑贡献。当然这好像在本质困难（原问题和对偶问题都足够困难）的时候并没有什么用。换角度统计实际上是一种对偶思想。

排列几乎可以认为是本质困难的。因为排列的逆排列还是排列😭😭😭。

很多神秘问题的本质都是构造。构造一种能够刻画局面的状态。构造一种取等条件。构造一种交互方法。构造两种恰好能平衡的算法。

11-09

加训！

CF2146 (div 2)

CF2146E

考虑 mex 的两种刻画方式：

出现的数在值域上的连续段
未出现数中的最小值

CF2146D2

神秘位运算

还有更深刻的结论

CF2155F

有个集合满足，查询交集大小。

可以根号分治。原因是可以通过标记元素是否出现来做到的单次询问复杂度。

对于较大的集合，标记将能够重复利用。因而挂在该集合上的查询的总复杂度由变为，也就是。

CF2146E

最优化问题中考虑弱化条件，即把一些不优的情况也放到决策集合里。这样可能会使得决策集合更容易维护。

最优类统计问题上实际上有两种本质不同的限制：「最优」和「条件」。弱化条件相当于是注意到两种限制存在重复，于是考虑更松的不优条件可能更容易处理。

11-10

加训。

CF2136

CF2136D CF2130D

绝对值可以拆开成最值（这也许是曼哈顿距离转切比雪夫距离）。

考虑最值的逻辑限制与等价。

CF2146D2

考虑规约子问题。考虑分治。

考虑无穷递降思想 / 归纳思想。

CF2136E

考虑边双相关相关性质时先考虑环。

考虑树相关的性质时先考虑链和菊花。因为树可以认为是这两种结构的组合。

CF2155C CF2151D CF2130B CF2136B

一步就充要的刻画问题通常是困难的。优先考虑一些必要性的剪枝。相当于挖掘了「合法情况」的一些性质。

定长区间 / 任意区间的相关性质考虑偏移后在端点处的性质。

考虑代表元。图上拉出一个生成树来考虑。考虑极大 / 极小值。

CF2133D ABC285E

进行「构造性决策」，先考虑结果的形式，获得性质之后再做。

这种思考方式的本质似乎是不过早考虑最优化剪枝，优先考虑对于特定的结果局面，如何算权值。因为在对问题没有深入研究的时候，我们也许不知道到底最优的答案长什么样。

11-11

CF 上分了。

总算摆脱了 pupil 的身份。

但是其实 specialist 也挺唐的。

构造。尝试构造能取到的上界。

CF2163D2

排列的 mex 是骗人的。区间 mex 等价于两边的 min，因为每个数恰好出现一次。

CF2163B

考虑特殊元素。如最小值 / 最大值 / 0 之类在某个方向的边界值。

CF2153D CF2163D2

考虑将操作视作运算。

考虑运算的单调性。min / max / mex / gcd / bitor 等操作都具有单调性。

考虑运算的结合律。考察两种操作是如何复合在一起的。

CF2153B

将等号拆成和同时满足。

找到尽可能满足一边的条件同时构造性的令另一边尽可能容易满足。

这实际上是在寻找某种必要条件。可以认为是必要性剪枝。

CF2151B

增量构建。考虑如何快速应对一些比较容易的修改。

11-12

还是，太菜了。

jiangly 怎么 10min 就写完了我晚上 2h 的东西😭。

感觉我还是思维速度有些慢，同时码速也太慢，写东西时总是在一些神秘地方犹豫。

加训。

CF2154D

>w< 不是这个猫真的太可爱了。

绝大多数题目都是在特定的限制下考虑问题的。考虑快速判定确定的局面能否满足限制。

CF2154C2

定序。对于无序二元组或元组，寻找合适的处理顺序。这是在限制允许的空间内加强了条件，可能会增添新的性质。

CF2160E

在的网格中，显然是线性的。但是很多时候也是可以通过根号分治来变成可以接受的。

11-13

咋生病了。

😷

这么不牛。

贪心调整的时候考虑「等价调整」和「优化调整」。应当在当前元素调整到上界时候，考虑后效性。

实际上在做题过程中经常会令人感觉有些困难的正是考虑后效性。因为考虑必要性剪枝/最优性剪枝，所谓的「决策」的过程实际上是假的。

具体地，在贪心做出决策的时候，以贡献为第一关键字，以能让之后贡献尽可能大为第二关键字，是正确的。

11-14

我咋还没好。

能打 cf 吗 /kel。

会赢吗 /kel。

冒泡排序交换次数下界为逆序对数。

只要存在逆序对就一定存在相邻逆序对。

相邻两项交换能够恰好减少一个相邻逆序对。

11-15

考察关键性质。设计状态等价类。有时候我们并不关心具体细节。

拉出一棵生成树 / 拉出一个直径来考虑树上问题。

链等价于直径长度为

11-18

咕咕咕

发现了深刻的结论！

若干变量之间的偏序关系只要能够构成 dag，则一定存在满足的这些偏序关系的排列。

构造性地，按拓扑序从大到小分配权值。

优先考虑合法解的判定。

11-20

P5665 [CSP-S 2019] 划分

考虑最优的转移一定是把每一段划的越小越好。因而一定取最大的可以转移的。

单调队列维护即可。

11-22

T3 关键性质，使变化的某个题目之多只会使变化一次。

11-23

T2 关键性质，基环树的构造强于环。任意基环树的构造可以直接映射到环上。

T3 关键性质，考虑跳的代价，仅与终点有关。因而若决定使用代价为的跳后，一定是最先使用恰好一次这样的跳。

Rainbow-Automaton's blog