XCPC 2025

美好的新赛季从补题开始.

pre

• 小心 $n$ 和 $m$ 写反.
• 注意数组不要开小或开大.
• 注意计算变量范围,不要能到 long long 的变量开 int .
• 感觉容易挂的地方写 assert .
• 感觉容易写挂的题,样例很弱的题一定要写对拍.
• 注意模数是不是质数.
• 注意操作的顺序.
• 认真读题,模拟完样例再写程序.
• 注意清空数组 .
• 相信所有题都是可做的 .
• 感觉不可做的,有较高多项式复杂度暴力的题,思考: 分治,贪心,DP,线段树.
• 感觉不可做的,有指数级复杂度暴力的最优化题,思考: 贪心,DP,流和割,暴搜加优化.
• 感觉不可做的,有指数级暴力的数数题,思考: DP,行列式,暴搜加优化,拉格朗日插值,容斥,造自动机.
• 后遭,交互题,考虑: 增量法,分治,暴搜策略.
• DP优化:凸优化(wqs),斜率优化,决策单调性,交换状态和值域,减少状态(包含常数上的).
• 感觉不可做的题,考虑各个元素,集合之间有什么关系.
• 就算过了样例,感觉没问题也要仔细分析一下各种情况,必要时对拍.
• 分段函数用vector,常数比map小很多.
• 做题别急 .
• 任何n较大的,可以快速算单项的东西考虑分段打表.
• 子区间问题有时可以类似最大子段和使用线段树维护,也有可能分治.

第一次集训

K

位运算炸int了: Map|=(str[i]=='#')<<i 前面半句话会转成int导致i在64左右的范围会直接挂掉.

I

题解非常妙,横着看很难,我们发现构造的排列对于一个位置,下一个位置是固定的,也就是说竖着一个除了末尾的字符串下一个出现的位置也是固定的,所以直接哈希检查即可,非常妙的题.

第二次集训

A

给定两个罗盘的度数,计算方位角.
实际上边界会变,取平均数的时候注意一下(赛时没注意到就WA好多发,,)

C

题意:你对城市建筑拍一张照,得到像素图,建筑可以被简化为一根柱子.
你每次可以询问一个像素点,返回该点是建筑还是天空(没东西),求最高建筑的位置和高度.(交互题,你要在 $12000$ 次询问内返回答案)

显而易见的结论是,对值域二分检查,nlogn绝对不够用.
然后mxx显然不会减小,对更高的值域二分,也显然不够用.
首先用一次检查mxx+1判断该楼会不会比当前更高,更高再二分.设想梯度图会被卡,还是不够用.

我们已经到算法优化的极限了,怎么办?
随机化查询坐标.于是这个题就乱搞过去了…

第2.5次集训

D

难点在于给一个数n,你要把它分组,每组可以为0,组之间有顺序,而且你分的组要单调不增,你要O(1)算这个值.

答案:爆典.
其实和n分成任意组(非0),每组不大于m的dp状态是一样的,难点在于证明.

你竖着想,5可以分成3和2,这是两根柱子.

然而你横着想,因为单调不增所以你的柱子都是从左打头从右结尾的,而且宽度上限就是m,得证.

A

给一个函数 $f((l,r))=(\min(a{l-r}),\max(a{l-r}))$ ,q次询问每次lr问最少几次可以让 $f(f(f(f(…f((l,r))))))$ 取到 $(1,n)$ .

div1的E…有点不敢做.

ICPC2024沈阳站

B

构造两个数列满足 $a_ib_j\mod nm$ 不重.
大胆猜,nm不互质无解,然后尝试从nm出发,在n这里构造1+km%nm,在m这里构造1+kn%nm.

D

先来一个结论:交换两个元素对一个排列的逆序对奇偶性的变化取决于区间差,排列的整体左移右移多少次可以转换为区间上的很多次交换,所以逆序对奇偶性变化可以O(1)算出来.

所以给的其实是一个排列,然后交换AB实际上是假的,对哪交换都可以,只需要算出开始的逆序对奇偶性就行了,而且因为刚开始只需要计算奇偶性,甚至能O(n)算出来.

E

不会写状压dp了…

温习一下:

dp[1<<16][16]//状态为i,结尾为j时最小
for 枚举状态  
    for 枚举上一个结尾点
        for 枚举新加进去的二进制状态

G

