layout: post
title: Codeforces Round 268 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
C - 24 Game (分类讨论 构造)
思路
首先(n<4)肯定无解
然后(n=4)可以用(1*2*3*4=24)
(n=5)可以用(1+2*4+3*5=24)
发现后面如果多出来的项数(x,x+1)可以变成(x+1-x=1) 然后乘上上面的(24)相当于没贡献
D - Two Sets (并查集)
思路
对于一个数(x)要么在(A)要么在(B)，如果在(A)并且存在(a-x)那么(a-x)肯定要也在A
在(B)同理，而且不可能出现在两个位置
所以我们创建一个A集合和B集合，如果最后两个集合合体了那就不合法不然就查询在哪个区间
E - Hack it! (构造)
思路
首先考虑一个数字(x),若(f(x)=y)那么(f(x+1e18)=f(x)+1=y+1)
我们设(sum_{i=0}^{1e18-1}f(i)=p(moda))
那么(sum_{i=1}^{1e18}f(i)=1+sum_{i=0}^{1e18-1}f(i) =p+1)
同理证明(sum_{i=2}^{1e18+1}f(i)=p+2)
(sum_{i=3}^{1e18+2}f(i)=p+3)
直到(sum_{i=a-p}^{1e18+a-p-1}f(i)=p+a-p=0(mod a))
所以(l=a-p,r=1e18+a-p-1)
所以需要求出(P)
$P=45x10^{x-1} $x是位数