集训队 题解p4463 2012

## CF1487B Cat Cycle 题解 ### 思路分析 在这道题中，很明显是一道数学题，因为有十分明显的数据范围： $$ n \le 10 ^ {9} , k \le 10 ^ {9} $$ 分析如下： - 对于 $n$ 为偶数的情况下，猫 $A$ 和猫 $B$ 永远不可能相遇，所以直接输 ......

2023年暑假集训总结/7.3 预估成绩：100+20+10+20=150 实际成绩：0+61+19+0=80 T1最大公约数 题意：有n个数，取n-1个数，求可以得到的最大gcd。 思路&做法： 有一个思路是将所有数字质因数分解，然后对于每一个质数，判断他是否在这n个数中“拖了后腿”，这样就可以O ......

卡B题了，难受 ## B. qsgg and Subarray [B-qsgg and Subarray_牛客练习赛112 (nowcoder.com)](https://ac.nowcoder.com/acm/contest/59717/B) ### 题意 给定一个长为n的序列，求有多少个子区间的 ......

## [题目链接](https://www.luogu.com.cn/problem/AT_abc306_f) ## 题目大意 对于 $S_1 \cap S_2 = \emptyset$, 定义长度为 $|S_1|+|S_2|$ 的序列 $A$，为 $S_1\cup S_2$ 排序后的结果。 定义二 ......

## [题目链接](https://www.luogu.com.cn/problem/AT_abc306_e) ## 题目大意 维护一个数据结构，数列长度为 $n$，$q$ 次操作，每次操作修改一个位置上的值，每次操作后输出数列里前 $k$ 小的数的和($k$ 是给定的)。 $n,k,q\leq 5 ......

