思路：下降<=>上升   两种思路： 一. 1.递推中要确定最后一列的积木数量，就一定要直到前一个符合要求的方案最后一列的积木数量， 所以用[n块][m列][k最后一列数量]记录   求递推关系式，考虑最后一列，若最后一列使用的方块数<k，如从1,2,3,...,k-1，所有的方案数加起来等价于(n,m,k-1)   若最后一列使用的方块数=k(>k就不是这个数组元素了)，那么就是最后一列用了k个方块=>先把前面m-1列摆好(n-k,m-1,k-1)   故[n][m][k]=[n][m][k-1]+[n-k][m-1][k-1] int a[] //j->...

前言：这是一道01分数规划题，要用二分+验证解决。记枚举元素为x，sum(value)/sum(cost)>=x即满足要求,sum(value)-x*sum(cost)>=0;则sum(value-x *cost)>=0 sum()=>最大的前k项加起来 AC代码&思路: #include<iostream> #include<algorithm> using namespace std; long long tmpdp[10010]; int n,k; struct ty { int cost,value; }goods[10010];...

前言：第M大元素，依然可以用二分+验证解决。现在问题是如何验证。记二分枚举元素位x，则应找到>=x的元素大于k的区间个数。因为这种区间的第k大的数在数组b中一定排在x的前面或一块（相等）。如果区间个数>=m，说明枚举的x<=第m大元素，反之，x>第m大元素。 注意：二分查找要求元素有序，但是排序过后的数组元素的位置就变了。比如1,4,5,1,2,3,排序完变成112345，第一到第三个元素从145变成112，与原数组明显不同，所以要用一个数组存排序过后的来二分，一个存原始数组 思路&AC代码： #include<iostream> #include&...

前言：具有二分性质，在处理到某个人时，教室数量突然就<0，然后就不能再处理请求了。将处理的订单数作为二分枚举对象依旧是一道二分+验证的题,并且同前缀和与差分结合起来（注意：涉及到对区间大量的+-操作，一定不能直接操作，而是要维护一个差分数组，不然时间直接爆表）   思路&AC代码： #include<iostream> #include<cstring>//memcpy() using namespace std; int room[1000010]; int delta[1000010]; int tmpd[1000010]; int n; struct...

思路：一道最值问题，故尝试把组成牌的套数当作二分对象，假设需要组成牌的套数过多就一定组不成（有明显的区分点）。故使用二分枚举+验证，现在重点在于如何验证？这要用到抽屉原理的知识。每套牌不能有重复的，则最多一张joker，如果need>套数，则一定有重复的。且给出的joker数量要足够 AC代码： #include<iostream> using namespace std; #define int long long int a[60]; int n,m; bool solve(int x) { int need=0; for(int i=1;i<=n;++i) { i...

题目： 贝西从公牛那里收到了 N （1 <= N <= 50,000） 巧克力，但不想吃得太快，所以她想计划下一个 D （1 <= D <= 50,000） 天的巧克力吃时间表，以便在这些日子里最大限度地提高她的最低幸福水平。 Bessie 的幸福感是一个整数，从 0 开始，并在她睡觉时在一夜之间减半（必要时四舍五入）。然而，当她吃巧克力 i 时，她的幸福感会增加整数 𝐻 我 H 我 ​ （1 <= 𝐻 我 H 我 ​ <= 1,000,000）。如果她在某一天吃巧克力，那么她当天的幸福感就被认为是她吃完巧克力后的幸福程度。贝西坚持要按照收到的顺序吃巧克...

题目：有 n 件刚洗完的衣服，其中第 i 件衣服上含有 ai 单位水分。 自然晾干的情况下，每件衣服每分钟可以减少 1 单位水分。 有一个可以使用的烘***，同一时间仅能容纳最多一件衣服。 在使用烘***的情况下，每件衣服每分钟可以减少 k 单位水分。 烘***每次使用的工作时间必须是整数分钟，不足 k 单位水分的衣服放入烘***，其包含水分最多降低至 0 ，而不会减为负值。 当衣服包含的水分变为 0 时，表示衣服已经干透了。 请你合理利用烘***，使得所有衣服干透所需的时间尽可能少。 输出所有衣服干透所需的最小可能分钟数。   输入格式： 第一行包含一个整数 n 。 第二行包含 n 个整数 ...

