字符串构造机 100pts
原题，见[赛记] 多校A层冲刺NOIP2024模拟赛01【衡中】 T1；
忍者小队 60pts
赛时最后想出来个 $ \Theta(n^2 \log n) $ 的 DP，所以60pts；
对于这个DP，直接用 map 维护一下所有lcm的状态转移即可；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int n, m;
int a[500005];
int vis[500005];
int ma;
vector<int> v[500005];
int gc[500005];
map<int, int> f;
int pri[500005], cnt;
bool vi[500005], vv[500005];
void w() {
for (int i = 2; i <= ma; i++) {
if (!vi[i]) {
pri[++cnt] = i;
for (int j = 2; j * i <= ma; j++) {
vi[i * j] = true;
}
}
}
}
int main() {
freopen("sor.in", "r", stdin);
freopen("sor.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
vis[a[i]]++;
ma = max(ma, a[i]);
}
w();
for (int i = 1; i <= m; i++) {
for (int j = 1; j * i <= ma; j++) {
if (vis[j * i]) {
for (int k = 1; k <= vis[j * i]; k++) v[i].push_back(j * i);
if (gc[i] == 0) gc[i] = j * i;
else gc[i] = __gcd(gc[i], j * i);
int pos = lower_bound(pri + 1, pri + 1 + cnt, j) - pri;
if (pri[pos] == j) vv[i] = true;
}
}
}
for (int i = 1; i <= m; i++) {
if (gc[i] != i) {
cout << -1 << ' ' << -1 << '\n';
continue;
}
if (vis[i]) {
cout << 1 << ' ' << v[i].size() << '\n';
continue;
}
if (vv[i]) {
cout << 2 << ' ' << v[i].size() << '\n';
continue;
}
f.clear();
for (int j = 0; j < v[i].size(); j++) {
int now = v[i][j];
if (!f[now]) f[now] = 1;
else f[now] = min(f[now], 1);
for (auto it = f.begin(); it != f.end(); it++) {
int u = __gcd(it -> first, now);
if (u < i) continue;
if (!f[u]) f[u] = it -> second + 1;
else f[u] = min(f[u], it -> second + 1);
}
}
cout << f[i] << ' ' << v[i].size() << '\n';
}
return 0;
}
对于正解，考虑到答案不会很大（小于等于 $ 7 $，考虑 $ 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 9699690 > 600000 $ ），所以可以先枚举答案，然后判断是否合法；
以下设 $ w $ 为值域；
判断是否合法的问题可以转化为方案数，设 $ f_i $ 表示当前 $ lcm = i $ 的方案数，则有转移 $ f_i = C_{sum_i}^{t} - \sum_{j = 2}^{\lfloor \frac{w}{i} \rfloor} f_j $；
最后判断 $ f $ 是否为 $ 0 $ 即可，这里可以对一个比较大的质数取模（毕竟是这个质数的倍数的概率较低）；
时间复杂度：$ \Theta(w \ln w) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const long long mod = 998244353;
int n, m;
int a[5000005], ma, vis[5000005];
int ans[5000005];
vector<int> v[5000005];
long long f[5000005], fac[5000005], fav[5000005];
long long ksm(long long a, long long b) {
long long ans = 1;
while(b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
long long C(long long a, long long b) {
if (a < b) return 0;
if (b < 0) return 0;
return fac[a] * fav[b] % mod * fav[a - b] % mod;
}
int main() {
freopen("sor.in", "r", stdin);
freopen("sor.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
vis[a[i]]++;
ma = max(ma, a[i]);
}
fac[0] = 1;
fav[0] = 1;
for (int i = 1; i <= 1000000; i++) {
fac[i] = fac[i - 1] * i % mod;
fav[i] = ksm(fac[i], mod - 2);
}
for (int i = 1; i <= ma; i++) {
for (int j = 1; j * i <= ma; j++) {
if (vis[j * i]) {
for (int k = 1; k <= vis[j * i]; k++) v[i].push_back(j * i);
}
}
}
for (int t = 1; t <= 7; t++) {
for (int i = 1; i <= ma; i++) f[i] = 0;
for (int i = ma; i >= 1; i--) {
if (v[i].size() < t) continue;
long long sum = 0;
for (int j = 2; j * i <= ma; j++) {
sum = (sum + f[i * j]) % mod;
}
f[i] = (C(v[i].size(), t) - sum + mod) % mod;
}
for (int i = 1; i <= m; i++) {
if (f[i] != 0 && !ans[i]) {
ans[i] = t;
}
}
}
for (int i = 1; i <= m; i++) {
if (!ans[i]) cout << -1 << ' ' << -1 << '\n';
else cout << ans[i] << ' ' << v[i].size() << '\n';
}
return 0;
}
狗卡 0pts
赛时被 $ 600005 $ 个 deque 欺骗以致于都 RE，以此警告；
deque 的空间要乘 $ 16 $ 还是多少，所以谨慎；
对于这个题，我们首先想一想每个武将只有一级的时候，那么每次选最小即可；
如果不是一级，考虑两个数段 $ a, b $ ，$ a $ 先于 $ b $ 当 $ \overline{a} < \overline{b} $ 时；
所以我们找每个武将的最长递增平均值段即可，考虑插入一个数，我们让它一直和前面的段合并直到递增即可；
用个堆维护一下，每次出最小的，时间复杂度：$ \Theta(n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
long long n, m;
vector<int> v[600005];
struct sss{
double val;
int id, l, r;
long long sum;
bool operator <(const sss &A) const {
return val > A.val;
}
}e[1200005];
priority_queue<sss> q;
int main() {
freopen("dog.in", "r", stdin);
freopen("dog.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int k, x;
for (int i = 1; i <= n; i++) {
cin >> k;
v[i].push_back(0);
for (int j = 1; j <= k; j++) {
cin >> x;
v[i].push_back(x);
}
int now = 0;
for (int j = 1; j <= k; j++) {
e[++now] = {1.00 * v[i][j], i, j, j, v[i][j]};
while(now > 1 && e[now].val <= e[now - 1].val) {
e[now - 1].r = e[now].r;
e[now - 1].sum += e[now].sum;
e[now - 1].val = 1.00 * e[now - 1].sum / (e[now - 1].r - e[now - 1].l + 1);
now--;
}
}
for (int j = 1; j <= now; j++) q.push(e[j]);
}
long long sum = 0, now = 0, ans = 0;
while(!q.empty()) {
sss t = q.top();
q.pop();
for (int i = t.l; i <= t.r; i++) {
ans += sum * v[t.id][i];
now += v[t.id][i];
sum++;
}
}
ans += (m - now) * sum;
cout << ans;
return 0;
}