My blog
  • 首页
  • 归档
  • 分类
  • 标签
  • 关于
  • 友链

arc062d | Painting Graphs with AtCoDeer

link
2022-06-10
math
#burnside #idea

十分厉害的数论提

十分厉害。 \(x,y\in[1,p\times (p-1)]\) 求使得 \(x^y=y^x \bmod p\) 的对数。 首先这个东西不能用原根,阶去分析, 因为 \(x\) 可能大于 \(p\),这样会产生一个 %p 不容易考虑了。 那只能观察这个定义域限制了。 先改写一下方程 :\((x\bmod p)^{y\ \bmod p-1}={(y\bmod p)}^{x\ \bmod
2022-06-09
math

ARC140

未补完 Link A 让你最多改 \(k\) 个字符,最大化循环位移得到的本质不同的串。 枚举循环节,然后贪心判断即可。。复杂度 \(O(d(n)n)\)。 B 题意你有俩操作必须轮流做,\(\mathrm{ARC \to R},\mathrm{ARC\to AC}\)。 冷静思考一下发现最终有可能操作的一定是 \(R\) 旁边的数。 1操作相当于把 \(\mathrm{A
2022-05-16
whole round

ABC251

Link A,B,C都是模拟题没啥好说的。 D 最开始想的是贪心做,以为信息熵足够贪心就行,然后发现不对。。。。。 然后看拿什么1,2,4,8,15什么的自然想到能不能把二进制拆开那么做。,这样数量太多了。 所以大概就能想到按10进制分,就xx0000,xx00,xx这样三组恰好 297。 E 很简单的DP,拆下环就行。 F 想了一小会,是调整那样做,复杂度爆炸。 然后
2022-05-15
whole round

KM 二分图最大权匹配。

可以说是抄的ix35的洛谷博客了。。。。。 改写 首先要讲最大权匹配改写成线性规划形式。 \[ \begin{aligned} \max \sum_{i\leq m}w_ix_i\\ s.t. \forall i\leq n,\sum_{j\leq m}w(i,j)x_j\leq 1 \end{aligned} \] \(x_i\) 代表着每条边选不选。 \(w(i,j)\)
2022-05-11
#simple thoughts #线性规划

SWERC 2021-2022

Links 和袁妹妹打的一场acm。感觉由于是 7点开始,有点疲劳了,我自己状态不是很好,爬了。。。。。 赛时只做对了6道,实际上可以做出8,9道以上,两道是DS,而且我思路都不是很对。而且还是较为简单的“送分题”,DS真的应该多加练习。 只说我做的吧。。 D 题。 题意是每次你可以插入或删除 \(\text{aa,bb,cc,abab,bcbc}\) ,问你能不能将 \(A\)
2022-04-25
whole round

线性基求交

线性基求交。 大概就是 \(A,B\) 线性基求交。 答案 \(C\) 一定满足 \(\forall x\in C,x\in A,B\) 。 所以我们考虑 \(A\) 的每一个基,看他在没在 \(B\) 中出现。 如果出现,保留,否则考虑只可能是 \(x\in B,x=d_i \oplus \sum d_{k_j},k_j<i\) 这种。 所以这代表了 \(B\) 和小于 \
2022-04-21
数据结构
#simple thoughts #线性基

决策单调性随笔

这个题让我入门了决策单调性(我爬了)。。。。。 说:谢谢出题人。 我:“谢谢出题人”。 首先,转化成 \(w_0+w_1,w_2,w_3,\cdots ,w_n\)。 然后有显然的 \((+,\min)\) 卷积,有: \[ f_x=\min_{i+j=x}(h_i+g_j) \] 设 \(x\) 最优转移点是 \(p_x\),通过四边形不等式,证明决策单调性。 \[ \b
2022-04-15
dp

lgv引理矩阵树

1。哭哭,不是很会线代。。。 真的瞎说属于是了。。 lgv lgv讲的是你有一个dag(有权),并且钦定了 \(n\) 个源,\(n\) 个汇。 路径权值定义成了边权的乘积。 你要先匹配路径端点,也就是对于 \((i,p_i)\) 含义就是 \(i\) 号源,匹配到 \(p_i%\) 号汇。 你要计算的是 ,对于每一种匹配方式,大小为 \(|n|\) 的路径的集合,使得集合中路径两两
2022-04-11
线性代数
#simple thoughts #线性代数

模拟赛补题解

contest-2022-2-6 T1 题意简述:求树上最长回文串的长度,字符集大小为1000。 大概二分+点分治。 如果光二分,那么我们其实不好判断。 如果光点分治,那么我们也不好确定回文中心的位置。 那么就结合起来。 我们点分治的时候,dfs如果到达点 \(x\) ,那么我们记录下 \(x\) 是否有可能成为经过分治中心的回文串。 就大概如果长度 \(>mid\) 那
2022-02-11
模拟赛
#binary search #点分治
1…34567…10

搜索

Hexo Fluid