题意： 就是个背包的题意，有n个物体和k个背包，输出最小的背包体积装下所有的物体， 不过装物体有个定义，要求先从大的装，直到装不下为止。 题解： 二分能做，但是这题二分没有唯一解啊！ 题解这么说的: 15 5 39 39 39 39 39 60 60 60 60 60 100 100 100 100 100 199 为一个合法的答案，但 200 不是，201 也不是 二分找最优解没法做 但是可以二分找局部解，然后枚举就行了。 这里我看了大佬的代码，也是过了，multiset果然好用啊，赶紧记一下。 代码：#include <bits/stdc++.h> using namespa...

题意： 就是给出你一个斐波那契数列，让你求第n项，n小于等于10的1e6次方。 题解： 斐波那契数列用矩阵快速幂求就行，这里不能二进制快速幂，需要转换到十进制快速幂，学到了 还有,一定要记得初始化，不然怎么超时的自己都不知道。 代码： #include <bits/stdc++.h> using namespace std; #define ll long long ll mod; char s[1000010]; struct node{ ll m[2][2]; node(){ memset(m,0,sizeof(m)); } friend ...

题意： 给出一个无向图，每条连通的点的距离都为1， 给出k个点，每个点上有一个人，每个人的步行速度是1，问最短需要多少时间，所有人能走到一个点上。 题解： 很好就能想出来，最短时间 = 相离最远的俩个人的距离/2，向上取整。 如何找这个最远的距离，用俩次bfs，这里不得不说真的很巧妙， 随意找一个人所在的点，dfs，找距离这个点最远的另一个人， 然后以找到的最远的那个人，再次bfs，和上面的bfs一样，找最远的第三个人。 那么答案就是第二遍bfs的距离， 不明白的可以在一条直线上画一下，就明白了。 代码：#include <bits/stdc++.h> using namespac...

题意： 题目意思很简单，就是给你俩个序列a和b。 输出最大的min(al....r)*sum(bl....r),这里min是区间的最小是，sum是区间和 题解： 首先处理a数组中的最小值，用单调栈得出每一个位置为最小值对应的左端点和右端点 考虑如何求最大值， 如果a[i]<0 那么就要最小化sum(b)， 如果a[i]>0 那么就要最大化sum(b), 现在问题转移到了求最大的sum(b)和最小的sum(b)在区间[l,r]上 记录b的前缀和，用线段树存放前缀和，求区间[l,r]的最大值和最小值， 最大化sum(b)就要用最大值-最小值 最小化sum(b)就...

题意：输入俩个序列，rmq(w,l,r)表示w序列从al到ar的最小值的下标 。题目要求输出最大的r，且要求区间1到r的rmq(w,l,r) == rmq(v,l,r)对任意的1到r的子串都相等 题解：定义俩个stack，从1到n，分别插入俩个队列的元素，始终维护这俩个stack的队首元素是以当前元素的最小的元素，如果俩个stack的大小不一样，就输出i-1，如果没有，输出n。准确的说stack的size是从1到当前值距离最小值的距离。 代码： #include <bits/stdc++.h> using namespace std; int a[100010],b[1000...

题意：题意是给出一个有向图，每条边的距离都是1，然后给出一个序列，即一条路径，输出一个该序列最小的子序列，且要求该子序列可以还原成原序列，差不多这个意思，读题读自闭了。题解：首先跑一边floyd，算出每个节点的最短路径，注意初始化。遍历序列，当n>3的时候，如果a[x][y] + a[y][k] == a[x][k]，那么就可以将中间的点给去掉，不影响走的路。 代码： #include <bits/stdc++.h> using namespace std; #define ll long long const int inf = 1e9+7; int a[110][110]...

