数位统计DP 给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0 ~ 9的出现次数。 假设 n = a b c d e f g n = abcdefg n=abcdefg 计算 d d d位上 x x x出现的次数 r e s res res记录答案 1、 ( 001 — — a b c − 1 ) (001——abc-1) (001——abc−1) x x x ( 000 — — 999 ) (000——999) (000——999) r e s + = a b c ∗ 1000 res += abc * 1000 res+=abc∗1000 2、 a b c ab...

状压DP 蒙德里安的梦想 求把 N ∗ M N*M N∗M的棋盘分割成若干个1*2的的长方形，有多少种方案。 先考虑横着放的情况 竖着放的自然唯一确定 状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示第 i i i列的每一行小方格被占用的情况 j j j为二进制数 1 1 1表示占用 状态计算 用 j j j表示 i i i列的状态 k k k表示 i − 1 i - 1 i−1列的状态 能从 i − 1 i-1 i−1列转移到 i i i列的条件 ① 两列没有冲突的情况 j & k = = 0 j \& k == 0 j&a...

树形DP 没有上司的舞会 状态表示 f [ u ] [ 0 ] f[u][0] f[u][0] : 所有从以u为根的子树中选择,并且不选择这个点的方案 f [ u ] [ 1 ] f[u][1] f[u][1]: 所有从以u为根的子树中选择,并且选择这个点的方案 状态计算 u u u为当前节点 j j j为子节点 f [ u ] [ 0 ] f[u][0] f[u][0]:不选当前节点 f [ u ] [ 0 ] = ∑ m a x ( f [ j ] [ 0 ] , f [ j ] [ 1 ] ) f[u][0] = ∑max(f[j][0],f[j][1]) f[...

功能: ①快速求前缀和 O ( l o g n ) O(logn) O(logn) ②修改某一个数 O ( l o g n ) O(logn) O(logn) 操作： ①：建树 void add(int x, int c) { //树状数组的插入操作 for (int i = x;i <= n;i += lowbit(i))tr[i] += c; } ②：区间查询：1 ~ x 前缀和 for(int i = x;i <= n;i += lowbit(i))res += c; ③：单点修改： for(int i = x;i;i -= lowbit(...

AcWing241. 楼兰图腾 在完成了分配任务之后，西部314来到了楼兰古城的西部。 相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。 西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。 西部314认为这幅壁画所包含的信息与这N个点的相对位置有关，因此不妨设坐标分别为 ( 1 , y 1 ) , ( 2 , y 2 ) , … , ( n , y n ) (1,y_{1}),(2,y_{2}),…,(n,...

AcWing242. 一个简单的整数问题() 给定长度为N的数列A，然后输入M行操作指令。 第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。 第二类指令形如“Q X”，表示询问数列中第x个数的值。 对于每个询问，输出一个整数表示答案。 输入格式 第一行包含两个整数N和M。 第二行包含N个整数A[i]。 接下来M行表示M条指令，每条指令的格式如题目描述所示。 输出格式 对于每个询问，输出一个整数表示答案。 每个答案占一行。 数据范围 1 ≤ N , M ≤ 1 0 5 1≤N,M≤10_{5} 1≤N,M≤105​, ∣ d ∣ ≤ 10000 |...

AcWing243. 一个简单的整数问题2(树状数组实现区间修改+区间查询) a 1 + a 2 + a 3 + a … a x a_{1}+a_{2}+a_{3}+a\dots a_{x} a1​+a2​+a3​+a…ax​ = = == == ∑ i = 1 x ∑ j = 1 i b j \sum^{x}_{i = 1}\sum^{i}_{j = 1}b_{j} ∑i=1x​∑j=1i​bj​ 给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一： 1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。 2、“Q l r”，表示询问...

AcWing 244. 谜一样的牛(二分) 思路 初始化所有数为1 代表没有用过 从后往前计算 找到还未用过的前k小的数是几 使得sum(x) == k成立的最小x即为答案 然后将这个数置为0 表示已经用过 有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。 现在这n头奶牛站成一列，已知第i头牛前面有 A i A_{i} Ai​头牛比它低，求每头奶牛的身高。 输入格式 第1行：输入整数n。 第2…n行：每行输入一个整数 A i A_{i} Ai​,第i行表示第i头牛前面有 A i A_{i} Ai​头牛比它低。 （注意：因为第1头牛前面没有牛，...

CodeForces - 1463D. Pairs 题意 将 个数，分成 对。其中 对进行取小操作，剩下的数进行取大操作。给你一个 个元素的序列 。问你 可以为多少种数，能得到 数组。 思路 将出现过的数字放在 数组 未出现过的数放在 数组 设 为 最多可以取多少次小 二分求 设 为 最多可以取多少次大 二分求 则 为最少可以取多少次小 最终 范围为 代码 #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 using namespace std; inl...

A.Non-zero 题意 对数组中任意一个数字执行不限次数的加一操作（ai = ai+1）使数组中所有元素的和、乘积都不等于零 思路 1.首先数组中不能存在0 否则乘积一定为0 所以 记录数组中0出现的次数cnt 对每个0都进行+1操作 ans += cnt2. 第一步保证了数组元素的乘积不等于0 要想使和不为零设原始数组中 各元素的和为sum 若 sum + cnt == 0 则只需对数组中的任何一个元素进行+1操作即可 ans += 1输出答案即可 #include<bits/stdc++.h> using namespace std; int a[105]; int mai...

A.Array with Odd Sum 题意： 给你一个数组 可以将数组中的任意一个数变成数组中存在的另一个数不限制这种操作的次数 问数组最后是否能变成这样一种状态：数组内所有元素的和为奇数我们可以分为以下几种情况 思路： 1.数组内所有元素都为偶数 这种情况下无法满足题意 2. 数组内的元素全部为奇数 这时又分为两种情况: (1).数组长度(元素个数)为偶数 不满足题意 (2).数组长度(元素个数)为奇数 满足题意 3.数组内既有奇数又有偶数 这种情况满足所有条件 综上 只要数组中有奇数但不全是奇数 即可满足题意 #include<bits/stdc++.h> using na...