Codeforces Round #697 Div3题解

感觉这套Div3有点东西的。G题是一道极限时间+基础dp+基础数论。F的模拟稍嫌恶心。D看着像是DP,其实就是贪心+二分还是有点意思的。不算是手速场。D题G题差不多能对标Div2的C的感觉。

勉强可以接受,G题的卡时间还是有东西的。

G. Strange Beauty

题意

给你一个长度为n的数组a。定义数组a是美的,当且仅当:对于任意的$i,\ j$,满足${a_i}\mid{a_j}$或者${a_j}\mid{a_i}$。问至少要删除多少个数字才能使a变美。

题解

算是DP。这道题挺卡常数的。

先说结论:$dp_i=\max{(dp_i, dp_{pos_{factor}} + count_{a_i})}$。其中$pos_{factor}$表示这个$a_i$的因数$factor$的位置。$count_{a_i}$表示当前这个$a_i$出现的次数。

再说具体做法:

首先,对于a进行预处理,把重复的数字都收进count的统计里面。然后维护$pos_{a_i}$记录每个数字出现的位置。

然后因为对于任意的${1}\leq{a_i}\leq{2\cdot{10^5}}$,他的因数不超过1000个($500^2=250000$)。那么对于当前的$i$,暴力找出这1000个因数。计算dp即可。

最后说超时问题:

首先,pos应该直接使用数组记录。因为${1}\leq{a_i}\leq{2\cdot{10^5}}$,开map会有个log。

然后,要去重。不然每次只+1会比较慢。

代码

Submission #111982668 - Codeforces
Codeforces. Programming competitions and contests, programming community

F. Unusual Matrix

题意

给你两个${n}\times{n}$的里面全是0或者1的矩阵:a和b。现在每次操作:你可以选择把一行的值全部异或1,也可以把一列的值全部异或1。问从a能不能通过一系列操作到b。

题解

考虑第一行。对于第一行选定了要不要异或这一行之后,结果就是固定的了。再决定了第一行要不要异或之后,每一列要不要异或就是必定的。接着扫描每一行。

代码

Submission #111976374 - Codeforces
Codeforces. Programming competitions and contests, programming community

E. Advertising Agency

题意

给你一个长度为n的数组a,要你从中挑k个数出来,要你挑出来的和最大。问你有多少种挑法。

题解

统计每个数出现的次数。然后从大往小挑选。当发现从某个数开始超过k个的时候,算个组合数。

代码

Submission #111973234 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Cleaning the Phone

题意

手机里有n个引用,每个应用占用内存为$a_i$,应用的分数为$b_i$,其中$1\leq{b_i}\leq2$。现在你要释放至少m的内存。问你最少失去的分数是多少。

题解

贪心+二分。应用分数只有两个,那么对于相同分数的应用,优先释放占用内存多的。于是枚举到底要释放多少个分数为1的应用,二分分数为2的应用。

要注意,因为要维护前缀和。而$a_i$的最大值是$10^9$。所以可能会爆int。

代码

Submission #111971020 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Ball in Berland

题意

有a个男生,b对女生。其中有k种可行的男女配对方案。现在你要从这些配对方案中选两对男女上来。要求选的配对是4个不同的人。问有多少种选择方案。

题解

枚举第一对。然后通过集合运算计算其他可能。这里可能需要注意的是,题目似乎没保证输入的配对不重复(比如a[0]=1,b[0]=1,然后立刻a[1]=1,b[1]=1这种)。所以我默认上了Set判重。

代码

Submission #111889729 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. New Year's Number

题意

给你一个数,问你这个数能不是由若干个2020和2021的和构成。

题解

n最多也就$10^6$,直接暴。枚举2020的个数0-500个,完了看能不能整除2021。

我会跟你说我上来直接$500\times500$的暴然后T了?

代码

Submission #111875464 - Codeforces
Codeforces. Programming competitions and contests, programming community

A. Odd Divisor

题意

给你一个n。问你是否存在一个非1的奇数能整除n。

题解

不停除2,直到不能被2整除,看看剩下来的是什么。

代码

Submission #111871231 - Codeforces
Codeforces. Programming competitions and contests, programming community

展示评论