题意：给出一个01字符串，输出一个字符串t，使得s和t的所有子串的非递减子序列长度相同，且0的个数最多 题解：从后面往前面找结果，记录0的个数和1的个数先考虑0：0肯定不变，要保证以这个0为起点的子串的最长的非递减子序列的长度下面考虑1：如果子串的非递减子序列包含这个1，那么前面肯定都是1，那么如果变成0，那么是不影响结果的。如果字串的非递减子序列不包含这个1，那么如果变成0，那么肯定会影响非递减子序列的长度结果显而易见：如果1的后面的1的个数>0的个数那么就可以将1变为0，否则就不能变。 代码: #include <bits/stdc++.h> using namespac...

有n个房间和n盏灯，你需要在每个房间里放入一盏灯。每盏灯都有一定功率，每间房间都需要不少于一定功率的灯泡才可以完全照亮。 你可以去附近的商店换新灯泡，商店里所有正整数功率的灯泡都有售。但由于背包空间有限，你至多只能换k个灯泡。 你需要找到一个合理的方案使得每个房间都被完全照亮，并在这个前提下使得总功率尽可能小。 Input 第一行两个整数n,k(1<=k<=n<=500000)。 第二行n个整数p[i](1<=p[i]<=10^9)，表示你现有的灯泡的功率。 第三行n个整数w[i](1<=w[i]<=10^9)，表示照亮每间房间所需要的...

有一块n*m的矩形巧克力，准备将它切成n*m块。巧克力上共有n-1条横线和m-1条竖线，你每次可以沿着其中的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为y1，y2，…，yn-1，而沿竖线切割的代价依次为x1，x2，…，xm-1。例如，对于下图6*4的巧克力， 我们先沿着三条横线切割，需要3刀，得到4条巧克力，然后再将这4条巧克力沿竖线切割，每条都需要5刀，则最终所花费的代价为y1+y2+y3+4*(x1+x2+x3+x4+x5)。 当然，上述简单切法不见得是最优切法，那么怎样切割该块巧克力，花费的代价最少呢？ I...

JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。 最近，JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成，并且想让“J、O、I”三个字母的出现次数恰好相同。 JOIOJI桑家有一份祖传的卷轴，上面写着一首长诗，长度为N，由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。 现在JOIOJI桑将这首长诗交给了你，请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。 Input 第一行一个正整数N...

D. Welfare State There is a country with nn citizens. The ii-th of them initially has aiai money. The government strictly controls the wealth of its citizens. Whenever a citizen makes a purchase or earns some money, they must send a receipt to the social service...

牛客第二场 A https://ac.nowcoder.com/acm/contest/882/A 你有n个点（0～n-1），按顺序形成一个环，初始时你在0的位子，你随机顺时针走一步或者逆时针走一步， 一旦你走到一个点后，环上所有点都被经过至少一次后，你就必须停下来。 问你最后停留在m这个位子的概率是多少。 你会发现落在0到n-1上的概率是相同的。。。。但是不会落在0位置处，所以加个判断 快速幂求分数幂就行了 结果输出的是前缀积。。。 #include <bits/stdc++.h> using namespace std; #defi...

牛客多校第二场 F题 题意就是给你2n个人，每个人之间都有相应的仇恨值，将这2n个人平均分成俩队，使得俩队之间的仇恨值最大 不会暴搜，还是自己多整理几个吧 https://ac.nowcoder.com/acm/contest/882/F #include <bits/stdc++.h> using namespace std; #define ll long long ll a[30][30]; int n; ll sum1 = 0,sum2 = 0; int s1[30],s2[30]; ll ans = 0 ; void dfs(int x,ll sum)...

有一个人从原点出发，然后有N个流星会在某个时刻落下，它们会破坏砸到的这个方格还会破坏 上下左右相邻的方块，输出最少多少时间之后他可以到达安全的地方，不可能则输出-1。 https://ac.nowcoder.com/acm/contest/997/I 直接看代码更好懂 #include <bits/stdc++.h> using namespace std; #define ll long long int n; int a[1010][1010]; int sx[6] = { 0 , 0 , 0 , 0,-1, 1}; int sy[6] = { 0 , 0...