「Jump up HIGH!!」
考试链接： https://codeforces.com/contest/1699
考试的时候 30min 写完 ABC 发现 D 没几个人就摸了。考完看了眼 E 发现一眼切。最后竟然上分了，我大受震撼。
求能否找到任意三个数字 $a,b,c$ 使得 $(a \oplus b) + (a \oplus c) + (b \oplus c) = n$ 。
容易发现奇数根本不可能，偶数随便构造。
给表格染色。使得对于任意一个格子，有且只有两个相邻格子和这个颜色不同。
以 2x2 为一个单位，交叉构造即可。
和后缀和。
求
$$
b_k = \sum_{i|k}a_i
$$
或
$$
b_k = \sum_{k|d}a_d
$$
都一样，没啥区别。
Continue reading “Dirichlet 前缀和”这个东西看了半天没想明白为啥不是最小生成树，然后发现最小生成树实际上是最小斯坦那树的特殊形式
— 最小生成树里的所有点都是关键点。
最小斯坦那树是指在一个无向图中，求其最小生成网络使得其
给定矩形的三个顶点，求其剩下的顶点。
签到
给定直线过点 $(0,0)$, $(a,b)$，求从 $(0,0)$ 出发，方向朝右，长度为一的线段的右端点。
一开始是二分硬做的，然后被卡精度了。
求出两点距离，对 $a,b$ 分别除于这个这个距离即可。
Continue reading “Atcoder Beginner Contest 246 解题报告”给定一个长度为 $n$ 的序列 $a$
求最大 $a_i|(a_j\&a_k)$ 满足 $i < j < k$
$3 \leq n \leq 10^6, 0 \leq a_i \leq 2 \cdot 10^6$
先考虑 $a_j\&a_k$，显然可以通过 SOS DP 来求出对于任意 $s$，其最靠后 $j$ 的能够有 $k$ 使得 $s \subseteq a_j\&a_k$ 的位置。
然后考虑贪心来最大化按位或，从高位往低位处理，如果能够有一位新为 $1$，则有限选择位数高的。
Continue reading “Codeforces 1208F Bits And Pieces”给定 $n$ 个长度为 $3$，字符集为 a-x 的字符串。
对于 $s, s \subseteq [ \texttt{a}, \texttt{x} ]$，有 $f(s)$ 表示有多少个给定字符串和 $s$ 交集非空。
输出 $\sum^{\oplus}_s f(s) * f(s)$
注意到基本上是 SOS DP 的模版，除一个问题 — 对于一个字符串可能会被统计多次。
简单容斥即可。
Continue reading “Codeforces 383E Vowels”给定一个长度为 $n$ 的序列 $a$。
对于每一个 $a_i$，询问是否存在 $a_j$ 使得 $a_i \& a_j = 0$，如果有输出 $a_j$（如果有多个，输出任意一个），否则输出 $-1$。
$1 \leq n \leq 10^6, 1 \leq a_i \leq 4\cdot 10^6$。
注意到 $a_i \& a_j = 0$，其实就是询问是否有数字满足其是 $a_i$ 的补集的子集。
SOS DP 求出每个集合是否有数字是其子集即可。
Continue reading “Codeforces 165E Compatible Numbers”为什么没在标题里写 SOS DP ？因为这 SOS 这个名字我第一次看的时候怎么看怎么觉得不正经，所以写全称让他看着正经一些。
个人感觉这个东西更像是一个套路而不是 DP 类型。
Sum over Subsets DP，即求子集和的 DP。更具体的说，用于在 $O(k \cdot 2^k)$ 的时间求出以下式子：
$$
f_{mask} = \sum_{i \subseteq mask} a_i
$$
即 Codeforces Round #695 (Div. 2)
许久不打变得更菜了…
给定 $n$ 个板子，每个板子上有一个相同的数字 $x ( 0 \leq x \leq 9 )$
随机选择一个数字 $y(1 \leq y \leq n)$，令板子 $i$ 上的数字变成 $ x + |y – i| \pmod 10$
显然，输出 $98\{987654321\}$ 的前 $n$ 位即可
#include <cstdio>
int main() {
int T;
scanf( "%d", &T );
while( T -- ) {
int n;
scanf( "%d", &n );
if( n == 1 )
printf( "9" );
else {
printf( "98" );
int cur = 9;
for( int i = 3; i <= n; i ++ ) {
printf( "%d", cur );
cur ++;
if( cur >= 10 )
cur = 0;
}
}
printf( "\n" );
}
}