【题解】“中国东信杯”广西大学第二届程序设计竞赛（同步赛）
首先这套题考虑到本校同学的水平以及因校情导致不能让我们的榜过于难看，实际上除了最后一题的数据都是很弱的，可能会影响其他学校同学的做题体验，所以先给大家道个歉（x）
我们之后会上传相对正常一些的数据，非常感谢大家能够参加我们的校赛同步赛！
A.“区 块 链”
应该大家都能做出来所以就不讲了，基本循环输入输出，部分语言注意双引号的转义
B. “人 工 智 能”
在给了说明的情况下模拟朴素的图像卷积
这题做不出来的正在从事cv方向学习的同学还是换个方向吧（笑）
因为卷积操作是一个累加乘积的过程，空白填充0的区域，这些区域与数累加相乘的和是0，所以其实可以不用计算
所以三种模式其实就是三种边界：
VALID：)
FULL：%2C%20n))
SAME：)
C. “大 数 据”
倒序判断是否相等即可，也是基本循环输入输出D. “云 计 算”
首先我们的目的是求：
那么显然可以贪心：让
大的值尽可能和更小的值相乘
但是这三项中
和
的变化规律相反，那么变形：
但是这三项中
因此按
E. Antinomy与红玉海
首先很明显答案的上限可以是但真的需要那么多吗？显然答案应该在
那么就可以二分check，那么如何check呢？
显然可以贪心一下，对于每一个卑微红：
1. 如果ans小于他想玩的回合数那肯定是不可行的
2. 如果大于他玩的局数，那么说明这个卑微红可以当
局的工具人
3. 如果大家可以当工具人的回合数 高于 当前ans那么说明这个ans是可行的
1. 如果ans小于他想玩的回合数那肯定是不可行的
2. 如果大于他玩的局数，那么说明这个卑微红可以当
3. 如果大家可以当工具人的回合数 高于 当前ans那么说明这个ans是可行的
时间复杂度))
但比赛时由于数据较弱其实有其他的假算法
首先直线平不平行看斜率就好，我们可以把“在同一条直线”的点看成一个集合，并且这个集合内满足传递性
由于点必须都在某条直线上，那么我们随便使用一个点（1号点），用斜率相等这个关系让每个点和他计算一下，得到若干个并查集
F. Antinomy与水晶都
看上去是几何题但实际上除了斜率的计算外和计算几何没什么关系了首先直线平不平行看斜率就好，我们可以把“在同一条直线”的点看成一个集合，并且这个集合内满足传递性
由于点必须都在某条直线上，那么我们随便使用一个点（1号点），用斜率相等这个关系让每个点和他计算一下，得到若干个并查集
然后我们枚举这些并查集，由于只应该有两条直线
所以对于不在第 i 个并查集的所有点应该在同一条直线上
这样就ok，复杂度约等于)
所以对于不在第 i 个并查集的所有点应该在同一条直线上
但比赛时由于数据较弱其实有其他的假算法
G. Antinomy与LaHee大森林
首先所有路径数显然是排列 可以接受的路径数 = 所有路径数 – 要避免的路径数
所以问题变为我们怎么计算先经过x再经过y的路径
请注意这是棵树，画一画就能发现。树上的最短路径而言，对于点 a 的子树，他去这个子树以外点的路径一定会经过点 a
时间复杂度)
是个有向图，很明显一个环里（或者说强连通分量）里都是可以隐藏掉的，我们可以直接把一个环当成一个点，资源是环上个点资源的总和
那这样的新点肯定是形成一个有向无环图DAG
然后我们在这个新图上跑最长路
H. Antinomy与伊尔美格
那这样的新点肯定是形成一个有向无环图DAG
然后我们在这个新图上跑最长路
什么？如何求最长路？
1. 你可以让边权都为负然后求最短路（当然不能用Dijsktra，可以用Bellman-Ford或者SPFA）
2. 因为是DAG，可以拓扑排序然后动态规划
3. Floyd是不行的（也不看看多少个点）
时间复杂度取决于如何求最长路
1. 你可以让边权都为负然后求最短路（当然不能用Dijsktra，可以用Bellman-Ford或者SPFA）
2. 因为是DAG，可以拓扑排序然后动态规划
3. Floyd是不行的（也不看看多少个点）
投递深圳同为数码等公司10个岗位