前言

有人会问ATSC是啥，自然是安徒生菜Australian Team Selection Contest啦

本蒟蒻考爆炸了→_→，但是为了业界良心，以及后人不会再思博，我拿出来共享一下2333

版权？未经授权别想了，反正他也看不懂中文(flag

详细题解参见在下的博客：http://medalplus.com

D1T1 Banarby's Farm

题目大意

给你一个网格图，每个点有个高度，你可以走上下左右四个方向，当且仅当相邻点和当前点的高度差不超过一个给定的常数$k$，你作为苦逼农场主，为了去铲金坷垃，你得从$(S_{x},S_{y})$出发，到$(E_{x},E_{y})$去。你想了一下，发现...你去不了。于是你需要搭桥，两个点之间能搭桥当且仅当

1. 两点在同一行或者同一列
2. 他们的高度差不超过$k$
3. 他们之间的所有点（不包括两端）的高度都严格小于他们的高度

因为经济危机，你得最小化需要的桥的数量。数据范围$N,M\leq 1000,H\leq 10^{9}$

Solution

几乎是签到题，根据性质三，我们不难想到用单调栈去优化建图，然后跑堆优化的$dijkstra$，这样时间复杂度就是$O(nm+nmlognm)$了。

D1T2 Eastconnex

题目大意

悉尼修了新路，城市由$N$条横向高速公路和$M$条纵向泥巴路组成。泥巴路从左往右标号，高速公路从下往上标号，泥巴路之间的距离间隔都是$1$，第$i$条高速路和第$i+1$条高速路的距离间隔为$A_{i}$，记$(i,j)$表示第$i$条泥巴路和第$j$条高速公路的交点。在泥巴路上走一个长度单位只需要$1$美元，而第$i$条高速公路上走一个长度单位则需要$C_{i}$美元。有$Q$个询问，每次询问从$(x,y)$出发，到达$(a,b)$的最小花费。$N,Q\leq 10^{5},M\leq 10^{9},everything else\leq 10^{9}$

强制在线

Solution

先对$A$做前缀和。

不难发现，正解一定长这样$(x,y)->(x,i)->(a,i)->(a,b)$，然后分三种情况讨论，我们发现花费为$\left | A_{y1}-A_{i} \right |+\left | X_{1}-X_{2} \right |\times Cost_{i}+\left | A_{y2}-A_{i} \right |$，然后根据小学数学，我们画端点分区间讨论，一共有三种情况分别为$\left\{\begin{matrix}A_{y1}-A_{i}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{y2}-A_{i}\\A_{i}-A_{y1}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{y2}-A_{i}\\A_{i}-A_{y1}+\left | X_{1}-X_{2} \right |\times Cost_{i}+A_{i}-A_{y2}\end{matrix}\right.$

相信大家都会做了QAQ，情况一三凸壳上树，线段树上做CHT，情况二RMQ问题。

证明？反证法证明。留bu给gao读su者ni自he己he思he考he。

D1T3 Guards

题目大意

悉尼大学有$N$幅世界名画，其中包含蒙娜考拉等，编号$1$到$N$，排成一排。第$i$幅画的价值为$V[i]$。你是著名神偷·怪盗基德，你要去偷画，但是可惜，大学有$G$个条子，每个条子保护$[S_{i},E_{i}]$内的所有画。但是第$i$个条子可以被$C_{i}$刀贿赂从而离开岗位，你的收益是偷到的画的价值减去用来贿赂的钱。聪明的你，能写个程序算一波么？$N,M\leq 2\times10^{5},V[i],C[i]\leq 10^{9}$

Solution

设$f[i]$表示前$i$幅画的答案，其中强制购买第$i$幅画

那么我们考虑存在这样一个指针$j$从$i$开始，往$i$走。那么有转移方程$f[i]=max\left \{ f[j-1]-counter+v[i] \right \}$

其中$counter$表示所有以我们中途$j$遇到的点为起点，终点$\geq i$的守卫的贿赂价值总和。

不难发现每个守卫的贡献都是对前缀所增加的。而守卫因为$i$的增加而逐渐被扔掉，所以我们很容易用双指针扫描线＋线段树去优化这个转移方程。

时间复杂度$O(n\log n)$

D2T1 Mahjong

题目大意

连连看（原题是麻将但是。。我实在不懂和麻将有什么关系，不如翻译成连连看好了），有$P$对点是配对的，给出一张无向图，不保证连通，无重边无自环。图上的每一个点保证都有配对对象。两个点能消去当且仅当

1. 他们是配对的。
2. 他们之间存在一条路径，不经过任何还没被消除的点。

试问最多能消去几对点？

Solution

考虑对点建DSU？关系不满足传递性，GODIE！

那么按照边建DSU，DSU同时附带维护SET，那么每次合并采用启发式合并，然后利用宽搜的方式去扩展状态即可。

时间复杂度$O(m\log n)$

D2T2 Sushi Selection

题目大意

有$T$个店，每个店卖$A_{i}$个寿司，因为做促销，在第$i$家店，买$k$个寿司，所需要的价格为$\sum_{j=0}^{k}V[i][j]$，保证$V[i][j]\geq V[i][j+1]$

你要买$M$个寿司，最小化花费。$M\leq\sum A_{i}\leq 10^{5},T\leq 230$

Soltuion

不难用反证法证明至多有一家店没买完。

于是问题就变成了经典问题，限定性01背包问题。我们直接用CDQ分治做即可。

D2T3 Ez

不想写了。。。直接主席树即可。

完结。感觉还是自己SB考挂了没去IOI，真的菜鸡。