Dawn-K's Blog

「From ashes to the empire」

「CodeNote」 CF1165E(贡献)

CF1165E 题意 给一个n,然后给出两个长度为n的数组a,b 我们定义$f(l,r)=\sum_{l<=i<=r}a_i*b_i$ 你可以任意改变b数组的顺序,使得$\sum_{1<=l<=r<=n}f(l,r) $(以下称作②)最小,输出最小值mod 998244353 思路 很明显求贡献的题. 我们可以这样考虑,我们定义c_i=...

Posted by Dawn-K's Blog on November 10, 2019

「CodeNote」 CF1165D(约数)

CF1165D 题意 多组输入t 对于每个输入,给你一个n,给你一个长度为n的序列a.问是否存在一个数,他的所有约数(除了1和它本身),都在这个序列中. 如果有,输出满足条件的最小的数,如果没有,则输出-1 $1<=n<=300$ $2<=a_i<=1e6$ 思路 思路很简单,对a数组排序,则约数x如果存在就是a[0]*a[n-1] ...

Posted by Dawn-K's Blog on November 10, 2019

「CodeNote」 反向拓扑

反向拓扑 介绍 反向拓扑是一个很常见的算法.解决的问题也很模板,是这样的一个问题: 有N个人，M个优先级a，b表示a优先于b。要求 ：编号最小的节点要尽量排在前面；在满足上一个条件的基础上，编号第二小的节点要尽量排在前面；在满足前两个条件的基础上，编号第三小的节点要尽量排在前面……依此类推。（注意，这和字典序是两回事，不能够混淆。 思路 这个思路初见还是真不好想.需要逆向思...

Posted by Dawn-K's Blog on November 7, 2019

「CodeNote」 牛客135D(阶乘末尾0)

牛客135D 题意 给你个n,求 1!+2!+...+n! 末尾的0的个数 $1<=n<=1e9$ 思路 我们单看对于一个数.首先阶乘末尾的0一定是由于其质因子中2*5得到的,又由于在一个数的阶乘的质因数分解中,2的数量一定大于5的数量.所以我们只需要看5的数量即可. 不难发现,如果我们假定f(x)表示x!末尾的0的个数的话.那么f(x)一定是个阶梯函数.其一...

Posted by Dawn-K's Blog on November 5, 2019

「CodeNote」 CF1200D(模拟)

CF1200D 题意 给你一个n,k,然后给出一个n*n的矩阵,每个元素是’B’或’W’,你能选择k*k的范围,使范围内所有的’B’变成’W’,然后求一次染色后最多可以有多少条”白线”. 白线是指全都为’W’的行和列的数量. $1<=k,n,<=2000$ 思路 题面很简单,就是模拟. 仅仅枚举染色范围的左上角,复杂度就是$O(n^2)$了,如果暴力计算...

Posted by Dawn-K's Blog on November 5, 2019

「CodeNote」 CF1166C(思维+二分+数学)

CF1166C 题意 给你n个数,从中选两个数,一个作为x,一个作为y,要求min(|x-y|,|x+y|)<=|x|,|y|<=max(|x-y|,|x+y|) 求满足条件的(x,y)的对数,(x,y)和(y,x)视作一种. $2<=n<=2e5$ $-1e9<=a_i<=1e9$ 思路 这个题其实大力讨论也是可以的,讨论之后二...

Posted by Dawn-K's Blog on November 5, 2019

「CodeNote」 CF1244D(思维+树)

CF1244D 题意 给出一个有n个节点的树,有三种颜色,给出每个节点染成三种颜色分别的代价,求一种染色方法使得任意相邻三点之间没有重复的颜色.要求输出任意一种方案,且保证代价最小.如果不存在方案,那么输出-1 $3<=n<=1e6$ $0<=c_{1i},c_{2i},c_{3i}<=1e9$ 第一行给出一个n 接下来三行一行n个数,表示染色的代...

Posted by Dawn-K's Blog on November 1, 2019

「CodeNote」 CF1248E(模拟+STL)

CF1248E 题目链接 题意 火车上有一行乘客,从左到右依次为1到n.在一号乘客的左侧有一个热水器,每个人都会在ti的时候想要去打水,每个人打水的时间都是p.打水需要排队.而且对于乘客i,如果在(1~i-1)范围内存在乘客正在排队,那么他就会等到前面的乘客都没在排队的时候,瞬间起身去排队.如果在一个瞬间有多个乘客想要起身,只有标号最小的乘客会排队,剩下的人会回到座位上等待下一时刻. ...

Posted by Dawn-K's Blog on October 26, 2019

「CodeNote」 CF1239A(思维+斐波那契)

CF1239A 题目链接 题意 题意很简单,给你一个n*m的方格图.要求每个方格涂黑白两色,要求对于每个方格,不得与超过一个同颜色的相邻(就是上下左右四个邻居中最多只能有一个和它同色的).输出有多少种涂色方式,答案对1e9+7取模 $1<=n,m<=1e6$ 图中是n=2,m=3的情况 分析 这个题咋看没有头绪.还是评论区大佬一语惊醒梦中人. 我们先讨论一个简...

Posted by Dawn-K's Blog on October 25, 2019

「CodeNote」 CF1238D1(思维+括号匹配)

CF1238D1 题意 如果一个括号串是匹配的,我们认为它是正确的. 给你一个长度为n的字符串,让你可以交换这个字符串中的任意两个(自己和自己交换也可以).定义ans为有多少种位移方法使得串是正确的? 要求输出ans的最大值. (位移位数k满足$0<=k<n$) $1<=n<=500$ 思路 这个题其实并不难,一开始的思路想复杂了. 首先我们统计一下...

Posted by Dawn-K's Blog on October 25, 2019

FEATURED TAGS
CodeNote Web开发 软件工程 SpringBoot 互联网架构 垃圾回收的算法和实现 设计模式 android DAO 数据库 Python Vue Linux Unity VSCode学习 操作系统 版本控制 C++ View Java Kotlin Missing-Semester
ABOUT ME

Dawnk | 计算机本科生 | 退役ACMer | Vocaloid 爱好者

FRIENDS