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)连...

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 += ...

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(){ ...

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...

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

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 ...

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(){ ...

Leetcode 327. 区间和的个数 (前缀和 + 离散化 + 树状数组) 题目 题意 有多少个连续的子数组，其和在 [ l o w e r , u p p e r ] [lower, upper] [lower,upper]之间 题解 可以想到的做法：用前缀和在 O ( 1 ) O(1) O(1)查询 [ i , j ] [i, j] [i,j]的和，枚举所有的二元组 [ i , j ] [i, j] [i,j], 满足条件就加上。 可以优化为： P r e Pre Pre为前缀和数组， 从小到大枚举 j j j， 由于 lower ≤ P r e [ j ] − P ...