CSP-S

考虑矩形数量的规模大概是 \(O(n^4)\) 量级的，故很难通过枚举的方式直接做。 弱化问题，如果只统计正着的矩形，个数是 \(O(n^3)\) 量级的。而斜着的矩形都是可以被一个恰当的正矩形包含的，此时两者对应顶点距离相同，存在性可以由顶点位置取与判断。 即，我们可以将一个边长为 \(x\) 正 ......

注意到关键性质 \(a_i\) 是 \(a_{i+1}\) 的因数，故小决策在 \(\frac{b_j}{a_j}\) 更大时是严格优于大决策的，而 \(a_j\) 相同的决策之间显然只有 \(b_j\) 最大的有用，故最终至多只会保存 \(O(\log m)\) 个有决策。 对于倍数增量的东西一定 ......

快读快写 namespace Testify{ inline int read(){ int f(1),x(0); char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=get ......

因为自己实力菜，所以去年被卡线了，今年又回来考试了。 Day 1 今天一校区的就要来了。 大部分板子是打完了，感觉今天只需要练练 dfs 和随便看看数论应该就可以了。 今年反而没有去年的紧张了，反正自己已经没有拿 1= 的实力了，不如好好享受这个过程。 ......

Day -12 第一次打 Div.1！！！ 然后： （乐） Day -1 开坑，补之前发生的东西。 ......

显然函数之间的调用关系形成了一张拓扑图，预处理出函数 \(i\) 或其内部所有乘法之积 \(mul_i\)。 在调用一个加法函数后调用一个乘法函数，等价于先调用这个乘法函数，然后调用这个加法函数乘数次。所以不妨让乘法函数先做，剩下加法函数产生的贡献只取决于加数和调用次数。这里和线段树的懒标记优先顺序 ......

Day -4 早晨和积分哥、Ignotus 一起进的校门。 操场的篮球架被干碎了，玻璃碎了一地。 有一块子弹形状的碎玻璃，如果除了这块能拼成一个完整的玻璃就有意思了。🤔 摆了一上午。P1600 写了一个裸的启发式合并，结果本机 \(100000\) 的数据被卡到了 38s。 但是 \(300000 ......

CPS-S 大纲 2.2.1 基础知识与编程环境 【 5 】Linux 系统终端中常用的文件与目录操 作命令 【 5 】Linux 系统下常见文本编辑工具的使用 【 5 】g++、gcc 等编译器与相关编译选项 【 5 】在 Linux 系统终端中运行程序，使用 time 命令查看程序用时 【 5 ......

[CSP-S2019] 树的重心 因为这道题令我十分兴奋，所以来写一下做完后的思考。 这道题用到了树的重心的种种性质，在写解法的时候会一一点出其用处。 首先，枚举每一条边，然后各自 \(O(n)\) 扫一次的 \(O(n^2)\) 做法是简单的。 那么接下来，就会出现不同的解法了： 优化 \(O(n ......

[CSP-S 2022] 策略游戏 题目传送门 题目分析 本文中 A 和 B 分别代表小 L 和小 Q，而原题中的 $A$，$B$ 两个数组在本题中分别用 $a$ 和 $b$ 表示。 矩阵这个描述就是障眼法。翻译一下题目： A 在 $a[l_1 \cdots r_1]$ 中选择一个 $x$，然后 B ......

[CSP-S 2022] 假期计划 题目传送门 题目大意 给定一个 $n \leq 2500,m \leq 10000$ 的无向图，有点权。求一条点权和最大的路径 $1\to A\to B\to C\to D\to 1$，满足： $A,B,C,D$ 均不为 $1$，且互不相同； 每一段路径上经过的点 ......

Description 给定一棵树，树的每个节点都有一个左括号或者右括号，求从根节点到每个点简单路径上的括号序列上合法的子括号序列数。 Analysis 显然树形 dp。 考虑如何设计状态，定义 \(f_i\) 表示从 root 到 \(i\) 节点的字串合法数量。 考虑转移，如果当前的括号为左括号 ......

P7913 [CSP-S 2021] 廊桥分配 考虑对于国际航班和国内航班单独进行分配 对于国际航班 处理 \(res1[i]\) 数组作为给国际航班分配 \(i\) 个廊桥的最大飞机停靠数量 \(res2[i]\) 同理 对于每一种类的航班 我们维护一个 \(in\) 优先队列和一个 \(left ......

T1假期计划 [CSP-S 2022] 假期计划 题目描述 小熊的地图上有 \(n\) 个点，其中编号为 \(1\) 的是它的家、编号为 \(2, 3, \ldots, n\) 的都是景点。部分点对之间有双向直达的公交线路。如果点 \(x\) 与 \(z_1\)、\(z_1\) 与 \(z_2\)、 ......

给定正整数 \(n\) ，计算 \(n\) 个元素的集合 \(\{1,2,3,...,n\}\)，所有非空子集和的乘 积取模 \(998244353\) 后的结果 \(n \leq 200\) 我的第一思路是考虑能不能通过 \(i-1\) 个元素的情况推出 \(i\) 个元素的情况，然后寄掉了，遂看 ......

10月4日 CSP-S 模拟赛总结 2457 题目大意 给定一个长度为 \(n\) 的排列 \(A\)，问交换两数的位置，最多能使逆序对的数量减少多少 思路 50 pts（\(n^2\)） 开两个二维数组， f1[i][j] 表示 \(i\) 与 \(j\) 互换位置时对于 \(i\) 减少的逆序对 ......

题目链接 对于括号题，基本是栈匹配没有匹配的左括号和区间 \(dp\) 两个方向。这道题括号序列并不确定，只能用区间 \(dp\) 搞。 如果直接设 \(f_{l,r}\) 表示 \(l\sim r\) 的合法括号序列，那么由区间 \(dp\) 的套路可知，需要枚举中间点进行合并，那么 \(()() ......

part 1: 题目描述： 当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。 机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只 ......

2023 CSP-S 备战 日常犯智 9.29 Dinic 中，如果 rest 为 \(0\)，直接终止循环。 int dinic (int u, int flow) { if (u == T) return flow; int rest = flow; for (int i = now[u]; i ......

[CSP-S2020] 儒略日 题目描述 为了简便计算，天文学家们使用儒略日（Julian day）来表达时间。所谓儒略日，其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数，不满一天者用小数表达。若利用这一天文学历法，则每一个时刻都将被均匀的映射到数轴上，从而 ......

Day 1 上午 —— 基础算法 模拟 + 枚举 小前言 碰到题目不会做 -> 先写个模拟压压惊（） 枚举法 枚举的思想是不断地猜测，从所有可能的集合中一一尝试，然后再判断是否符合题目的条件。 单独提到枚举时我们往往认为这是一个暴力做法，但事实上并非如此，恰当的枚举往往会是解题的关键步骤。 例题 1 ......

P7075 [CSP-S2020] 儒略日 1.题目描述 为了简便计算，天文学家们使用儒略日（Julian day）来表达时间。所谓儒略日，其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数，不满一天者用小数表达。若利用这一天文学历法，则每一个时刻都将被均匀的映 ......

暴力枚举 枚举国内和国外的廊桥数量配额，再模拟航班停机过程 #include <cstdio> #include <algorithm> using namespace std; const int N = 100005; struct Flight { int l, r; // l 抵达时刻，r ......

P5659 [CSP-S2019] 树上的数 前言 被队友（大爹）易giegie要求做这道题，一天一夜绞尽脑汁终于写出来了。（下了样例test1调试） 然后被要求写博客 虽然我觉得没啥用，但是写一下吧 一些说明 1.把数在删边时交换的过程看做移动，停留过的点和相关的边认为是经过这些点和边 2.把一条 ......

从小猴编程公众上发现的题单，本人抄到洛谷上，供大家参考。 【小猴】CSP-S 2023 真题题单 - 简单篇: https://www.luogu.com.cn/training/383609 【小猴】CSP-S 2023 真题题单 - 基础篇: https://www.luogu.com.cn/t ......

4173: 车牌 (plate) 题目内容 小 \(Y\) 毕业之后来到了车管所工作，他现在掌管着下北泽全市的车牌分配。具体的说，下北泽的车牌是一个长度为 \(5\) 的字符串，字符串的每个字符是一个 \(0−9\) 的数字或者一个 \(A−Z\) 的大写字母。为了避免混淆，每种字符串的车牌最多只能 ......

蒟蒻的第一次 CSP & 第一篇游记。 同时应该也是最后一次 CSP。 第一轮 Day 998244350 下载准考证。 Day 0 (2023.9.16) 和学校请了一天的假，成功错过三门考试。血赚.jpg 上午看了看 CSP 初赛复习，写了喵了个喵，但没调完。 在谷上看到 CSP-J 出锅，希望 ......

高中 OI 生涯开端。 9.16 初赛 小图灵估分 81.5，比去年稍微低一点，不过过初赛应该是没问题了。 2B 铅笔坏了导致耽误了一些时间，最后没有充足的时间去检查，还把一道原本选对的题改错了/kk，以及一道题看反了，还有零零碎碎的小错误，导致了这个分数。 不过再怎么说也应该是过初赛了，希望复赛能 ......

P7916 [CSP-S 2021] 交通规划 sol Statement 传送门 Solution 好题。 发现 \(k\le 2\) 的分值非常多，于是我们考虑从 \(k=2\) 入手。 颜色相同就不用说了，直接染成同一种颜色就行了。 我们考虑其他情况， 就是颜色不相同的情况，我们一定是找了一条 ......

#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long LL; const int N = 2505; vector<int> G ......