赛季才刚开始,不能说太多伤心的话,简单写写记记就好了吧
题目大意
一幅有向图有 $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
题目大意
有 $n$ 个人玩淘汰赛。
每一轮,假设当前还剩 $k$ 人,则他们随机分成 $\lfloor \frac k2 \rfloor$ 组($k$ 为奇数时有一人轮空),最后晋级 $\lceil \frac k2 \rceil$ 人。每个人能力互不相同,两人对打时一定是能力强者获胜。
求所有可能的局面数,答案对 $2^{64}$ 取模。
$1 \leq n \leq 10^{18}$
注意题面坑:Two tournaments are called different if there is a game (between two participants) in one of the tournaments that doesn’t occur in the other tournament. 这句话是错的!
题目大意
有一个 $n\times m$ 的黑白棋盘,初始时候每个格子都是白色。
接下来 $q$ 次操作,每次把第 $a_i$ 行的 $[l_i,r_i]$ 这个区间反色。
每次操作结束就会问你,是否存在 $x_1,y_1,x_2,y_2$,满足
- $1 \leq x_1 < x_2 \leq n$
- $1 \leq y_1 < y_2 \leq m$
- $(x_1,y_1)$ 与 $(x_2,y_2)$ 同色
- $(x_1,y_2)$ 与 $(x_2,y_1)$ 同色
- $(x_1,y_1)$ 与 $(x_2,y_1)$ 异色(即:对于矩形的四个角,对角同色,同侧异色)
若存在,则输出其中一组解。
$n,m \leq 2000,~q \leq 5\times 10^5$
不知不觉大一就过完了。这一年混杂着学习、acm,好多感想。
想想还是觉得要简单写写吧。