acm训练记录及总结 - 萌音云笔记

acm训练记录及总结

2020-02-12 12:03:18

-------
# [Codeforces Round #611 (Div. 3)](https://codeforces.com/contest/1283)
## A. Minutes Before the New Year 
这题没什么说的，转化至分钟再相减，但还要提高下手速。
## B. Candies Division
这题根据题意给的公式以及样例来计算即可。
## C. Friends and Gifts
C题大致思路是对的，但是被hack了，hack点是3 0 0， 正确做法应该是将空位的下标存到一个数组里，再将能填的数字填到另一个数组里，通过模拟从小到大交叉插入即为答案。
需要注意细节问题。
## D. Christmas Trees
这题题意很简单，算法也很巧妙，这类题可以用BFS各个点进行拓展，称为多源BFS。
## E. New Year Parties
E题应该使用贪心算法，最大值很容易求，依次判断左中右就行了，最小值的话需要往右边靠，同时标记下当前的数是否操作过。

-------
# [Codeforces Round #515 (Div. 3)](https://codeforces.com/contest/1066)
这场整场都挺考验思维了，都需要点投机取巧。
## A. Vova and Train
第一题还是相对简单的，求整个区间灯的个数再减去被火车覆盖的就行。
## B. Heaters
第二题相对来说比第三题要难，但这题算是一种很经典的问题，在其他地方似乎见过类似的题目，应该积累下。
这题官方题解描述有点绕，自己本地debug代码运行过程才彻底理解。
设last表示最左端热水器的右端点，这样就能覆盖掉区间内的热水器，然后通过不断更新last在得到最终答案。
## C. Books Queries
C题是一道模拟题，根据题意不断更新左右端点。也是够可笑的，第一反应是想用树状数组，稍微想想发现不可行。
## D. Boxes Packing
D题正向遍历会有些麻烦，所以运用逆向思维，从后往前遍历，因为题意给的是每次将最左端的点去掉，所以我们从后往前遍历完肯定就是最大值。
## E. Binary Numbers AND Sum
官方题解相对来说更便于理解，给你一个二进制字符串，我们从低位开始扫描。
因为是与运算，所以只有当两个1运算才会对答案有贡献。然后直接用低位开始遍历即可，用p记录2的幂。

-------
# [Codeforces Round #612 (Div. 2)](http://codeforces.com/contest/1287)
这整场都有点难度。
## A. Angry Students
第一题太着急了，没彻底读懂题就直接交了一发wa3。。。就求两个A直接最长的P就好了。
## B. Hyperset
B题暴力即可，但题意有点抽象。百度到的一篇博客的思路很好，应当积累下来。已知两个字母求另一个字母的话可以不用一堆if来判定，只需要累加他们ascii码。
## C. Garland
C题是一道典型的DP，但比赛的时候一直在想贪心怎么wa了。
用一个三维dp[i][j][k]表示前i位填了j个奇数，且当前位置的奇偶性为k。
然后扫一遍的时候判断当前位置是否等于0，等于的话就要分两种考虑，一种是当前位置填偶数，一种是奇数。不等于0的话判断当前位置的奇偶性就好。

-------
#[Codeforces Round #527 (Div. 3)](http://codeforces.com/contest/1092)
## A. Uniform String
手速
## B. Teams Forming
手速
## C. Prefixes and Suffixes
C题就是根据题意暴力即可，赛时觉得太复杂，需要考虑的情况太多而没写。
## D1. Great Vova Wall (Version 1)
这题是一道彻头彻尾的思维题，运用栈的性质判断两个位置的差是否为偶数。
## D2. Great Vova Wall (Version 2)
D2运用了单调栈。
## F. Tree with Maximum Cost
F题需要用到一个新的知识点，换根法。换根适用于无根树找根，两个根直接产生的结果又有联系，可以互换的情况。
这种方法同时常用于树形dp。