前言：又是一道模板题，我感觉关于边界的问题不好考虑，确定好自己唯一的一种写法就好。我的写法是按照正常思路考虑，然后求<=的最后一个元素时将mid=l+(r-l+1)/2，即(l+r+1)/2，写成r-l可以将让两个int范围边缘的正数相加不超限。后附有二分代码与使用STL函数的代码 AC代码（学习二分思想）： #include<iostream> #include<algorithm> using namespace std; int a[200010]; int n; int solve1(int x)//找>=x第一个位置的下标 { int mid; i...

模板题，记住算了...想的有点晕 前言：首先要知道(a * b)%p==(a%p)*(b%p)%p; 因为这一题普通乘法用ull会超范围，只能用int128，但是int128要手写输入输出，所以还是用快速幂，快（慢）速乘算了 思路：如3^^5==3^^(0101)==3^^(2^^2+2^^0);然后每次都计算下一次 AC代码： #include<iostream> using namespace std; #define ull unsigned long long ull p; ull quick_mul(ull a,ull b)//实现了a*b%p { ull ans=0; ...

前言：这两道题需要二叉树的知识（不会的可以去B站搜搜），需要画图，但博客里好像没有在线画图的功能，所以我只能写写大致的思路了  题解31：https://ac.nowcoder.com/acm/problem/16692  PS：二叉树遍历知二求一，但已知先后序遍历不行，需要额外的特殊条件来将左右子树分开 AC代码&思路： #include<iostream> #include<string> using namespace std; string zhong,hou; void solve(int l1, int r1, int l2, int r2) { i...

前言：左右移操作一定要检查左右移的位数不是负数，两个等价的表达式，在边界数据输入后，结果天差地别 如：1<<n 和2<<(n-1),输入正数时两者等价，输入0时2<<-1未定义操作，会出现奇奇怪怪的值，使得输入函数的参数出错，最终无限递归，内存超限，所以当时我都想着用short来记录三种情况了，结果一直是90%内存超限（谁知道我改了多久，当时都想着用vector动态分配内存了）。但是下面的代码也没再改回来了，用short算了 PS:早知道用cmath中的pow了，@myself->get.reason(use too 复杂 "<<" rep...

题解29：https://ac.nowcoder.com/acm/problem/50999  听说这是递归的及格之作?[doge] 前言：首先我们要知道要处理几种的特殊情况： 1.(((3+5)^(1+1) 2.(3+5)))^(1+1) 3.(3+5)^(((1+1) 4.(3+5)^(1+1))) 分别对应开头，末尾，中间右边和中间左边位置的括号 思路&AC代码： #include<iostream> #include<cmath>//pow() #include<string> using namespace std; string s; i...

题解24：https://ac.nowcoder.com/acm/problem/15979  AC代码&思路：递归的话原则上太慢了 #include<iostream> using namespace std; long long solve(long long x)//就是在算二进制1的个数，我感觉还是自己举一些简单的例子比较好理解 { if(x<=1) {return x;}//递归的结束条件 x==0 f=0, x==1 f=1 if(x & 1){return solve(x>>1)+1;}//由二进制与十进制互化的知识可知，只有最后一位...

思路：因为一个二进制数做位运算，每个位的位运算独立，所以并不要枚举每个数，枚举每个二进制位分别是0或1，看运算完后的结果。 AC代码： #include<iostream> #include<string> #include<cstring> using namespace std; int a[35]; int b[35]; int main() { ios::sync_with_stdio(0);cin.tie(0); memset(a, 0 , sizeof(a)); for(int i=0; i<=34; ++i) { b[i]=1; } in...