笔记

https://qoj.ac/problem/8008

不难发现,

随机到某些位置,之后最短路

先O(nm)预处理出能到的点,

考虑最小的随机位置

首先,我们将求和式进行展开:

∑ j = 1 ∞ j ( n − i n ) j − 1 i n \sum_{j=1}^{\infty} j \left(\frac{n - i}{n}\right)^{j-1} \frac{i}{n} j=1j(nni)j1ni

( n − i n ) j − 1 \left(\frac{n - i}{n}\right)^{j-1} (nni)j1 视为常数,记为 x x x,则上式可以重写为:

i n ∑ j = 1 ∞ j x j − 1 \frac{i}{n} \sum_{j=1}^{\infty} jx^{j-1} nij=1jxj1

这是一个常见的等比数列求和,其和为:

i n ⋅ 1 ( 1 − x ) 2 \frac{i}{n} \cdot \frac{1}{(1-x)^2} ni(1x)21

x x x 恢复为 ( n − i n ) j − 1 \left(\frac{n - i}{n}\right)^{j-1} (nni)j1,得到最终结果:

i n ⋅ 1 ( 1 − ( n − i n ) ) 2 = i n ⋅ 1 ( i n ) 2 = n i \frac{i}{n} \cdot \frac{1}{\left(1-\left(\frac{n - i}{n}\right)\right)^2} = \frac{i}{n} \cdot \frac{1}{\left(\frac{i}{n}\right)^2} = \frac{n}{i} ni(1(nni))21=ni(ni)21=in

因此,经过推导求证,我们得到了结论:
∑ j = 1 ∞ j ( n − i n ) j − 1 i n = n i \sum_{j=1}^{\infty} j \left(\frac{n - i}{n}\right)^{j-1} \frac{i}{n} = \frac{n}{i} j=1j(nni)j1ni=in


CF741C

考虑二分图染色,

对于每一对情侣,相互连边,

相邻的2i和2i-1也连边,都代表颜色不同,


CF1656G

限制是只有一个环,

先随便造一个回文排列

现有一个排列p

如果i,j处在同一个环,

那么pipj相互指向

拆成两个环

回文只需要第i位和第n-i位相同

考虑将一些小环合并成大环

i,j,n-i+1,n-j+1两对可以同时交换


https://www.luogu.com.cn/problem/CF1844E

这个题需要一些打表

考虑手玩一下

发现只要确定第一行第一列就可以确定所有的格子

之后容易发现一个小规律

a b a c b a
c a c b a c
b c b a c b
a b a c b a
b c b a c b
a b a c b a

不难发现行于行之间,列于列之间有重复

用1,2,3,分别表示a,b,c

在模三意义下就可以加一得出合法矩阵


https://qoj.ac/problem/6376

考虑高斯消元

共三个方向,

也就是三个变量,

但是有接近n方个限制
也就是n方个方程

考虑从中选一部分,

使用这些方程消元求解

考虑两个方向

发现只考虑左右六十度即可有2n-1个变量

依次写为x1–x2n-1

发现成为一条链状结构

每个限制只链接两个变量

模拟即可


https://qoj.ac/problem/5416

考虑倒着做

如果某个角匹配到了某个模型,

就可以将这个矩阵改为通配符

之后贪心


Empty up a Bottle

对水量操作可以看作成2的k次方

一次可以进行一组操作,所以如果a+b为奇数,

则可乘2的k次方,也可除2的k次方

不妨设a,b是偶数,c为奇数,

保证c是奇数后

辗转相减求gcd

只要在O(log(A+B))轮内完成


https://qoj.ac/problem/1436

每个盒子贡献是x

要大的数尽量占更多的=盒子

所谓更大指更高位

若最高位为2的b次方,

且只有不超过k-1个数字有,

发现他们单独放一个盒子一定为最优解

设x1,y一个盒子

x2一个盒子


x 1 , x 2 < 2 b < = y x_1,x_2<2^b<=y x1,x2<2b<=y

