Qoj 9111 Zayin ans String / ABC 356 E
谨以此帖记录一个有意思的 Trick
题意
给了一个长度为 \(n\) 的目标串 \(s\) 和 \(m\) 个模式串
每个模式串有一个价值 \(v\)
要求从 \(s\) 中选出一个子序列 \(t\)， 定义 \(t\) 的价值为他的所有子串的价值和（若该子串没出现在模式串中， 那么他的价值为 0）
最大化 \(t\) 的价值和长度的比值
思路
看到多模匹配问题， 想到 AC 自动机
考虑把所有模式串加到 AC 自动机里面， 然后在自动机上 dp
自然地想到 \(dp(i, j, k)\) 表示现在在 \(s\) 的第 \(i\) 位， 选了 \(j\) 位， 这一位在自动机的 \(k\) 节点上
转移就枚举选的下一位是谁
时间复杂度 \(O(n^4)\)， 不可接受
现在该 Trick 救场了
难点在于我们无法直接比较一个选了 \(i\) 位， 一个选了 \(j\) 位的两个子序列的价值， 所以必须记录他们的长度
现在介绍一种方法
二分答案为 \(lim\)
\[lim = \frac{\sum_{0 \le i \le j < |T|} val(i, j)}{|T|} \]把长度移项
\[|T| * lim = \sum_{0 \le i \le j < |T|} val(i, j) \]这样， 等式右侧的是 \(dp\) 值， 左侧的 \(|T|\) 开一个数组来记录
每次转移的时候 \(dp -= lim\)
因为每转移一次， 位数增加一， 所以只需看最后的 \(dp\) 是否为非负数即可判断该答案是否合法
该 Trick 的关键在于实现 在不记录长度的情况下， 比较两个子序列的价值大小
代码
#include <bits/stdc++.h>
#define int long long
#define double long double
#pragma GCC optimize(2)
using namespace std;
const int N = 1e5 + 10, MOD = 998244353, INF = 1e9;
const double eps = 1e-17;
int Q_pow(int a, int b){
int ans = 1, p = a;
while(b){
if(b & 1) ans = (ans * p) % MOD;
b >>= 1;
p = (p * p) % MOD;
}
return ans;
}
int t;
int n, m, val;
string s, ss;
struct Node{
int son[26];
int fail, ed;
}tr[N];
int cnt, sum[N], v[N][26];
queue <int> q;
void Insert(string s, int v){
int p = 0;
for(auto i : s){
int ch = i - 'a';
if(!tr[p].son[ch]) tr[p].son[ch] = ++cnt;
p = tr[p].son[ch];
}
tr[p].ed += v;
}
void Get_fail(){
for(int i = 0; i < 26; i++){
if(tr[0].son[i]){
q.push(tr[0].son[i]);
}
}
while(!q.empty()){
int tp = q.front();
q.pop();
sum[tp] = sum[tr[tp].fail] + tr[tp].ed;
for(int i = 0; i < 26; i++){
if(tr[tp].son[i]){
tr[tr[tp].son[i]].fail = tr[tr[tp].fail].son[i];
q.push(tr[tp].son[i]);
}else{
tr[tp].son[i] = tr[tr[tp].fail].son[i];
}
}
}
}
double f[1001][4001];
int dp[1001][4001], len[1001][4001];
bool Check(double lim){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= cnt; j++){
f[i][j] = -INF;
dp[i][j] = 0;
len[i][j] = 0;
}
}
f[0][0] = 0;
dp[0][0] = 0;
len[0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= cnt; j++){
f[i + 1][j] = f[i][j];
dp[i + 1][j] = dp[i][j];
len[i + 1][j] = len[i][j];
}
for(int j = 0; j <= cnt; j++){
int ch = s[i] - 'a';
int to = tr[j].son[ch];
if(!to) continue;
if(f[i + 1][to] + eps < f[i][j] + sum[to] - lim){
f[i + 1][to] = f[i][j] + sum[to] - lim;
dp[i + 1][to] = dp[i][j] + sum[to];
len[i + 1][to] = len[i][j] + 1;
}
}
}
for(int i = 1; i <= cnt; i++){
if(f[n][i] >= 0){
return 1;
}
}
return 0;
}
signed main(){
// freopen("1.in", "r", stdin);
cin >> t;
while(t--){
cin >> n >> m >> s;
for(int i = 1; i <= m; i++){
cin >> ss >> val;
Insert(ss, val);
}
Get_fail();
double l = 0, r = 2e8, ans = 0;
for(int i = 1; i <= 50; i++){
double mid = (l + r) / 2;
if(Check(mid)){
ans = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
Check(ans);
for(int i = 1; i <= cnt; i++){
if(f[n][i] >= 0){
int ret = dp[n][i] * Q_pow(len[n][i], MOD - 2) % MOD;
cout << ret << "\n";
break;
}
}
for(int i = 0; i <= cnt; i++){
memset(tr[i].son, 0, sizeof(tr[i].son));
tr[i].ed = tr[i].fail = 0;
sum[i] = 0;
}
cnt = 0;
}
}
类似的题 - ABC 356 E
题意
求 \(\sum_{(a_i, a_j)} \frac{a_i}{a_j}\) \((i\ != j\ 且 a_i \ge a_j)\)
思路
转化一下， 其实就是在求 \([k * a_j, (k + 1) * a_j)\) 的数量再乘上 \(k\)
类似埃氏筛地做即可
和上面那题类似， 都是把除数均摊到了每一步上
代码
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 1e7 + 10;
int n;
int a[N], sum[N];
map <int, int> cnt;
signed main(){
// freopen("1.in", "r", stdin);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
cnt[a[i]]++;
sum[a[i]]++;
}
for(int i = 1; i <= (int)1e7; i++){
sum[i] += sum[i - 1];
}
int ans = 0;
for(auto i : cnt){
int ti = 1;
ans += (sum [i.first + i.first - 1] - sum[i.first]) * i.second;
for(int j = i.first + i.first; j <= 2e6; j += i.first){
++ti;
ans += (sum[j + i.first - 1] - sum[j - 1]) * ti * i.second;
}
ans += (i.second - 1) * i.second / 2;
}
cout << ans << "\n";
}