CF2144C Non-Descending Arrays
思路
考虑 dp 。
对于每个位置，都有换或者不换两种状态，所以设 \(f_{i, 0/1}\) 为考虑前 \(i\) 个位置，并且第 \(i\) 个位置交换或者不交换累计的收益。接下来枚举每种情况：
-
对于 \(f_{i, 0}\) ,显然可以通过 \(f_{i - 1, 0}\) 直接转移，接下来判断一下能否从 \(f_{i - 1, 1}\) 转移；当交换会带来收益，也就是 \(a_i > b_{i - 1} \text{并且} b_i > a_{i - 1}\) 时 ，也可以通过 \(f_{i - 1, 1}\) 转移。
-
对于 $f_{1, 1}，转移的逻辑是一样的，但是由于 \(i\) 号位置要进行交换，所以判断 \(i - 1\) 时要反过来判断。
最后考虑边界，有 \(f_{1, 0} = f_{1, 1} = 1\) 。
代码
void solve(void) {int n; std::cin >> n;std::vector<int> a(n + 1);std::vector<int> b(n + 1);for(int i = 1; i <= n; i++) std::cin >> a[i];for(int i = 1; i <= n; i++) std::cin >> b[i];i64 f[110][2];memset(f, 0, sizeof(f));f[1][1] = f[1][0] = 1;for(int i = 2; i <= n; i++) {f[i][0] = f[i][1] = 0;for(int s = 0; s < 2; s++) {int prea = (s == 0 ? a[i - 1] : b[i - 1]);int preb = (s == 0 ? b[i - 1] : a[i - 1]);if(a[i] >= prea && b[i] >= preb) {f[i][0] = (f[i][0] + f[i - 1][s]) % P;}}for(int s = 0; s < 2; s++) {int prea = (s == 0 ? a[i - 1] : b[i - 1]);int preb = (s == 0 ? b[i - 1] : a[i - 1]);if(b[i] >= prea && a[i] >= preb) {f[i][1] = (f[i][1] + f[i - 1][s]) % P;}}}i64 ans = (f[n][0] + f[n][1]) % P;std::cout << ans << '\n';
}
CF2144D Price Tags
思路
首先注意到，\(x \in [2, \max({c_1, c_2, \dots, c_n})]\) ，物品价格的上限是 \(\lceil \frac{\max(c)}{x} \rceil\) 。但是依次枚举时间复杂度是 \(O(n^2)\) 的，怎么优化呢？
可以按照物品的最终售价 \(p\) 分桶，设 \(C = \max(c)\) ，建立数组 \(cnt[1..C]\) 记录每种价格有多少种物品，再维护前缀和 \(s[1..C]\) ，此时对于任何区间 \([L, R]\) ，原价在这个区间中的商品数量就为 \(s_R - s_{L - 1}\) 。
枚举 \(x\) ，那么商品的售价范围就在 \(p = 1, 2, \dots, \lceil \frac{C}{x} \rceil\) ，对于每个售价，原价在 \([(p - 1) \times x , p \times x]\) 的商品价格一定会分到 \(p\) 上，这些商品的数量就为 $s_{p \times x} - s_{(p - 1) \times x - 1} $ ，记作 \(cnt\_new\) ，它们带来的收益就为 \(cnt\_new \times p\) 。接着计算修改价格后能使用的旧标签的数量，就为 \(\min(cnt\_new, cnt_{p})\) 。之后就可以计算答案了。
时间复杂度为 \(O(\sum^{C}_{x = 2}\frac{C}{x})\) ，是调和级数级别的，也就是 \(O(n\log n)\) 。
代码
void solve(void) {int n, y;std::cin >> n >> y;std::vector<int> c(n + 1);for(int i = 1; i <= n; i++) {std::cin >> c[i];}int Cmax = *std::max_element(c.begin() + 1, c.end());std::vector<int> cnt(Cmax + 1, 0);for(int i = 1; i <= n; i++) cnt[c[i]]++;std::vector<int> s(Cmax + 1, 0);for(int i = 1; i <= Cmax; i++) {s[i] = s[i - 1] + cnt[i];}i64 ans = LLONG_MIN;for(int i = 2; i <= Cmax + 1; i++) {i64 sum = 0;i64 used = 0;int maxn = (Cmax + i - 1) / i;for(int p = 1; p <= maxn; p++) {int L = (p - 1) * i + 1;int R = std::min(p * i, Cmax);if(L > Cmax) break;int cnt_new = s[R] - s[L - 1];int cnt_old = (p <= Cmax ? cnt[p] : 0);sum += (i64)p * cnt_new;used += std::min(cnt_new, cnt_old);}i64 get = sum - (i64)(y * (n - used));ans = std::max(ans, get);}std::cout << ans << '\n';
}