题解

程序在最后呀 ovo

A. 等价于给每个人尽量分配多的过题数。

答案是 $\min (\frac{c}{a},b)\backslash min\; (\backslash frac\; c\; a,\; b)$ .

B. 注意到要求 "最短的回文子串(长度 > 1)", 那这就简单很多了。

情况只有两种 "aa" (长度 = 2)， "aba" (长度 = 3)。

复杂度 $O(n)O(n)$.

C 最多过几天，那就是要让每天选择不舒适度最小的即可

注意到每次使用都会使不舒适度翻倍

那么对于每个口罩，被使用的次数 上界很松，总计算量 $n\log kn\; \backslash log\; k$。

维护最小值可以使用堆 总复杂度 $O(n\log k\log n)O(n\backslash log\; k\; \backslash log\; n)$.

D 转化后就是求 分别的个数。

考虑当前枚举到 下标 $ii$

对于 且 $a[i]\times a[j]>k\iff a[j]>\frac{k}{a[i]}a[i]\; \backslash times\; a[j]\; >\; k\; \backslash Lrarr\; a[j]\; >\; \backslash frac\; k\; \{a[i]\}$.

对于 且 $a[i]\times a[j]=k\iff a[j]=\frac{k}{a[j]}a[i]\; \backslash times\; a[j]\; =\; k\; \backslash Lrarr\; a[j]\; =\; \backslash frac\; k\; \{\; a[j]\}$ .

对于 且 .

那么就把 $[1,i-1][1,\; i\; -\; 1]$ 的数做一个数点问题就可以了， 树状数组或set都ok.

复杂度 $O(n\log n)\mathrm{.}O(n\backslash log\; n).$

E 迷宫问题， 用bfs + 数组记录剪枝即可，复杂度奇怪。

F 题目的意思是重排数位使得 $n\mathrm{\%}375=0,n\le 10^{30000}n\; \backslash \%\; 375\; =\; 0\; ,\; n\; \backslash leq\; 10\; ^\; \{30000\}$.

注意到 $n={\sum }_{i=0}^{maxbit}{d}_i\times 10^{i}n=\; \backslash sum\_\{i\; =\; 0\}\; ^\; \{maxbit\}\; d\_i\; \backslash times\; 10\; ^\; i$ , $n\mathrm{\%}375=({\sum }_{i=0}^{maxbit}{d}_i\times (10^i\mathrm{\%}375))\mathrm{\%}375.n\; \backslash \%\; 375\; =\; (\backslash sum\_\{i\; =\; 0\}\; ^\; \{maxbit\}\; d\_i\; \backslash times\; (10\; ^\; i\; \backslash \%\; 375))\backslash \%375.$

举个例子

$247965\mathrm{\%}375=(2\times (10^5\mathrm{\%}375)+4\times (10^4\mathrm{\%}375)+7\times (10^3\mathrm{\%}375)+9\times (10^2\mathrm{\%}375)+6\times (10^1\mathrm{\%}375)+5\times (10^0\mathrm{\%}375))\mathrm{\%}375247965\; \backslash \%\; 375\; =\; (2\backslash times\; (10^5\; \backslash \%\; 375)\; +\; 4\backslash times\; (10^4\; \backslash \%\; 375)\; +\; 7\backslash times\; (10\; ^\; 3\; \backslash \%\; 375)\; +\; 9\backslash times\; (10\; ^\; 2\; \backslash \%\; 375)\; +\; 6\; \backslash times\; (10^1\; \backslash \%\; 375)\; +\; 5\backslash times\; (10\; ^\; 0\; \backslash \%\; 375))\; \backslash \%\; 375$

我们发现 $\mathrm{\forall }i>2,10^i\mathrm{\%}375=250.\backslash forall\; i\; >\; 2,\; 10\; ^\; i\; \backslash \%\; 375\; =\; 250.$

证明考虑归纳， 对于 $i=3,1000\mathrm{\%}375=250i\; =\; 3,\; 1000\; \backslash \%\; 375\; =\; 250$ 成立。

设 $i=k,10^k\mathrm{\%}375=250i\; =\; k,\; 10\; ^\; k\; \backslash \%375\; =\; 250$ 成立

则 $i=k+1,10^{k+1}\mathrm{\%}375=(250\times 10)\mathrm{\%}375=250.i\; =\; k\; +\; 1,\; 10\; ^\; \{k\; +\; 1\}\; \backslash \%\; 375\; =\; (250\; \backslash times\; 10)\; \backslash \%375\; =\; 250.$

所以结论成立。

所以只需要枚举最后三位取值情况判断就可以了 也就是

设 $S=d_1+d_2+\mathrm{.}\mathrm{.}\mathrm{.}+d_{maxbit}\mathrm{.}S\; =\; d\_1\; +\; d\_2\; +\; ...\; +\; d\_\{maxbit\}.$

等价于判断 $((S-d_i-d_j-d_k)\times 250+100d_i+10d_j+d_k)\mathrm{\%}375=0.((S\; -\; d\_i\; -\; d\_j\; -\; d\_k)\; \backslash times\; 250\; +\; 100d\_i\; +10d\_j\; +\; d\_k)\; \backslash \%\; 375\; =\; 0.$

枚举值域以及注意前导0的情况， 复杂度 $O(\log n+10^3)O(\backslash log\; n\; +\; 10^3)$

A : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49782231

B : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49782811

C : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49783522

D : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49785483

E : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49798093

F : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49789385