C - easy math
\[\Pi a_i \le 2024^b\\ \log_2 (\Pi 2^{k_i}) \le \log_2(2024^b)\\ \sum k_i\le b\log_2 2024 \]因此答案就是\(b = \frac{\sum k_i}{\log_2 2024}\)
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;
#define int i64
using pii = pair<int,int>;
using vi = vector<int>;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
int sum = 0;
for(int i = 0, x; i < n; i ++) {
cin >> x;
sum += log2(x);
}
cout << ceil(sum / log2(2024));
return 0;
}
E - 拼接串
考虑值域只有\(18\),因此我们可以用\(f[i]\)表示状态\(i\)对应的最长区间。其中\(i\)是一个\(18\)位二进制整数
我们可以先用双指针统计出每个\(l\)对应的合法区间的最大右端点\(r\)。并且更新\(f\)。
然后我们可以在做一次dp,状态为\(g[i]\)表示\(i\)的子集对应的最场区间。
此时答案就可以表示为\(\max(g[i]+g[(2^{18} - 1) \oplus i])\)。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;
#define int i64
using pii = pair<int,int>;
using vi = vector<int>;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vi a(n + 1);
for(int i = 1; i <= n; i ++)
cin >> a[i], a[i] = (1 << (a[i] - 1));
int N = (1 << 18) - 1;
vi f(N + 1);
for(int l = 1, r = 0, t = 0; l <= n; l ++) {
while(r + 1<= n and (t & a[r + 1]) == 0)
r ++, t |= a[r];
f[t] = max(f[t], r - l + 1);
t ^= a[l];
}
for(int i = 0; i < N; i ++) {
for(int j = 1; j <= N; j <<= 1){
if((i & j) == 0)
f[i | j] = max(f[i | j], f[i]);
}
}
int res = 0;
for(int i = 0; i <= N; i ++)
res = max(res, f[i] + f[N ^ i]);
cout << res;
return 0;
}
H. 经文
\(f[i][j][l]\)表示前\(i\)位,且已经匹配了\(j\)个完整的串,当前串匹配到了\(l\)的方案数。然后我们可以枚举下一位放什么,这里面如果失配,下一位不一定需要从头开始匹配,我们可以用\(kmp\)的前缀数组进行计算下一位可能匹配到哪一位。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;
#define int i64
using pii = pair<int,int>;
using vi = vector<int>;
vector<int> prefix_function(const string &s) {
vector<int> pi(s.size());
for (int i = 2, j = 0; i < s.size(); i++) {
while (j > 0 && s[i] != s[j + 1]) j = pi[j];
if (s[i] == s[j + 1]) j++;
pi[i] = j;
}
return pi;
}
const int mod = 998244353;
struct mint {
int x;
mint(int x = 0) : x(x) {}
int val() {
return x = (x % mod + mod) % mod;
}
mint &operator=(int o) { return x = o, *this; }
mint &operator+=(mint o) { return (x += o.x) >= mod && (x -= mod), *this; }
mint &operator-=(mint o) { return (x -= o.x) < 0 && (x += mod), *this; }
mint &operator*=(mint o) { return x = (i64) x * o.x % mod, *this; }
mint &operator^=(int b) {
mint w = *this;
mint ret(1);
for (; b; b >>= 1, w *= w) if (b & 1) ret *= w;
return x = ret.x, *this;
}
mint &operator/=(mint o) { return *this *= (o ^= (mod - 2)); }
friend mint operator+(mint a, mint b) { return a += b; }
friend mint operator-(mint a, mint b) { return a -= b; }
friend mint operator*(mint a, mint b) { return a *= b; }
friend mint operator/(mint a, mint b) { return a /= b; }
friend mint operator^(mint a, int b) { return a ^= b; }
};
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, k;
cin >> n >> k;
string s;
cin >> s;
int m = s.size();
s = " " + s;
auto pi = prefix_function(s);
vector f(n + 1, vector(k + 2, vector<mint>(m + 1)));
f[0][0][0] = 1;
for(int i = 0; i < n; i ++) {
for(int j = 0; j <= k; j ++) {
for(int l = 0; l < m; l ++){
for(char c = 'a'; c <= 'z'; c ++) { // 枚举 i+1 位放什么字母
bool ok = false;// 有没有匹配成功过
for(int pre = l; ok == false; pre = pi[pre]) {
if(s[pre + 1] == c) { // 匹配
if(pre == m - 1){
f[i + 1][j + 1][0] += f[i][j][l];
} else {
f[i + 1][j][pre + 1] += f[i][j][l];
}
ok = true;
}
if(pre == 0) break;
}
if(ok) continue;
f[i + 1][j][0] += f[i][j][l];
}
}
}
}
mint res = 0;
for(int i = 0; i < m; i ++)
res += f[n][k][i];
cout << res.val();
return 0;
}
I - 数据检索系统
按照题目模拟
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;
#define int i64
using pii = pair<int,int>;
using vi = vector<int>;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int mod, k, n, q;
cin >> mod >> k >> n >> q;
vi vis(mod);
for(int x; n; n --) {
cin >> x;
for(int i = 1, y = 1; i <= k; i ++) {
y = y * x % mod;
vis[y] |= 1;
}
}
for(int x, f; q; q --) {
cin >> x, f = 1;
for(int i = 1, y = 1; i <= k; i ++) {
y = y * x % mod;
f &= vis[y];
}
cout << f << " ";
}
return 0;
}
J - Beautiful Sequence
对于数组\(a[i]\)我们记\(A\)表示数字\(a[i]\)出现在了下标\(A[a[i]]\)的位置。对于\(b\)有类似的\(B\)
对于题目的要求,可以转换为对于值域\([l,r]\),如果值域内的数都选就是 beautifu 序列。
很容想到一个性质,对于值域\([l,r]\)的子序列,如果\(a,b\)相同,则一定满足值域\([l,r-1]\)的子序列\(a,b\)也一定相同。
因此我们可以用双指针求出对于每一个\(l\)符合条件的最大的\(r\)。
现在我们考虑如何快速判断出值域\([l,r]\)的子序列在\(a,b\)出现的顺序相同。此时应满足
\[\forall x,y \in [l, r], (A[x] > A[y]) = (B[x] > B[y]) \]我们如果暴力的判断实际是\(O(N^2)\)的,加上双指针的复杂度,肯定无法通过。
我们可以考虑,如何在已知\([l,r - 1]\)满足的情况下,判断\([l,r]\)是否满足?
我们可以用两个std::set<int>
分别维护\(A[l,r-1],B[l,r-1]\)。 当我们插入\(A[r],B[r]\),可以在set
中找到前后的第一个数字,并判断是否相等,这样的复杂度是\(O(\log N)\)。所以总体复杂度就是\(O(N\log N)\)。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;
#define int i64
using pii = pair<int,int>;
using vi = vector<int>;
const int inf = LLONG_MAX / 2;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n;
vi a(n + 1), b(n + 1), A(n + 1), B(n + 1);
for(int i = 1; i <= n; i ++){
cin >> a[i];
A[a[i]] = i;
}
for(int i = 1; i <= n; i ++) {
cin >> b[i];
B[b[i]] = i;
}
int res = 0;
set<int> pa , pb;
for(int l = 1, r = 0; l <= n; l ++ ){
auto check = [&](int i) -> bool {
int x = A[i], y = B[i];
auto rx = pa.upper_bound(x), ry = pb.upper_bound(y);
if((rx == pa.end()) != (ry == pb.end())) return false;
if(rx != pa.end()) {
if(a[*rx] != b[*ry]) return false;
}
if((rx == pa.begin()) != (ry == pb.begin())) return false;
if(rx == pa.begin()) return true;
auto lx = prev(rx), ly = prev(ry);
if(a[*lx] != b[*ly]) return false;
return true;
};
while(r + 1 <= n and check(r + 1)){
r ++;
pa.insert(A[r]), pb.insert(B[r]);
}
res += r - l + 1;
pa.erase(A[l]), pb.erase(B[l]);
}
cout << res;
}
K - 渡劫
我们可以建立分层图,这样的话一次免费的机会就是层与层之间的单向边。然后建立一个超级终点,然后从每一个点到超级终端的单向边权就是点权。
然后就是要求所有点到终点的最短路,实际上我们从终点反向建边求单源最短路。
答案就是最短路的最大值。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;
#define int i64
using pii = pair<int,int>;
using vi = vector<int>;
const int inf = LLONG_MAX / 2;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
int N = 2 * n;
vector<vector<pii>> e(N + 1);
for(int u, v, w; m; m --) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
e[u].emplace_back(v + n, 0);
e[v].emplace_back(u + n, 0);
e[u + n].emplace_back(v + n, w);
e[v + n].emplace_back(u + n, w);
}
for(int i = 1, x; i <= n; i ++) {
cin >> x;
e[0].emplace_back(i, x);
e[0].emplace_back(i + n, x);
}
vi dis(N + 1, inf), vis(N + 1);
dis[0] = 0;
priority_queue<pii,vector<pii>, greater<>> heap;
heap.emplace(0, 0);
while(not heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto [v, w] : e[u]) {
if(vis[v] or dis[v] <= d + w) continue;
dis[v] = d + w;
heap.emplace(dis[v], v);
}
}
int res = -1;
for(int i = 1; i <= n; i ++)
res = max(res, min(dis[i], dis[i + n]));
cout << res;
return 0;
}
标签:i64,return,int,cin,2024,using,mint,湖南省,HNCPC
From: https://www.cnblogs.com/PHarr/p/18538584