THUPC

《南开大学数分I月考III在初赛开始四十分钟时结束》 早晨试图速成泰勒展开失败了 考试前 zsy 把 yzf 接到学校了，应该是国赛后第一次见 yzf 考完试发现 yzf 已经买好 KFC 了/bx，但因此迷路了。。。正好三人都少打 1h 分头签到，我开到《转化》了，真不喜欢这题但只能硬着头皮写，W ......

洛谷 P9970 [THUPC 2024 初赛] 套娃 根据 CF1870E 的 结论，\(\text{mex}\) 真正“有效”的区间只有 \(\mathcal{O}(n)\) 个。 ......

题面 定义一个集合的 \(\operatorname{mex}\) 是最小的不在 \(S\) 中的非负整数。给定一个序列 \(a_1,\dots,a_n\)，对于每个 \(1\leq k\leq n\)，我们按照如下方式定义 \(b_k\)： 对于 \(a\) 的所有长为 \(k\) 的子区间，求出 ......

题目大意 你需要对每一个长度的区间，求出以他为长度的区间的 \(mex\) 构成集合的 \(mex\) \(n\le10^5\) 大致思路 有一个神奇的结论：对于点 \((l,r)\) 为 \(mex_{l,r}\) 的矩形，其中按颜色分割得到的矩形数是 \(O(n)\) 级别的 证明&实现：我们考 ......

难度极低。显然，句子开头是You are right, but即为人工智能。 #include <iostream> #include <string> #include <cstdio> namespace io{ template <typename T> inline void read(T& ......

B. 一棵树 首先有个暴力 dp，设 \(f_{i,j}\) 表示在 \(i\) 子树内选了 \(j\) 个的最小值，转移是平凡的。 然后发现这玩意是凸的，于是可以直接上 slope trick。 但是涉及到合并两个序列，直接平衡树启发式合并是 \(O(n\log ^2n)\) 的。但是你会发现，我 ......

注意到，\(x_i\) 取 \(k\) 的概率是 \(p(1-p)^{k-1}\)，是和为 \(1\) 的等比数列，下面考察数列前缀和的性质。 不难想到，概率每次乘以 \(1-p\) 像是概率的分步乘法，每一步正是加一的操作。于是可以得到如下转化：初始时 \(S=0\)，每一时刻 \(S\) 先增加 ......

注意到，\(x_i\) 取 \(k\) 的概率是 \(p(1-p)^{k-1}\)，是和为 \(1\) 的等比数列，下面考察数列前缀和的性质。 不难想到，概率每次乘以 \(1-p\) 像是概率的分步乘法，每一步正是加一的操作。于是可以得到如下转化：初始时 \(S=0\)，每一时刻 \(S\) 先增加 ......

