Luogu P1495 题解 思路 首先看一下题目,可以理解为求解下面的方程: \[ \left\{ \begin{array}{c} x \equiv b_1 \pmod {a_1} \\ x \equiv b_2 \pmod {a_2} \\ \cdots \\ x \equiv b_n \pmod {a_n} \\ \end{array} \right. \] 很显然可以用中国剩余定理求解,下面讲一下具体过程。 求出 2024-04-29 #题解 #洛谷
2024 成都七中多校联训游记 Day 0 早上 6:00 准时起床,跑到番禺校区门口。看到我们的公务车,感觉很高级。 IMG_0834(20240329-202147) 结果我们五个学生在车上等 lily 一个人,相当抽象啊。 到了机场先和番禺的人一起办了值机,然后越秀的说刚出发蚌埠住了。等啊等,看了 \(20 \rm min\) 的 B 站,感觉他们可能还要很久。准备启动,然后刚进游戏,他们来了!!!受不了一点。 2024-04-10 #游记 #成都七中 #多校联训
2024 成都七中多校联训内容 前言 这是较为完整的训练内容,当然有若干场训练并没有整理出题单,而是写在了 PPT 里面,懒了,不搬了。其次有一场讲评的录屏是不完整的,这个要怪讲评人。 比赛 题目原题均在 ACCoders,被 CodingCow 搬到了 OiClass(有些没搬),题面可能略有修改,数据并非原数据,是重新造的。 2024 多校集训 C 层 - 冲刺 NOIP 模拟 1 题目 P9006 操作 P9007 染色 2024-04-10 #成都七中 #多校联训
算法详解 - 素数 定义 素数,又被称为质数。我们一般定义质数为除了 \(1\) 和自身之外没有其他因数的数,特别的 $1 $ 不是质数。 判断 试除法 我们考虑如何判断质数,一种很显然的思路就是枚举这个数的因数。假设这个数是 \(x\),则我们可以枚举 \([2,\,\sqrt{x}]\) 之间的整数,判断是否可以整除,如果没有找到一个可以整除的数,那么可以认为这是一个质数。时间复杂度是 \(O(\sqrt{x}) 2024-04-09 #算法详解 #素数 #质数
算法详解 - 重链剖分 简介 重链剖分,也被称为树链剖分,一般的,OIer 口中的树链剖分就是指重链剖分。今天我们就来一起学习重链剖分。 概念 重儿子 既然是重链剖分,那么我们就要理解什么是重。我们定义一个点的子节点中子树最大的点为这个点的重儿子。我们可以通过下面的一个例子来理解: 其中,节点 \(1\) 的子节点有三个,分别是 \(3,\,5,\,6\),它们的子树大小分别是 \(4,\,1,\,2\),于是我们按照 2024-04-08 #算法详解 #重链剖分
算法详解 - 自适应辛普森法 前置知识 我们可以看道一个奇怪的式子: \[ \int^R_L f(x)\, \textrm{d}x \] 究竟是什么意思呢?其实就是求函数 \(f(x)\) 在 \(L\) 到 \(R\) 之间的定值积分。在讲求值之前,要先讲一下映射、函数和积分。 映射 再讲函数之前,先要讲一讲映射。首先我们考虑有两个非空集合 \(X\) 和 \(Y\),如果存在一种法则 \(f\),使得 \(X\) 中的每 2024-04-02 #算法详解 #自适应辛普森法
OiClass P2688 简单计算题解 思路 我们简单导一下柿子: \[ \begin{align*} \sum_{i=0}^{p} \left\lfloor\frac{iq}{p}\right\rfloor &= \left\lfloor\frac{0q}{p}\right\rfloor + \left\lfloor\frac{1q}{p}\right\rfloor + \cdots + \left\lfloor\frac{p 2024-03-19 #题解 #OiClass
TYOI 省选集训 and 2024 GD 省选游记 集训 Day -INF 知道可以来集训,感觉特别开心,因为可以合法逃学两周! Day -3 \(\sim\) Day 0 大年初五就从潮州回到广州,收拾了一下东西,年初七大家就到了学校。 很好,又和高中生一起住,不过这次我们来得很早,所以高二还没有开学。一开始宿舍里面只有我、includeCPP、jr_linys 三个人。所以 includeCPP 非常放纵。 Day 1 \(\sim\) Day 2024-03-01 #游记 #TYOI #省选
CF1244C 题解 思路 我们看到题目,给定四个数 \(n\)、\(p\)、\(w\)、\(d\),求解三元一次不定方程组: \[ \left\{ \begin{array}{l} x\cdot w+y\cdot d=p\\ x+y+z=n \end{array} \right. \] 观察一下你就会发现 \(z\) 的值是你可以随便指定的,因为他只对 \(n\) 产生影响,而不对方程一产生任何贡献。于是我们忽略 \ 2024-02-28 #题解 #CodeForces
AT_abc255_e 题解 思路 朴素做法 首先我们考虑一定可以有一个点是幸运数,于是我们可以考虑遍历每一个 \(S_i\),钦定 \(a_i\) 是一个幸运数,然后我们就可以反推出 \(a_1\) 的值。然后我们统计 \(a_1\) 重复被计算出的次数。因为只要有一个 \(a_i\) 被确定了,整个序列就确定了。也就是说,\(a_1\) 的重复次数就是我们要求的最多的幸运数个数,因为他们都是同一个序列。如果我们这样做,时间 2024-02-28 #题解 #AtCoder
OiClass 2024 CSP-J 公益赛 #4 题解 引言 这场比赛出题人认为是 \(\approx\) CSP-J + 的难度,预估的平均分在 \(200\) 分左右。比赛的命题思路简单来说就是第一题水题但是考虑在题面里面写很多抽象的东西混淆视听;第二题有些思路的结论题,如果猜出了结论复杂度应该还是非常优秀的;第三题是本场比赛最难的题,算法本身并不难,但是这个思路上有一个优化很难想,这就给很多选手做题带来了很大的困扰,可能无人 AC;第四题是原题加 2024-02-28 #题解 #OiClass #公益赛
THUWC 2024 游记 Day -INF 大喜,第一年打比赛就直通 THUWC 了,开心到飞起。 Day -7 开始寒假集训前一天,发现重庆天气很冷,极限跑去优衣库不看价格买了一件羽绒服。付款的时候 699 真的蚌埠住了,还好 Mate 60 Pro 专属卡返现了几十块,小回了一波血。 Day -6 \(\sim\) -1 在番禺校区集训,学了一堆树上的算法,感觉很懵。集训还没结束就走了。 Day 0 启程 由于住番禺郊 2024-02-28 #游记 #THU
OiClass 公益赛宣传 OiClass 公益赛宣传 活动意义 为了增强 oiClass 社区活跃度,提升 oiClass 用户的 oi 水平,促进 oier 之间的联结互动,特别开展本公益活动,希望大家踊跃参加。 oier 水平的提升,不仅在学,更在练,多打比赛无疑是提升水平的有效渠道。 本次活动由 TYOI 高水平选手进行命题和验题,由 chxulong 把控题目质量,题目难度控制在 CSP-J 水平,对于冲刺本年 2024-02-25 #OiClass #宣传 #公益赛
CF1368E Ski Accidents 题解 思路 首先我们看到题中给出,这个图是一个 DAG,因此很容易的就可以想到拓扑排序。那么我们在思考一下,如何满足题目中给出的删除的点不超过 \(\frac{4}{7}n\) 的要求。我们可以举一个例子,看到下面的二叉树: 如果我们按照拓扑排序遍历,每次遍历到深度对 \(3\) 取模为 \(0\) 的节点,就删除。那么很显然,这个策略可以正常的分割出符合条件的链。同时,对于这个具有 \(7\) 个节 2024-02-23 #题解 #CodeForces
洛谷 P10170 [DTCPC 2024] 小方和小立方 题解 思路 一眼看上去,这题非常非常的难,对吧???好吧,我的第一反应就是 DP,但是 DP 似乎并不能非常优雅的解决问题。然后我就想到了马拉车,但是马拉车+特判实现起来实在是有些繁琐。 突然,我猛地发现,如果每个字母的出现次数不超过 \(2\) 次的话,回文串的长度最多就是 \(52\)。也就是说,暴力的时间大约是 \(O(52n)\),很显然,这是可以非常轻松通过的。那么我们只需要枚举回文串的中心, 2024-02-17 #题解 #洛谷
洛谷 P10160 [DTCPC 2024] Ultra 题解 题意 给定一个01串,可以将串中的 1010101...010101 替换为 0101010...101010 反之亦然。求可能的最小的 1 的数量。 思路 我们可以发现,如果有连续的多个(\(\geq2\))\(0\),那么我们不可能将连续 \(0\) 左侧或右侧的一起处理。因此,为了方便,我们可以将左右两侧分开处理。当我们将左右两侧分到无法再分的程度时,我们再次观察。 容易发现,去除两侧的前导 2024-02-17 #题解 #洛谷
Oiclass PU2TI P3791 棋子题解 思维 我们可以优先考虑以下的三情况: 1 2 3 此时我们会发现 1 和 2 挡住了 3 ,那么此时 1 和 2 必然将先死一个。 1 3 5 此时我们会发现所有棋子都可以先死,因此方案数为棋子数的全排列数,即其阶乘。 1 2 4 此时 1 和 2 挡住了 4 ,只要 1 或 2 先死一个,那么后面的就可以按照方案二的情况来计算。 因此我们可以考虑维护一个像方案二一样的 1 3 5 7 9 . 2023-12-16 #题解 #OiClass
CF985C 题解 建议升绿 这道题是一道贪心。很容易想到,我们你需要先进行一次排序,然后再进行一些操作。 首先我们可以排除无解的情况,当第 \(n\) 短的木板的长度与最短的木板的长度之差 \(> l\) 时,不可能有任何一种符合题意的方案。这个很好证,有兴趣的朋友可以自己证一下。 然后我们考虑如何制定一个合理的贪心计划。首先我们可以尝试确定一个最大的桶大小,这对后面的操作有很大的帮助。很显然,最大的桶大小就 2023-12-15 #题解 #CodeForces
Oiclass PU2TI P3846 杨辉三角题解 打表+卡常题 思路 不难发现,最短路径不外乎以下两种可能: image-20231216150315312 一种是先一直向下,再一直向右下;而另一种是先一直右下再一直向下。对于 \(k \leq \frac{n}{2}\) 的请况,很显然是选择第一种路线,否则是第二种路线。 我们可以通过一个简单的技巧来将两种路线合一,我们可以发现,其实第二种情况相当于第一种情况中将 \(k\) 改为 \(n 2023-12-12 #题解 #OiClass
CSP 2023 游记 终于想起来 好吧,鸽了怎么久,还是要来写一下的 初赛 赛时 初赛那天上午,我很早就到了广大附。走进去之后,发现一个 TYOIer 都没有,然后就在门口等队友。吹着上午凛冽的秋风,等啊等,发现他们怎么一直不来啊啊啊啊啊。等到离可以进考场还有 \(5\) 分钟的时候,我就自己走进去了,孤独,又无助。 后来等到考试快要开始,我们的其他队员才陆陆续续地到,听说是因为堵车了(笑死)。 对于早上入门组的初赛, 2023-12-05 #游记 #CSP