给n个点,这些点组成一个简单多边形,你最多询问n次,每次返回多边形在 $x=i$ 处的切片长度,你要回答多边形面积.

很神秘的题.你要计算 $\int_{-1000}^{1000}f(x)\mathrm dx$ 的值,每次询问回答一个点的 $f(x)$ .
有一个性质:这个面积函数在x轴两点之间是线性变化的,于是考虑询问端点.具体地:
坐标都不相同:f(x)分了(n-1)段,询问分段点即可(两端是0).
有相同的:f(x)分了(n-2)段,询问最左最右两个端点,然后对分段区询问中点.

然而题目返回的是 p/q 的形式, pq 可能很大,使用longdouble最后向0.5取整(发现题目都是整数点,所以答案只可能是 x.0 或 x.5 ).

第三次集训

A

有一个nm矩阵,部分格子有障碍物(*)否则为空,你要对空格子用[0,k]种颜色涂色,其中[1,k]种颜色同行同列只能出现一次,0颜色可以无限使用,设你用了z个0,代价是 $ck+dz$ ,cd是给定常数,求最小花费.

题解说是网络流,然而还有一种办法可过.

E

有一个n节点的环,你每次可以选任意[1,m]个连续节点涂成黑色,对面也要这么做,不能涂色的人输,现在nm多组询问,对每次询问输出谁赢.

先手第一步除非可以直接赢,否则环会被拆成链.然后后手除非m是1否则必然可以把链断成完全相同的两部分,然后后手只需要模仿先手就一定会赢.

G

给n个不覆盖的矩形,你要找出所有的对称轴.注意:假如正方形可能由一个长条+两个小正方形组成,这个正方形依旧有4条对称轴.

观察发现对称轴必须经过一个点,而且最多有四个,只要能够 $O(n\log n)$ 检查就已经赢了.由于矩形可能是拼起来的,所以常规记录线的方法不可行,要考虑用点记录矩形.

结论:被偶数个矩形覆盖的点无效(矩形覆盖是仅限边界四个点的),如图

+-+      +-x-+
| |      | | |
x-+-+    x-x-x
|   |    |   |
+---+    +---+

然后直接翻转检查点即可.
但是不出意外的话是要出意外了,点绕直线对称的结论是啥来着?

$$Ax+By+C=0\\\\ x'=x_0-2A\frac{Ax_0+By_0+C}{A^2+B^2}\\\\ y'=y_0-2B\frac{Ax_0+By_0+C}{A^2+B^2}$$

第四次集训

和银趴(Linux install party)撞了(悲).
全场唐完,刚开始是队友1的D见祖宗了,然后是队友1的G数组开小了(开1e5题干2e5),然后Flu的H结论对了但是不敢写(诈骗)一度悬置这个题.然后队友2的B疯狂WA,然后屡了一下思路之后过了.

G:单调栈题,没做出来,后来发现是弹”时间差”个元素即可.
A:empty中场来到我这说,, 0011 就是 gugugaga (捣乱来了)…

A

括号树…是啥?

首先把0011转换为括号匹配,可知合法不合法.然后建括号树进行拓扑序计数即可.
括号树:

((())())
   / \
(())  ()
  |
 ()

以某个点为根的树拓扑序(子节点一定要出现在根节点前面)的个数:

$$n!\left(\prod_{i=1}^nsz_i\right)^{-1}$$

$sz_i$ 表示以 $i$ 节点为根的子树大小.

看别人的码才发现,逆元有一个 $O(n)$ 的递推方式,之前一直用的快速幂 $O(n\log n)$ 算逆元,常数大的不行.

E

给一张图代表城市,城市会被水淹,求从1点出发淹没所有城市的最小水高度.

Flu原先想的是,一个城市被淹的时候走的都是最短路,所以直接对每个城市的边权取min然后对所有城市的min取max就行了,然而不对,比如

  1
4/ \5
2---3
  1

这种情况最小边权是4,因为淹没了2之后淹没3是顺手的事.

所以正解是最小生成树.

C

有一个问题: 哈密顿路 和 哈密顿回路 不是一个东西.前者只需要遍历就可以了,后者则需要状压DP.

然而…
树上进行链的合并要动态维护sz,同时由于dp值会发生变化,要开一个辅助数组临时存放,然后在一整个链合并完之后在集中推平,草,合并链都不会写,这么唐吗…

