AtCoder - 競プロ典型 90 問 - 记录

# [001 - Yokan Party](https://atcoder.jp/contests/typical90/tasks/typical90_a)

Difficulty : 4 / Yellow

题目要求出分完段后最小段的最大值(包含最小值最大),容易想到二分答案.

二分答案$[1,L]$,在```check```函数中枚举每一个裂口,只要当前长度大于等于答案,累加段数.最后段数如果大于等于$K$,返回```true```,因为段数大可以合并任意两段而不改变最小值.

# [002 - Encyclopedia of Parentheses](https://atcoder.jp/contests/typical90/tasks/typical90_b)

difficulty : 3 / yellow

数据范围$N\leq20$,可以直接暴力递归.

每次递归到头时在判断是否是正确的括号序列(~~剪枝太麻烦~~).

# [003 - Longest Circular Road](https://atcoder.jp/contests/typical90/tasks/typical90_c)

diifficulty : 4 / yellow

贪心.

答案是树的直径$+1$,用反证法证明:

一棵树直径在最上边,其他点垂在下面.假设最优解是直径一端$A$到直径上非端点的另一点$C$,设另一端点为$B$,设集合$S_i$表示子树$i$中所有点,那么答案就是$|AC|+\max_{D\in S_C}|CD|+1$,直径解答案为$|AB|+1$,而我们能知道,$|AC|+\max_{D\in S_C}|CD|\leq|AB|$(否则它就是直径了).所以直径解一定永远不劣.

求出树的直径,答案为直径$+1$.

# [004 - Cross Sum](https://atcoder.jp/contests/typical90/tasks/typical90_d)

difficulty : 2 / orange

先求出每一行每一列的总和,输出该店所在行和加列和,再根据容斥原理减去点的值.

# [006 - Smallest Subsequence](https://atcoder.jp/contests/typical90/tasks/typical90_f)

difficulty : 5 / green

普通的01背包时间复杂度是$O(N^2)$,过不去.而这道题可以考虑贪心.因为答案串的长度已经给定,字典序只与第一个不相同的字符大小有关,所以只要每一步都求出范围内符合条件的最小的字母,即可以拼成答案串.

那么对于每一个位置,它的范围是什么呢?还是因为只要前面最大,无需考虑后面,所以只要把后面留出全加上正好凑齐的个数就行.维护最大值用优先队列,先将第$[0,n-k)$个字母加入堆中,然后枚举$[n-k,n)$,每次加入$s_i$,取出最大值,直接输出即可.

用堆维护的同时,有一个问题,"子串"必须是原序列的顺序,所以每取完一个,它前面的所有字母都不能再取,于是可以用```std::pair<char,int>```加入堆,第二关键字存当前字母的下标,加入堆中.输出时,只要第二关键字小于上一个的下标,就直接```pop```掉就行了.

因为每个点只会入堆一次,部分点出堆一次,所以总体上时间复杂度还是$O(N\times \log_2 N)$.

# [007 - CP Classes](https://atcoder.jp/contests/typical90/tasks/typical90_g)

difficulty : 3 / yellow

类似于匹配的题目,可以用得到双指针.但是这道题细节还挺多.需要把$a_0$置成负无穷,将$a_{n+1
}$置成正无穷.

但是一个$10^9$级别的数减去负无穷就会得到正无穷加$10^9$,会爆掉.所以负无穷就设置成$-10^9$.而同理,正无穷设置成$2\times10^9$.

# [008 - AtCounter](https://atcoder.jp/contests/typical90/tasks/typical90_h)

difficulty : 4 / green

朴素的动态规划时间复杂度是$O(N^2)$,明显超时.那么可以把所有不属于```atcoder```字符串的字母都删掉,但最坏情况下还是$O(N^2)$.于是发现,对于一个字母,它的方案数是它前面所有位置在它前一个的方案数总和,没有其他限制条件,所以可以设$f_i$表示```atcoder```串中第$i$个字符截至目前的方案数,转移方程为$f_{s_i}=f_{s_i}+f_{s_i-1}$.时间复杂度$O(N)$.

