ZJUT12 Day5

1、CF 1426C Increase and Copy

tags：数学、贪心

首先要认识到这样一个事实：先加再添加该数永远比先添加该数再加划算。

举个例子。比如我们现在从数列里取出某元素$x$，那么第一种操作对应的增量为$2(x+1)-x=x+2$，第二种操作对应的增量为$2x+1-x=x+1$。

所以一定是把最开始的$1$先添加到某个量以后再在数列末尾不断添加该数。

假设我们执行了$x$次$+1$操作，$y$次将该数添加至数列末尾的操作，那么我们可以依据题目条件得到$(1+x)(1+y)\ge n$。

所以$(x+y{)}_{min}\ge x+\frac{n}{1+x}-1$。

这玩意儿拿基本不等式搞一搞得到取等条件为$x=\sqrt{n}-1$。

不过因为根号这东西可能是小数，所以比较一下$\lfloor x\rfloor ,\lfloor x+1\rfloor ,\lfloor x-1\rfloor$三个函数值就好了。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int calc(const int &n, const int &x) { return x - 1 + n / (1 + x) + (n % (1 + x) != 0); } int main() { int t; cin >> t; while (t--) { int n; cin >> n; int s = sqrt(n) - 1; int ans = calc(n, s); if (s >= 1 && calc(n, s - 1) < ans) ans = calc(n, s - 1); if (calc(n, s + 1) < ans) ans = calc(n, s + 1); cout << ans << endl; } return 0; }

2、*CF 432D Prefixes and Suffixes

tags：字符串，KMP，dp

这道题目非常好。

看到和字符串前缀有关第一反应就是KMP。先把前缀和后缀相等这个条件放一边，我们来研究一下怎么快速统计某字符串中任意前缀的出现次数。

设$f[i]$为$s[1..i]$在字符串$s$中的出现次数，那么显然$f[n]=1$。($n$为字符串长度)

那么考虑如何计算$f[i]$。首先明白这样一个事实：子串$s[1..i]$在$s$中出现和$s[i]$某个前缀的某个后缀等于该子串等价。

听起来有些拗口，下面举个例子：$abcababcabc$。

前缀$abc$在这个字符串中的出现位置为$[1,6,9]$。(下标从一开始)。

所以我们可以把这个串分为$abc/ababcabc$，$abcababc/abc$，$abcababcabc/$。其中$/$号将整个字符串划分为了两个子串，而在第一个子串中$abc$是它的一个后缀。

分析到这里，我们会发现出现了一个非常熟悉的东西。观察上例的第一个子串。因为$abc$是整个字符串的一个前缀，所以它必定作为前缀出现在第一个子串中；而我们又知道$abc$又是第一个子串的后缀，所以$abc$其实是第一个子串的最长公共前后缀。

所以递推转移式就很自然地可以写出来了。因为$f[n]$我们已经知道等于$1$，所以采取从后往前刷表递推的方式。当我们计算到$f[i]$时，$f[i]$作为某个前缀的后缀的所有出现次数已经计算过了。那么由于$next$数组计算的是真后缀，所以它本身作为自己的最长公共前后缀的情况并没有统计到，所以首先我们将$f[i]$加一；其次，根据上面的分析，这个值对之后值产生的贡献其实就是$f[next[i]]+=f[i]$。

为了统一递推关系，我们可以把$f$初始化为全$0$，这样$f[n]$也可以包含在该关系式里。

那个看起来很迷惑的递推$f$的循环实际上是这么来的，我也是第一次看到，思考了好半天。记录下来方便后人。

那么这题只剩下统计相等前后缀了。本来想用哈希跑，不过我看到大师的代码里是直接拿next跳的。仔细想一想确实很巧妙。首先自己是一个，下一个相等的前后缀那肯定就是next[n]，再下一个就是next[next[n]]…。

可以理解为next每次都是前后对称的一个东西。还是对next的理解不够。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5 + 10; char s[MAXN]; int main() { scanf("%s", s + 1); int n = strlen(s + 1); vector <int> nxt(n + 1, 0), f(n + 1, 0); for (int i = 2, j = 0; i <= n; ++i) { while (j > 0 && s[j + 1] != s[i]) j = nxt[j]; if (s[j + 1] == s[i]) ++j; nxt[i] = j; } for (int i = n; i >= 1; --i) { ++f[i]; f[nxt[i]] += f[i]; } vector <int> ans; for (int i = n; i; i = nxt[i]) ans.push_back(i); cout << ans.size() << endl; for (auto i = ans.rbegin(); i != ans.rend(); ++i) cout << *i << ' ' << f[*i] << endl; return 0; }