2016 Sichuan Province Programming Contest

2016 Sichuan Province Programming Contest

代码

• 2016 Sichuan Province Programming Contest

---

A. Nearest Neighbor Search

• (dx)根据(x_0)与([x_1, x_2])位置考虑。
• (dx、dy、dz)单独考虑。

---

B. Odd Discount

• 做法一：对于两个不同优惠((i,j))，所有方案中与两个优惠商品交集为奇数，即同时取到两种优惠的个数为(2^{n-2})种。
• 简要证明：

1. 记(x)为集合(i)有而集合(j)没有的个数，(y)为集合(j)有而集合(i)没有的个数，剩余(n-x-y)个考虑交集与购买方案的交集奇偶性。
2. 若交集部分与购买方案的交集为奇数，这种方案有(2^{n-x-y-1})种，那么(x)位需要和集合(i)的交集为偶数，(y)位与集合(j)的交集也偶数，方案数分别为(2^{x-1},2^{y-1})，则方案数为$$2^{x-1}cdot 2^{y-1}cdot 2^{n-x-y-1}=2{n-3}$$再考虑交集与购买方案的交集为偶数情况，方案数也是这个，所以总的方案数为$$2^{n-2}$$

• 做法二：参考ICPC-CAMP题解
• 用(f(p_1,p_2,cdots,p_i,s_{i+1},s_{i+2},cdots,s_n,r))表示已经购买了(i)件商品，(i+1cdots n)的优惠状态为(s)，且交集奇偶性为(r)的价格之和。
• 按购买的商品个数划分阶段，根据(p_{i+1})和(s_{i+1})来计算交集的奇偶性即可。

---

E. Coins

• 分类讨论：

1. 只有一种硬币时，返回相应的个数。
2. (a_1=0)，分两种情况：(a_2=1)时，$$2 | 3, imes,5 | 6, imes,8 | cdots$$即从3开始，每三个一组，每组有两个值。
   (a_2>1)时，构成$$2,3,4,5,6,7, imes,9,cdots$$
   此时，在(2a_2+3a_3)范围内有两个值取不到。
3. (a_1>0)时，分三种情况：
   (a_1 =1, a_2=0),此时构成$$1, imes,3,4, imes, imes,6,7, imes, imes,cdots$$
   共(1+2a_3)种值。
   (a_1>=2, a_2=0)，可以构出([1, a_1+3a_3])内的值。
   (a_2>0)，那么总可以构出([1, a_1+2a_2+3a_3])内的所有值。

---

F. Floyd-Warshall

• 随便构一棵树出来，那么两点之间的路径的最短路要么直接走树边，否则走非树边。
• 因为非树边最多100，涉及200个点，那么可以枚举必经的顶点，bfs到其他点的最短距离，时间复杂度为(O(200N))。

---

G. Road History

• 考虑每条边加入带来的效果（中间的推论过程）：

1. 若连接的是两个连通块，如果要构成奇数条边，则一边贡献奇数，一边贡献偶数才行。
2. 如果连接的是同一个联通块，则构成环，如果构成的环长度为偶数，显然没有什么卵用（如果其他两点需要经过这两个点，走环的任意一侧奇偶性都一样，加入这条边后也没什么改变）。如果环长度为奇数，说明整个连通块任意两点都有奇数长度的路径（因为走到奇环上可以根据需要走其中一侧可以改变路径的奇偶性）。
3. 在考虑连通块是否有奇偶性时，在1.中的合并就需要额外考虑奇环的存在。
4. 并查集维护时，需要维护当前节点到根的奇偶性，可以维护当前节点与直接父节点的奇偶性，路径压缩时直接连向根节点即可维护节点到根的奇偶性。

---

I. Longest Increasing Subsequence

• 对于(n)个数来说，我们只关心其大小关系，用(5^5)枚举每个位置的值在整个序列中的排名。
• 固定排名后，用(f(i,j))表示第(i)大的值为(j)的方案数，转移时为$$f(i,j)=sum_{k=0}^{j-1}{f[i-1][k]}$$维护前缀和即可(O(1))转移。

---

J. Matrix Transformation

• 维护四个方向的链表。