-------
# [Codeforces Round #531 (Div. 3)](https://codeforces.com/contest/1102)
**知道了自己薄弱环节还是数学。思维还是不够跳跃**
## A. Integer Sequence Dividing
给你一个从1到n的序列，求将其分成两组使其差最小。
这题应该利用奇偶的特性，找到其规律n % 4 == 0 || n % 4 == 3。
## B. Array K-Coloring
B题想的太复杂，n和k和$a_i$的范围都很小，可以使用$O(n^2)$的暴力来写。
## C. Doors Breaking and Repairing
我觉得C才是真正的签到。 注意仔细读题。
## D. Balanced Ternary String
D题使用贪心的策略，假如0的次数大于n/3的话就从后面往前扫，将0替换成2以及1，其他的同理。
## E. Monotonic Renumeration
E题算一道思维题，找到重合区间最右端，转化为经典的线段覆盖问题。

-------
# [Codeforces Round #535 (Div. 3)](https://codeforces.com/contest/1108)
## A. Two distinst points
根据题意瞎搞搞。
## B. Divisors of Two Integers
B题思路很清晰，但是multiset运用的不够熟练。
## C. Nice Garland
C题因为数据不大，根据题意枚举出六种开头取最小的情况即可。
## D. Diverse Garland
D题和C题类似，以前好像做过类似的，就直接出思路了。
## E1. Array and Segments (Easy version) &&  E2. Array and Segments (Hard version)
E题赛时想假了，可能把最大值减小了。正规的解法应该假设没点都是最小值，还有存区间按照端点位置来存取。

-------
# [Codeforces Round #529 (Div. 3)](https://codeforces.com/contest/1095)
## A. Repeating Cipher
两分钟手速模拟题
## B. Array Stabilization
B题让你移除一个元素，使其剩下的元素中最大值减最小值最小。所以排序判断一下即可。
## C. Powers Of Two
C题可以将n转化成二进制，然后判断它是否能拆分成k份。
## D. Circular Dance
这类环状的题目似乎遇到很多次了，一直是自己的弱项。
可以以任一孩子作为第一个孩子，假设以编号 1 为第一个，编号1有两个相邻的孩子信息 a,b
如果 b 在 a 的顺时针方向，那么第二个孩子就是 a，反之为 b。
确定了前两个孩子后
i 从 1 开始遍历，第 i 个孩子的两个相邻的孩子a,b已经确定一个在 i+1 位置了，那么剩下的那个肯定在 i+2 位置，遍历到 n-2 却id确定最终序列。
## E. Almost Regular Bracket Sequence
E题是一道思维题，而括号序列是一个很容易被拿来出题的例子，应当积累。
这题的整体思路就是要知道一个括号要达到匹配规则，那么在匹配完符合条件的括号之后有多出来的两个左括号或者右括号。
其次从左边开始）不能比（多出两个以上，不然无法通过翻转一个得到符合规范的括号列，当刚好多出一个的时候这个括号必须翻转。
## F. Make It Connected
F题特么最小生成树裸题！还是应该所有题目都看一眼的。说不定能做。

-------
# [Codeforces Round #540 (Div. 3)](https://codeforces.com/contest/1118)
## A. Water Buying
签到两分钟
## B. Tanya and Candies
还算容易想，当拿掉第i个物品后，前i个的奇偶性不变，后面的相反，所以我们维护两个前缀和。
## C. Palindromic Matrix
这种题这辈子都不会了。。。
大模拟，但官方题解很良心，这也应该是程序员的基本素养，将代码简化到通俗易懂。
## D. Coffee and Coursework
D题分为D1和D2，但只是数据范围不同，所以直接写在一块。
正规做法是二分优化贪心。对答案进行二分，将mid天数贪心均分n杯咖啡。
## E. Yet Another Ball Problem
这题是思维题，读懂了题还是很好想的，就是有三种情况：
相邻的两对相同位置不能相同，例如(1, 3) (1, 4)；
任何两对不能相同，例如(1, 2) (1, 2)；
每对的两个数不能相同，例如(1, 1);
## F1. Tree Cutting (Easy Version)
F1可以写，F2就麻烦了。
它题意是给一棵树，有些节点是红色或蓝色，或无色，切掉一条边后分成两棵树且红蓝在不同的树；问有多少条边可以切。
所以我们可以用DFS求解出所有点以自己为根的子树 i 中1,2,节点的个数num1,num2，然后根据母树与子树之间的num1,num2值做差，能够得到 i 的另一部分的1,2,节点个数，然后再判断这两部分是否符合条件即可。
要注意**如果以i为根的子树含有两种颜色，它与它pre节点的边即使断开，也不符合。**

