codeforces 1312E. Array Shrinking 题意： 相同的两个 x x x可以合并成 x + 1 x+1 x+1，给一个序列，问最后数组中最少能剩下多少个数。 思路: 数据500，很明显的区间dp数据。 考虑之前区间 s u m [ 1 ] [ j ] sum[1] [j] sum[1][j]表示 i ， j i，j i，j合并以后能得到一个 k k k，如果 k = 0 k=0 k=0，表示不能合并到一起。 先预处理 s u m [ i ] [ j ] sum[i][j] sum[i][j]的元素个数为 j − i + 1 j-i+1 j−i+1， s u m [ i...

codeforces 1325 E-Ehab’s REAL Number Theory Problem 原题： E. Ehab’s REAL Number Theory Problem 题意： 1. Every element in this array has at most 7 divisors. 2. 从中挑出几个数，使得他们的乘积为完全平方数，问你最少要挑几个？  题解：  Every element in this array has at most 7 divisors.  翻译一下就变成了：  该数组中每个元素的质因子不超过2个。 ①  这个条件肯定有用。 接着思考一下：如果我们...

codeforces 1325 F. Ehab’s Last Theorem 题意： ​ 给一个 n n n个点的无向图（无重边、自环），要找出包含不少于 ⌈ n ⌉ ⌈n⌉ ⌈n⌉个点的简单环或独立集。 题解： ​ 性质如果无向图中不存在不少于 ⌈ n ⌉ ⌈n⌉ ⌈n⌉个点的简单环，则必然存在不少于 ⌈ n ⌉ ⌈n⌉ ⌈n⌉个点的独立集。 ​ 证明：令 s q = ⌈ n   ⌉ sq=\lceil \sqrt{n} \ \rceil sq=⌈n ​ ⌉, 先找一个dfs树   ① \ ^①  ① ,标记节点深度，如果一条非树边(back-edges)连接的两个点的深度的差大于等于 s ...

Codeforces D. Prefix-Suffix Palindrome 题解： 和D1相同，区别是找中间的回文串要压缩时间，用到了马拉车算法。（算法介绍在下面： #include<bits/stdc++.h> using namespace std; #define ll long long ll maxlen, flg; string Manacher(string s1){  string s = "$#"; for (int i = 0; i < s1.size(); i++){  s += s1[i], s += '#'; } vector&...

codeforces 1326 E.Bombs 题意： 给定 [ 1 , n ] [1,n] [1,n]的排列p,q，将 p i p_i pi​依次加入初始为空的集合S， q i q_i qi​的值表示第i次加入的值为bomb。若加入的是bomb就把当前集合最大值从集合中移出(先加再移出)。现在规定对于每一个i， q 1 . . . q i − 1 q_1...q_{i-1} q1​...qi−1​都是bomb。求对于每一个 i ∈ [ 1 , n ] i∈[1,n] i∈[1,n]每次操作后集合中的最大值。 题解：  首先bomb越多，最大值一定不会变的更大，所以该序列一定为非递增序列。 用...

Educational Codeforces Round 84 题解 A-Sum of Odd Integers 题意：  n n n是否能表示为  k k k个不同的正奇数之和? 题解： k k k个不同不同的正奇数之和最小值为 k 2 k^2 k2 ，故仅当  n > = k 2 n >= k^2 n>=k2 且两数奇偶性相同时满足条件。要开long long不然wa. 代码： #include<bits/stdc++.h> using namespace std; #define ll long long void solve(){  ll n, k; ci...

codeforces 1332 E - Height All the Same(组合数学、奇偶性) 题意： 现在有一个 n ∗ m n∗m n∗m的方格，第 i i i行第 j j j列有 a [ i ] [ j ] a[i][j] a[i][j]个方块。 你可以执行以下操作任意次： 1、选择 ( i , j ) (i,j) (i,j)使 a [ i ] [ j ] a[i][j] a[i][j]加上 2 2 2。 2、选择两个相邻的方格，将其方格数加上 1 1 1。 现在问初始 a [ i ] [ j ] a[i][j] a[i][j]可以是 [ L , R ] [L,R] [L,R]中的任...

codeforces 1330 C.D.题解 Dreamoon Likes Coloring **题意：**给 n < = 100000 n<=100000 n<=100000个待染色的格子， m m m个 l i l_i li​对应 m m m次染色过程（ m m m种颜色)，第 i i i次染色的区间范围为 [ p i , p i + l i − 1 ] [p_i, p_i+l_i-1] [pi​,pi​+li​−1] , 其中， p i p_i pi​的值可从区间 [ 1 ， n − l i + 1 ] [1，n-l_i+1] [1，n−li​+1]中任选。每一个格子最...

LeetCode数独问题中Bitset的巧妙用处 36. 有效的数独 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。  数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。   上图是一个部分填充的有效的数独。 数独部分空格内已填入了数字，空白格用 '.' 表示。 示例 1: 输入: [ ["5","3",".",".","7",".","...

Morris 遍历 中序遍历 前言： ​ 我们在中序遍历的时候，一定先遍历左子树，然后遍历当前节点，最后遍历右子树。在常规方法中，我们用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点，但这需要我们付出额外的空间代价。我们需要用一种巧妙地方法可以在 O(1) 的空间下，遍历完左子树可以再回到当前节点。我们希望当前的节点在遍历完当前点的前驱之后被遍历，我们可以考虑修改它的前驱节点的  r i g h t right right

分数 题目 1/1 + 1/2 + 1/4 + 1/8 + 1/16 + … 每项是前一项的一半，如果一共有20项, 求这个和是多少，结果用分数表示出来。 类似：3 / 2 当然，这只是加了前2项而已。分子分母要求互质。 注意：需要提交的是已经约分过的分数，中间任何位置不能含有空格。请不要填写任何多余的文字或符号。 思路 通分，暴力求和，找满足最大公约数为一即为答案。 代码 #include<bits/stdc++.h> using namespace std; int gcd(int a, int b) {  return b ? gcd(b, a % b) : a; } int...

试题 A: 跑步训练 本题总分：5 分 题目 【问题描述】 小明要做一个跑步训练。初始时，小明充满体力，体力值计为$ 10000$。如果小明跑步，每分钟损耗 $600 $的体力。如果小明休息，每分钟增加  300 300 300的体力。体力的损耗和增加都是均匀变化的。 小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循环。如果某个时刻小明的体力到达  0 0 0，他就停止锻炼。 请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。答案中只填写数，不填写单位。 思路 模拟就行 代码 #include<bits/stdc++.h> using namespa...

codeforces Round680 C. Division 题解 题目 Oleg’s favorite subjects are History and Math, and his favorite branch of mathematics is division. To improve his division skills, Oleg came up with  t t t pairs of integers  p i p_i pi​ and  q i q_i qi​ and for each pair decided to find the greatest integer  x ...

Codeforces Round #677 (Div. 3) 题解 A. Boring Apartments 题目  题解 简单签到题，直接数，小于这个数的 + 10 +10 +10。 代码 #include <bits/stdc++.h> using namespace std; #define ll long long #define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); const int maxn = 2e5 + 10; int a[maxn]; void solve(){  ll ans = 0...