考场

看 \(t1\) 特别像省选 \(day2\) \(t1\)，然而做法没有任何扩展性
于是写了一个背包骗到部分分，开始想怎样套上鸽巢原理，写了一个在随机数据下比较正确的做法就撤了
\(t2\) 一开始 \(n\) 多看了一个零，以为 \(O(n)\) 过不去，想了半天求循环节，发现过不了
后来想到既然多于 \(\frac{n}{2}\)，那么随机的概率是非常大的，于是卡个时随机 8 次位置就自信提交了
\(t3\) 写了类似后来算法一的做法，然而发现并过不了大样例，并且一开始没有发现边权为 0 对答案的影响，最后手模随机样例才发现了漏洞

本来 60+100+60=220 是个很不错的分数，然而万万没想到由于 \(t2\) 最后统计答案的时候写挂了！！！\(t3\) 也因为写法问题没有得到部分分
以后对于没给大样例的正解一律要对拍！！！

---

A. Set

对于数列求前缀和，那么区间和为零相当于两个前缀和相减为零。
根据鸽巢原理 \(n+1\) 个位置里一定有两个相同，输出即可

---

B. Read

既然有一个值出现的位置多于 \(\frac{n}{2}\)，那么随机一个位置，随机到这个值的概率至少 \(\frac{1}{2}\)，那么随机次数达到 10 次左右可以认为几乎正确了。本地随机数据测试基本上最多试两次就可以出答案。
题解给出摩尔投票法，即和自己相同计数器+1，否则-1，那么最坏情况所有非关键值都给关键值-1，还是会剩下要求的关键值。
这里的理解方式非常形象

---

C. 题目交流通道

首先对于边权全为正的情况，若两点 \((i,j)\) 存在点 \(k\)，满足 \(dis[i][k]+dis[k][j]=dis[i][j]\)，那么这条边的值只要比 \(dis[i][j]\) 大即可，有 \(k-dis[i][j]+1\) 种方案