2021-2022 BUAA XCPC Team Supplementary Training 02¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 2/22 | 12 | 12 | 12 |
A¶
**solved by JLK **
题意¶
签到
题解¶
签到
B¶
solved by JLK
题意¶
给定一个\(n\times m\)的地图，有起点、终点、路和障碍物。再给一个操作序列\(s\)，每次操作为上下左右。顶到障碍物则不走，到达终点马上结束。每次可以花费一步在任意位置删去一个操作或加入一个操作。求最小代价使得能够到达终点。
\(1 \le n,m,len(s) \le 50\)
题解¶
定义状态\(d_{i,j,k}\)表示原操作序列进行完了前\(k\)个，到达\((i,j)\)的最小代价。那么每次可以：
进行原来的一个操作\(\to d_{i',j',k+1}\)
加入一个操作\(+1\to d_{i',j',k}\)
删去一个操作\(+1\to d_{i,j,k+1}\)
每次代价是1，可以用两个队列来维护BFS。
\(O(n^2len(s))\)
C¶
solved by TYB
题意¶
\(n\)个格子，其中有\(k\)个格子是黑色，剩下的\(n-k\)个是白色，要求涂黑尽量少的格子，使得任意连续的\(r\)个格子中都至少有\(2\)个黑色格子。
\(n,k,r\le10^5\)
题解¶
贪心，遇到一个不合法的区间，尽量把后面的白色格子染黑即可。
D¶
solved by TYB
题意¶
有\(n\)个问题，每个题目有解决所需时间\(t_i\)，按照如下策略完成题目：
1、随机选择\(k\)道题阅读。
2、在已经阅读过的题目中，选择耗时最短的一道题目解决它。
3、随机阅读一道没有阅读过的题目。
4、如果还有题目没有解决，返回步骤2。
一种方案的罚时为所有题目完成时间之和，求所有可能方案的罚时和，对\(10^9+7\)取模。
\(n,k\le 300,t_i\le10^6\)
题解¶
考虑每个题目的贡献，就是它的\(t_i\times\)它完成时还未解决的题目数。那么就要求某道题目第\(j\)个被解决的方案数，然而这个东西不好算，考虑算某道题目在前\(j\)个被解决的方案数。算完成时间第\(i\)小的题目在前\(j\)个被解决的方案数，可以转化为一个长度为\(n\)的排列，\(i\)在前\(\min(k+j-1,n)\)个，这前\(\min(k+j-1,n)\)个数中，有\(\le j-1\)个数\(<i\)的方案数，枚举有多少个数\(<i\)，然后就可以直接排列组合算。时间复杂度\(O(n^3)\)。
E¶
solved by Claris
题意¶
题解¶
F¶
upsolved by TYB&JLK
题意¶
有一个\(n\times n\)的方格，有\(l\)台灯，每台灯可以选择照亮横向或竖向，半径为\(r\)的区域。现在要求不能有两台灯方向相同并有照亮重合。求是否可行。
\(1 \le n,r,l \le 1000\)
题解¶
每台灯两个状况，有一些灯不能同时取某一个状况，那么就是2-SAT了。
G¶
solved by YZW
题意¶
\(n\times m\) 的地图，每个格子可为陆地、海洋或未知。未知格子可能为陆地、海洋二者之一。陆地格子之间四连通。求最大可能的陆地块数。
\(1\leq n,m\leq 40\)
题解¶
注意到与陆地相连的未知格子无贡献，肯定先钦定它们是海洋。
剩下的未知格子黑白染色连边跑二分图匹配，即可得到最大独立集的点数即最大的陆地块数。
剩余陆地格子单独统计即可。
\(O(n^2m^2)\)
H¶
solved by TYB
题意¶
给出\(k\)条线段\([l_i,r_i]\)，选择若干条没有交的线段，使得覆盖的长度尽量大。
\(l_i\le r_i\le n\le10^{18},k\le2\times10^5\)
题解¶
实际上有用的点只有\(2k\)个，即所有的\(l_i-1,r_i\)，所以离散化后直接DP即可。
I¶
solved by YZW
题意¶
坐标轴上 \(x=0\) 处坐落着邮局，邮差只能从邮局拿信出发送信，邮差同一时刻最多只能拿 \(k\) 封信。坐标轴上还分布着 \(n\) 所住户，第 \(i\) 所住户位于 \(x=x_i\) 处，需要收 \(m_i\) 封信。
邮差一分钟行进一个单位长度，求送完所有信的最短时间。
\(1\leq n\leq 1000\)，\(1\leq k,|x_i|,m_i\leq 10^7\)
题解¶
首先注意到邮差在一次送信过程中不会跨过 \(0\)，不然他肯定会经过邮局，此时把信拿满更优，于是正负分开考虑。
对于一个半轴，每次贪心地送最远的 \(k\) 封信，取模加速暴力即可。
\(O(n)\)
J¶
solved by YZW
题意¶
\(n\) 种物品，第 \(i\) 种物品价格 \(a_i\)，每种物品有无限个。
\(q\) 个人，第 \(i\) 个人拿着 \(v_i\) 单位 money，依次从第 \(l_i\) 种物品买到第 \(r_i\) 种物品，对于某件物品，能买就买，一直买到不能买为止。求最后剩下多少 money。
\(1\leq n,q\leq 2\times 10^5\)，\(1\leq a_i,v_i\leq 10^{18}\)
题解¶
只需注意到取模必定至少减半，因此一个人最多买 \(\log\) 种物品。
线段树维护区间最小值，在线段树上二分区间中最靠左且小于某个值的位置。依次找到下一个能买的物品买买买。
时间复杂度 \(O(q\log n\log v_i)\)
K¶
solved by JLK
题意¶
参考这场的D题。问的是获胜轮数。\(n\le 20\)
题解¶
相同方法，但是直接算会TLE，当当前答案够小的时候退出即可。
L¶
solved by JLK
题意¶
有\(n\)个点，要用有向线段连成一个链。给定长度为\(n-2\)的序列，表示每个拐角是往左还是往右。构造出方案。不存在三点共线。
\(1 \le n \le 50\)
题解¶
按照这种思路似乎不存在无解的情况。
现在假定确定了\(i-1\)个线段，要找第\(i\)个线段，和第\(i+1\)个线段构成第\(i\)个拐角。
假设拐角是左，当前点是\(x\)，那么找下一个点的时候，找到一个点\(y\)，如果所有没选的点\(z\)满足\(x\to y\)和\(y \to z\)两个向量的叉积大于0，那么就选这个\(y\)点。
因为这样肯定能满足第\(i\)个拐角的限制。再考虑相互是否会冲突。不难发现选的点一定是在当前所有点的凸包上，那么选这个点之后，剩下来的点不管是左还是右，一定能取到另外一个在凸包上的点满足条件。
只需要开始的时候找到一个合适的点（在凸包上的点）即可。
\(O(n^4)\)（这种数据范围的构造题暴力一点也没影响）
记录¶
开局JLK看A，失误WA了一发后AC(0:08)。
然后TYB签C(0:13)。
YZW看到J可做，JLK看到K做过类似的题。先写J，WA后AC(0:41)。
K WA之后又被卡了几次TLE之后AC(0:50)。
随后仍然看到几个可做题。YZW过I(0:55)。TYB过F(1:03)。JLK过B(1:22)。TYB过H(1:31)。YZW过G(1:45)。
同时JLK尝试构造L，没有考虑初始位置WA后AC(2:39)。
同时TYB和YZW看D，推了一下式子后过了(3:07)。
最后一起看E，找了一下Claris的板子，看到类似的，然后抄过了(3:43)。
总结¶
JLK：还是前期有点急了，罚时略多。中后期都挺稳的。
Dirt¶
A(-1)
J(-1)
K(-3)
L(-1)