0103abc 的网站

简单的问题。子序列相关题目考虑在子序列自动机上 dp。套路的，设 $to{i,j}$ 表示 $i$ 后面第一个字符 $j$ 出现的位置，$fi$ 表示当前到 $i$ 位置，可以得到的不同的子序列的数目。则 $to{i,j}$ 显然可以 $O(n)$ 处理，$fi$...

XorForces。每日被 Hack。 首先考虑异或的性质： 壹 若 $x\oplus y=0$，则 $x=y$。 壹.证明 若 $x\oplus y=0$，则 $x$ 和 $y$ 二进制表示下每一位的值都相同，显然只有两个数完全相同时才能有这样的性质。因此得证。 贰 若 $x\oplus...

好题啊！ 考虑一个经典套路。 若一个人不会，则她的分数 $-1$，否则她的分数 $+1$。 转化问题。 首先一个人的分数 $-1$，若她会，则她的分数 $+2$。 此时考虑两个人 $A$，$B$。对于问题 $i$： $A$ 和 $B$ 都不会问题 $i$。则相对贡献为 $0$。 $A$ 和 $B$...

套路题。考虑设函数 $F(i)$： $F(i)=1$，$\exists j\in[1,n]\cap\mathbb{N+},aj\mid i$。 $F(i)=0$，$\forall j\in[1,n]\cap\mathbb{N+},aj\nmid i$。 然后发现 $(i,j)$ 为 的充要条件是...

简单题。考虑维护每一个字符对答案的贡献： 和 只能为当前的最大值，贡献为 $1$，而 可以为其他所有值，贡献为 $i-2$（$i$ 表示当前是第 $i$ 个字符）。 然后直接统计出来，修改的时候乘逆元即可。时间复杂度为 $O(n\log n)$。如果线性预处理逆元则可以做到 $O(n)$。

考虑对于四个人 $a$，$b$，$c$，$d$。两次询问分别询问 $a,b,c$ 和 $b,c,d$。若两次询问的结果不一样，则说明 $b$ 和 $c$ 一定不同类别。找出这样的一组 $b$ 和 $c$ 之后将其和所有其他人做询问，就可以得...

入门交互。考虑每一次询问出每一个位的值。从低位到高位考虑，若此时当前位的 $1$ 的数量减少 $1$，则说明这一位的值为 $1$，否则直接暴力推算出其下一个 $1$ 的位置。 交互次数为 $\log$ 级别，可以通过。

又是大水题。 考虑连续两个元素对答案的贡献。 $(0,0)$：一居室和二居室对答案的贡献均为 $0$。（$1$） $(0,1)$：一居室和二居室对答案的贡献均为 $1$。（$2$） $(1,0)$：一居室和二居室对答案的贡献均为 $1$。（$3$） $(1,1)$：一居室对答案的贡献为...

简单题，考虑简单 dp。发现 $k$ 很小，因此设 $f_{i,j,0/1}$ 表示前 $i$ 个元素，修改了 $j$ 个位置，当前位置不选 / 必选，最大子段和的值。转移类似于普通的 1-D 最大子段和。具体见代码。

upd：添加代码。 首先所有非空子序列的数目为 $2^n-1$ 是奇数，因此两数的差也只能为奇数，最小值最小为 $1$。因此考虑构造串 $000\ldots01$，此时两数的差为 $1$。根据上面的分析发现差的绝对值必然是奇数，因此无更优构造。 单组数据时间复杂度为 $O(n)$。