# [010 - Score Sum Queries](https://atcoder.jp/contests/typical90/tasks/typical90_j)

difficulty : 2 / orange

简单的前缀和,$a_i$统计$1$班前缀和,$b_i$统计$2$班前缀和,注意每一个$i$都要算$a$和$b$.

# [012 - Red Painting](https://atcoder.jp/contests/typical90/tasks/typical90_l)

difficulty : 4 / green

并查集维护联通块.只要想到并查集就不难了.每次把一个点变红时,枚举它上下左右四个方向上的所有点,是红色就该点所在加入联通块,询问时判断两点是否都为红且在一个联通块中.

# [013 - Passing](https://atcoder.jp/contests/typical90/tasks/typical90_m)

difficulty : 5 / green

比较简单的5颗星难度,只需要将$1$和$n$分别作为起点跑一遍```dijksrta```即可.

注意无向图,边数为$2\times m$.

# [014 - We Used to Sing a Song Together](https://atcoder.jp/contests/typical90/tasks/typical90_n)

difficulty : 3 / yellow

本题的贪心策略与洛谷P1966一致,先直接将$a$,$b$分别排序,对应的学校和人即为一对,答案是$\sum_{i=1}^n |a_i-b_i|$.

# [016 - Minimum Coins](https://atcoder.jp/contests/typical90/tasks/typical90_p)

difficulty : 3 / yellow

因为最多只需要$9999$枚硬币,所以直接枚举前两种硬币,推出第三种硬币需要多少枚,以及判断是否是整数.

# [020 - Log Inequality](https://atcoder.jp/contests/typical90/tasks/typical90_t)

difficulty : 3 / orange

由$\log_2a < b\log_2c$,得:$\log_2a < \log_2c^b$,因为函数$f(x)=\log_2x$在定义域内单调递增,所以只需要判断是否$a < c^b$就行了.

# [021 - Come Back in One Piece](https://atcoder.jp/contests/typical90/tasks/typical90_v)

difficulty : 5 / green

在有向图中互相可达,想到强连通分量.只需将每个强连通分量的点数求出.答案即为$\sum_{i=1}^{cnt}size_i\times(size_i-1)/2$.

# [022 - Cubic Cake](https://atcoder.jp/contests/typical90/tasks/typical90_v)

difficulty : 2 / orange

要切成正方体,那么棱长就应该是$\gcd(a,b,c)$.用辗转相除求$\gcd(\gcd(a,b),c)$求得边长,分别用$a,b,c$除,得到每条边上的块数,再分别减一得到每条边切割数,相加即为答案.

# [024 - Select +／- One](https://atcoder.jp/contests/typical90/tasks/typical90_x)

difficulty : 2 / yellow

先统计出每个点对应一共差多少$sum$,就是至少需要$sum$次操作,如果$k<sum$直接```No```.如果限制次数多,可以将任意一个调完的点$+1$再$-1$,消耗两次操作,于是就看$(k-sum)$是否能整除$2$,如果能就```Yes```,否则就```No```.

# [026 - Independent Set on a Tree](https://atcoder.jp/contests/typical90/tasks/typical90_z)

difficulty : 4 / yellow

要求输出$\lceil\frac{n}{2}\rceil$个互相没边的点.对于一棵树,互相没边的点一定在不同层,而我们让它尽量多,超过$\lceil\frac{n}{2}\rceil$可以不输出.也就是从$1$开始```dfs```,第一次加入所有奇数层的点,第二次加入偶数层的点,而两次```dfs```后答案大小相加正好等于$n$.那么至少有两个中的一个答案,大小大于等于$\lceil\frac{n}{2}\rceil$,输出它即可.

# [027 - Sign Up Requests](https://atcoder.jp/contests/typical90/tasks/typical90_aa)

difficulty : 2 / orange

对于每一个字符串,只需要判断它是否出现过,用```set```.没出现就输出$i$,再加进去.

正在渲染内容...