AGC025 解题记录

### A Digits Sum
$for$循环题目，就不翻译了。

### B RGB Coloring
题意：一个长度为$n$的序列，可以染成三种颜色或者不染，得分分别为$A,B,A+B,0$。问有多少种本质不同的序列满足总分为$K$
$A,B,n\le 3\times 10^5,K\le 18\times 10^{10}$

题解：傻逼题都想了那么久。先不考虑$A+B$，那么我们只需要枚举$Aa+Bb=K$就行了，因为$N\le 3\times 10^5$实际上$a,b\le 3\times 10^5$，直接for循环枚举就完了。现在考虑$A+B$，发现可以认为是同时涂了两种颜色。等价于涂两种颜色。对每一个$(a,b)$都算一下组合数就可以了。

### C Interval Game
题意：数轴上$N$个区间，$A$决定一个顺序，$B$会按顺序走到指定区间内的某一个点。$A$想让$B$走的距离尽量长，$B$想走的尽量短。问最后距离会是多少。$N\le 10^5$

题解：唉，被贪心吊打了。其实特别简单。加入$[0,0]$，把所有的区间按照$L$排序插入一个$set$再按照$R$排序插入一个$set$。交替拿出一个$L$最大的/$R$最小的，拿出来之后在另一边删掉。直到没有办法走了就停。
但是不会证。

### D Choosing Points
题意：要构造一种方案选$N^2$个坐标小于$2N$的点，满足没有任意两个点的距离为$\sqrt D_1$或$\sqrt D_2$。$N\le 300$

题解：翻了翻暑假的课件，发现了这样一种神仙做法：
对$a^2+b^2=D$进行讨论，如果$D$为奇数那么$a,b$奇偶性不同。发现黑白交替染色满足走奇数步异色，偶数步同色，那么用黑白交替染色走$a,b$一定会把颜色取反。
否则，如果$D\%4=2$，$a,b$都是奇数，每一行交替染色即可。
如果$D\%4=0$递归到边长为$N/2$，$D$为$D/4$，也就是把$2\times 2$看作一个方格。

### E Walking on a Tree
题意：给⼀棵$N$个点的⽆向树和树上的⼀些路径。
你需要为每个路径定向。
如果⼀条边双向都被⾛过，可以提供2的幸福值。
如果⼀条边只有⼀个⽅向被⾛过，⽆论⾛过多少次，也只能提供1的幸福值。
如果⼀条边没有被⾛过，不提供幸福值。
问最大幸福度。
$N\le 2000$

题解：神仙结论，理论最大值就是实际最大值。也就是说假设一条边被两条路径经过，一定能取到双向幸福值。
感性理解：一些通过边链接的已经定向的路径集若全部反向依然满足条件。那么对于一条边假设同向且两条路径所在集合不同，我们可以让经过它的两条路径所在集合的其中一个反向，变成不同向。那么可不可能两条路径所在集合相同呢？发现因为在树上，两条路径的交一定是一条链，而边一定在该链上。所以不影响。

### F Addition and Andition

弃啦$qwq$

Rockdu's Blog

导航

最近发表

大佬们的友链