====== 比赛地址 ======

[[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的轮回里.

整体状态欠佳,希望明天好好发挥吧.

<del>这次的比赛告诉我们学好高代和淑芬是多么的重要.以后出去打区域赛一定要带上数学笔记去.</del>