ATC杂题

li_cat · 2025-11-22 20:37:20 · 个人记录

ATC的题都懒得写代码

感觉很多都是缺一个性质观察，感觉可以直接几句话带过......

先记录下关键性质，后面再想想性质能不能通过非瞪眼的方式推导出来，试下能不能总结规律

删掉树上的若干节点，保证树仍然连通，直径 \le k ，求删点最少

考虑枚举新树直径中点，那么所有到达中点 > \lfloor\frac k 2\rfloor 的点都要被砍掉

或者考虑保留尽量大的点，那么就可以试着dp留点

记f(u,i,0/1)为当前点选/不选，最大高度为i能留的最大点数

给定一个整数 K 。求一个 K 的正整数倍 S，使得 S 的数位累加和最小

首先答案存在一个上界，一定是 \le 原数数位和的

那么发现这个答案的上界很小，只有 5\times 9=45

然后考虑怎么做，因为数字可能很大，考虑数位DP

如果按照常见的数位dp做，应该是f(pos,i)为枚举到第pos位，余数为i时的最小，然后发现这个时候是第几位是不重要的，直接不要

不过这样一看可能有后效性，也许可以用dijkstra做？

考虑能不能去掉这个min变成不需要最短路的做法，因为答案很小，可以直接把答案扔到状态里变成f(i,j)，表示余数为i，答案为j的可行性，这样就变成可达性问题了

不过这样乘一个50的常数好像和dijkstra没啥区别（）

求满足以下两个条件的正整数 n 的最小可能值：

n 是 K 的倍数

n 的十进制表示中包含 S 作为子串

发现第二个条件更强

考虑先满足第二个条件，然后去凑倍数

那么答案的形式就可以记作 L+S+R

那么这个时候再考虑满足第一个条件

那么就相当于要求 L\times 10^{|S|+|R|}+S\times 10^{|R|}+R \equiv 0 (\mod K)

发现这个方程可以知二求一，可以枚举一部分解一部分

先考虑枚举R的长度，然后发现可以枚举两个量，要么枚举L要么枚举R

这时|L|+|R|\le |K|，因为可以直接把余数铺到S后面

发现可以根据R的长度来确定枚举谁，当|R|\ge |K|时枚举L，当|R|>|K|的时候枚举R，这样根据位数来分开处理复杂度是根号的

枚举完之后用扩欧做把另一个解出来即可

时间复杂度 O(\lg K (\sqrt K\lg K))