void dfs(int pos){
    sz[pos]=1;dp[pos][1]=0;
    for(auto v:edge[pos]){
        dfs(v);
        fill(tmp,tmp+400,-1145141919810);
        for(int i=1;i<=sz[pos];++i){
            for(int j=1;j<=sz[v];++j){
                for(int k=0;k<=min(i+j-1,2*min(i,j));++k){
                    tmp[i+j-k]=max(tmp[i+j-k],k*num[pos]+dp[pos][i]+dp[v][j]);
                }
            }
        }
        for(int _=1;_<=sz[pos]+sz[v];++_){
            dp[pos][_]=tmp[_];
        }
        sz[pos]+=sz[v];
    }
}

第五次集训

B

设 $f(x)$ 是一个数分解成质数的最小个数.
对于偶数,使用哥德巴赫猜想(除了2),必定能够拆成两个奇质数.
对于奇数,首先是拆成2和f(奇数-2),然而还可以拆成三个奇质数的和(偶数+奇质数,又是猜想),所以上界是3.

VP

回想起来了括号匹配结论是卡特兰数.

I Nim Game

读假题了…题干要求的是对区间加,然后区间判断nim能不能玩.

nim能不能玩是用线性基,然后区间加可以用树状数组差分解决.

C Random Number Generator

回顾BSGS和二次剩余的区别:分别让求

$$a^x\equiv b\mod p$$ $$x^2\equiv a\mod p$$

这俩不一样…

吉林省赛

C

如何计算巨运算符,如

$$pow=\sum_{x_1=0}^{n-1}\sum_{x_2=0}^{n-1}\sum_{x_3=0}^{n-1}a_{(x_1+x_2+...+x_n)\mod n}$$

最后发现最后一个就是sum数列或者prod数列,然后考虑向前处理:
碰到sum说明有n个这样的数列,所以乘n即可.
碰到prod要对其求n次方.

H

两段区间上要支持区间加上某个数字,你要判断两段区间可以任意交换顺序后是否相等.

哈希.但是要考虑怎么哈希,赛时想到的方法有:

1. 维护区间所有和的二次方和.(以及其加强版,维护三次方和(初始时再加一个随机偏移))
2. 选一个数做底,维护其a次方的和.
3. 维护区间所有数的抑或和.

事实上,方法1很容易被卡,加强版过了这个题.
方法2好写好调,为什么不写?
其实做法3假了,因为区间加和不是区间抑或,所以是没法维护的…

两段区间是分奇偶的,如何维护?
考虑把奇数做成正的,偶数做成负的,判断其加和是否为0即可(所以只需要一颗线段树).

OTH

群U说可以直接把交互逻辑写进程序,然后留个开关即可.

杂题随机做

后面因为期末考试外加各种比赛的原因,根本补不完题,扔最后了…

CF2043E

你有两个矩阵AB,每次能对一行&一个数,也可以对一列|一个数,问最终A能否转换为B.

正着想把A转成B很难,就倒过来想: & 就是把一列0转换为通配符, | 就是把一行1转换为通配符,然后加到队列里宽搜一下,最后模糊匹配一下答案就出来了.

gym103428F

非常好的题.有n堆石子,两个人博弈,每次要拿前面拿的石子数的因数倍,且任选几个大于等于你要拿的数量的石堆拿走这么多石子,问保证你赢的情况下,你有多少种初始拿法?

首先考虑1的情况,此时必胜当且仅当石堆中存在一个奇数堆,这样的话你把所有奇数堆变成偶数堆,然后 模仿 对面怎么拿,你是必赢的.
然后考虑不存在奇数堆的情况,全是偶数堆的话用1去拿显然是必输的,因为会被模仿.所以偶数堆直接全部除2直到出现奇数,此时问题变成前面一种情况.
答案就是(最小奇数+1)/2.

洛谷4446

把 $x^{1/4}$ 以内的质数全部除掉,剩下的一定是一个立方数或不可开方数.

然后预处理 $x^{1/4}$ 以内的质数,同时处理 $x^{1/3}$ 以内的立方数,就可以对最后二分判定是不是立方数.

ARC150D

设E(Xi)为i点期望被选中的次数，那么 $ans=∑_{i=1}^n​E(X_i​)$ 。
设i点的深度为di。
如果一次操作选中了除1到i路径以外的的点，那么对i没有影响，所以只需要考虑选1到i路径上的点的情况。

