Petrozavodsk Camp, Summer 2021 IQ test¶
排名 | 当场过题数 | 至今过题数 | 总题数 |
---|---|---|---|
46/90 | 5 | 12 | 13 |
B¶
upsolved by JJLeo
题意¶
数据结构,给定定值
- 设
是将 升序排序后的结果,输出 。 - 单点修改
。
(
题解¶
因此题目转化为分别维护
注意到
- 对于前者,权值线段树维护某个权值内所有的元素排序后的
,这里 。
合并时右侧区间的元素排名会增大
- 对于后者,
,因此至多有 种不同的取值。
权值线段树维护某个权值内所有的元素排序后
合并时右侧区间的元素排名会增大
总时间复杂度为
C¶
upsolved by
题意¶
官方题解是三页论文。
题解¶
建议发表。
D¶
upsolved by JJLeo
题意¶
初始长度为
题解¶
考虑一个
- 如果
一起选,则有 。 - 否则设
和 一起选,那么 和 独立,因此有 。 对所有可能转移过来的可能取 。
可以发现
- 如果
已经被转移, ,且 还未被转移,则有 。 - 如果
和 都被转移, ,且 还未被转移,则有 。 - 如果
和 都被转移, ,且 还未被转移,则有 。
第一个转移可以 _Find_next()
找到下一个合法的
E¶
solved by 2sozx Bazoka13 JJLeo
题意¶
交互题,给定一个
题解¶
原图连通,只需判断每个点度数是否为偶。
先问出总边数,然后随机一个点集
进行
正确性证明:
首先如果
和 之间的边数是奇数,显然从 出发不存在能回到 的回路。或者说, 和 之间的边数的奇偶性和 中所有点度数和的奇偶性相同,因此必然存在一个度数为奇的点。 假设有一个点
的度数为奇,在其它点确定被划分到 和 时,这个点如果划分到 使得中间边数是偶数,则其划分到 就会让中间边数为奇,反之亦然。因此每次有 的概率错判,最终错判的概率是 ,显然是可以接受的。
F¶
solved by 2sozx JJLeo
题意¶
给定质数
- 将
变为 或者 。
(
题解¶
容易发现
否则,设
每次变化可以写为
G¶
upsolved by JJLeo
题意¶
给定一个
题解¶
超级 IQ test,太离谱了,大致写一下。
有
计算四个量:
- 四阶完全子图数量
。 - 四元点对
的数量,四个顶点不同,且 和 颜色不同。这个可以枚举每个顶点枚举其两种颜色边的数量后 计算。 - 四元点对
的数量,四个顶点不同,且 颜色相同,相当于两个同色三角形共用一条边,对每个点预处理一个 bitset 之后枚举两个点将其 bitset 按位与起来求 的数量即可,复杂度为 。 - 四元点对
的数量,四个顶点不同,且 颜色相同, 和前面四条边颜色不同。相当于两个三角形共用一条边,共用的边和其它颜色不同,对每个点预处理一个 bitset 之后枚举两个点将其 bitset 按位与起来求 的数量即可,复杂度为 。
上述四个值均是
H¶
solved by 2sozx Bazoka13 JJLeo
题意¶
构造恰有
题解¶
对于
对于
考虑一个完全图,随便选两个点再连出一个点,在此基础上,在这两个点之间不断增加点形成一条链,每增加一个点就能让点对数量增加
初始图为
官方题解是是设链上增加了
个点,那么所有合法的 覆盖了 。
I¶
upsolved by JJLeo
题意¶
二维平面上一堆矩形,为简化题意保证对于两个不同的矩形,其顶点横纵坐标均不相同。
问有多少个矩形三元组,其互不相交。(
题解¶
考虑每个矩形代表一个点,两个矩形之间如果有交则连一条黑边,否则白边,那么需要求白色三角形的数量。如果我们能求出同色三角形的数量和黑色三角形的数量,就可以得到答案。
对于前者,黑白边完全图求同色三角形是经典问题,我们只需求出每个点有多少条黑边和白边,也就是每个矩形和多少个矩形相交:
首先需要维护一个数据结构,支持插入线段、删除线段、查询一条线段和多少条线段相交。
和线段
不相交当且仅当 或 ,且如果 必然不会 ,因此用两个树状数组维护 的前缀和和 的后缀和,用总线段数减去这两个即可。 接下来利用扫描线扩大到二维平面上,我们扫描
这个维度,在相关点在数据结构中加入/删除/查询 这条线段。 对于左右边界为
的矩形和多少矩形相交,首先计算 的矩形,从小到大遍历,对于每个矩形在 处加入 ,在 处删除 ,那么每个矩形在 处插入线段之前先查询一下 与多少线段相交,即为 与其相交的矩形个数。 接着再计算计算
的矩形,还是从小到大遍历,对于每个矩形在 处加入 ,但不在 处删除。每个矩形在 处加入后记录一下 和多少线段相交,在 处再查询一下 和多少线段相交,增量即为 与其相交的矩形个数。
对于后者,即为计算两两相交的矩形三元组:
还是需要解决一维上的问题,维护一个数据结构,支持加入线段、删除线段、以及计算有多少个两两相交的线段三元组。
考虑设
是有多少条线段覆盖了 这个点, 是有多少条右端点不是 的线段覆盖了 这个点, 即为最右线段右端点为 的三元组数量,那么答案即为 。 接下来还是利用扫描线扩大到二维平面上,扫描
这个维度,在相关点在数据结构中加入/删除/查询 这条线段。 从小到大依次遍历,对于每个矩形在
处加入 ,在 处删除 。每个矩形加入时算一下加入后相比加入前增加了多少个三元组,答案即为对于每个矩形对该增量求和。 为什么这样不会算重?因为每个三元组恰好被
最大的那个矩形所计算到。
总时间复杂度为
J¶
upsolved by JJLeo
题意¶
对于两个排列
- 每种数字恰好出现一次。
。 。 。
那么就称
现给定两个排列
(
题解¶
可以发现列之间的顺序不影响答案,因此可以将每列按第一行的元素从小大排序,也就是将
引理:
不妨让每个位置代表一个点,排列和字符串所产生的性质
则连有向边 ,则 串合法当且仅当这个图无环,显然只在一行是不能有环的,因此如果有环那么也一定有这样的环: 。 考虑
中最大的值 ,如果 也即 ,因为第二行没有再比 大的数了,所以 没有任何出边,不会产生环,从而把这一列删掉不会有任何影响。 如果
也即 ,那么对于 必然也有 ,从而 。对于这些 的 也不会存在于一个环中,因为它们一旦做到 就只能继续往右走,而右侧所有点都没有出边。 因此每个串的构造过程可以抽象成两种操作:
- 删掉一个最大的数。
- 删掉一个最大的数和它右边所有数。
可以发现每次操作
等价于选一个数,且所有操作 选出来的数都是一个上升子序列,且操作序列不同根据上述分析得到的 也是不同的。
因此问题转化为一个排列中一些位置不定,求对于每一种可能的
不妨设
设
总时间复杂度为
K¶
upsolved by JJLeo
题意¶
题解¶
考虑如果我们有一个多重集
子集中属于
的部分的和要么是 要么是 ,分别有 种方案和 种方案。 如果不是这样,那么其绝对值必然小于
且不为 , 中元素均为 倍数,从而子集和模 永远不为 ,从而必然不是 。
预处理所有大小不超过
设
可以发现这样对
一个细节是如果直接用所有预处理的多重集那么数量会过多,乘上一个
L¶
upsolved by JJLeo
题意¶
两个长度为 A,B,C,?
组成的字符串,可以将问号替换为这三种字母,问有多少种替换方式使得两者的最长公共子序列长度恰为
题解¶
考虑两个字符串的前两个字符,根据抽屉原理,四个字符必然由两个是相同的。再考虑接下来两个字符串的两个字符,重复
如果能观察到这一点,就可以猜想符合条件的字符串一定具有鲜明特点,且容易计数。
在比赛中如果发现了这一点,那么做法应该暴力打表找规律。可以发现只有以下两种情况 LCS 恰好是
- 第一个字符串为
AB
交替,第二个字符串奇数位置都是C
,偶数位置是A
或B
。 - 两个字符串偶数位置都是
C
,前 个奇数位置第一个字符串是A
第二个字符串是B
,后 个奇数位置第一个字符串是B
第二个字符串是A
。
这两种模式 ABC
当然是可以互换的。
考虑如何计数,一种方式是直接枚举 ABC
的全排列然后计数,但是这样会重,需要限制第二种模式 A
只算
当然题解给出了严谨证明,大致就是利用数学归纳法,删掉前两个或后两个字符就能得到一个已经归纳过的字符串对,对新增字符暴力分类讨论即可,这里略。
记录¶
0h:MJX 说 M 是签到,ZYF 懵了。懵了一会儿好像懂了,直接暴力过了。然后 MJX 看了看 A 想了下过了,开始和ZYF CSK 想F,逆十字7min过了,但是啥也想不出来,IQ--。
1h:然后卡到快俩小时,E 看错了题意没看到连通,完全是个新题,随机一发过了。ZYF开始想恒等式的解法,推了半天,发现是个恒等式。但是其实是对的,少开个 long long wa 了一发,然后过了。
2~5h:然后开始做梦构造H,开始CSK想了个构造的方法,但是好像覆盖不全,经过亿点点的推进,想到了先构造几个完全图,然后再连起来,去构造这60个数,感觉暴力跑不完就先考虑俩完全图连一起(?为啥不直接考虑一个?),暴力跑了一堆数据出来,发现差了点,最后想到好像一个完全图自己就最优了(?为什么最后才能想到,属于是构造题血脉压制了)。