前言

这几天训练的太频繁了，一天一场比赛，简直不要太👹。从四月25号到5月3号9天开了7场。

比赛地址

https://ac.nowcoder.com/acm/contest/9925

F Fireworks

链接

https://ac.nowcoder.com/acm/contest/10272/F

题意

你想要放一个的烟花，你可以花费时间n来制作一个烟花，花费时间m点燃所有的烟花，烟花被点燃以后就释放了，但是他只有$\frac{p}{10^4}$的概率完美释放，你想完美释放至少一个烟花，那么需要的最少时间的期望是多少？

T组输入

A Matrix Equation

链接

https://ac.nowcoder.com/acm/contest/10662/A

题意

给你两个01方阵AB，你要找到一个01矩阵C，使得在2的模群中$A\times C=B\cdot C$ ,其中 $\times$ 为一般矩阵乘积， 符号 $\cdot$ 为哈达马积（Hadamard product）

问你C有多少个解

L Simone and graph coloring

链接

https://ac.nowcoder.com/acm/contest/12548/L?&headNav=acm

题意

给你一个排列，排列的长度不超过$10^6$。你要对他的每一个元素进行染色，要求染色后不存在任何一个逆序对的两个元素颜色相同。你需要输出染色的数组。

题目

做法

这个题目就是一个克鲁斯卡尔重构树的板子题，当然你也可以使用主席树来做

细节思路

我们构建克鲁斯卡尔重构树以后，答案就是lca的点权，所以是生成树+并查集+树剖+lca

克鲁斯卡尔重构树

有的时候，我们需要对最小生成树进行进一步的研究，比方说我们考虑最小生成树上任意两点路径的最小值，这个可以使用主席树、树剖等做法，
但是我们这样考虑，加入新的点，让边权变为点权，路径权的最小值就成了点权的最小值，如下图所示，最小生成树的点全部成为了克鲁斯卡尔重构树上的叶子，非叶节点充当了边权。

1
2
3
4
5
6
7

graph LR;
1((1))-- 5 ---2((2))
2((2))-- 4 ---3((3))
3((3))-- 3 ---4((4))
1((1))-- 8 ---4((4))
2((2))-- 7 ---5((5))
4((4))-- 2 ---6((6))

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x : y。
即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v 的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这Ｎ个组合齿轮能否同时转动。

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

Rinne 最近学习了位运算相关的知识，她想运用自己学习的知识发明一个加密算法。
首先她有一个源数组 A，还有一个密钥数组 B，现在她想生成加密后的数组 C。
她发明的方法是：当计算$$C_i$$的时候，首先将 $$C_i$$赋值为$$C_{i-1}$$，然后加上$$ A_i$$ 分别与每一个满足 $$j \lt i$$ 的 $$B_j$$ 异或后的和，然后加上 $$B_i$$ 分别与每一个满足 $$j \lt i$$ 的 $$A_j$$ 异或后的和，最后加上 $$A_i$$ 与 $$B_i$$ 的异或和。
形式化的讲，关于 $$C_i$$ 的递推式为以下式子：