允许选中好点，但不算选中好点的贡献，这和原问题是等价的。

所以问题可以转化为，di个点，每次等概率抽取一个点，抽到第di个点时贡献加1，一直抽直到所有点都被抽到过。

假设已经被抽到过的点有k个，那么再抽一次抽到未被抽到的点的概率为 $\frac{d_i-k}{d_i}$ ，期望 $\frac{d_i}{d_i-k}$ 抽到下一个未被抽到的点（做某件事情成功的概率为p，期望做 $\frac1p$ 次成功）。

所以把所有点都抽到的期望次数为 $\sum{k=0}^{d_i-1}\frac{d_i}{d_i-k}=d_i\sum{k=1}^{di}\frac1k$ ，每次抽到第di个点的概率都是 $\frac1{d_i}$ ，所以第di个点期望被抽到 $\sum{k=1}^{d_i}\frac1k$ ,

所以 $ans=\sum{i=1}^n\sum{j=1}^{d_i}\frac1j$ .

连带:一个n面色子,问期望多少次能把所有面都投出来.
设f(i)表示当前n面色子,投出来了i种颜色.
$f(i+1)=f(i)+\frac{n}{n-i}=n\sum_{i=1}^n\frac 1i$

cf1446c

给你一堆数,每个数字会找与这个数字抑或和最小的数字连边,最后会形成一张图,你要删掉最少的点使图联通,求最少删几个点.

首先删点很复杂,我们转化为保留最多的点.
显然最后剩下的一定是一棵树,而且只有一对是互相是xor的最小值.

联想trie树,树上的相邻节点之间满足xor最小(因为前面都一样,后面自然最小),所以建一个字典树维护01.

如果只有左右儿子,直接返回即可.如果都有,那么根据最长往外延展1个的原理,是max(l,r)+1.
直接合并即可.

CF1778F

给你一棵树,树上有点权,每次你可以让一个整个子树乘上子树的gcd(最多做k次操作),问你根节点的值最后最大是多少.

首先,假如没有k的限制,直接拓扑排序即可.
假如没有呢…首先维护子树gcd和所有数的ceilsqrt().
ceilsqrt:对于x有最小的c满足c^2是x的倍数.具体地,对x分解质因数之后所有p的次方取 $\lceil \frac i2\rceil$ 最后乘一起就可以了.

首先,最后答案一定是根乘上根的一个因子.

其次,因为维护哪里要乘哪里不乘很不方便,所以我们转化为一个判断性问题:
对于根节点,倒序枚举所有因子,判断假如说子树要变成这样最少要多少次,然后再比较,就可以很轻松得到答案.
所以写一个dfs(num,ko,val):
如果子树gcd是val因子,直接返回.
否则如果子树gcd的平方是val因子,那么需要对子树进行一次gcd操作,返回.
否则如果子树根节点的平方还不是val因子,或者这是个叶节点,那么无法完成操作.
然后要对子树进行操作:先操作子树,然后再操作根节点,对于每个子树w要把gcd(w)变成ceilsqrt(d)的倍数,这样就可以把根节点gcd^2(w)是d的倍数,否则完不成操作.
dfs传参即可.

CF1841C

给你一个字符串,你最多能更改一位,求最大值.
字符串只有ABCDE五种字母,分值分别是1,10,100,1000,10000,一个字母贡献是正的当且仅当右边不存在严格比他字典序大的字母,如ABCDE的贡献是 $-1-10-100-1000+10000$ .

本来我认为是直接枚举每位是ABCDE,然后只要能O(1)算贡献就完事了,所以pre表示前缀最大,然后倒着枚举,这么着后半段是算出来的,前半段是枚举的,但是这么着会假,比如 AExxxxxxxxx 在枚举E后面的时候AE只会被单纯统计起来,没有大小关系,就会WA,想改正又很难写.

正确做法是贪心,一个字符想改有两种情况:改大:最左侧的是最优的,能带来最少的负字符.改小:最右侧是最优的,因为有更大的概率是正贡献.所以对10个位置暴力改成其他字符,然后检查即可.

P1983

碰到什么高于什么,联想图论建模和差分约束.

连边进行拓扑排序分层(找最长链).

P9211

随机化神仙题.

