A. 缩进优化
题目描述
有 \(N\) 行,每行有 \(A_i\) 个空格。你可以选择一个默认 TAB 长度 \(x\)。并用一个 TAB 替换 \(x\) 个空格。求最终需要 TAB 和空格数量之和的最小值。
思路
我们先对值的出现次数做一个前缀和,然后枚举 \(x\)。并枚举 \(x\) 的倍数再统计答案即可。这样是一个调和级数的复杂度。
空间复杂度 \(O(N)\),时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXV = 1000001;
int n, sum[MAXV];
ll ans = (ll)(1e18), cnt[MAXV];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1, x; i <= n; ++i) {
cin >> x;
sum[x]++;
cnt[x] += x;
}
for(int i = 1; i < MAXV; ++i) {
sum[i] += sum[i - 1];
cnt[i] += cnt[i - 1];
}
for(int i = 1; i < MAXV; ++i) {
ll res = 0;
for(int j = 0; i * j < MAXV; ++j) {
res += 1ll * j * (sum[min(MAXV - 1, i * (j + 1) - 1)] - (!j ? 0 : sum[i * j - 1])) + (cnt[min(MAXV - 1, i * (j + 1) - 1)] - (!j ? 0 : cnt[i * j - 1])) - 1ll * i * j * (sum[min(MAXV - 1, i * (j + 1) - 1)] - (!j ? 0 : sum[i * j - 1]));
}
ans = min(ans, res);
}
cout << ans;
return 0;
}
B. 外星人
题目描述
给定一个数 \(x\),和一个数列 \(A\),你要找到一个排列 \(P\),使得 \(x\bmod A_{P_1}\bmod A_{P_2}\bmod \dots \bmod A_{P_N}\) 最大。并求出有多少个这样的 \(P\)。
思路
显然当我们模完一个较小的数后,再模较大的数就没有意义了,所以如果我们想跳过一个数,那么只需把它丢到更小的数后面。因此先对 \(A\) 从大到小排序。
令 \(dp_{i,x}\) 表示考虑前 \(i\) 个数,当前数变成了 \(x\) 的方案数。如果我们选择模,那么有转移 \(dp_{i+1,x\bmod A_{i+1}}\leftarrow dp_{i,x}\)。如果不模,那么 \(dp_{i+1,x}\leftarrow dp_{i,x}\cdot (N-i)\)。最后看最大有方案数的答案即可。
时空复杂度均为 \(O(Nx)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1001, MAXV = 5001, MOD = 998244353;
int n, x, a[MAXN], dp[MAXN][MAXV];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> x;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + n + 1, greater<int>());
dp[0][x] = 1;
for(int i = 0; i < n; ++i) {
for(int j = 0; j <= x; ++j) {
dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * (n - i - 1) % MOD) % MOD;
dp[i + 1][j % a[i + 1]] = (dp[i + 1][j % a[i + 1]] + dp[i][j]) % MOD;
}
}
for(int i = x; i >= 0; --i) {
if(dp[n][i]) {
cout << i << "\n" << dp[n][i];
return 0;
}
}
return 0;
}
标签:cnt,int,sum,MAXV,UR,++,dp
From: https://www.cnblogs.com/yaosicheng124/p/18446464