-------
# [Codeforces Round #544 (Div. 3)](https://codeforces.com/contest/1133)
## A. Middle of the Contest
找起始时间的中间时间就行。
## B. Preparation for International Women's Day
利用取模的性质即可，统计他们模k后的个数在匹对一下。
## C. Balanced Team
upper_bound()搞定。
## D. Zero Quantity Maximization
第一次遇到爆double的 需要用long double。
用map<long double, int> 存下他们相同的个数，还要额外加上a和b都等于0的情况。
## E. K Balanced Teams
E是一道dp题，设dp[i][j]表示从第i个同学开始，已经有j个队伍的情况下的最大人数。
然后用一个cnt数组统计下第i个同学开始能达到的最大人数。
这样的话就能有一个转移方程dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i]);
## F1. Spanning Tree with Maximum Degree
统计下他们的度，然后以度最大的点为顶点进行bfs就好了。

-------
# [Codeforces Round #473 (Div. 2)](https://codeforces.com/contest/959)
## A. Mahmoud and Ehab and the even-odd game
看题目就知道了。
## B. Mahmoud and Ehab and the message
map暴力。
## C. Mahmoud and Ehab and the wrong algorithm
C题是一道构造题，但题意自我感觉有点抽象。
就给你一个n，让你构造出两棵树。
## D. Mahmoud and Ehab and another array construction task
数学题，先打表筛选出mx内的所有素数，1e6内差不多有8e4个素数，所以mx开到2e6。
## E. Mahmoud and Ehab and the xor-MST
~~oeis是个好东西。~~

-------
# [Educational Codeforces Round 41 (Rated for Div. 2)](https://codeforces.com/contest/961)
## A. Tetris
统计最小出现次数就行了。
## B. Lecture Sleep
前缀和。
## C. Chessboard
需要点思维的模拟题，其实就两种类型，起点为0或者1，确定了起点，后续的点也就确定了。
## D. Pair Of Lines
计算几何。
给你n个点，问你能否让所有点都在两条直线上。
我们可以固定三个点，然后移除所有在线上的点，最后判断剩下的点是否在另一条直线上即可。
## E. Tufurama
抽象出题意就是求<i, j>对数，使得a[i] >= j, a[j] >= i 且(i < j)。
先记录满足i<=a[j]的最大下标idx(idx<j)，然后vec[idx].push_back(j)，这保证了第二个条件。
然后依次在树状数组中插入a[i]，并查询满足a[i]>=j的j的个数。
(为了利用树状数组，需要把a[i]压缩，因为大于n的a[i]等同于n)

-------

# [Codeforces Round #476 (Div. 2) [Thanks, Telegram!]](https://codeforces.com/contest/965)

## A. Paper Airplanes
公式题。
## B. Battleship
模拟。
## C. Greedy Arkady
经典的二分答案。
## D. Single-use Stones
没那么复杂，维护一个前缀和就行了。

-------

# [Codeforces Round #615 (Div. 3)](https://codeforces.com/contest/1294)

## A. Collecting Coins

签到。

## B. Collecting Packages

贪心的思想模拟下就好了。

## C. Product of Three Numbers

给你一个数n，问你能否找到三个数a b c，使得他们相乘等于n。

你可以一个根号筛选出因子就可以了。

## D. MEX maximizing

大致题意：

刚开始有一个空集合，会往里添加q次数，每次加一个值，而且你可以让这个数任意加减x若干次

每次添加后就查询当前最小的不属于这个集合的非负整数是什么。尽可能让这个最小的不属于这个数列的非负整数最大。

解题思路：

由于每次添加的数t可以加减任意次的x，故我们只需记录t%x，用num[i]表示i的个数

