2020-2021:teams:wangzai_milk:weekly2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:weekly2 [2020/05/15 23:31] infinity37 [题目] |
2020-2021:teams:wangzai_milk:weekly2 [2020/05/24 13:27] (当前版本) zars19 [团队训练] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 2020.05.11-2020.05.17 周报 ====== | ====== 2020.05.11-2020.05.17 周报 ====== | ||
| ===== 团队训练 ===== | ===== 团队训练 ===== | ||
| - | 2020.05.13 [[https://vjudge.net/contest/373595#rank|2019 Multi-University Training Contest 1]] ''prob: 3:5:13'' ''rnk：141/?'' | + | 2020.05.13 [[https://vjudge.net/contest/373595#rank|2019 Multi-University Training Contest 1]] ''prob: 3:7:13'' ''rnk：141/?'' |
| [[20200513比赛记录]] | [[20200513比赛记录]] | ||
| 行 41: | 行 41: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| - | [[后缀自动机]] ''待填坑'' | + | [[后缀自动机]] ''好题推荐/广义后缀自动机待填坑'' |
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| 行 50: | 行 50: | ||
| [[20200513比赛记录#f-typewriter]] | [[20200513比赛记录#f-typewriter]] | ||
| ===== Zars19 ===== | ===== Zars19 ===== | ||
| + | |||
| + | ==== 题目 ==== | ||
| + | |||
| + | [[20200513比赛记录#D-Vacation]] | ||
| + | |||
| + | [[20200513比赛记录#A-Blank]] | ||
| + | |||
| + | ==== 比赛 ==== | ||
| + | |||
| + | [[https://atcoder.jp/contests/abc155/|AtCoder Beginner Contest 155]] | ||
| + | |||
| + | 很久之前的$\text{ABC}$，$\text{atcoder}$的题的确画风不太一样。前三题都很简单，从后面说起 | ||
| + | |||
| + | **[[D. Pairs]]** | ||
| + | |||
| + | 给出一个长度$N$的数组，问两两乘积的第$K$大。 | ||
| + | |||
| + | 题解：第$K$大的乘积是正数、负数、零很容易计算得出，然后对于正负数的情况分别进行二分，结果在$[-10^{18},10^{18}]$。check过程中对每个数字lower_bound计算对小于等于$\text{mid}$的乘积数的贡献。正数的情况要注意每组被计算两次，以及数字与自己本身的乘积不能计入。另外各种取整要想清楚。 | ||
| + | |||
| + | **[[E. Payment]]** | ||
| + | |||
| + | 给出$N$在$1$到$10^{1,000,000}$之间，可以使用$10$的整数幂面值的纸币，如果你的支付大于$N$店员会找给你多余的钱，问你和店员使用的纸币张数总和的最小值。 | ||
| + | |||
| + | 题解：用$\text{dp[i][0]}$和$\text{dp[i][1]}$分别表示在第$i$位付正好的钱和多付$1$个单位的钱的最小张数。只要想到表示方式状态转移方程就也很好想，从高位到低位扫一遍。 | ||
| + | |||
| + | **[[F. Perils in Parallel]]** | ||
| + | |||
| + | $N$个炸弹处在坐标轴上，给出每个炸弹的坐标和状态$A_i,B_i$，状态为$1$表示激活$0$表示非激活。$M$项可选操作，每项操作$l_i,r_i$表示将坐标处在这个区间的炸弹状态反转。问有没有没有一个操作集可以使得所有炸弹状态为$0$。 | ||
| + | |||
| + | 题解：定义操作$O_i$为反转坐标在$i$及以前所有炸弹的状态，将炸弹状态$w$数组进行异或差分，操作$O_i$相当于仅改变$w_{i+1}$。题中操作可以分解成$O_{l_i-1}$和$O{r_i}$，将$l_i$和$r_i+1$两点之间连边（lower_bound查找后），反转时一次要同时改变两个端点的状态，故图中每一连通块中状态为$1$的点需要是偶数个，如不是则没有可能。若符合则必有可能的方案，用任意生成树，由叶子节点到根判断是否需要反转即可。 | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| 行 55: | 行 85: | ||
| [[https://vjudge.net/problem/HDU-6583/origin|HDU6583 TypeWriter]]:这题一贴出来，就知道，老没做题了（别骂了），但是这道题目确实比较有意思，后缀自动机优化dp，如果搞懂了这道题目会让后缀自动机的使用灵活程度upup，避免只会写后缀自动机模版题的尴尬场面。 ——Infinity37 | [[https://vjudge.net/problem/HDU-6583/origin|HDU6583 TypeWriter]]:这题一贴出来，就知道，老没做题了（别骂了），但是这道题目确实比较有意思，后缀自动机优化dp，如果搞懂了这道题目会让后缀自动机的使用灵活程度upup，避免只会写后缀自动机模版题的尴尬场面。 ——Infinity37 | ||
| + | |||
| + | [[https://atcoder.jp/contests/abc155/tasks/abc155_e|abc155 E. Payment]]:是赛时没有想出的题目，但代码很短，思路很简单。是神奇dp思维题。——Zars19 | ||
2020-2021/teams/wangzai_milk/weekly2.1589556677.txt.gz · 最后更改: 2020/05/15 23:31 由 infinity37
