ARC142

ARC142

第一场 ARC，perf 1.1k+，菜死了/dk

• A

讨论 $k$，如果反转后的数比它小，那它就没救了

否则设反转后数字为 $R(k)$

如果 $k>N$，那它也没救了

如果 $k=R(k)$（是回文数）那么枚举 $k,10k,100k···$ 直至大于 $N$，数字个数即为所求

否则枚举 $R(k),10R(k),100R(k)···$ 直至大于 $N$，这里的个数要乘 2，因为 $k,10k···$ 也是小于 $N$ 的，此时考虑若 $k<N$，数字个数要加一

• B

构造题，上下边缘的数字不用考虑，因为根据奇偶性就知道不行

中间的数字就要构造成波浪状，大数比两边的小数大，小数比两边的大数小

这个构造方法因人而异，给一下我的：

	for(int i=1;i<=n;i+=2)a[i]=(i+1)/2;
	for(int i=2;i<=n;i+=2)a[i]=n+1-i/2;

• C

哈哈交互题

反正 $2n$ 次，把全跑一遍

不难想到 $dis(1,2)=\min\limits_{i=3}^ndis(1,i)+dis(2,i)$

但是有一种情况，就是 $dis(1,2)=1$，这时最小值是 3

如何辨别？如果 $dis(1,2)=1$，此时最小值点不相邻，如果 $dis(1,2)=3$，此时最小值点相邻

搞定

剩下的咕一会，等我的 OI 英语 实力更强了再来补