Deep_Dark_FAntasy♂

未归档

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 未归档（共176篇）

String Deletion

链接：https://vjudge.net/contest/400848#problem/D注：a/2向上取整就是(a+1)/2代码： #include<bits/stdc++.h> using namespace std; const int maxn = 2e5+7; char s[...

水题

2020-10-13

3 480

D - Squares

链接：https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d思路：分为x轴和y轴来进行组合考虑1.如果x轴A,B不相交，y轴随便的话假设A在左，B在右，我们考虑AB在x轴上有哪些情况，怎么算呢？b现在在最右边，a向右移动有n-a-b+1种方式，b向...

思维组合数学

2020-10-12

5 453

The Moon

链接：https://vjudge.net/contest/400607#problem/D突然想起来概率里面还有一个概率dp，这个之前确实学的不扎实，通过这道题回顾一下。题意：打一局游戏的胜率是p，初始开箱爆率是q=2%，每打一局游戏如果赢了，可以开箱，如果没开中，开箱爆率会加2%（最大为100%...

期望dp

2020-10-12

5 627

数学考试

思路：fx表示1-x的排列对于前(pi<x)的限制都满足，但是不满足x的限制条件的个数。fx初始为n！现在要去掉不合法的，为了避免重复计算,应该减去所有pi的贡献，即fpi(n-pi)!。*代码：** #include<bits/stdc++.h> #define int long...

dp 组合数学

2020-10-10

3 494

Searchlights

链接：https://vjudge.net/contest/399982#problem/D思路：其实就是个枚举，想明白的话就很简单，想不明白就会绕进去。题目其实很简单，就是考虑怎么通过向右向上走能出去，且走的次数最小。参考题解的枚举方式：在有效的监控中枚举，考虑横坐标差为x的监控向上走y步能够逃离...

枚举

2020-10-09

3 589

快速傅里叶变换和快速数论变换FFT&NTT

快速傅里叶变换(FFT) 作用：加速多项式乘法朴素高精度乘法时间O(n^2),但FFT能O(nlog2n)的时间解决前置知识： 1.点值表示法： f(x)={( x0,f(x0) ),( x1,f(x1) ) ,( x2, f(x2) ), ( x3, f(x3) ), ( x4, f(x4) ...

FFT NTT

2020-10-06

3 706

Ponk Warshall

链接：https://ac.nowcoder.com/acm/contest/7817/H原字符串与新字符串的字符构成一对，那么如果A-A这种就不需要换，若形如A-B就和B-A交换，但如果没有B-A呢？系统的归一下类：A-A 0次A-B B-A 1次A-B B-C C-A 2次A-B B-C C-D...

2020-10-01

3 506

Subsequence Count

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6155思路：考虑构造dpdp[i][j]表示前i个，以j为结尾的不同子序列有多少个。如果第i个是1，那么dp[i][1]=dp[i-1][1]+dp[i-1][0]+1,dp[i][0]=dp[i-1][0]...

递推式线段树矩阵 dp

2020-09-30

3 511

健康监测计划

链接：https://acm.ecnu.edu.cn/contest/317/problem/B/思路：按k我们来考虑k=0，那么肯定一个都不放，k=1，那么显然只能放一个，k=2呢？所有叶子结点都放，先去想k=4，那就是把叶子结点都去了，然后新的树中的叶子结点。k=3呢？就是k=4中，新选的点中随...

叶子节点树度深度贪心

2020-09-27

3 528

233 Matrix

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5015思路：我们可以考虑将每个列向量组看成由前一个列向量组通过线性变换得到的。矩阵快速幂的核心思想就是构造关系矩阵，即考虑当前列向量组如何由之前向量组左乘一个矩阵得到。那么考察某一列与之前一列的关系，我们发现...

矩阵快速幂

2020-09-27

2 548