-1 序

寄啦，哈哈。

今年是新疆维吾尔自治区第一次组织省选。

今年有很多神奇的事情，比如特派员换了，新疆成立竞赛组委会了，办省选了，有 $\frac{1}{3}$ 了，有实体 NOI Linux。当然也不都是好事，疫情精准防控的代表上海已经被奥米克戎攻陷，全国疫情更是此起彼伏，见不到头。这种情况下信息学竞赛还能基本上「出淤泥而不染」，维持较为正常的赛季流畅已是相当不易。

在疫情的限制下，XJOI 最终未能选择新疆大学作为考点，而是选择了一所高中 -- 乌鲁木齐市第一中学。

A Four Points

题目大意

给定矩形的三个顶点，求其剩下的顶点。

思路

签到

B Get Closer

题目大意

给定直线过点 $(0,0)$, $(a,b)$，求从 $(0,0)$ 出发，方向朝右，长度为一的线段的右端点。

思路

一开始是二分硬做的，然后被卡精度了。

求出两点距离，对 $a,b$ 分别除于这个这个距离即可。

题目链接：https://codeforces.com/contest/383/problem/E

1 题目大意

给定 $n$ 个长度为 $3$，字符集为 a-x 的字符串。

对于 s, s \subseteq \[ \texttt{a}, \texttt{x} \]，有 $f(s)$ 表示有多少个给定字符串和 $s$ 交集非空。

输出 $\sum^{\oplus}_s f(s) \* f(s)$

2 思路

注意到基本上是 SOS DP 的模版，除一个问题 -- 对于一个字符串可能会被统计多次。

简单容斥即可。

0 引

为什么没在标题里写 SOS DP ？因为这 SOS 这个名字我第一次看的时候怎么看怎么觉得不正经，所以写全称让他看着正经一些。

个人感觉这个东西更像是一个套路而不是 DP 类型。

1 什么是 SOS DP

Sum over Subsets DP，即求子集和的 DP。更具体的说，用于在 $O(k \cdot 2^k)$ 的时间求出以下式子：

题目链接：https://codeforces.com/contest/165/problem/E

1 题目大意

给定一个长度为 $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$。

2 思路

注意到 $a_i \& a_j = 0$，其实就是询问是否有数字满足其是 $a_i$ 的补集的子集。

SOS DP 求出每个集合是否有数字是其子集即可。