用ans去递增查询是否可以满足要求就行，如果num[ans%x]不为0，说明之前有一个没发挥作用的t可以用来顶替该位置上的ans，ans就可以+1去查询下一个

## E. Obtain a Permutation

我们先将所有数都减一，然后判断当前这位数时候能在当前列，在当前列的什么位置。

对于不能正确移动的数我们就通过这个改变这个值来强制改变。

最后计算一下每列最少需要多少次操作就行了。

## F. Three Paths on a Tree

想用lca来着，不知道哪里错了。。。(待补)
官方题解是先求出这课树的直径端点a b，然后枚举出c。
$res \ = \ \frac{dis(a,\ b)\ +\ dis(b,\ c)\ +\ dis(a,\ c)}{2}$

-------
# [Codeforces Round #480 (Div. 2)](https://codeforces.com/contest/980)
**注意模0和除以0的情况。**
## A. Links and Pearls
A签到题，统计o和-的个数。
## B. Malin
B题意有一丢丢难懂，可以根据样例来模拟，问情况考虑。
## C. Posterized
C其实也是暴力模拟。

-------
# [Codeforces Round #478 (Div. 2)](https://codeforces.com/contest/975)
## A. Aramic script
A都能被卡下，set忘记clear了。
## B. Mancala
模拟。
## C. Valhalla Siege
前缀和加二分。
## D. Ghosts
题意有点抽象，当某一时刻与其他点相遇，这两个点的权值都会+1，问你负无穷t到无限时间过后所有点的权值总和为多少。
就是你把他们时间相等的那个式子推出来就差不多了。
$aV_{xj}\ -\ V_{yj}\ =\ aV_{xi}\ -\ V_{yi}$

