2024.2.7-8 寒假训练记录（21）

洛谷P3193 [HNOI2008] GT考试

题目链接

KMP+dp+矩阵快速幂

还没有理解得很清楚，主要是对KMP理解还不够深刻

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<PII, PII> PIIII;const int N = 2010;int n, m, mod;struct Martix
{int a[30][30]; // 在这里修改矩阵的大小Martix() { memset(a, 0, sizeof(a)); }Martix operator*(const Martix &B) const // 乘法运算符重载{Martix res;for (int i = 0; i < m; i ++ )for (int j = 0; j < m; j ++ )for (int k = 0; k < m; k ++ )res.a[i][j] = (res.a[i][j] + a[i][k] * B.a[k][j]) % mod;return res;}
} G;vector<int> pi(N);
void get_pi(string s)
{int j = 0;for (int i = 2; i <= m; i++){while (j && s[j + 1] != s[i]) j = pi[j];if (s[j + 1] == s[i]) j ++ ;pi[i] = j;}for (int i = 0; i < m; i++){for (char ch = '0'; ch <= '9'; ch++){j = i;while (j && s[j + 1] != ch) j = pi[j];if (s[j + 1] == ch) j ++ ;G.a[i][j] ++ ;}}
}Martix power(Martix &a, int b)
{Martix ans;for (int i = 0; i < m; i ++ ) ans.a[i][i] = 1;while (b){if (b & 1) ans = ans * a;b >>= 1;a = a * a;}return ans;
}void solve()
{cin >> n >> m >> mod;string s; cin >> s;s = " " + s;get_pi(s);G = power(G, n);int ans = 0;for (int i = 1; i <= m; i ++ ) ans = (ans + G.a[0][i]) % mod;cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

ATC abc339E Smooth Subsequence

题目链接

线段树优化dp

把以每个数字结尾的最佳答案存进线段树中，查询即可

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 5e5 + 10;
const int mod = 1e9 + 7;struct Node
{int l, r, maxx;
} tr[N * 4];void pushup(Node &u, Node &left, Node &right)
{u.maxx = max(left.maxx, right.maxx);
}void pushup(int u)
{pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}void build(int u, int l, int r)
{tr[u] = {l, r, 0};if (l == r) return;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}void modify(int u, int pos, int x)
{if (tr[u].l == pos && tr[u].r == pos){tr[u].maxx = x;return;}int mid = tr[u].l + tr[u].r >> 1;if (pos <= mid) modify(u << 1, pos, x);else modify(u << 1 | 1, pos, x);pushup(u);
}Node query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r) return tr[u];int mid = tr[u].l + tr[u].r >> 1;if (r <= mid) return query(u << 1, l, r);else if (l > mid) return query(u << 1 | 1, l, r);else{auto left = query(u << 1, l, mid);auto right = query(u << 1 | 1, mid + 1, r);Node res = {l, r};pushup(res, left, right);return res;}
}void solve()
{int n, d;cin >> n >> d;build(1, 1, N);vector<int> dp(n + 1);for (int i = 1; i <= n; i ++ ){int x;cin >> x;Node res = query(1, x - d, x + d);dp[i] = max((i64)1, res.maxx + 1);modify(1, x, dp[i]);}int ans = 0;for (int i = 1; i <= n; i ++ ){ans = max(ans, dp[i]);}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

ATC abc339F Product Equality

题目链接

哈希

这里的一个trick是，乘积的个数比较少，哈希之后很可能出现一样的关键字，此时可以进行双哈希（或更多的哈希都没问题），取不同的模数，减小出现相同关键字的概率

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 5e5 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;void solve()
{int n;cin >> n;vector<string> a(n);map<int, int> mp1, mp2;auto mm = [&](string s, int mod){int res = 0;for (auto t : s){res = (res * 10 + t - '0') % mod;}return res;};vector<int> b1(n), b2(n);for (int i = 0; i < n; i ++ ){cin >> a[i];b1[i] = mm(a[i], mod1);mp1[b1[i]] ++ ;b2[i] = mm(a[i], mod2);mp2[b2[i]] ++ ;}int ans = 0;for (int i = 0; i < n; i ++ ){for (int j = 0; j < n; j ++ ){ans += min(mp1[(b1[i] * b1[j]) % mod1], mp2[(b2[i] * b2[j]) % mod2]);}}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}