沈某

分类

bm(1) dp(1) 未归档(8) 贪心(1)

/ 注册

全部文章（共11篇）

2015 ACM National Contest Romania G - Por Costel and the Orchard Gym - 100923G （好难的dp）

问题给一个NxM的矩阵，找一个联通块，让这个联通块的权值最大。有这么几个要求： 1.每一行不能间断地取点，也就是每一行必须取一段连续的区间。 2.下一行如果取了那么与上一行必须有相交的部分，也就是要联通 3.不能不取，至少取一格（ 1<=T<=4,1<=n,m<=30...

2019-08-02

0 598

2019牛客多校第二场B

先保存一下代码。 /*Q:每次可以走1-k步，起点为0，问经过n点的概率（n<=1e18,t<=10,k<1021） dp[i]=(dp[i-1]+dp[i-2]+....+dp[i-k])/k; n-> oo,p=2/(k+1) 证明：走k步期望走出的距离是 1+2...

BM线性递推

2019-07-25

0 907

hdu6125 Free from square（状态压缩+分组背包）

题意：在从1-n个数里选不超过m个数，至少选一个，这些数的乘积没有平方数因子（除了1），有多少种选法。思路大致是一个状态压缩+分组背包的问题。其实还没怎么搞懂，先贴上代码，尝试写了一些注释，有问题可以留言交流 #include<cstdio> #include<al...

2019-04-19

0 630

Educational Codeforces Round 62 (Rated for Div. 2)C. Playlist（优先队列）

题意给n首歌，最多选择其中的k个，每首歌有一个长度t和美丽度b，你的愉悦度是你选择的歌曲的总长度*这些歌曲中美丽度最小的那个数。思路: 给这n首歌按歌的美丽度从大到小排序，从前往后遍历。每次我们把我们当前的这首歌的长度塞进优先队列（从小到大）如果长度大于k，队首出列，当前的愉悦度就是队列...

优先队列

2019-04-09

0 523

2019西北工业大学程序设计创新实践基地春季选拔赛(重现赛)C Chino with Queue(状压dp)

C.Chino with Queue 题目描述 Chino的数学很差，因此Cocoa非常担心。今天，Cocoa准备教Chino和排队有关的问题。我们总是会学各种排列组合的问题，那些题目大多数都是套路。而Cocoa不喜欢套路。通常来说，每个人在排队的时候都会对前一个人有所意见，而如果他们排在第一...

2019-04-06

0 597

大数卢卡斯求组合数板子

f数组是求阶乘的，可以开大点。 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespa...

2019-04-06

0 712

洛谷P2480[SDOI2010]古代猪文(卢卡斯+费马小定理+中国剩余定理)

题意： @#¥&《？…%&…¥&#¥%%%#¥%&……#……%……&*%……&*¥…&%&¥…%#¥%……（一大堆废话）求根据费马小定理，可以转化为求关键就在于求那个指数。首先这个数比较大，卢卡斯开不了这么大的数组，那怎么办呢...

2019-04-01

0 456

2019CCCC团(zi)体(fu)天(chuan)梯(mo)赛(ni)总结

2019CCCC团(zi)体(fu)天(chuan)梯(mo)赛(ni)总结 Day1: 中午开始坐了5h的绿皮到沈阳…没撒好说的晚上去吃队友在东大的同学强烈推荐的李连贵熏肉大饼，直到下了taxi我才意识到这个店名貌似有点？？？？？某李姓队友刚经历了蓝桥杯的暴击，难道又要在这连跪？？？？？最后…...

2019-03-30

0 657

POJ3017 Cut the Sequence（单调队列优化dp）好题！！必做！！

Cut the Sequence POJ - 3017 Given an integer sequence { an } of length N, you are to cut the sequence into several parts every one of which is a cons...

2019-03-28

0 850

最长下降子序列O(n^2)及其方案数

直接贴代码，可以直接用 len是长度，ans是方案数 #include<cstdio> #include<algorithm> #include<map> #include<cstring> #include<queue> #define...

2019-03-14

0 501