A.Sublime Sequence

很简单的一个题，如果个数为奇数则是这个数本身，如果个数为偶数结果为0。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--) {
        int x,n;
        cin>>x>>n;
        if(n%2==0) {
            cout << 0 << endl;
        }
        else {
            cout << x << endl;
        }
    }
    return 0;
}

B.Lasers

迷惑性很大的一个题，看起来是一个复杂的问题，但是实际上，无论怎么行走，到达（x,y）一定穿越n+m个激光。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--) {
        int n,m,x,y;
        cin>>n>>m>>x>>y;
        int a;
        for(int i=0;i<n;i++) {
            cin >> a;
        }
        for(int i=0;i<m;i++) {
            cin >> a;
        }
        cout << n+m << endl;
    }
    return 0;
}

C.Pacer

为了最大化得分 S，我们从最大可能值开始尝试，也就是 S = k。我们检查 k 的奇偶性是否满足约束条件：k % 2 == (l_end ^ l_start)？如果满足，那么我们可以在这K分钟内每一分钟都跑。最终位置正确，得分最大化。该区间的得分为 k。如果不满足，我们就不能跑 k 次（否则最终位置会是错的）。我们能跑的最多次数是 k-1 次。k-1 的奇偶性与 k 相反，所以它一定满足约束。我们只需跑 k-1 次，并在其中1分钟原地不动即可。该区间的得分为 k-1。

从最后一个要求的时间 a_n 之后，直到测试在 m 时刻结束，我们不再有任何位置约束。这意味着在 a_n 到 m 之间的每一分钟，我们都可以选择跑动来得分，而不用担心在某个时间点必须出现在特定位置。这一阶段的持续时间是 m - a_n 分钟。因此，我们可以额外获得 m - a_n 分。

#include <bits/stdc++.h>
using namespace std;

struct R {
    long long time;
    int location;
};

bool cmp(const R& a, const R& b) {
    return a.time < b.time;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n;
        long long m;
        cin >> n >> m;
        vector<R> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i].time >> v[i].location;
        }
        v.push_back({0, 0});
        sort(v.begin(), v.end(), cmp);
        long long ans = 0;
        for (size_t i = 1; i < v.size(); ++i) {
            R start = v[i - 1];
            R end = v[i];
            long long k = end.time - start.time;
            if (k == 0) continue;
            int required_parity = start.location ^ end.location;
            if (k % 2 == required_parity) {
                ans += k;
            } else {
                ans += k - 1;
            }
        }
        long long last = v.back().time;
        ans = ans + m - last;
        cout << ans << endl;
    }
    return 0;
}

D.Destruction of the Dandelion Fields

贪心，使用一个数组存放所有奇数蒲公英田，将偶数蒲公英田直接加在结果上。排序奇数数组，计算需要舍弃的田数n=数组长度/2，排除掉最小的n片田，将其他收成加在结果上。注意如果只有偶数，割草机永远不会启动。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        long long s = 0;
        vector<long long> v;
        for (int i = 0; i < n; ++i) {
            int a;
            cin >> a;
            if (a % 2 == 0) {
                s += a;
            } else {
                v.push_back(a);
            }
        }
        if (v.empty()) {
            cout << 0 << endl;
            continue;
        }
        sort(v.begin(), v.end());
        for (size_t i = v.size() / 2; i < v.size(); ++i) {
            s += v[i];
        }
        cout << s << endl;
    }
    return 0;
}

E.Split

滑动窗口问题，使用双指针快速统计所有满足条件的子数组数量。如果一个子数组是“牛逼”的，那么它的任何一个子子数组也是“牛逼”的。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    vector<int> tc(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        tc[a[i]]++;
    }
    vector<int> tr(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        if (tc[i] % k != 0) {
            cout << 0 << endl;
            return;
        }
        tr[i] = tc[i] / k;
    }
    long long ans = 0;
    vector<int> wc(n + 1, 0);
    for (int l = 0, r = 0; l < n; ++l) {
        while (r < n && wc[a[r]] < tr[a[r]]) {
            wc[a[r]]++;
            r++;
        }
        ans += (r - l);
        wc[a[l]]--;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F.Gravity Falls

贪心，寻找最优后缀。

#include <bits/stdc++.h>
using namespace std;

int find(vector<int>& ca, const vector<vector<int>>& a, int c) {
    if (ca.size() == 1) {
        return ca[0];
    }
    while (ca.size() > 1) {
        int minv = -1;
        bool all = true;
        for (int idx : ca) {
            if (a[idx].size() > c) {
                all = false;
                if (minv == -1 || a[idx][c] < minv) {
                    minv = a[idx][c];
                }
            }
        }
        if (all) {
            break;
        }
        vector<int> next;
        int shortest = -1;
        for (int idx : ca) {
            if (a[idx].size() <= c) {
                if (shortest == -1) {
                    shortest = idx;
                }
                continue;
            }
            if (a[idx][c] > minv) {
                continue;
            }
            if (a[idx].size() == c + 1) {
                 if (shortest == -1) {
                    shortest = idx;
                }
            }
            next.push_back(idx);
        }
        if (shortest != -1) {
            return shortest;
        }
        ca = next;
        c++;
    }
    return ca[0];
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> a(n);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        a[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> a[i][j];
        }
    }
    vector<bool> used(n, false);
    vector<int> ans;
    int count = 0;
    while (count < n) {
        int idx = ans.size();
        vector<int> c;
        for (int i = 0; i < n; ++i) {
            if (!used[i] && a[i].size() > idx) {
                c.push_back(i);
            }
        }
        if (c.empty()) {
            break;
        }
        int best = find(c, a, idx);
        for (size_t i = idx; i < a[best].size(); ++i) {
            ans.push_back(a[best][i]);
        }
        used[best] = true;
        count++;
    }
    for (size_t i = 0; i < ans.size(); ++i) {
        cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

G.Farmer John's Last Wish

数论+数据结构，按题目的意思进行模拟就好。使用预处理，算出1到N每个数的所有约数并存起来。

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
vector<vector<int>> d(N);

void pre() {
    for (int i = 1; i < N; ++i) {
        for (int j = i; j < N; j += i) {
            d[j].push_back(i);
        }
    }
}

void solve() {
    int n;
    cin >> n;
    vector<int> c(n + 1, 0);
    vector<int> cc(n + 2, 0);
    set<int> s;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        for (int d : d[x]) {
            if (c[d] > 0) {
                cc[c[d]]--;
                if (cc[c[d]] == 0) {
                    s.erase(c[d]);
                }
            }
            c[d]++;
            if (cc[c[d]] == 0) {
                s.insert(c[d]);
            }
            cc[c[d]]++;
        }
        int ans = 0;
        if (!s.empty()) {
            auto it = s.rbegin();
            if (*it == i) {
                if (s.size() > 1) {
                    it++;
                    ans = *it;
                }
            } else {
                ans = *it;
            }
        }
        cout << ans << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}