( x 1 A N D x 2 ) + x 2 = x 1 + x 2 = ( x 1 O R x 2 ) + ( x 1 A N D x 2 ) < y + ( x 1 A N D x 2 ) (x_1ANDx_2)+x_2 = x_1+x_2 = (x_1ORx_2)+(x_1ANDx_2)<y+(x_1ANDx_2) (x1ANDx2)+x2=x1+x2=(x1ORx2)+(x1ANDx2)<y+(x1ANDx2)

证明无论怎么分配都会有k-1个盒子贡献了2的b次方

则b可以删掉


https://qoj.ac/problem/5504

考虑容斥贪心

但是限制二选一

2-SAT不是很好处理,不好保证n个0或1

考虑如何连边,同时线段树优化建图,然后缩点

上面限制如果一个没有满足,则要求下面全部满足

发现限制全部长成这个样子

对sx向sy连边,表示当sx是1时,sy也要是1

考虑建立DAG

在上面取点,分割实现一侧为0,一侧为1

枚举他的左边或右边,

让他的前驱或后驱为一半,剩余为另一半即可

考虑加边时的变化

如果一次变化中跳到了小于n或大于2n,则构造不成立

在使用拓扑序加点时,某次落入[n,2n]的区间即是合法解


https://www.luogu.com.cn/problem/CF1646F

注意到目标状态不一定要最优,

不能保证可以

考虑换一个目标结果,

将结果转化为每个人从1-n都拿一张

就不会出现已经凑齐了n张牌还必须要失去的结果了

显然不是等价的转化,

但是可以在多项式时间内求解,

接下来考虑贪心,只要一个人手中有重复的牌就往前送,

考虑一个值为一的牌移动多少次,牌和人相互匹配,必然存在一个循环移位,使结果合法

所以最多耗费n(n-1)/2次操作

每个操作有会用n次

所以操作数合法


https://qoj.ac/problem/895

一个趣味网络流题

证明一个充分条件

每个颜色最多有(m+1)/2个匹配

将这些1-n个加入到set’中

考虑这些set的大小,

每次只加入一个点,

左边m个点,表示m个颜色,右边n个点,表示要连n个边

每种颜色最多连一个边,边也只能连一个点,容量为一

左右连边,金星二分图匹配,

只要流满就成立

左边每个出度和右边每个入度都是m+1-n,

将右边最后一个拆成m’个,就是一个二分正则图,根据霍尔定理,一定存在完美匹配

相关推荐

  1. 笔记

    2024-07-11 02:18:03       8 阅读
  2. 拼音笔记笔记

    2024-07-11 02:18:03       34 阅读
  3. 笔记】HDFS基础笔记

    2024-07-11 02:18:03       24 阅读
  4. 笔记】Hbase基础笔记

    2024-07-11 02:18:03       25 阅读
  5. mySql笔记

    2024-07-11 02:18:03       42 阅读
  6. less 笔记

    2024-07-11 02:18:03       43 阅读
  7. React笔记

    2024-07-11 02:18:03       41 阅读

最近更新

  1. Spring 系列

    2024-07-11 02:18:03       0 阅读
  2. 什么是CRISPR/Cas9?

    2024-07-11 02:18:03       0 阅读

热门阅读

  1. 代码随想录Day76(图论Part11)

    2024-07-11 02:18:03       5 阅读
  2. 优雅下线的艺术:Eureka服务管理深度解析

    2024-07-11 02:18:03       7 阅读
  3. 【LeetCode】12. 小张刷题计划

    2024-07-11 02:18:03       5 阅读
  4. samout 最新版本state 逐层控制加速收敛

    2024-07-11 02:18:03       6 阅读
  5. 【个人笔记】跨域问题

    2024-07-11 02:18:03       5 阅读
  6. webpack 打包配置

    2024-07-11 02:18:03       4 阅读
  7. 人类历史时间轴

    2024-07-11 02:18:03       7 阅读
  8. 使用Python自动化收集和处理视频资源的教程

    2024-07-11 02:18:03       6 阅读
  9. 参数式确定的函数的导数公式及其推导过程

    2024-07-11 02:18:03       5 阅读