Deep_Dark_FAntasy♂

未归档

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

/ 注册

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

拉格朗日插值法的介绍与应用

update 9.23 lagrange重心插值改进&&模板定理：给定n+1个不同数的取值，可以唯一确定一个次数不超过n的多项式。如何求出这个多项式可以使用拉格朗日插值法。拉格朗日插值法：假设我们得到了n+1个点，定义：xj的"开关"为：为什么称它为开关呢？因为构...

拉格朗日插值

2020-09-21

1 1068

B: Graph Theory Class 来自专栏

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6889伪图论题，板子找的好就能A。大概要求出这个东西：lcm(2,3)+min(lcm(2,4),lcm(3,4))+min(lcm(2,4),lcm(3,4))+min(lcm(2,5),lcm(3,5...

2020-09-21

2 657

Buy and Resell hdu-6438

题意：给出n，和a[i]代表第i天东西的行价，问收益最大是多少，在此前提下交易次数最少是多少？思路：维护一个小根堆，每次将堆顶与a[i]比较，如果a[i]<min,直接把a[i]放入，如果a[i]>min,那么可以a[i]-min就暂且作为我当前的收益，当然这不一定是最优的方案，考虑后面...

贪心

2020-09-17

2 497

翻硬币问题hiho1172

先看官方题解：这个游戏叫做Turning Turtles，它的本质就是Nim游戏。那么它到底是如何转化为Nim游戏的呢？让我们一步一步来分析。首先，我们先将局面分解一下，每一次我们只考虑一枚硬币。不妨设所有硬币全部背面朝上的局面为局面0假设现在N枚硬币，只有第1枚是正面朝上的。该局面只能转化为全部...

博弈 nim游戏翻硬币

2020-09-08

1 786

2020hdu多校第二场1001 Total Eclipse

题目链接：https://vjudge.net/contest/391866#problem/A题目描述：开始的想法是都减去最小的值，这样一个连通块就被分为了若干连通块，如此重复。但这样不好实现。可以反过来去想。既然删点困难可以考虑其逆过程，加点。把所有点从大到小排序，然后放入集合中，然后遍历所有这...

反向建图并查集

2020-08-30

1 409

H-Harmony Pairs 来自专栏

题目大意：给出n，问从0到n有多少数对(A,B)，满足A<B,但是A的数位之和大于B的数位之和？解题思路：数位dp。之前使用数位dp，都是求解一个范围[L,R]内满足某个条件的数有多少。这次是求满足条件的对数。学到的第一个是用空间换时间，就是把lima，limb之类的都写进dp里，形成一个5维...

数位dp

2020-08-29

2 723

A-Permutation 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5675/A思路：对于 i 位置若 a[i-1]* 2%p没有使用过就使用，否则就使用 a[i-1]* 3%p，若两个都已被使用，说明必定有冲突。代码： #include<bits/stdc++.h> us...

2020-08-10

2 577

E-Game 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5675/E题意：从右向左将木块推动，直到不能再推木块，求所有列的max的最小值。思路：比较直观的是二分答案M，然后从高度M，从右往左推，模拟。等价于求前缀平均值的最大。实际上从左往右先把所有能推到左边的都尽量平分到到...

二分模拟思维

2020-08-10

2 565

Fear Factoring(分块)

Problem C — limit 1 secondFear FactoringThe Slivians are afraid of factoring; it’s just, well, difficult.Really, they don’t even care about the factor...

数论整除分块

2020-08-08

1 742

计算方法：如何计算回文的阶梯型增长

今天做题时遇到了一个问题：对于一个序列S1,S2,S3,S4,S5,...,Sn如何计算以下的这些东西：i=1 S1+S2+...+Sni=2 S1+2S2+...+2Sn-1+Sni=3 S1+2S2+3S3+...+3Sn-1+Sn...i=n-2 S1+2S2+3S3+...+3Sn-1+Sn...

2020-08-07

1 494