我们发现,原字符串只会有 $1\%$ 的字符会错,而且对你的容错率有足足 $3\%$ ,检查没有什么很特殊的性质,考虑随机化.
随机化的步骤是:枚举 所有长度 ,对所有长度随机 $500$ 个位置,假如说这个长度是对的,那么错误字符概率应该期望占比 $1\%$ 左右.
所以要对长度随机,最后匹配最多的长度会进行深度匹配,也就是遍历所有位置取最大的那个字符.

笔者本来以为是对长度随机化,所以shuffle了一下就开始深度匹配了,复杂度假的一批…

P2893

给一个序列,你可以把任意数字变大或变小,代价就是差的绝对值,问你把原数组变成单调不减或单调不增的数列的最小代价?

非常典的题,有很多变式(六倍经验…).
首先有一个结论是,当原数组单调的时候,所取值一定在原数组出现过.

设dpij表示第i个元素取第j个值,i之前元素满足单调的最小代价,有

$$dp_{ij}=\min(dp_{i-1,k}+abs(dat_i-val_j)),k\le j$$

注意到后半部分是不随k变化的,所以提出来:

$$dp_{ij}=\min(dp_{i-1,k})+abs(dat_i-val_j),k\le j$$

整一个前缀min就完事了.

变式1:变成单调不降时最少动多少个元素? $n-LIS$ .

变式2:变成单调 递增 的最小代价?
把原数组变为 $dat_i-i\to dat_i$ 然后再跑上面的,意思是我们已经扣掉了增益,然后直接加上就可以了.

变式3:数据放大(想一个nlogn的做法):
(下面都在分析非下降数列)
根据贪心的原则,假如说当前有一个数字x,后面来了一个y,假如y不比x小,那么直接加入即可.
否则一定x变小或者y变大或者两者都有,但是这个和是一定的.所以显然是取更小的那个更优,于是加上abs之后把顶端max元素弹出,加入两个小的y.
贪心nlog即可.

计数转01 计数视频

给一个0-(n-1)的排列,q次询问,每次询问区间[l,r]上所有子区间的mex和.

考虑转化计数方法:对于i=1~n询问即为区间上有多少个子区间满足mex>=i,只需要枚举mex即可(也就是说012这个区间会因为存在0+1,存在01+1,存在012+1,答案是3)

枚举0~i出现的最左端left(i)和最右端right(i),对于整个区间的贡献即为(left(i)-l+1)*(r-right(i)+1),也就是必须包含这个小的区间,拆开式子得到

$$ans=left(i)\times r-left(i)\times right(i)+left(i)-l\times r-right(i)+1$$

使用前缀和优化即可,对于一个区间二分查出最大的子区间left(i)和right(i)被包含的.

计数转01 2 HihoCoder-1646

有 $n$ 个包含 01? 的串，每个串的 ? 可以填成 0/1。求在所有情况下把这些串插入字典树得到的树的大小的和。
$n \leq 20,|S| \leq 50$。

字典树大小 这个东西很难刻画。
我们使用经典等价转换：字典树大小等价于本质不同前缀个数，也就是所有串前缀的并。

于是用容斥计算：$\sum_S (-1)^{|S|-1} LCP(S)$。
(用人话说:枚举所有n个字符串的子集,|S|表示枚举的子集大小.LCP(S)的意思是枚举的字符串这里面的公共前缀有多少个)

直接状压n暴力check即可, $O(2^nn|S_i|)$ ,如果使用集合合并的神秘科技可以优化到 $O(2^n|S_i|)$ ,其中S_i是字符串最大长度.

计数转概率 AGC030d

直接枚举是会爆表的,尝试转成概率:每次有1/2的概率进行操作,最后的答案就是期望乘上2^q种情况.

设fij表示i位置数字大于j位置数字的概率,一次交换只会影响xy直接比较的元素,所以有

f[x][y]=f[y][x]=v(f[x][y],f[y][x]);
for j in range(1,n+1):
    f[x][j]=f[y][j]=v(f[x][j],f[y][j]);
    f[j][x]=f[j][y]=v(f[j][x],f[j][y]);

最后直接相加再乘上情况数即可.

计数转概率2 HDU-5396

有一个表达式，长的是这样：$n$ 个数 $a_1,a_2,…,a_n$，每两个数之间有一个操作符号。每次可以选择一个操作符运算，直到只剩一个数，这个数就是表达式的结果。问所有情况下最后的数的和。 $n \leq 500$

