Day24h

数学

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章 / 数学（共20篇）

Two Arrays

C. Two Arrays \(dp[i][j]\)表示有\(j\)个数每个数的范围为\(1～i\)时的非递减排列种数，因为 n 和 m 的数据范围也不大，用记忆化搜索很快可以得出每一个值。再来看满足条件时的\((a,b)\)，\(a\)为非递减序列，\(b\)为非递增序列，所以\(b...

记忆化搜索容斥原理 dp

2020-01-15

0 436

Mafia

C. Mafia 参考：Editorial for Codeforces Round #202 假设最终答案为\(x\)，则\((x-a[i])\)表示的是第\(i\)个人可以充当监护者的局数，而\(\sum^n_{i=1}{(x-a_i)}\)表示得则是在进行\(x\)局游戏保...

思维二分

2020-01-13

0 433

Median on Segments (Permutations Edition)

E1. Median on Segments (Permutations Edition) 参考：CF1005E1 Median on Segments (Permutations Edition) 思维中位数为m的条件为，在那一段中，小于 m 的数的个数为 x 个，大于 m 的数有 y...

中位数思维

2020-01-11

0 434

Polycarp and Div 3

D. Polycarp and Div 3 参考：1005D - Polycarp and Div 3 做这道题要明白一些东西：能够被3整除的数，其数位之和为3的倍数如果把数分成一位一位，相邻三个不为0位置一定能够组成一个被3整除的数（111，112，121，122，...

2020-01-11

0 407

New Year and Permutation

C. New Year and Permutation 参考：Codeforces Round Hello 2020 A~E 题解发现了一个网站OEIS，如果打表找规律的话会很方便，虽然这道题没有用上.... 具体思路可看参考视频。一般数学题都是打表找规律，如果找不出规律，例如...

2020-01-06

0 497

站军姿

D. 站军姿参考：随机在圆上生成n个点，这n个点在同一半圆的概率是多少？思路：直接利用公式，随机在圆上生成n个点，这n个点在同一半圆的概率是\(\frac{n}{2^{n-1}}\) ，求逆元的时候直接用费马小定理即可代码： // Created by CAD on...

概率

2019-09-08

0 437

Fibonacci again and again

Fibonacci again and again 参考：SG函数和SG定理【详解】思路：这是比较简单的SG定理的运用，SG定理——游戏和的SG函数等于各个游戏SG函数的Nim和如果一个位置x的SG值为0，那么这个点就为必败点P，否则就是必胜点N 必败点：用N表示必胜点：...

博弈论

2019-09-07

0 482

巴比博弈

巴比博弈参考：博弈论及算法实现只有一堆n个物品，两个人从轮流中取出(1~m)个，最后取光者胜。考虑到若n=m+1那么第一个人不论如何取都不能取胜。进一步我们发现若 n=k(m+1)+r，先取者拿走r个，那么后者再拿(1~m)个 n=(k-1)*(m+1)+r；先...

博弈论

2019-09-07

0 538

火烧赤壁

火烧赤壁隔了一天再来理解就想对来说舒服多了，也不知道是不是因为昨天太忙了没有专心.... 参考：火烧赤壁题解火烧赤壁题解思路：首先必须要明白一点，这道题需要将船只的位置标记出来，但是看到数据为(-1e9,1e9)就可以知道，很明显直接用一个数组来储存是不可能的。但...

离散化

2019-09-06

0 648

XOR Guessing

E. XOR Guessing 第一次做这种交互题，刚开始还看不懂，现在已经差不多可以理解了，清空缓存区用cout<<endl;即可，需要注意的是，如果用fflush(stdout)来清空缓存区，注意不能关同步思路：最多可能是\(2^{14}-1\)总共14位数...

交互题

2019-08-23

0 379