Warning: session_start(): open(/tmp/sess_04f6bfdcfe6ce9595a9ee3031a5116be, 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
====== 比赛地址 ======
[[https://ac.nowcoder.com/acm/contest/5666 |牛客OJ]]
Rank: 116/1116
Pro: 4/5/10
====== 题解 ======
===== [A] B-Suffix Array =====
==== 题意 ====
给出一个仅包含a和b的字符串,对于该字符串的每一个后缀,定义一个键值,键值第$i$位的值是出现在该后缀中的最后一个和第$i$位的字母相同的位置与$i$的差(如果没有就是0).然后对于所有的键值进行排序.求最后结果.
==== 题解 ====
盲猜了一波结论.
定义$a[i]$为第$i$位后面第一个相同字母的位置与$i$的差,然后将这个值看做一个新的字符串,进行后缀排序,排序的结果就是答案.
===== [F] Infinite String Comparision =====
==== 题意&题解 ====
签到题
===== [H] Minimum-cost Flow =====
==== 题意 ====
给出一个图以及每条边的费用.有一些询问,每一个询问会给出两个数字,$u,v$.然后对于每一组询问,每条边的流量会变成$\frac{u}{v}$.求从点1到点n流量为1时的最小费用.
==== 题解 ====
增广路径的选择与流量无关,所以可以先预处理出所有的增广路径,然后对于每一个询问尝试让这些路径流满就行了.
===== [J] Easy Integration =====
==== 题意 ====
求$\int_{0}^{1}(x-x^{2})^{n}dx \mod 998244353$
==== 题解 ====
含参变量积分中的Beta函数.
结论:$B(p,q)=\frac{\Gamma(p)\Gamma(q)}{\Gamma(p+q)}=\frac{(p-1)!(q-1)!}{(p+q-1)!}$
====== 总结 ======
第一场真的是开幕雷击.
开场做了F和J后陷入了很长一段时间的空档期.A题一直TLE,怀疑是后缀排序的问题,换成上交的板子之后一发AC.之后主要的精力放在了H和I上.写H的时候真的是失了智了,一个变量清空太早导致一直RE,如果能及时发现错误的话,很快就可以想到优化手法了.D题最后推出来了式子,却陷入到了WA的轮回里.
整体状态欠佳,希望明天好好发挥吧.
这次的比赛告诉我们学好高代和淑芬是多么的重要.以后出去打区域赛一定要带上数学笔记去.