我们还是考虑转期望。令 $f{l,r}$ 表示 $[l,r]$ 的答案。那么显然有转移 $f{l,r}=\frac{1}{r-l}\sum{k=l}^{r-1} v(f{l,k},f_{k+1,r},opt_k)$，$v(x,y,opt)$ 表示 $x\ opt\ y$ 的结果。

最后答案即为 $f_{1,n} \times (n-1)!$。

P4424

神秘找规律题.

对于两个数ab,假设0是或,1是与,从a的低位按照b的低位二进制进行运算(a开头补0),结果等于 $a>b$ .
例如 a=0001 , b=0010 ,运算结果 0|0|0&0|1=1 ,直接比较 a>b 也是1(ab高位在右,按照字符串规则去看)

P5339

很棒的组合数学题,补齐了板子…

在这里有结论:假设有四种颜色,每种颜色分别能涂abcd个格子,问你在长度为n的格子上有多少种涂颜色的方案.
考虑EGF(EGF卷积的意义就是随意插入混合),把这四个卷积起来最后取第n项就是答案.

实际卷的时候有一个事情:lim是比abcd和大的第一个2的幂,以及,abcd在做完NTT之后可以直接乘一起取模,然后再做FNTT.

[abc306g]

神秘题.问你能否在一张图上走很大步回到原点.

找环:考虑这些环大小的gcd是数字的倍数,建立正图反图,进行dfs,统计正图深度(反图用于统计谁可以到达原点,否则整这个环是无意义的.)

然后进行环大小的统计:对于环大小有一个结论:

abs(dep[i]+1-dep[j])

使用情景:对于任意正整数a,图上存在一个包含1点的,长度不是a倍数的环的充要条件是对于有向边ij满足深度在上面的式子.可以理解为环上从a到b可以正着走也可以反着走环,所以环的大小被”拼出来”.

神秘小式子

a|b=a^b^(a&b)
a|b=a+b-(a&b)

CF2136F1

神秘交互题.首先全部填1能得到 $\lfloor\frac xn\rfloor$ ,然后考虑设计一个能够区分[1,n/2]的办法.

答案是构造 $[l,1,l,2,…,l,r]$ 这个能测出来,太惊讶了.

CF696F

对于一个数组a,每次能选择一个两个元素并插一个平均数(整数)进去.直到这个数组再也不能插入数字结束,如果最后的数组是一个公差1的等差数列那么就是”好”的.
现在给你一个数列n,你要求出有多少个连续子数组是”好”的.

非常妙的题.
首先发现公差绝对不是偶数,因为能再插一个数.
然后发现公差实际上是选出来的数两两差值的gcd.

由于gcd在固定左端点时右端点的区间gcd是单调的,所以我们需要找到最左端的值,满足区间gcd是2的倍数.
相同数字会导致区间在check时出现(可以-不可以-可以)的局面,所以我们初始时应当排除掉相同数字做差出0的局面,也就是第二次二分得到最左端连续的数字.

具体地:使用线段树的复杂度是建树nlog,查询log^2.
而使用st表则是建表nlog^2查询log(左端点和右端点取一个gcd就可以了)

CF2120D

给你一个矩阵的size,和元素的种类数,你需要确定一个最小的矩阵,满足矩阵内元素在最坏情况下填数,但是你按行按列删除后,最后剩下的元素完全一致的子矩阵的大小不小于给定的axb.

比如给定

1 2 1         1 1           1 1
4 5 6    =>   4 6      =>   1 1
1 8 1         1 1

最后能删成的矩阵大小是2x2.
你要在保证行最小的前提下最小化列,输出答案.

神秘抽屉原理题.首先保证n行最小答案就是 k(a-1)+1 .
考虑什么时候m最小,首先最坏条件下m是一个上界.
我们考虑这个抽屉是多大的:可行的元素种类是从n行中选a行我们想要的,而且这个想要的是k种取值,答案就是kC(n,a).
那么我们让这些元素有一种至少出现b次就是 k\C(n,a)*(n-1)+1.

CF2066C

给你一个数列,你有三个寄存器PQR,你要从头开始,每次必须选择寄存器的一个抑或上数列第i项,你必须随时保证存在PQR中两个的数字相等,问你有多少种操作方式(某次操作选了不同的寄存器就被视作不同操作.)