我们队赛时被 J 题创死了 awa 离做出来差一个剪枝，而且赛后试了试不加剪枝甚至能过…… 6 题离场。 一些题解 J 套娃 先对 \([0,n]\) 中每个数 \(k\) 分别考虑。 假设总共出现了 \(c\) 次 \(k\)，第 \(i\) 次出现的位置是 \(pos_{i}\)，（令 \(po ......

【THUPC 2024 初赛】 转化 我都能做出来，那就是大水题了。 思路 首先我们要确定最大可以变色的球的数量 \(tot\)。 有如下两个贪心步骤： 所有颜色使用分裂操作，并更新 \(a_i\)。 ​ 此时的有 \(tot=\sum_{i=1}^n \min(a_i,b_i)\)（需要更新 \( ......

鸣谢 cinccout。赛时两次看出了我的错误/bx。 闲话：在我看过的所有人的做题过程中，大家都不约而同的把 棋子数量相同时答案相同 当作了第一发（。但是很可惜，这个结论是错误的。 样例已经给出了当棋子数量为 \(2\) 的答案，在此我们略去讨论。 对于棋子数量为 \(1\) 答案也很明显是后手必 ......

赛时队友把这题丢给我说他们去写 B，然后我成功成为了战犯。 首先考虑一个朴素的暴力，建出一个类似线段树的结构。然后每次合并两个儿子节点，操作次数为 $n\log n$，大约需要 1e7 次操作，不能通过。 这时候有一个思路，如果一个区间里的东西比较满，就会让它很慢。但是如果区间比较满，那么重复位置的 ......

2023.12.11 今天报名了 \(\text{THUPC}\)，想玩一下，也没想打出什么结果。 和同学组了个队。 2023.12.17 \(11\) 点到学校机房。 我过 \(M\)。 lzy 到机房了。 我过 \(C\)。 zwz 会 \(E\)，zwz 写 \(E\)，挂挂挂，调调调。 lz ......

前言 THUPC 2023，Dinshey 交拧螺丝一题，罚时 20 发以上。 Dinshey：我保证不拧螺丝。 我：我保证拧螺丝。 回顾 F 从 12 点调到 15 点。TLE 爆了。 反思 时间流逝之快，我真的就过不去了吗？ ......

队伍组成： \(\text J\color{red}{\text{ijidawang}}\)，负责切题； \(\text K \color{red}{\text{8He}}\)，负责切题； \(\color{#008000}{\text{x383494}}\)，负责拖后腿。 Day -1 之前组的一 ......

大约是进复赛了，那就写个游记吧。 队伍名：福州一树开车大队。 队伍组成：CTT Day3 49.64 分选手，noip 260 分的候选队，NOI2022 E 类铁牌获得者。 2023.12.17（初赛） 原定策略是我做模 3 余 0 的题，lzq 做模 3 余 1 的题，lhr 做模 3 余 2 ......

「比赛游记」THUPC2024 初赛游记 路上小心 ずっと探してた　捧げた心臓の在処 （我一直在寻找着 曾献出的心脏如今何在） 本当の想いを教えて　夢物語でいいから （告诉我你真实的想法吧 纵使如梦话般缥缈） 最後になにがしたい？どこに行きたい？ （在这最后一刻你还想要做什么？你还想去向何方？） わ ......

算法竞赛打 THUPC，就像，只能度过一个相对失败的人生。 本来周末理综考得稀烂就急，这下打完 THUPC 就更急了。 不知道啥时候我们队就凑齐了，然后不知道啥时候就直接要比赛了。 本来分的是 ljc 先开 ABCD，我开 EFGH，lty 开 IJKLM。 结果开场一个“M 是签到，但是我不会”给 ......

洛谷传送门 LOJ 传送门 QOJ 传送门 复读官方题解。 考虑除了原图的 \(2^k\) 个点，再建一些辅助点，\((u, i, j)\) 表示前 \(i\) 位中修改了 \(j\) 位得到 \(u\)。那么除了原图的 \(m\) 条边，我们还有下面这些边： \(u \xrightarrow{0} ......

队友 ： fft(kxwenorz)，zi_gao 初赛 Day -7 组队成功，队里面两个大佬。一位是 NOIP 300 可惜没打现场赛的大佬 fft；一位是身体虽然变小，头脑依然灵光的 zi_gao小朋友。 还有一个混子，看名字就知道是菜狗，就是我 Imcaigou 哒。 THUPC 组队成功， ......

P5451 [THUPC2018] 密码学第三次小作业 题解 已知 \((e_1, e_2) = 1\)。 \[\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix} \]现在，已知 \(c_1\) ，\(c_2\)，\(e_ ......

Day \(\text{M}_r(\text{O}_2)\)。 这东西原来叫减半报警器？？ 首先这题肯定和数论没啥关系，因为 \(10^5\) 之内的 \(\max \omega(n)=6\)，即一个数至多只有 \(6\) 个质因子。 然后我们发现如果 \(x\) 有 \(k\) 个不同的质因子，这 ......

prologue 这很难评（调了我 1h，我都想紫砂了。 还是典型得不重构就看不见系列。 analysis 如果我们还是一个正常人，那么我们大体上是能看到题目的加粗字，这个格式很明显符合我们的同余最短路的格式。（如若不知，请先出门直走） 然后我们就要考虑这个同余最短路的实现。这个题目不同于往常的同余 ......

洛谷传送门 首先特判 \(a_i = 0\)，然后： \(\begin{aligned} f_k(x) & = \sum\limits_{i = 1}^k |a_i x + b_i| \\ & = \sum\limits_{i = 1}^k a_i |x + \frac{b_i}{a_i}| \en ......

题目链接 以下设 \(B\) 为一个阈值，同时也表示值域分块的块长。 先考虑所有 \(b\) 都不为 \(0\) 的情况。对于一组询问，我们设一个 \(x\) 表示：当前已搬完所有 \(a\leq x\) 的砖。那么每次只可能是以下两种情况之一： 有至少一摞砖在当前这个单位时间内被搬完 拿 \(x\ ......

# [THUPC2022 决赛] rsraogps ## 题目描述 给序列 $a_1,\dots,a_n$，$b_1,\dots,b_n$，$c_1,\dots,c_n$， 定义区间 $[l,r]$ 的价值为 $a_l,\dots,a_r$ 按位与，$b_l,\dots,b_r$ 按位或，$c_l, ......

[传送门](https://www.luogu.com.cn/problem/P7424) 我们发现，考虑每个子弹击碎哪些木板是不现实的，所以我们要转换问题：**考虑每个木板被哪个子弹击碎** 考虑可持久化线段树，转换问题成**求区间$l\sim r$的第s早发射的子弹**，模板题 上代码： ``` ......

[题目传送门](https://www.luogu.com.cn/problem/P8210) [更好的阅读体验](https://www.cnblogs.com/baijian0212/p/p8210.html) ### 思路 > 结论：如果序列原先就合法，答案为 $0$；否则，最多使用两个寄存器 ......

这篇题解会只讲怎么 dp，所以我们这里跳过博弈论的部分。 Let's rephrase the problem statement as follows: > 给定 $n,m$，设 $x=1\oplus 2\oplus\cdots\oplus n\oplus m$。求有多少个有序三元组 $(a,b, ......

考虑如果每个数恰好出现两次，那么容易得出一个序列合法当且仅当将每个数两次出现位置看作一个区间 $[l_i,r_i]$ 的两个端点，那么这些区间两两之间不存在包含关系。 考虑每个数出现四次的情况，我们钦定两次为 $i$，两次为 $i+n$，这样可以转化为 $2n$ 的情况，而容易发现只有 $1122$ ......