Codeforces1128D Complete Tripartite

Description

一个$n$个顶点，$m$条边的无向图，保证无重边与自环，不保证连通

设$v_1, v_2 \subseteq V$是两个不相交的非空点集，定义$f(v_1, v_2)$在满足以下所有条件时为真：

• $v_1$中的点之间不存在边
• $v_2$中的点之间不存在边
• 对于任意分别在$v_1, v_2$中的每一对点$(x, y)$之间均有边

问能否将$V$分为三个非空的，不相交的点集$v_1, v_2, v_3$使得$f(v_1, v_2), f(v_2, v_3), f(v_1, v_3)$均为真

若能则输出每个点所在的点集，否则输出$-1$

Codeforces1228E Another Filling the Grid

Description

给定一个$n \times n(1 \le n \le 250)$的矩阵，用$1 \sim k(1 \le k \le 10 ^ 9)$的数进行填充，每行每列最小值为$1$

求方案数

Codeforces79D Password

Description

你有$n$个一开始都为灭的灯泡，排成一排

同时你有$l$个长度，分别为$a_1 \sim a_l$

每次你可以选择一段连续子序列，长度为某个$a_i$，将这些灯泡的状态改变（亮变灭，灭变亮）

你可以做任意多次，使得最后有且仅有$k$个位置的灯泡是亮的，这些位置已经给定，为$x_1 \sim x_k$

求最小次数

数据范围

$1 \le n \le 10000,1 \le k \le 10, 1 \le \ l \le 100$

洛谷 P4869 albus就是要第一个出场

Description

已知一个长度为$n$的正整数序列$A$（下标从$1$开始），令$S = { x|x \le x \le n }$，$S$的幂级$2^S$定义为$S$所有子集构成的集合。定义映射$f:2^S \rightarrow Z$，$f( \emptyset ) = 0$，$f(T) = XOR { A _ t },(t \in T)$

现在$albus$把$2^S$中每个集合的$f$值计算出来， 从小到大排成一行， 记为序列$B$（下标从$1$开始）。

给定一个数， 那么这个数在序列$B$中第$1$次出现时的下标是多少呢？