思路  设cnt[i]表示当前层摆放的宽度，h[i]表示当前层摆放的最大高度 因为上层的宽度不能超过下层的宽度，所以我们可以从后往前优先考虑上层宽度 利用前缀和的思想来求放在同一层合并后的宽度  代码 // Problem: Tower of Hay // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/24881 // Memory Limit: 65536 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #inc...

做法：dp 思路  设dp[i]为打死第i个鼹鼠时，最多打死鼹鼠的个数（一定打死第i个鼹鼠的情况） 因为游戏开始时，你可以自由选定机器人的初始位置，一定会打死一只鼹鼠，所以初始化把dp[i]设为1 之后枚举前后两只鼹鼠，如果距离小于等于时间，说明在这时间内能打死两只鼹鼠，同时更新答案即可  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i+...

做法：数论+快速幂+离散化 思路  如果不删任何数的话就是设不能取的值和为那么结果就是 不能取的值最多有1e5，我们可以采用离散化来存 没有限制的数我们可以采用快速幂来计算 注意要判重  代码 // Problem: [HAOI2012]容易题(EASY) // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/19989 // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) ...

做法：状压dp+区间dp 样例解释 第 3 行到第 6 行表示长度为 2 的 4 种 01 串合并方案。00→1，得 10 分，01→1 得 10 分，10→0 得 20 分，11→1 得 30 分。 思路  设是在区间中状态为的最大分数 因为m个字符能合并成1个字符 所以我们可以求出在len长度的字符串，合并之后的长度为 由于我们每次合并都是以m为长度，所以右端点不必挨个枚举，每次减去m-1即可 设k为的分割点我们可以枚举区间内的状态为区间相当于已经合并后的状态(0 or 1)那么的值就是字符串(s + (0 or 1)) 当如果res==m-1，说明该串可以被合并，我们就去找每个合法状态中...

思路  叶结点只能挂在叶结点上，而父结点可以挂在父结点上也可以挂在叶结点上 所以优先从叶结点开始挂装饰品，利用叶结点的花费来更新父结点的花费，并记录该父结点下的叶结点装饰品的数量  代码 // Problem: Tree Decoration // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/24623 // Memory Limit: 65536 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include...

做法：线段树 思路：  看到区间修改区间查询联想到线段树 区间内加上一个首项为k公差为1的等差数列在pushdown操作可以在左子树的lazy为当前结点的lazy，右子树的lazy为当前结点的lazy加上左子树的长度sum利用等差数列求和公式  代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=200005; int n,m; ll a[N]; struct node{ int l,r; ll lazy,v; }tree[N<<2]; void pushu...

题意 有n个数，其中位置b的数一定大于等于位置a的数,且a和b之间的数都比a小。已知最大的数的位置及大小。求这n个数的可能的最大值。 做法：差分 思路  因为每个数要尽可能大，所以a和b相等，且a+1~b-1的数比a小1 区间内的数同时增大或减小某一个数可以用差分处理  代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define...

思路  把左右和上下选择分开讨论 先考虑左右的情况如果右边的点选左方向，左边的点选右方向，这样的话需要计算w其他情况求最大即可 上下也是这种情况  代码 // Problem: 网格 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/E // Memory Limit: 524288 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using...

思路 本题关键点在于模数是3这样子就可以转化为根据二项展开式 可以得到系数又因为模数非常小，组合数可以用Lucas定理计算 代码 // Problem: 系数 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/B // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace s...

思路  将整个数组进行分割，使每个子数组都包含1~k至少一次 我们可以选取每个子数组最后一个数，再加上任意一个数即可组成最短不存在子序列  代码 // Problem: The Cow Lineup // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/106586 // Memory Limit: 60000 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include <iostream> #in...

做法：状压dp 思路 每个点与附近连边的点用二进制状态表示，1表示有边，0表示无边该状态选取的点也用二进制状态表示，1表示选了，0表示没选选取该点的值后的差值为该点的值减去转移前的差值 代码 // Problem: 树上博弈 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/E // Memory Limit: 524288 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bi...

思路  记录怪物的第一次第二次出现时间can[]表示叶妹妹是否具有攻击这个怪物的能力num[]表示叶妹妹不能攻击该怪物的数量sum表示叶妹妹能杀怪物的数量 根据贪心策略，每一次泽鸽鸽优先攻击自己没有攻击过且第二次出现早的怪物，这样子叶妹妹就越早能杀怪如果这一时刻不存在泽鸽鸽优先没有攻击过的怪物，那么泽哥哥就随便杀一只  代码 // Problem: 模仿游戏 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/G // Memory Limit: 524288 MB // Time Limit: 6000 ...

思路  先判断从s开始是不是能走到t 二分中位数的大小如果相邻的两个点都大于等于mid，中位数能达到mid如果大小大小交替走也成立  代码 // Problem: 美丽的路径 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9985/A // Memory Limit: 524288 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using nam...