CCPC2016 合肥站

A.传递

如果存在一条边\textless u,v \textgreater \in P,而Q中存在一条u->vv->u的路径则一定不满足。因此只要P\cup QP\cup rev(Q)中都没有环就可以了。

C.朋友

以i为根的询问,显然如果与i相邻的黑边有奇数个则先手胜,否则后手胜。

E.扫雷

dp[i][u][d][w]表示考虑前i列,第一行第i列的雷的个数为u,第三行第i列的雷的个数为d,且还需w个雷才能满足第二行第i列的需求。

G.小R与手机

LCT
很糟糕的代码

H.异或密码

暴力

J.最大公约数

gcd(i, j)==gcd(i+k*j, j),注意到这个性质,同时f(i, j)==f(i+k*j, j)
因此枚举j,再枚举j的同余系,此时只需计算\sum{ \lfloor ((a_i/gcd)*(j/gcd))/c \rfloor}
a_i 是一个等差数列(a_i=i+k*j),因此(a_i/gcd)*(j/gcd)也是等差数列,公差是(j/gcd)*(j/gcd)
b_i=(a_i/gcd)*(j/gcd),因此结果就是\sum\lfloor\frac{b_i}{c} \rfloor = \sum\frac{b_i-b_i\%c}{c}=\frac{\sum b_i-\sum b_i\%c}{c}
因此只要计算\sum b_i\%c
由于b_i是等差数列,因此b_i\%c有循环节,而c的大小最多只有log级别,所以直接暴力找循环节。

发表评论