神秘题.
因为PQR三个数必须抑或上a,所以任何时刻的P^Q^R都等于前缀抑或.
而且任意时刻有两个数相等,那么一定有一个数的值就是前缀抑或.
考虑dp:设 $dp{i,j}$ 表示前i项,有一个数字是pre[i],剩下两个数字为j时候的答案,假如j=pre[i-1],那么随便选一个抑或就可以了,有 $dp{i,pre[i]}\leftarrow 3dp_{i-1,pre[i-1]}$ ,假如j=pre[i],同理…

严正声明:在cf能少用umap就少用!!!又被卡了…

Even Circuit

根据鸽巢定理…搜索范围不会超过值域上限…
所以这是个诈骗题,直接搜索就可以了…
但是还得加一个优化:从2e5的数组里面选很少个,应该枚举下一个选的位置,而不是记录总数量以及当前选不选.

void dfs(int num,int res,int xx){
    if(ff==1)return;
    if(res<=0){
        if(vis[xx]!=0){
            ff=1;
        }else{
            vis[xx]=1;
        }
        return;
    }
    if(num>n){
        return;
    }
    for(int i=num;i<=n;++i){
        dfs(i+1,res-1,xx^dat[i]);
    }
    // dfs(num+1,res-1,xx^dat[num]);
    // dfs(num+1,res,xx);//用上面的别用下面的
}

Adjacent Add

给你一个数组.每次操作可以在ai加上x(可以为负),ai+1加上kx(k给定),问你任意操作后数组能不能变成一样的.

观察不变量:

$$C = A_1 - \frac{1}{K}A_2 + \frac{1}{K^2} A_3 + \dots + \left(-\frac{1}{K}\right)^{N-1} A_N$$

当整个数组相等时,长这样:

$$C = x - \frac{1}{K} x + \frac{1}{K^2} x + \dots + \left(-\frac{1}{K}\right)^{N-1} x$$

所以我们直接用两个式子相减,然后尽可能贴近这个值附近检查整数x是不是解就行了.

对于一个x:检查是不是解的时候可以用发散性正着检查,也可以用能否整除以及最后是不是x倒着检查.(经检验[-20~20]区间能过)

Yelkrab

放到字典树上,维护ans数组表示在队伍为j时的答案.
发现一个字典树节点sz++的时候只会对其所有因子产生贡献.
所以枚举因子暴力维护即可.

Flipping Paths

呃…首先,斜着的横行的W或者B奇偶性一致的时候就有解.
然后考虑贪心,每次取最下方的元素构造一条路径走过去即可.

CCPC 2024 Online

找最小

线性基,发现AB的sum在交换一对的情况下是AB分别抑或上 $a_i\oplus b_i$ ,于是用 $a_i\oplus b_i$ 构造线性基.

随机过程

有一个结论是,你有n个选择,你选m次,然后你选择种类的期望计算方法为:

每个选择不出现的概率是 $(1-\frac1n)^m$ ,知道这个就很好算了.

同时,你有n种物品,每件物品p个,你选m次(注意,不放回),你选择种类的期望:

每个种类至少出现一次的概率是 $(1-\frac{\binom{(n-1)p}{m}}{\binom{np}{m}})$ ,期望直接乘几种即可.

---

疯狂星期六

对于某某花费不能超过自己最大限额的题大概率是网络流.

ICPC 2024 Online I

链接

G The Median of the Median of the Median

给一个序列,算出”中位数的中位数的中位数”.

中位数的题首先考虑二分.

于是考虑二分最后的中位数,记录a数组每个元素是不是小于等于n,然后前缀和在n方时间内算出数组b,因为我们只需要检查是不是即可,并不需要算出真实的b,所以b是一个01上三角矩阵.然后考虑怎么算出c:
首先一段a对应的b也是一段上三角矩阵,所以前缀和是向右上角做的前缀和.然后这段区间有多少个元素是个等差数列,直接枚举前缀和即可计算得到c,也是一个01矩阵,然后数有多少个1,加一起就是所有元素的中位数是不是mid了,非常仙的一道题.

我们为什么把中位数的限制放宽到小于等于mid即可?
因为二分会帮我们找到最大的mid.

C Permutation Counting 4

参考大佬的博客.

非常妙的题.给定n个区间[l,r]求有多少个1n排列p满足 $p_i\in[l_i,r_i]$ ,答案模2.

