题目大意
给定一幅 $n$ 个点的二分图。左边的每个点度数至少为 $1$ 至多为 $3$,且左边每个点只会连向右边编号大于等于它的点。
现在你要选择一些边,限制如下:
- 右边的每一个点都要被覆盖到;
- 有一个 01 矩阵 $A_{n\times n}$,若 $A_{i,j}=1$ 则表示左边第 $i$ 个点和第 $j$ 个点不能同时被覆盖到;
- 对于左边的每一个点,如果它没被覆盖到则代价为 $0$,否则代价为 $M_i^{d_i}$,其中 $d_i$ 表示被它覆盖了多少次。满足上面两条的情况下要使得代价最小。
求最小代价,或输出无解。
$n \leq 18,~1 \leq M_i \leq 100$
多测,$T \leq 10$
1s
奋战一星期,造台单周期
赛季才刚开始,不能说太多伤心的话,简单写写记记就好了吧
题目大意
一幅有向图有 $n$ 个结点,初始没有边。
有 $q$ 个操作,四种类型:
- $+\ o\ v\ k\ a_1\ \cdots\ a_k$:加入边 $(v,a_1),\cdots,(v,a_k)$
- $+\ i\ v\ k\ a_1\ \cdots\ a_k$:加入边 $(a_1,v),\cdots,(a_k,v)$
- $-\ o\ v\ k\ a_1\ \cdots\ a_k$:删除边 $(v,a_1),\cdots,(v,a_k)$
- $-\ i\ v\ k\ a_1\ \cdots\ a_k$:删除边 $(a_1,v),\cdots,(a_k,v)$
加边之前会保证原来没有这条边,删边之前会保证原来有这条边。
每次操作后,可以得到一个连通性矩阵 $a$($a_{i,j}=1$ 表示 $i$ 能到 $j$),输出
$1 \leq n \leq 400,\ 1 \leq q \leq 800,\ 1 \leq A,B \leq 10^9$
3s
题目大意
有 $n$ 个元素,第 $i$ 个元素在初始 $0$ 时刻时值为 $a_i$,此后每个时刻增加 $b_i$ 并模 $p_i$,即在 $t$ 时刻时值为 $(a_i+b_i\cdot t) \bmod p_i$,其中 $t$ 为整数。
求
输出这个最大值,及其对应的最早的时刻。
$1 \leq n,T \leq 10^5,\ \ 0 \leq a_i,b_i < p_i,\ \ 5\times10^8 < p_i < 10^9$
多测,$\sum n \leq 10^6$,80% 数据保证 $n \leq 1000$
保证 $p_i$ 为质数;
$a_i,b_i$ 在 $[0,p_i)$ 范围内随机生成;
5s