第300场周赛 https://leetcode-cn.com/contest/weekly-contest-230/ 3-通过最少操作次数使数组的和相等：双指针+贪心 https://leetcode-cn.com/problems/equal-sum-arrays-with-minimum-number-of-operations/ 大意：给定两个数组a,b，里面的元素都是1-6之间的数，每次操作可以对任意数组中的任意元素修改为1-6之间的数，问最少操作数使得两数组的元素和相等。 思路：假设a的和比b的和大，那先对a从大到...

https://ac.nowcoder.com/acm/contest/9982#question D-牛牛与整除分块 https://ac.nowcoder.com/acm/contest/9982/D 大意：构造集合S={x: x =N/i, i=1,2,3...N},求n/x在S中第几大(S去重降序排序) 思路：先看n=10时S中有哪些数。 多列出几个数可以发现当时，,当时，x是多少，那么n/x就第几大。 所以当时，我们先求出n/x在右边集合中排第几，在加上左边的集合大小(左边集合大小为)就是答案。 #include <i...

数位dp一般两种解法：递推和记忆化搜索。解决的问题大多是某个数或某几个相邻的数在某位上出现或不出现的问题。 不要62 http://acm.hdu.edu.cn/showproblem.php?pid=2089 递推法： #include <iostream> #include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <string.h&gt...

Codeforces Round #702 (Div. 3) https://codeforces.com/contest/1490 A-Dense Array：贪心 #include <bits/stdc++.h> #define ull unsigned long long #define ll long long const int inf = 0x3f3f3f3f; const int mod =&nbsp...

OI周赛15 https://ac.nowcoder.com/acm/contest/4911#question B-三角形：动态规划O(n*m*10000) https://ac.nowcoder.com/acm/contest/4911/B 大意： 给n个背包，第i个背包有mi个物品的价值，从这n个背包中各取一个物品，总价值为这n个物品的价值和，求总价值前k的总价值和。 思路： 从背包中取物品，每个背包中的物品必取一个，由此联想的用dp来做。 先找状态：因为要求总价值前k的和，并且从数据上看来，一次选完后总价值不会超过10000，那就从1-...

周赛22 https://ac.nowcoder.com/acm/contest/11038 A-战争尾声：暴力O(200*200*n) https://ac.nowcoder.com/acm/contest/11038/A 思路： 给定的国家的范围再（1，1）到（200，200），那么依次计算这里面的每个点到各个国家的距离是否相等，找到相等的那个点即可，又因为如果有多个距离相等的点优先取x最小的，再x相等就去y最小的，那我们x从1开始遍历，y从1开始遍历，最先满足条件的就是答案。 #include <iostream> #include...

小白月赛31 https://ac.nowcoder.com/acm/contest/10746 A-A｜B：动态规划 https://ac.nowcoder.com/acm/contest/10746/A 题目大意： 给定a和x，找出有多少个b满足 1<= b <= x , a|b = a+b 思路： 我们先把a和x用二进制形式表示，然后从最高位到最低位填满b。 如果要a|b=a+b，那么a和b相同的位不能位1，只能为零。又因为1<=b<=x，如果a的第i位是0，x的第i位是0，并且x的前缀和b的前缀相同，那么b的第...

1007 求期望 思路： 对于每一种器材有两种选择，1/2的概率，根据乘法原理 1/(2^2)(a+b)(c+d) = 1/(2^2) (ac+ad+bc+bd) 可知等式右边就是所求的期望，可以合并成等式左边的式子，所有只要对每种器材的两个属性求和然后相乘取模，又因为最后结果要先乘2^n,所以最后的答案就是(a1+b1)(a2+b2)...(an+bn) #include <bits/stdc++.h> #define ll long long const int mod = 1...

https://ac.nowcoder.com/acm/contest/8827 E-Color：前缀和+二进制 https://ac.nowcoder.com/acm/contest/8827/E 题目大意：给定一组数，问有多少子区间满足子区间内的每种数的个数为偶数（even number）。 思路：以数组中的每一个为区间右端点，然后去找左端点，然后我们先求出1-n中每个数出现的次数。又因为这些数的大小在0-20之间，所有我们可以利用二进制的形式取记录这些数出现的奇偶次数，1 奇次， 0 偶次，如果要求某段区间内所有数出现都是偶次，在记录完这次二进制形式后，看看之前...

https://ac.nowcoder.com/acm/contest/8755 A-爱丽丝的人偶（一） https://ac.nowcoder.com/acm/contest/8755/A #include <iostream> #include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <string.h> #include &l...

第一场 https://ac.nowcoder.com/acm/contest/6218 B-魔法数字 思路：直接看样例，n=3,m=10,3首先可以变成4，2，9，然后4只能通过+1变成5，因为减1成3的话又回去了，平方的话变成16（**n最大不能超过m+m-n**，因为如果超过m+m-n的话要一直做减一操作变为m，那还不如直接一直加一变成m），所以只能加一，同理2可以变成1，9可以变成10，8结束，所以最受操作数是2，可以看出来这是一个广搜的过程，运用队列来实现，而用队列来实现的话通过哪个路径先到达m，哪个的操作次数就是最少，**同时要注意做减1操作的时候n不能小于0**...

第三场 https://ac.nowcoder.com/acm/contest/9246 简单的公式：快速幂 class Solution { public:     /**      * 返回c[n]%1000000007的值      * @param n long长整型 即题目中的n      * @ret...

数据结构：分块+线段树 https://ac.nowcoder.com/acm/contest/1168/G #include <iostream> #include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <string.h> #include <cmath> #include <bitset> #inc...

https://ac.nowcoder.com/acm/contest/8848#question A-优秀的拆分(power) 解法一： 任意一个自然数都可以拆分成若干个不同的2的幂次方的和，比如1100010100，相当于1不断向左移，而1向左移动一位就相当于乘2，题目说是正整次幂，所有二进制第一位不能为一，否则会加一，不和题意。 #include <iostream> #include <cstdio> #include <algorithm> #include <stack>...