目录

Codeforces Round 662 Div.2

地址: https://codeforces.com/contest/1393

A Rainbow Dash, Fluttershy and Chess Coloring

题意:

水题,观察一下,发现明显规律,直接写

题解:

直接输出$\lfloor \frac{n}{2} \rfloor +1$就行

B Applejack and Storages

题意:

给你n块木板的长度,还有两种操作方式:1.添加一块长度为x的木板 2.删除一块长度为x的木板; 求每次操作后,当前所有的木棍能否取出8个来,组成一个正方形和一个长方形(含正方形)

题解:

先记录木板每个长度的数量,然后再根据木板长度的数量记录木板相同长度的组数,最后判断操作后木板的组数是否能满足组成正方形和矩形即可

C Pinkie Pie Eats Patty-cakes

题意:

给出$n$个数字,问有没有某种排列方式,使得任何相同两数字距离最大,问这个最大距离是多少

题解:

这题可以贪心,对每组数,首先找到这组数出现次数最多的数的次数$t$,并且用另外一个数组记录每一个数出现的次数。 最后遍历,当某个数出现的次数等于$t$时,结果$ans++$,最后直接输出$ans+\frac{n-ans*t}{t-1}-1$。

D Rarity and New Dress

题意:

有一个$n\times m$的字符矩阵,问有多少个如图的菱形,满足构成菱形的字符为同一个字符

题解:

这题就是DP。 用$dp[i][j]$表示以$(i,j)$为最下方的顶点构成的菱形有多少个 $dp[i][j] = 1 + min(min(dp[i - 1][j - 1], dp[i - 1][j + 1]), dp[i - 2][j])$ 之后再用一个check函数检查$(i,j)$位置与它头顶上4个位置字符是否一致 最后对满足题意的点加和就行。

E1 Twilight and Ancient Scroll (easier version)

题意:

给出一串经过处理过的字符串(每个字词的任何位置都恰好增加了一个字母),原来的字符串包含按字典顺序不减顺序的单词。 要求你从现有的某些单词中删除一个字母(以撤消拼写),以获得原始字符串的某些版本。你需要找到所有恢复字符串的方法,最后模上$10^9+7$

题解:

先咕咕,还不会做。。。

E2 Twilight and Ancient Scroll (harder version)

题意:

基本和E1一样,但是数据更强,限制更多一点。

题解:

先咕咕,还不会做。。。