问题 给一个NxM的矩阵，找一个联通块，让这个联通块的权值最大。 有这么几个要求： 1.每一行不能间断地取点，也就是每一行必须取一段连续的区间。 2.下一行如果取了那么与上一行必须有相交的部分，也就是要联通 3.不能不取，至少取一格 （ 1<=T<=4,1<=n,m<=300 ,-1e4<=a[i][j]<=1e4） 思路 首先，我们很容易想到一个dp dp[i][j][k]表示到第i行，区间为j-k与上面联通的最大价值。 与区间[j][k]联通也就是上一行左右端点有至少有一个在[j][k]之内 这个代码比较好写，如下 for(int i=2;i&l...

先保存一下代码。 /*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+...+k =k(1+k)/2 也就是每段k(k+1)/2中，每个点被踩到的概率是 k/(k(k+1)/2)=2/(k+1) 所以无穷远处的点被踩到的概率就是2/(k+1) 考虑暴力，复杂度nk ，tle 考虑矩阵快速幂，复杂度k^3logn,tle bm线性递推 k^2logn，ac ...

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

题意 给n首歌，最多选择其中的k个，每首歌有一个长度t和美丽度b，你的愉悦度是你选择的歌曲的总长度*这些歌曲中美丽度最小的那个数。 思路: 给这n首歌按歌的美丽度从大到小排序，从前往后遍历。 每次我们把我们当前的这首歌的长度塞进优先队列（从小到大）如果长度大于k，队首出列，当前的愉悦度就是队列中所有元素的总和*当前这首歌的美丽度。为什么呢？？因为我们是按歌曲的愉悦度从大到小排序的，那么我们当前的愉悦度肯定是我们队列里面最小的那个愉悦度，然后我们又是让队列中最小的先出队，即保证队列里面的sum总是前i个的最大值，那么答案不就是a[i].w * sum么。考虑如果我们当前的这个t是一个很小的...

C.Chino with Queue 题目描述 Chino的数学很差，因此Cocoa非常担心。今天，Cocoa准备教Chino和排队有关的问题。 我们总是会学各种排列组合的问题，那些题目大多数都是套路。而Cocoa不喜欢套路。 通常来说，每个人在排队的时候都会对前一个人有所意见，而如果他们排在第一个，也会颇有微词。因此，排一个尽可能让更多人满意的队伍是一件难事。 假设我们要给n个人排队，Wij表示了j排在i之前一个给i带来的舒适度，Wii而就表示了i排在第一位的舒适度。 通过一番模拟，Chino当然计算出了最优的方案，不过Cocoa希望Chino能计算地快一点。 题目对于Chino来说太难啦...

f数组是求阶乘的，可以开大点。 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; #define inf 0x3f3f3f3f #define ll long long #define mod 1000000007 #define maxn 1000005 ll f[maxn]; void init(){ f[0] = 1; for (int ...

题意： @#¥&《？…%&…¥&#¥%%%#¥%&……#……%……&*%……&*¥…&%&¥…%#¥%……（ 一大堆废话） 求 根据费马小定理，可以转化为求 关键就在于求那个指数。首先这个数比较大，卢卡斯开不了这么大的数组，那怎么办呢？？？我们可以看到999911658不是一个质数，因式分解可以得到999911658=2 x 3 x 4679 x 35617;我们就可以得到以下同余方程组 x就是我们要求的那个指数 用中国剩余定理解这个方程得到x 不会的同学可以跟着我一起复习一下： 已知： 上面那张图,假设有k项 我们令 ...

2019CCCC团(zi)体(fu)天(chuan)梯(mo)赛(ni)总结 Day1: 中午开始坐了5h的绿皮到沈阳…没撒好说的 晚上去吃队友在东大的同学强烈推荐的李连贵熏肉大饼，直到下了taxi我才意识到这个店名貌似有点？？？？？某李姓队友刚经历了蓝桥杯的暴击，难道又要在这连跪？？？？？最后…熏肉大饼真香 Day2: 第二天没想到沈阳直接下雪…？？？ 下午一点比赛开始，因为网络有延迟点进去就看见第一题已经有200多人ac了？？？看了一眼题意直接在提交框里写了一发，提交，ce…发现是编译器选错了然后又提交…ac。然后打开cb，看了一下第二题，字符串模拟，好的，敲了大概10min，提交，ce...

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 consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. ...

直接贴代码，可以直接用 len是长度，ans是方案数 #include<cstdio> #include<algorithm> #include<map> #include<cstring> #include<queue> #define inf 0x3f3f3f3f #define ll long long #define maxn 100005 using namespace std; int a[5005],dp[5005]; ll num[5005]; int main(){ int n; scanf(&qu...

POJ1185炮兵阵地(状压dp) 学了两周的状压dp，终于把这道题a了… 参考的这篇大佬的博客学习的状压 点这里 题意: 给一个N X M的地图，其中P代表平原能放一个炮兵，H代表一个山不能放炮兵，每个炮兵可以打到上下左右相距为2的距离。问在炮兵互不伤害的情况下地图上最多能放多少个炮兵。（N <= 100,M <= 10） 思路： 看到数据范围和显然这是一道状压dp的题目，首先我们把地图处理好，P用0表示，H用1表示，每一行看作一个二进制数，然后我们把每行所有的可行状态dfs出来。然后再dp就可以了 dp[i][j][k]表示第i行第j个状态，第i-1行第k个状态的最大...

牛客练习赛40 D题有没有人用O(n)的写法啊