[link](http://211.140.156.254:2333/contest/387) ### T1 转化为 $(b_i,a_i)$ 与 $(b_j,a_j)$ 之间的斜率。 发现性质（省略），只需要计算相邻两个点之间的答案即可，用 set 就行了。 ### T2 先找性质，发现即为 $a, ......

[比赛地址](https://ac.nowcoder.com/acm/contest/60254) ## A.ST和TS回文问题 题意：给出一个字符串s，进行q次操作，操作如下： `1 x`:给字符串的末尾加上一个字符x `2 k`:查询是否存在长度为k的字符串t，满足s+t==t+s ### So ......

其实也没什么好写的吧。 大概列几点 - 模拟赛成绩要求每次 $200+$（似乎不难？），尽量 $250+$，争取更多 $300+$。（不过没记错的话去年 NOIP 结束的时候给今年定的目标就是 $300+$，可能都定低了？） - 少学点 useless algorithm，多练练 useful al ......

###题目大意 有一只蚂蚱，它把手机掉到了水坑里。然后它把手机捞出来，发现手机键盘都坏了。 那么手机没有坏之前就是介个样子的： ![image](https://img2023.cnblogs.com/blog/2953879/202307/2953879-20230704101526343-144 ......

# CF29B 交通信号灯 ## [传送门](https://www.luogu.com.cn/problem/CF29B) 题目很好理解，这里就不多说了，思路都在代码里 ```cpp #include using namespace std; double l,d,v,g,r; int main( ......

[传送门](https://www.luogu.com.cn/problem/P9431) ~~这个人赛时看错了几次题目导致样例调了 1h。~~ ## $Sol1: n \leqslant 10, T \leqslant 10$ 乱搞分。 枚举跳跃的顺序，判断可不可行，最后取最大值，复杂度 $O(( ......

注意到相邻两数的向下取整的差值不可能大于 $1$，也就是： $$ \lfloor \frac x k\rfloor-\lfloor \frac {x-1} k\rfloor \leq 1 $$ 稍微推广一下，我们得到： $$ x-1-\lfloor \frac {x-1} k\rfloor \leq... ......

[Regions](https://www.luogu.com.cn/problem/P5901) 这是提供一种时间复杂度不那么优秀但十分好写也好理解的做法。 ### 题目大意 给定一颗 $n$ 个节点的树，每个节点拥有一个颜色，进行若干次询问，每次询问给出两种颜色 $A,B$，求所有颜色为 $A$ ......

# T1 [BS5463【NOI2018模拟7】xiz](https://oj.bashu.com.cn/code/problempage.php?problem_id=5463) 考场A了，猜的结论。 求出每个位置上一个和他相同的数的距离，进行 KMP。但是每个数在 $B$ 中第一次出现的位置不好 ......

首先不难想到一个贪心，就是先填出一个全黑的行，然后再用其填黑列。 而且在其中“填出一个全黑的行步数”我们应该最小化。 那么如何最小化“填出一个全黑的行步数”呢？我们发现关键所在是白点，我们可以进行操作填黑它。 我们设对应的操作为 $(x,y)$,白点为 $(a,y)$,则 $(x,a)$ 为黑。 ......

6-26 T1多米诺骨牌 Hades 与 Dionysus 在狂饮后玩起了多米诺骨牌的小游戏。 现在桌上有 n 块多米诺骨牌，每块多米诺骨牌上半部分和下半部分上都有一 个整数。每次翻转可让一块多米诺骨牌上下翻转，即上下部分数交换。 Hades 想 让 n 块骨牌上半部分的数加起来是一个偶数，而 Di ......

2023年暑假集训总结/7.3 预估成绩：100+50+40+20=210 实际成绩：100+25+24+25=174 T1房 题意：有n个已知中心和长度且互不重合的区间，问有多少个长度为t的区间恰好与其中一个区间的一个端点相等，且不与所有区间重合 思路&做法： 签到题，注意到答案上界为2n，只需要 ......

# CF1394D Boboniu and Jianghu 题解 ## Links [Luogu](https://www.luogu.com.cn/problem/CF1394D) [Codeforces](http://codeforces.com/problemset/problem/1394 ......

本文网址：https://www.cnblogs.com/zsc985246/p/17523153.html ，转载请注明出处。 ## 传送门 [「CF830E」Perpetual Motion Machine](https://codeforces.com/contest/830/problem/ ......

# [ARC133E] Cyclic Medians 题解 ## Links [Luogu](https://www.luogu.com.cn/problem/AT_arc133_e) [AtCoder](https://atcoder.jp/contests/arc133/tasks/arc133 ......

根据 $P_i$ 是个排列，那将 $i$ 和 $P_i$ 进行连边之后不难发现图是由许多环构成的。 则若 $i$ 为 `(`，$P_i$ 则肯定为 `)`，$P_j = i$ 的 $j$ 肯定也为 `)`，否则就会出现度数为 $2$ 的情况。 所以发现一个点与相邻两个点的状态是恰好相反的，即确定环上 ......

## 前言 [题目传送门！](https://www.luogu.com.cn/problem/P2202) [更好的阅读体验？]() 提供一个平衡树做法，虽然和 `std::set` 一个道理就是了。（那你为啥不写 set！！！！） ## 前置知识 如何判断两个点对应的正方形相交？正方形的边长是 ......

[CF 传送门](https://codeforc.es/contest/1621/problem/G) | [LG 传送门](https://www.luogu.com.cn/problem/CF1621G)。 优化树状数组 + 反向处理。 ## Solution - 发现直接做不好下手。难点主要 ......

## AtCoder ABC168C : (Colon) 题解 ### 前置知识 本题主要考察的是高中知识——余弦定理。 具体的相关信息可以参考知乎的一片文章：《[余弦定理及推理证明过程](https://zhuanlan.zhihu.com/p/359951716)》。 简单的说，就是如果两个线段 ......

# CF1580D Subsequence 题解 ## Links [Luogu](https://www.luogu.com.cn/problem/CF1580D) [Codeforces](https://codeforces.com/problemset/problem/1580/D) ## ......

没想出来什么优美的解法，来个乱搞。 特判平凡情况 $n\le 2$，其中 $n=1$ 显然有 $1=\frac{1}{1}$，$n=2$ 无解。 众所周知 $1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^k}+\frac{1}{2^k ......

# Description 没头脑是一家大公司的CEO。该公司由N人组成，编号为1到N，没头脑编号为1。每个员工（没头脑除外）都有一个老板，我们说这个员工是该老板的助手。每个老板都可以有多名助手。没头脑没有老板，但有他的助手。 之后会有一些任务，没头脑会将该任务委托给他编号最小的助手。然后，该助手也 ......

2023年暑假集训总结/6.26 - 背锅的chara - 博客园 (cnblogs.com) 2023年暑假集训总结/6.27 - 背锅的chara - 博客园 (cnblogs.com) 2023年暑假集训总结/6.28 - 背锅的chara - 博客园 (cnblogs.com) 2023年暑 ......

6-28 T1二分哥 Um_nik 是一个很强的 Codeforces 选手。 Petr 也是一个很强的 Codeforces 选手。 对于某个排列，我们定义一次“交换”为选择两个不同的位置将他们交换。他们两个人各自拿到一个长度为 n 的初始升序的排列，随后 Um_nik 会将这个排 列“交换”7n ......

6-30 GCD 有 R − L + 1 个整数，分别为 L, L + 1, . . . , R − 1, R。你可以做如下操作最多 K 次：• 选择其中两个数 a, b，删掉它们，并往里面插入一个新的数 a × b。请判断是否可以让剩余所有数的 GCD 不为 1。该题存在 T 组数据。 显然，让所 ......