shyyhs

分类

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3901人学习

AtCoder思维大提升

6篇文章 753人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 848人学习

全部文章（共469篇）

关于背包二进制分解来自专栏

因为任何数都可以用二进制表示,在你的价值里面..然后最后一堆可以放一起的原因是前面可以表示任何数了,最后一堆无非就是填充最后一个1.举个栗子.假设我有个数10101010,很显然的一个结论10000000>1000000+100000+10000+1000+100+1.然后我主位的那个1肯定是...

DP

2020-08-03

3 552

Vladik and Memorable Trip 来自专栏

cf的每个dp题,都有它的特点吧,这个dp就很有特点,但是不难,也没什么好说的..代码如下: #include <bits/stdc++.h> using namespace std; const int N=5e3+5; int dp[N],a[N],w[N],e[N]; bool ...

DP

2020-08-03

1 509

质数与合数来自专栏

一个模拟题,得在自己清醒的时候打...不然就会乱坟岗..思路很简单,就是找到两个质数是不是差>(k+1),因为我们都足够聪明.那么,你下次肯定会取1(假设我是FFF),而我取k都到不了,那么我必输.其它肯定是我必胜,因为1,2,3你都不能取.所以这题就没了.但是,细节是真的多...具体看代码吧...

模拟数论

2020-08-03

1 699

Mike and gcd problem 来自专栏

挺有意思的一个题目,但是因为放在dp专题,所以在想怎么dp...还是不会dp,在网上也没找到dp的题解...至于这题性质,脑袋编译了下,但是没继续深入证明把他们全部变成偶数即是最优解...在这里阐述下证明..首先假设它们的gcd()为1.那么怎么操作才能使得方案数最小呢?先对序列进行分类分奇偶..首...

数论

2020-08-03

1 745

k-Tree 来自专栏

ll dp[N][N][2];//深度i 总权值为j 是不是存在权值大于d的边..然后随便转移就好了... #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; c...

DP

2020-08-02

0 559

兔子的排列来自专栏

题目的意思就是一个序列本来是0,1,2...n-1.然后要你变成p[0],p[1],p[2]...p[n-1],通过交换相邻的两个数每两个相邻的数都可以交换一次,你可以选择交换的顺序.问你有多少种交换顺序?很有意思的一道记忆化搜索题目,emm,大佬教我做的...具体怎么做呢?就是一个典型的分治,加记...

DP

2020-08-02

3 878

Word Cut 来自专栏

一道cf的dp题,也挺好的,虽然没牛客难..牛客还是牛/..这题是可以选择单词断开然后连起来,类似环.考虑dp,令dp[0][i]为操作i次是原串的方案数,dp[1][i]为操作i次是其他串的方案数.然后显然就有两个dp方程. dp[0][i]=dp[1][i-1]*(n-1). dp[1][i]=...

DP

2020-08-02

1 714

随风飘来自专栏

是一个组合数学问题,朴素的对于每个都不取k,那就是两个for的事.但是对于取k,我们应该如何分析呢?总的是n,我们拿走k个.在拿走的过程中,我们考虑始终保留两个特殊的,假设说我不存在取的过程,那么这两个产生的贡献必定是一次lcp.但是我们考虑拿走,这个它会多几次呢?其实也挺显然的,C(n-2,k)考...

组合数学

2020-08-01

4 863

网格填数来自专栏

不努力永远都只能是菜鸡,菜鸡..这题咋一眼看会觉得很难,但是呢.首先的矩阵大小是hw的,但是他只要求nm的任意加起来为奇数.当然题目似乎没讲只能填1~9的数..你会发现假如第一个nm的矩阵确认,那么符合条件的填法也是确认了..因为为了维护奇数,我平移一个数,移进来的数和移出去的数奇偶性一定是一样的,...

DP

2020-08-01

7 724

网格游戏

期望dp哎,虽然以前也写过,但是不系统..虽然看到还是很迷茫的.题目描述: 有一个游戏平板上面有n×m个格子，一开始每个格子都是关闭的，每个格子里面都有一个标记已知每种标记恰好出现两次，也就是一共有n*m/2种标记规定一次移动为依次(one by one不是同时)打开一对格子查看里面的标记，如果...

DP

2020-08-01

12 1173