-------
# [Educational Codeforces Round 80 (Rated for Div. 2)](https://codeforces.com/contest/1288)
## A. Deadline
第一题我是真的觉得难懂。
给你n, d 判断是否存在一个整数x使得$x\ +\ \lceil \frac{d}{x\ +\ 1} \rceil\ \le\ n$
想用二分，标签也给了二分标签，但写了会似乎不太行啊。也找不到二分的ac代码。
最终还是被迫于暴力。
## B. Yet Another Meme Problem
B就有意思了，给你一个A, B，让你计算出(a, b)的对数${1\ \le\ a\ \le A,\ 1\ \le\ b\ \le\ B}$满足a*b + a + b = conc(a, b)。
我们可以从公式下手，最终推出来简化公式。
算一下在小于B时有多少个b满足$10^{n} - 1$算出 n 。再乘以 A 即可。
## C. Two Arrays
C用的dp，因为A不降B不升，所以$min_b\ \ge\ max_a$，那么我用将B翻转，于是能得到一个2m的单增序列。
设dp[i][j]表示到i选择的元素为j的方案，则$dp[i][j]\ =\ dp[i][j]\ +\ dp[i - 1][k]\ (k\ \le\ j)$;
$res\ =\ \sum_{i\ =\ 1}^{n}dp[2m][i]$
## D. Minimax Problem
[二分答案](https://www.cnblogs.com/pixel-Teee/p/12203748.html)

-------
# [Codeforces Round #554 (Div. 2)](https://codeforces.com/contest/1152)
## A. Neko Finds Grapes
签到，$min(odd_a,\ even_b)\ +\ min(odd_b,\ even_a)$
## B. Neko Performs Cat Furrier Transform
第二题有点意思，我们可以选择贪心的思想，将数变小直到1。
在这个过程中可能已经有答案出现，我们就停止循环。
每次将最高位的1变成0即可。
## C. Neko does Maths
数学题，题意很简单，就是给你两个数a, b，让你找到一个, 使得lcm(a + k, b + k)最小。
分析：我们可以转化题意为求gcd最大，因为设a < b, gcd(a, b) = gcd(b, a) = gcd(a, b - a)。
既然我们要求最大的gcd，那么就一定是俩数中最大的约数，而b - a又是定值，所以我们枚举b - a的约数，然后把a凑到含有此约数为止，因此需要凑的值k = x - a % x，当然，a%x=0时k=0.除此之外记得开ll。
## D. Neko and Aki's Prank
括号序列系列题目，DP。
给你一个n，问你长度为2n的所有合法括号序列建成一颗trie树，求trie树上选出一个最大不相交的边集, 输出边集大小。
肯定有奇数层，因为奇数层的点只能连向相邻的偶数层，就可以将边转化成点。
最终答案就是偶数层的点数。

-------
# [Codeforces Round #483 (Div. 2) [Thanks, Botan Investments and Victor Shaburov!]](https://codeforces.com/contest/984)
## A. Game
提交之前一定要注意考虑清楚各种点。
若为奇数，则直接输出中间这个值，若为偶数，则输出n / 2 - 1位置。因为拿大的那位为先手。
## B. Minesweeper
模拟题。
## C. Finite or not?
数论题。
题意：给你p, q, b。问你p / q在b进制下是否为有限小数。
首先我们能确定一点，当p能被q整除的话，则他一定是有限小数。
然后我们能发现，在10进制情况下，只有当q的因数仅有2和5倍数时，p / q才能是有限小数。
于是这启发我们猜结论：仅当q的质因数集合包含在b的质因数集合内时，p / q在b进制下才是有限小数。
[很详细的题解](https://blog.csdn.net/weixin_43960370/article/details/101478170)
## D. XOR-pyramid
区间dp问题。
[题解](https://blog.csdn.net/qq_34374664/article/details/80938924)

-------
# [Codeforces Round #616 (Div. 2)](https://codeforces.com/contest/1291)
## A. Even But Not Even
反思自己读题，总喜欢自己给题目加条件。
这题其实取两个奇数就可以了。
## B. Array Sharpening
因为元素不能相同；
找到变化后最长上升前缀和最长下降后缀进行比较就可以了；
## C. Mind Control
枚举区间。
## D. Irreducible Anagrams
给你一个字符串s，q次询问，每次问你s[l...r]是否至少具有一个不可约的字谜。
我们就看他的任意前缀中字符集个数时候不同就好了。
首先可以确定的是n = 1的时候一定是可以的，因为他要可约字谜一定是要分成至少两份。
然后当收尾字符不同的时候我们也一定能找到一个前缀中它们的字符集个数是不同的。
最后当字符中至少包含三种不同字符的一定是可以找到的，我们可以这样来放：
找到字符串中最后出现的一种字符，将其所有次数放在最前面，然后将s[n]全部接到后面，最后剩下的字符任意放置就好，这样的话我们肯定也是可以找到一个前缀中字符集是不相等的一种排列。

-------
# [Codeforces Round #484 (Div. 2)](https://codeforces.com/contest/982)
## A. Row
模拟。
## B. Bus of Characters
贪心。
我们可以用栈来优化，先按照w从小到大排序。
假如他是内向的人，我们就输出当前最小的没坐人的位置，然后入栈。
假如是外向的人，我们就出栈就好了。
## C. Cut 'em all!
给你一棵树，让你找到最大的可删除的边，使得剩下的联通块里点的个数均为偶数个。
首先我们可以确定的是当n为奇数的时候我们肯定是不能找到这种边的。
然后我们从一个点开始往下找，子节点数为偶数的话说明当前点与其父节点那条边就能被删除。
## D. Shark
还是很绕，待补！https://blog.csdn.net/weixin_39453270/article/details/80391161

-------
# [Codeforces Round #485 (Div. 2)](https://codeforces.com/contest/987)
今天收获很大。
## A. Infinity Gauntlet
虽然是签到题，模拟就行，但打错了单词。。。罚时++
## B. High School: Become Human
看着挺容易的，让你快速比较$$x^y$$和$y^x$的大小，我们两边同时取个log就可以比较了。但log的精度误差是不可控的。。
## C. Three displays
简单的dp，原理和最长上升子序列一样。
## D. Fair
D还是很好的。
题意：给出一个n个城镇m条边的图，给出每个城镇拥有的特产（可能多个城镇有相同特产）。有k种不同特产。
要求每个城镇需要其他城镇运输特产到自己的城镇，每个城镇必须拥有s种特产，那么在城镇满足s种特产后，需要的最短路径是多长，最短路指的是特产运输过来走过的边的数量。

分析：一开始没想到可以BFS，一直抓着最短路的方向，想多源应该用什么算法，却忘了最基础的BFS求出来的就是最短。

我们只有按个点进行BFS，当达到s种的时候return就好了。

## E. Petr and Permutations
这题就比较有意思了。
给你一个长度为n的排列，Petr对其进行3n次随机操作，Alex对其进行7n+1次随机操作。
给你一个结果，问你是谁进行的操作。

那么我们可以利用到排列的性质：对于一个排列，逆序数为奇数的排列称为奇排列，逆序数为偶数的排列称为偶排列。
所以只要求出逆序对就知道是奇数操作还是偶数操作。
又因为当n为奇数的时候，3n为奇数，7n+1为偶数；n为偶数的时候3n为偶数，7n+1为奇数。所以可以得出答案。
## F. AND Graph
位运算的一道好题。
给出m个大于等于0且小于$2^n$的不同的整数，如果两个数x&y=0，就把这两个数连接起来，问有多少个连通分支？
[题解](https://blog.csdn.net/qq_40507857/article/details/80574428)

-------
# [Codeforces Round #618 (Div. 2)](https://codeforces.com/contest/1300)
## A. Non-zero
签到题。
## B. Assigning to Classes
同签到题。
## C. Anu Has a Function
又是关于二进制的题目。
我们观察答案，对于答案的第 i 位而言，如果有大于等于两个数字，或者没有一个数字第 i 位的值为1，那么答案的第 i 位必定为0。
因为如果没有一个数字的第i位为1的话，显然第i位不可能有1，如果大于等于两个数字第 i 位为1，那么不论怎么这两个数（或这些数）的先后顺序，后一个数字在函数执行完后都必会把这一位变成0。
## D. Aerodynamic
一道披着计算几何的思维题，也怪自己读错题，以为点是随意输入的。
这题只要判断多边形是否是关于原点对称即可。
## E. Water Balance
贪心的思想。
当添加一个数进来时， 若比前面的数要小，则合并。
 若合并后的数比它前面的数还小，则继续合并，直到不能合并为止

-------
# [Codeforces Beta Round #27 (Codeforces format, Div. 2)](https://codeforces.com/contest/27)
## A. Next Test
第一题比较容易，就是给你n个数，输出从1～n第一个未出现的数，若都出现，则输出n+1。
## B. Tournament
读懂题后也是个模拟题，让你输出缺少的一场比赛结果。
## C. Unordered Subsequence
让你找任意一个无序的子序列，先判断是否有序，无序的话，我们自然可以找最短的，也就是长度为3的。
两种状态 大小大 和 小大小。
## D. Ring Road
多种解法的一道图论题。
第一种解法就是经典的二分染色，对他们相交的边建边，0101的染色即可。
第二种解法是刚学的2-sat，原理类似，对他们相交的边建边，然后跑一遍板子就好了。
## E. Number With The Given Amount Of Divisors
接触到的一个新概念：反素数。
对于任何正整数x，若其约数的个数记为g(x)，若某个正整数x满足以下条件则称x为反素数。
对于任意的0 < i < x，都有g(x) > g(i)。
** [反素数博客](https://blog.csdn.net/ACdreamers/article/details/25049767) **

这题就是道反素数的题，我们用一个DFS来遍历即可。
```cpp
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53}; // 前16个数相乘基本就超过1e18了

ll res = INF;

void DFS(int p, ll tmp, int num) { // p表示第几个素数, tmp为答案, num为因子个数
    if (num > n || p >= 16) return;
    if (num == n && tmp < res) res = tmp;
    for (int i = 1; i <= 64; i++) { // (1 << 64) > 1e18
        if (res < tmp) break;
        tmp *= prime[p];
        dfs(p + 1, tmp, num * (i + 1));
    }
}

```

最后修改于：2020-02-12 14:15:11