[atcoder abc133]解题报告

打的第一场atcoder的比赛……

没有hack还真是少了份FST的趣味(划去)

比赛页面

A题

题目大意:比较a*n与b的大小

这题还用说吗……没有坑点。

B题

题目大意:给你n个d维空间上的点,求有多少点对使得这两个点之间的距离是正整数

这题也没有什么好说的,首先算距离的平方,之后只需要看是否”sqrt(距离)*sqrt(距离)==距离“即可(此时sqrt返回值用int存就行)

C题

题目大意:给出正整数L和R,找出正整数i,j∈[L,R],使得(i*j)%2019最小,输出最小值

这题我居然能WA四次……

首先可以特判:若R/2019>L/2019或L=0或R=0,说明[L,R]中一定有一个2019的倍数,此时直接输出0;
剩下来的情况就只有L/2019=R/2019,此时只需要在[L%2019,R%2019]中暴力求解就行。

D题

题目大意:有n座山围成一个环,每相邻两座山之间有一条沟渠。若有一座山的山上下了x*2的雨,那么这座山相邻的两条沟渠分别可收集x的雨量。一开始每条沟渠蓄水量为0。现在把每条沟渠的蓄水量告诉你,求每一座山可能降下多少雨?

真·“水”题(划去)

其实这题蛮有意思的。比赛时我没想到列方程组,倒是想了个另外的方法——二分。

二分什么?二分第一座山的降雨量。之后按照顺时针或逆时针,每一座山的降雨量都可以推出来。之后最后一座山和第一座山之间的沟渠特判一下即可。

不过要注意什么时候返回true,什么时候返回false。因为根据奇偶性,不同的山降雨量大小对答案的影响不同。举个例子,若第一座山降雨量偏小。那么第二座山降雨量偏大。第三座山降雨量偏小,第四座山降雨量偏大……以此类推。可以用一个flag不断异或1来实现。

E题

题目大意:给一棵树,现在要在每个节点上染一种颜色(颜色种类为1~K),若两个点之间距离<=2,则这两个点的颜色不能相同。询问一共有多少种染色方法?答案对1e9+7取模。

这题稍微画一画就能发现规律的,本质上就是个计数原理。

你会发现:一个节点的亲儿子节点多少与亲儿子节点可以染色的种类有多少有关:比如第一个儿子可以染p种,那么第二个儿子可以染p-1种,第三个儿子可以染p-2种……

不过要注意根节点与其儿子节点之间的关系,与之后的计数不太一样(很小的差别),这个在纸上画画亦可发现。

F题

题目大意:还是给你一棵n个节点树,每条边都有一个颜色和权值。颜色种类在1~n-1内。接下来q个询问,每次询问若将颜色为j的边的权值全部更改为w,问从节点u到节点v的权值和。询问之间互不影响。

这题比赛时没想出来。后来问了下群里的大佬们,不得不%

可以用离线算法:每个询问拆分成点到根节点的权值和,之后dfs一遍,每到一个节点就将该点的询问处理完。

在那之前要dfs一遍,记录根节点到该点的权值和以及经历了多少不同颜色的边等等。

代码先留空,后面再补。

发表评论