首先我们构造矩阵 $A_{ij}=[j\in[l_i,r_i]]$ ,要求的答案如下:

$$\sum_{P}\prod_{i=1}^nA_{ip_i}$$

P是排列.这其实就是枚举排列是否合法.
这个定义很像行列式:

$$\det(A)=\sum_{P}\mathrm{sgn}(p)\prod_{i=1}^nA_{ip_i}$$

事实上,要求的式子被称为积和式,记作 $\mathrm{perm}(A)$ ,只是去掉了正负号,不难发现:

$$\mathrm{perm}(A)\equiv\det(a)\mod 2$$

其实是判断矩阵中是否有向量可以被其他向量表示出来.

对每一个 $l,r$ 限制,构造一张无向图,让 $(l,r+1)$ 连边表示区间上能够构造一个 $(u,v-1)$ 的”可达”,如果已经可达就是不可以,否则加边.使用并查集即可维护.

为什么维护l,r+1不是直接lr?
考虑(2,3)(3,4),他们会重叠,所以实际上不能构造出(2,4)的向量.

ICPC 2024 Online II

L 502 Bad Gateway

首先发现一个策略是,找到一个pos满足前半部分等,后半部分一直刷新,直到刷进前半部分,设前半部分期望为 $E_1$ ,后半部分期望是 $E_2$ ,列式:

$$E_1=\frac1{pos}\frac{pos(pos+1)}{2}$$ $$E_2=1+\frac{pos}nE_1+\frac{n-pos}{n}E_2$$

最后的期望是

$$E_3=\frac{pos}{2}+\frac{n}{pos}-\frac12$$

使用基本不等式,得到答案是 $\lceil\sqrt{2n}\rceil$ 或 $\lfloor\sqrt{2n}\rfloor$ 中的一个.

G Game

赛时没做出来,是因为读假题了…Flu以为筹码会还回来导致一直懵逼不知道咋做.

类似辗转相除的过程,可以赢/输最多 y/x 次,答案就很明显了.dfs的时候反转xy,输赢也要反转,概率也要反转.

E Escape

奇偶图dfs,任何人不能原地停留,而且反复横跳会+2步,所以对每个机器人处理范围内的奇偶数字的最小值,然后对主人公也跑一遍奇偶图最小值,注意如果只是跑最短路会WA15,构造一个需要两次走过的点,这个时候单次遍历的pre数组直接失效导致误报无解实际有解.

码题集

子矩阵抑或和

给一个矩阵,求出其所有子矩阵元素抑或和的和.

先考虑问题的一维版本,一个数列区间抑或和可以使用前缀和快速求出 $pre{r}\oplus pre{l-1}$ ,这个时候问题转换为任意两个前缀和相乘的加和结果.统计整个区间0和1的个数,答案就是 $cnt_0cnt_12^{pos}$ .

现在考虑矩阵版本,子矩阵先做前缀和,然后问题变成了矩阵任意两行,任意两列,交叉出来这四个数的抑或和的加和.模拟一维的做法,先枚举二进制位,然后枚举两行和一列,然后把这两行压成一行(直接抑或就行),然后剩下的和一维一样处理即可.

数学图

有n个点,每个点的值为 $a_i$ .建图方式如下:
如果 $a_i=a_j$ ,则i和j之间有一条权值为0的边.
如果 $\gcd(a_i,a_j)\neq1$ ,则i和j之间有一条权值为1的边.
如果 $a_i$^$a_j\le k$ ,则i和j之间有一条权值为1的边.
问从s点出发到达所有点的最小花费.

$$n<2e5,k<5,a_i<1e6$$

这个题点权的大小比较离谱,考虑中转点.对于情况1,对所有值相同的点都开一个中转点即可.对于情况二,首先, $\gcd(a_i,a_j)\neq1$ 表示这俩数有公共因子,所以对于一个数,我们对这个数的所有质因子都连边即可,每个质因子都是一个中转点.对于第三种情况,发现k的值特别小,于是对于一个数,暴力枚举所有k对应的数,然后和情况1中的值中转点连边.

这个题还有一个特殊的性质: 边权只可能是0或1 ,所以我们建立双端队列代替dijk的堆跑最短路.

质因数分解和

给定数列a,计算

$$\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)a_ia_j\mod1e9+7$$

其中 $n\le2e6,a_i\le1e9$ .

居然是道莫反题,没做出来真惭愧.