Warning: session_start(): open(/tmp/sess_db43d4d1a5874db655be4bea54b1d545, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
=====比赛信息===== * **日期：2020.7.23** * **比赛地址：** [[https://codeforces.com/group/azDPdoF24f/contest/288496/standings/groupmates/true#|传送门]] * **做题情况：lxh(H)，tyx(-)，gyp(G)** =====题解===== ====A - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====B - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====C - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====D - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====F - Finding the Order==== ===solved by tyx=== ===题意=== ===数据范围=== ===题解=== ====G - Maximum Product==== ===solved by gyp=== ===题意=== 给出$a,b$，求$[a,b]$之间各位数字乘积最大的数 ===数据范围=== $1 \le a,b \le 10^{18}$ ===题解=== 答案一定是$b$或者是和$b$有某一个前缀相同或第一位减一后面全跟着9，一共只有几十种情况，判断一下即可 ====H - Biathlon 2.0==== ===solved by lxh=== ===题意=== 给出$m$对$(c_i,d_i)$，以及$n$次询问，每次询问对于$(a,b)$，哪一对$(c_i,d_i)$能最小化$a \times c_i + b \times d_i$ ===数据范围=== $1 \le n,m \le 5\times 10^5$，$0 \le a_i,b_i \le 10^9$，$1 \le c_i,d_i \le 10^9$ ===题解=== 把询问按照$- \frac{a}{b}$排序，相当于找一个下凸包的极值点，斜率优化dp即可解决 ====I - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====J - ==== ===solved by === ===题意=== ===数据范围=== ===思路=== =====Replay===== 第一小时：tyx和lxh开始想A，gyp开始想G，tyx一开始认为A是贪心后来发现不对，lxh交了一个贪心WA了，gypG一直在WA第13个点 第二小时：tyx发现了gyp写的G题的问题，gyp通过G，lxh把A题换成了爆搜然后T了，tyx和gyp开始想J 第三小时：gyp的J题一直WA第13个点，tyx和lxh开始想H，一开始认为是三分但是一直WA 第四小时：gyp发现H题是一个凸包，可以用斜率优化解决，lxh开始写斜率优化但是一直WA，后来发现没有开longlong，开了以后通过 第五小时：三个人重新开始想A题，发现可以用bitset优化dp求解，但是空间并不够用，最后没有通过 =====总结===== * 斜率优化要注意规避精度问题 * 当某个题没有思路的时候要强迫自己换一个题想或者换一种方法