年度鸡场

完结撒花喵

A. 复制鸡

题意

对于一个数组，定义一次操作为选择一个连续子序列，并将每个数复制一份加在原数后面。给定任意次操作后的数组，输出原数组的最小长度。

思路

问题等价为求数组最少可以被划分为多少段，满足每段内元素相同。

也就是说，答案是拐点 。

时间复杂度：

对应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. 好伙计猜拳

题意

定义对于一个长为 的整数二元组数组 ，若对于所有 ，均满足 且 ，那么这个数组是好的。

给定一个长为 的整数二元组数组，定义操作如下：

1. 花费 ，删除一个二元组；

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';
}

算是个 签到

C. 数列之和

题意

对于一个由偶数组成的序列 ，求出其中所有长度大于 的连续子数列的元素和，去重后升序排列，得到新序列。对于新序列，询问第 个整数的值。

思路

首先，假设子数列为 ，那么元素和为 。

通过打表可以发现，取值遍历除了大于等于 的 的幂次以外的所有正偶数，下面给出证明：

首先， 和 的奇偶性相同，而前者减去了偶数，后者减去了奇数，所以式子为偶数乘奇数，一定为偶数。

其次， 的幂次只能表示为 和本身的乘积，而 ，所以只能令 ，同时满足条件的 只有 ，所以只有 符合条件。因此式子一定不是大于等于 的 的幂次。

接下来我们证明如何遍历所有非 的幂次的偶数。

在上述条件下，式子可写为 ，其中 为大于等于 的奇数， 为大于等于 的 的幂次。那么我们只需证明对于任意 ， 是否遍历所有大于等于 的正奇数。

设 ，那么 ；

设 ，那么 。

由于 ，且 。所以 遍历所有大于等于 的正奇数（特殊地， 时， 遍历所有正奇数）。

证毕。

那么可以发现，需要排除的数很少，我们直接枚举即可，也不需要二分。

时间复杂度：

对应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. 薪得体会

题意

给定两个长为 的整数数组 ，设 初始值为 ，定义一次操作为选择一个未被选择的下标 ，若 ，则 ，否则 。求 可能的最大值。

思路

首先，为了尽可能达到最大的 ，最优策略是直接按照 从小到大的顺序操作。

如果当前无法满足 ，那么说明 肯定至少比前面的所有 大，我们可以交换 到前面，从而得到最大的 。

时间复杂度：

对应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. 小鸡的排列构造

题意

构造一个长为 的排列 ，满足给定的 条限制。一条限制由 组成，代表位置 在区间 排序后位置发生变化。

思路

首先，如果限制的区间长度是偶数，那么我们输出降序序列即可。

否则的话，我们可以考虑最小的合法限制区间，也就是长度为 的区间，显然我们将其排列为 (中位数，最大，最小) 或者 (最大，最小，中位数)。而有趣的是，如果我们将降序序列的 位和 位交换，恰好可以满足这个排列。举例来说， 操作结束后变为 ，显然符合条件。

时间复杂度：

对应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

题意

给定一个排列，独立询问区间 内位置 对应的元素在区间排序后的新位置。

思路

首先，这是一个主席树模板题，但本题并没有要求强制在线（类似交互题一样的，回答一个询问后才会给出下一个询问），我们不妨考虑离线做法。

显然我们只需求出区间内比位置 对应的值更小的元素个数 ，那么答案就是 。那么不妨思考，如果询问的位置对应的值都相等，那么我们会如何处理询问。

我们可以将比位置 对应值更小的元素对应位置记为 ，然后预处理前缀和，从而做到线性复杂度回答询问。

那么回到现在的问题，我们完全可以从小到大枚举所询问的位置的值，完成询问后将对应位置记为 。而对于前缀和数组的处理，显然暴力更新是不对的，我们可以考虑使用树状数组维护。

时间复杂度：

对应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. 铁刀磨成针

题意

对于一个武器，初始攻击力为 ，接下来包含 个回合，每个回合包含两个阶段：

1. 花费一单位磨刀石提升一点攻击力，最多一次；

2. 造成同等攻击力的伤害，并使得攻击力降低一点，最多一次。

给定磨刀石数量 ，求最大伤害。

思路

显然我们可以将攻击造成的伤害划分为三个阶段：只加不打；边加边打；不加只打。

第一阶段累积攻击力，第二阶段维持攻击力不变，第三阶段攻击力逐一下降，为等差数列。

考虑到数据范围，我们可以枚举从第 时刻开始打，答案取最大值即可。

时间复杂度：

对应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';
}

那就更 Dirty 了兄弟

K. 鸡翻题

题意

对于无穷多页的书，给定当前左边的页码 ，右边的页码为 ，约定 之前的页码都是 ，输出是否可以使得左右两边的页码总和为 。

思路

我们可以将左边的页码记为 ，右边的页码记为 ，那么有 ，求得 。

由数据范围可知不会因为范围导致无解，所以我们只需判断能否整除。

时间复杂度：

对应AC代码

void solve() {
    int x, y;
    cin >> x >> y;
    cout << ((y - 2 * x - 1) % 4 == 0 ? "YES\n" : "NO\n");
}

签到

L. 变鸡器

题意

给定一个长为 的大写字母组成的字符串，定义一次操作为选定两个不同的字符，并从字符串中删除。判断是否可以通过若干次操作将字符串变为 。

思路

首先，我们可以扫一遍字符串，检查是否存在对应的子序列，如果不存在直接判无解。

否则剩下的字符数量应该为偶数，且可以两两配对。通过一些贪心思路可以得出的结论是，如果出现次数的最大值大于总数的一半，那就无法配对，否则一定存在解。当然，这个结论在前面的场次已经出现过了，也许也可以看出补题情况。

时间复杂度：

对应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";
}

合理怀疑不会做的都没补题（