Solved 9 of 12.年度鸡场
A. 复制鸡
题意
对于一个数组，定义一次操作为选择一个连续子序列，并将每个数复制一份加在原数后面。给定任意次操作后的数组，输出原数组的最小长度。
思路
问题等价为求数组最少可以被划分为多少段，满足每段内元素相同。
也就是说，答案是拐点 \(+1\)。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
int ans = 0;
for(int i=1;i<=n;i++) {
if(a[i] != a[i - 1]) ans ++;
}
cout << ans << '\n';
}唯一有用的是pdf欸！
B. 好伙计猜拳
题意
定义对于一个长为 \(p\) 的整数二元组数组 \((a,b)_i\)，若对于所有 \(i \in [2,p]\)，均满足 \(a_{i-1} \leq a_i\) 且 \(b_{i - 1} \leq b_i\)，那么这个数组是好的。
给定一个长为 \(n\) 的整数二元组数组，定义操作如下：
花费 \(c_1\)，删除一个二元组；
花费 \(c_2\)，调换一个二元组，即 \(a, b\) 互换位置。
输出使得数组变成好的需要的最小代价。
思路
数据范围提示我们可以 \(O(n^2)\)，那么我们可以先不考虑贪心之类的方法，转而思考如何转移状态。
可以发现，这题无非是 \(O(n^2)\) 复杂度下求最长上升子序列长度 的小拓展，在其基础上多了是否需要交换的状态。所以我们只需定义 \(dp_{i,j}\) 为以 \(i\) 结尾且该位是否翻转的最小代价，然后从前面转移状态即可。
时间复杂度：\(O(n ^ 2)\)
对应AC代码
void solve() {
int n, c1, c2;
cin >> n >> c1 >> c2;
vector<vector<long long>> dp(n + 1, vector<long long>(2, inf));
dp[0][0] = 0;
vector<pair<int, int>> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i].first >> a[i].second;
long long ans = inf;
for(int i=1;i<=n;i++) {
for(int j=i-1;j>=0;j--) {
if(a[i].first >= a[j].first && a[i].second >= a[j].second) {
dp[i][0] = min(dp[i][0], dp[j][0] + 1LL * (i - j - 1) * c1);
}
if(a[i].first >= a[j].second && a[i].second >= a[j].first) {
dp[i][0] = min(dp[i][0], dp[j][1] + 1LL * (i - j - 1) * c1);
}
if(a[i].second >= a[j].first && a[i].first >= a[j].second) {
dp[i][1] = min(dp[i][1], c2 + dp[j][0] + 1LL * (i - j - 1) * c1);
}
if(a[i].second >= a[j].second && a[i].first >= a[j].first) {
dp[i][1] = min(dp[i][1], c2 + dp[j][1] + 1LL * (i - j - 1) * c1);
}
}
ans = min(ans, min(dp[i][0], dp[i][1]) + 1LL * (n - i) * c1);
}
cout << ans << '\n';
}算是个 \(dp\) 签到
C. 数列之和
题意
对于一个由偶数组成的序列 \(a\)，求出其中所有长度大于 \(1\) 的连续子数列的元素和，去重后升序排列，得到新序列。对于新序列，询问第 \(k\) 个整数的值。
思路
首先，假设子数列为 \([l, r]\)，那么元素和为 \(\frac{(2l-2+2r-2)(r-l+1)}{2} = (l + r - 2)(r - l + 1)\)。
通过打表可以发现，取值遍历除了大于等于 \(4\) 的 \(2\) 的幂次以外的所有正偶数，下面给出证明：
首先，\(l + r\) 和 \(r - l\) 的奇偶性相同，而前者减去了偶数，后者减去了奇数，所以式子为偶数乘奇数，一定为偶数。
其次，\(2\) 的幂次只能表示为 \(1\) 和本身的乘积，而 \(r - l + 1 \geq 2\)，所以只能令 \(l + r - 2 = 1\)，同时满足条件的 \(r - l\) 只有 \(1\)，所以只有 \(2\) 符合条件。因此式子一定不是大于等于 \(4\) 的 \(2\) 的幂次。
接下来我们证明如何遍历所有非 \(2\) 的幂次的偶数。
在上述条件下，式子可写为 \(n = A \cdot B\)，其中 \(A\) 为大于等于 \(3\) 的奇数，\(B\) 为大于等于 \(2\) 的 \(2\) 的幂次。那么我们只需证明对于任意 \(B\)，\(A\) 是否遍历所有大于等于 \(3\) 的正奇数。
设 \(r - l + 1 = 2^k\)，那么 \(n = (2a - 3 + 2^k)\cdot 2^k\)；
设 \(l + r - 2 = 2^k\)，那么 \(n = (-2a + 3 + 2^k) \cdot 2^k\)。
由于 \(2a - 3 \geq -1, -2a + 3 \leq 1\)，且 \(-2a + 3 + 2^k = r - l + 1 \geq 2\)。所以 \(\frac{n}{2^k}\) 遍历所有大于等于 \(3\) 的正奇数（特殊地，\(2^k = 2\) 时，\(\frac{n}{2^k}\) 遍历所有正奇数）。
证毕。
那么可以发现，需要排除的数很少，我们直接枚举即可，也不需要二分。
时间复杂度：\(O(\log n)\)
对应AC代码
void solve() {
long long x;
cin >> x;
x *= 2;
for(long long i=4;i<=x;i*=2) {
x += 2;
}
cout << x << '\n';
}全是注意力
D. Viva La Vida(Fried-Chicken's Version)
待补充
E. 任造化落骰
待补充
F. 薪得体会
题意
给定两个长为 \(n\) 的整数数组 \(a, b\)，设 \(x\) 初始值为 \(0\)，定义一次操作为选择一个未被选择的下标 \(i \in [1, n]\)，若 \(x \geq a_i\)，则 \(x = \max(x, a_i + b_i)\)，否则 \(x = \max(x, a_i)\)。求 \(x\) 可能的最大值。
思路
首先，为了尽可能达到最大的 \(a_i+b_i\)，最优策略是直接按照 \(a_i+b_i\) 从小到大的顺序操作。
如果当前无法满足 \(x \geq a_i\)，那么说明 \(a_i\) 肯定至少比前面的所有 \(a_j\) 大，我们可以交换 \(i\) 到前面，从而得到最大的 \(a_j + b_j\)。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n;
cin >> n;
vector<pair<int, int>> p(n + 1);
for(int i=1;i<=n;i++) cin >> p[i].first >> p[i].second;
sort(p.begin() + 1, p.end(), [](pair<int, int> &a, pair<int, int> &b){ return a.first + a.second < b.first + b.second; });
int ans = 0, mx = 0;
for(int i=1;i<=n;i++) {
auto &[a, b] = p[i];
if(ans >= a) ans = max(ans, a + b);
else ans = max(ans, mx);
ans = max(ans, a);
mx = max(mx, a + b);
}
cout << ans << '\n';
}妙妙贪心
G. 目标是【L2】传说高手
待补充
H. 小鸡的排列构造
题意
构造一个长为 \(n\) 的排列 \(p\)，满足给定的 \(m\) 条限制。一条限制由 \(l_i, r_i, c_i\) 组成，代表位置 \(c_i\) 在区间 \([l_i, r_i]\) 排序后位置发生变化。
思路
首先，如果限制的区间长度是偶数，那么我们输出降序序列即可。
否则的话，我们可以考虑最小的合法限制区间，也就是长度为 \(3\) 的区间，显然我们将其排列为 (中位数，最大，最小) 或者 (最大，最小，中位数)。而有趣的是，如果我们将降序序列的 \(2k-1\) 位和 \(2k\) 位交换，恰好可以满足这个排列。举例来说，\(7,6,5,4,3,2,1\) 操作结束后变为 \(6,7,4,5,2,3,1\)，显然符合条件。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(m + 1), b(m + 1), c(m + 1);
for(int i=1;i<=m;i++) cin >> a[i] >> b[i] >> c[i];
if((b[1] - a[1]) % 2 == 0) {
for(int i=n;i>=1;i--) cout << i << ' ';
cout << '\n';
}else {
for(int i=n;i>=1;i-=2) {
if(i == 1) cout << 1 << ' ';
else cout << i - 1 << ' ' << i << ' ';
}
cout << '\n';
}
}脑电波题
I. 小鸡的排列构造的checker
题意
给定一个排列，独立询问区间 \([l, r]\) 内位置 \(c\) 对应的元素在区间排序后的新位置。
思路
首先，这是一个主席树模板题，但本题并没有要求强制在线（类似交互题一样的，回答一个询问后才会给出下一个询问），我们不妨考虑离线做法。
显然我们只需求出区间内比位置 \(c\) 对应的值更小的元素个数 \(p\)，那么答案就是 \(l + p\)。那么不妨思考，如果询问的位置对应的值都相等，那么我们会如何处理询问。
我们可以将比位置 \(c\) 对应值更小的元素对应位置记为 \(1\)，然后预处理前缀和，从而做到线性复杂度回答询问。
那么回到现在的问题，我们完全可以从小到大枚举所询问的位置的值，完成询问后将对应位置记为 \(1\)。而对于前缀和数组的处理，显然暴力更新是不对的，我们可以考虑使用树状数组维护。
时间复杂度：\(O(n \log n)\)
对应AC代码
template<class Info = int>
struct FenwickTree {
int n;
vector<Info> info;
FenwickTree() : n(0) {}
explicit FenwickTree(int _n, Info _v = Info()) : info(_n + 1, _v), n(_n) {}
inline static int lowbit(int x) { return x & (-x); }
void pointUpdate(int pos, Info _info) {
for (int i = pos; i <= n; i += lowbit(i)) info[i] = info[i] + _info;
}
Info rangeQuery(int r) {
Info ans{};
for (int i = r; i > 0; i -= lowbit(i)) ans = ans + info[i];
return ans;
}
Info rangeQuery(int l, int r) {
return rangeQuery(r) - rangeQuery(l - 1);
}
Info lowerBound(int x) {
int pos = 0, t = 0;
for (int j = 20; j >= 0; j--) {
if (pos + (1 << j) <= n && t + info[pos + (1 << j)] <= x)
pos += (1 << j), t += info[pos];
}
return pos;
}
};
void solve() {
int n, m;
cin >> n >> m;
FenwickTree<int> bit(n);
vector<int> a(n + 1), idx(n + 1);
for(int i=1;i<=n;i++) {
cin >> a[i];
idx[a[i]] = i;
}
vector<vector<array<int, 3>>> q(n + 1);
for(int i=1;i<=m;i++) {
int l, r, c;
cin >> l >> r >> c;
q[a[c]].push_back({i, l, r});
}
vector<int> ans(m + 1);
for(int i=1;i<=n;i++) {
for(auto &[j, l, r] : q[i]) {
ans[j] = bit.rangeQuery(l, r) + l;
}
bit.pointUpdate(idx[i], 1);
}
for(int i=1;i<=m;i++) cout << ans[i] << '\n';
}感觉写主席树和树状数组的人数五五开（
J. 铁刀磨成针
题意
对于一个武器，初始攻击力为 \(x\)，接下来包含 \(n\) 个回合，每个回合包含两个阶段：
花费一单位磨刀石提升一点攻击力，最多一次；
造成同等攻击力的伤害，并使得攻击力降低一点，最多一次。
给定磨刀石数量 \(y\)，求最大伤害。
思路
显然我们可以将攻击造成的伤害划分为三个阶段：只加不打；边加边打；不加只打。
第一阶段累积攻击力，第二阶段维持攻击力不变，第三阶段攻击力逐一下降，为等差数列。
考虑到数据范围，我们可以枚举从第 \(p\) 时刻开始打，答案取最大值即可。
时间复杂度：\(O(n)\)
对应AC代码
void solve() {
int n, x, y;
cin >> n >> x >> y;
int ans = 0;
for(int p=1;p<=y;p++) {
if(p > n) break;
int kp = min(n, y) - p;
int len = min(x + p, n - min(n, y) + 1);
ans = max(ans, kp * (x + p) + (x + p + x + p - len + 1) * len / 2);
}
cout << ans << '\n';
}\(O(1)\) 那就更 Dirty 了兄弟
K. 鸡翻题
题意
对于无穷多页的书，给定当前左边的页码 \(x\)，右边的页码为 \(x + 1\)，约定 \(1\) 之前的页码都是 \(0\)，输出是否可以使得左右两边的页码总和为 \(y\)。
思路
我们可以将左边的页码记为 \(x + 2k\)，右边的页码记为 \(x + 2k + 1\)，那么有 \(2x + 4k + 1 = y\)，求得 \(k = \frac{y - 2x - 1}{4}\)。
由数据范围可知不会因为范围导致无解，所以我们只需判断能否整除。
时间复杂度：\(O(1)\)
对应AC代码
void solve() {
int x, y;
cin >> x >> y;
cout << ((y - 2 * x - 1) % 4 == 0 ? "YES\n" : "NO\n");
}签到
L. 变鸡器
题意
给定一个长为 \(n\) 的大写字母组成的字符串，定义一次操作为选定两个不同的字符，并从字符串中删除。判断是否可以通过若干次操作将字符串变为 \(\mathtt{CHICKEN}\)。
思路
首先，我们可以扫一遍字符串，检查是否存在对应的子序列，如果不存在直接判无解。
否则剩下的字符数量应该为偶数，且可以两两配对。通过一些贪心思路可以得出的结论是，如果出现次数的最大值大于总数的一半，那就无法配对，否则一定存在解。当然，这个结论在前面的场次已经出现过了，也许也可以看出补题情况。
时间复杂度：\(O()\)
对应AC代码
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> cnt(26);
for(auto &it : s) cnt[it - 'A'] ++;
string t = "CHICKEN";
int idx = 0;
for(int i=0;i<n;i++) {
if(idx < t.size() && s[i] == t[idx]) idx ++;
}
if(idx < t.size()) {
cout << "NO\n";
return;
}
for(auto &it : t) cnt[it - 'A'] --;
int mx = *max_element(cnt.begin(), cnt.end()), sum = accumulate(cnt.begin(), cnt.end(), 0ll);
if(sum % 2 == 1 || mx > sum / 2) {
cout << "NO\n";
return;
}
cout << "YES\n";
}合理怀疑不会做的都没补题（