Contestant(alt). Rank 1774. Rating +20.

A. TubeTube Feed

题意

给定两个序列 \(a, b\)，选择 \(a_i\) 的代价为 \(a_i + i\) (从 \(0\) 开始)，价值为 \(b_i\)。输出代价不超过 \(t\) 的条件下的最大价值。

思路

我们找出所有代价不超过 \(t\) 的价值，并遍历这些价值，找出最大值即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, t;
    cin >> n >> t;
    vector<int> p;
    vector<int> e(n);
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        if(cur + i <= t) p.emplace_back(i);
    }
    for(int i=0;i<n;i++) cin >> e[i];
    if(p.empty()){
        cout << -1 << '\n';
        return;
    }
    int mx = p[0];
    for(auto &x : p) {
        if(e[mx] < e[x]) mx = x;
    }
    cout << mx + 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

很水

B. Karina and Array

题意

给定一串整数序列，定义序列的美丽值为所有相邻两数乘积的最大值。在可以任意删除元素且最后至少剩余两个元素的条件下，输出最大的美丽值。

思路

很显然，我们直接排个序，对前两个和最后两个分别取乘积，并取最大值即可。

时间复杂度：\(O(n \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = -inf;
    ans = max(ans, a[0] * a[1]);
    ans = max(ans, a[n - 2] * a[n - 1]);
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

还是很水

C. Bun Lover

题意

给定一个肉桂卷的大小 \(n\)，输出边长的总和。

具体来说，如下图，棕色线段的长度就是答案：

思路

我们将其拆分成两段，如下图（来自官方题解）：

可以发现粉色和青色段最后都会向里折1格，我们将其展开，那么长度恰好成为了一个等差数列的前 \(n\) 项和。

具体来说，青色的长度为 \(1 + 2 + \dots + n = \frac{n \cdot (n + 1)}{2}\)，粉色的长度为 \(1 + 2 + \dots + (n + 1) = \frac{(n + 1) \cdot (n + 2)}{2}\)

因此，最后的结果为 \(\frac{(n + 1) \cdot (n + 2)}{2} + \frac{n \cdot (n + 1)}{2} + 1 = \frac{(n + 1) \cdot (n + 2) + n \cdot (n + 1)}{2} + 1 = \frac{2 \cdot (n + 1)^2}{2} + 1 = (n + 1)^2 + 1\)

不过当然，像我这样盲猜有规律然后直接乱写也是可以的，这样你可以得到 \(26 + (n + 6)(n - 4)\)。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    cout << 26 + (11 + 11 + (n - 5) * 2) * (n - 4) / 2 << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

无脑Ocean在线乱猜

D. Super-Permutation

题意

给定排列 \(a\) 的长度，构造一个新序列 \(b\)，其中 \(b_i = ((a_1 + a_2 + \ldots + a_i) \bmod n) + 1\)。

若能找出一个排列 \(a\)，满足构造出的新序列 \(b\) 为一个排列，那么输出 \(a\)，否则输出 \(-1\)。

思路

我们先来猜测一下如何构造：

首先，为了方便拿到 \(1\)，我们将第一个数指定为 \(n\)。

那么我们接下来就可以放上 \(n - 1\) 和 \(2\)，此时 \(n + n - 1 = 2n - 1, 2n - 1 + 2 = 2n + 1\)，\((2n - 1) \bmod n + 1 = n, (2n + 1) \bmod n + 1 = 2\)，此时我们拿到了 \(n, 2\)。

我们继续放上 \(n - 3\) 和 \(4\)，此时 \(2n + 1 + n - 3 = 3n - 2, 3n - 2 + 4 = 3n + 2\)，\((3n - 2) \bmod n + 1 = n - 1, (3n + 2) \bmod n + 1 = 3\)，此时我们拿到了 \(n - 1, 3\)。

依次类推，我们可以构造出排列 \(\{n, n - 1, 2, n - 3, 4, \ldots \}\)，以此得到序列 \(b = \{1, n, 2, n - 1, 3, \dots \}\)。

不难发现，上述构造方法对 \(1\) 和偶数都一定有解，而除 \(1\) 之外的奇数都无解。

事实上，我们来单独考虑这种无解情况，\(b_n = (a_1 + a_2 + \ldots + a_n) \bmod n + 1= (1 + 2 + \ldots + n) \bmod n + 1 = \frac{(1 + n)n}{2} \bmod n + 1\)。

如果 \(n\) 为 \(1\) 或者偶数，那么分母对 \(n\) 有效，可以写作 \((1 + n) \frac{n}{2} \bmod n + 1\)，我们无法在提出 \(n\) 后让式子为整数。

而相反地，当 \(n\) 为除 \(1\) 之外的奇数时，上述式子变成了 \(n \frac{1 + n}{2} \bmod n + 1\)，我们可以提出 \(n\)，此时 \(b_n\) 变为了 \(1\)。

猜测的第一句话其实是一定需要满足的，我们假设 \(a_k = n\)，此时 \(b_k = (b_{k - 1} - 1 + a_k) \bmod n + 1= b_{k - 1}\)，那么为了防止 \(b\) 元素重复，\(k\) 只能为 \(1\)。

那么，\(b_1\) 只能为 \(1\)。

不难发现，当 \(n\) 为除 \(1\) 之外的奇数时，\(b_1 = b_n\)，因此无解。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<bool> st(n + 1);
    vector<int> ans(n);
    ans[0] = n;
    st[n] = true;
    bool ok = true;
    for(int i=1;i<n;i+=2) {
        ans[i] = n - i;
        if(st[n - i]) ok = false;
        st[n - i] = true;
    }
    for(int i=2;i<n;i+=2){
        ans[i] = i;
        if(st[i]) ok = false;
        st[i] = true;
    }
    if(!ok) cout << -1 << '\n';
    else{
        for(auto e : ans) cout << e << ' ';
        cout << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

根据题意构造（x），根据猜测构造（√）

E. Making Anti-Palindromes

题意

定义反回文串为一个长为 \(n\) 的字符串 \(s\)，满足对于任意 \(i \in [1, n]\) 都有 \(s_i \neq s_{n - i + 1}\)。

给定一个字符串，定义操作为选定任意两个不同位置的字符并交换它们，输出将字符串变为反回文串所需的最小的操作数。若无解输出 \(-1\)。

思路

首先，\(n\) 是奇数时，一定无解。

其次，只要有一个字母出现次数大于 \(\frac{n}{2}\)，那么也是无解，毕竟一定会出现至少一对相同的字母。

那么，我们统计 \(s_i = s_{n + 1 - i}\) 的个数为 \(k\)，以及对于所有字符 \(c\)，\(s_i = s_{n + 1 - i}\) 的个数的最大值 \(m\)，借此，我们可以先缩小一下范围：

1. \(ans \geq m\)，因为这 \(m\) 对一定得和其他不同的字符对进行交换；

2. \(ans \geq \lceil \frac{k}{2} \rceil\)，因为我们至少得两两配对。

那么显然，如果满足可以两两配对的条件，\(ans_{min} = \lceil \frac{k}{2} \rceil\)。

但如果不满足，那么我们不难发现，只要我们将数量少的字符对和其他数量少的字符对的进行交换，那么最后一定只会多出数量最多的那个字符对，也就是我们之前统计的数量为 \(m\) 的那个字符。

那么，最后约束就只剩下 \(m\) 了，\(ans_{min} = m\)。

因此，最后答案就是 \(\max(m, \lceil \frac{k}{2} \rceil)\)。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n % 2 == 1){
        cout << -1 << '\n';
        return;
    }
    vector<int> cnt(26), oc(26);
    int m = 0, k = 0;
    for(int i=0;i<n/2;i++) {
        oc[s[i] - 'a'] ++, oc[s[n - i - 1] - 'a'] ++;
        if (s[i] == s[n - i - 1]) cnt[s[i] - 'a']++, k++;
    }
    for(int i=0;i<26;i++){
        m = max(m, cnt[i]);
        if(oc[i] > n / 2){
            cout << -1 << '\n';
            return;
        }
    }
    cout << max(m, (k + 1) / 2) << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

好绕，好高级，我好若

F. Gardening Friends

题意

给定一棵根为 \(1\) 且边权都是 \(k\) 的树，定义树的价值为所有点到根节点的 最大长度。

定义一次操作为将根修改为相邻的任意节点，代价为 \(c\)。

输出任意次操作后，树的价值 与 代价和 的差值的最大值。

思路

首先，我们可以用 \(\mathtt{bfs}\) 先找出以 \(1\) 为根的最长链，记端点为 \(s\)。

那么，我们再以 \(s\) 为根进行 \(\mathtt{bfs}\)，显然最长链就是整棵树的最长链了。

我们记这个最长链的另一个端点为 \(t\)，若我们以 \(t\) 为根再进行一次 \(\mathtt{bfs}\)，那么对于所有的点，我们都可以快速求出以它为根的最长链长度了。

那么，我们枚举所有点，若长度为 \(p\)，并且和 \(1\) 相距 \(q\)，那么我们更新最大值 \(k * p - c * q\)。

为何能快速求出呢？因为在正反两次 \(\mathtt{bfs}\) 树的最长链时，我们可以更新出 每个点的所有链中 的 两条最长链，然后我们就可以取最大值。

时间复杂度：\(O(n)\)

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, k, c;
    cin >> n >> k >> c;
    vector<vector<int>> e(n + 1);
    for(int i=1;i<n;i++){
        int u, v;
        cin >> u >> v;
        e[u].pb(v), e[v].pb(u);
    }
    auto bfs = [&](int s){
        queue<int> q;
        q.ep(s);
        vector<int> d(n + 1, -1);
        d[s] = 0;
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(auto y : e[x]){
                if(d[y] != -1) continue;
                d[y] = d[x] + 1;
                q.ep(y);
            }
        }
        return d;
    };
    auto d1 = bfs(1);
    int s = max_element(all(d1)) - d1.begin();
    auto ds = bfs(s);//找出最长链
    int t = max_element(all(ds)) - ds.begin();
    auto dt = bfs(t);
    int ans = 0;
    for(int i=1;i<=n;i++) ans = max(ans, k * max(ds[i], dt[i]) - d1[i] * c);
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

也是个很有意思的图论

G1. Magic Triples (Easy Version)

详见G2，区别是G1的数据量更小

G2. Magic Triples (Hard Version)

题意

定义如果一个三元组 \((i, j, k)\) 满足下面的条件，那么这个三元组是有魔力的：

1. \(1 \leq i, j, k \leq n\)；

2. \(i, j, k\) 各不相同；

3. 存在一个正整数 \(b\)，满足 \(a_i \cdot b = a_j, a_j \cdot b = a_k\)。

给定一个序列，输出所有三元组中有魔力的个数。

思路

首先，我们完全可以在确定一个数的条件下，枚举正整数 \(b\) 来计算答案。

那么我们不妨确定 \(j\)，并枚举 \(b\)，那么 \(a_i = \frac{a_j}{b}, a_k = ba_j\)。

很显然，如果我们从小到大枚举，是一定会超时的。

考虑到 \(b\) 一定是整数，所以我们在计算 \(b\) 的时候可以顺便计算 \(\frac{a_j}{b}\)，那么复杂度可以降到 \(\log a_j\)。

当然，考虑到重复问题，我们单独计算 \(b = 1\) 的贡献。

在 \(1e6\) 的范围内，复杂度可行，但对于 \(1e9\) 的数据，我们一定得做优化了。

考虑到 \(a_k = ba_j \leq \max(a)\)，我们可以一定程度复杂度，此时可以 \(AC\)。

时间复杂度：\(小于O(n \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    int mx = 0;
    map<int, int> mp;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        mp[cur] ++;
        mx = max(mx, cur);
    }
    int ans = 0;
    for(auto [a, cnt] : mp) {
        ans += max(0ll, cnt * (cnt - 1) * (cnt - 2));
        if(a != 1 && mp.count(1) && mp.count(a * a)) ans += cnt * mp[1] * mp[a * a];
        for (int b = 2; b <= a / b && a * b <= mx; b ++){
            if(a % b != 0) continue;
            if(mp.count(a / b) && mp.count(a * b)) ans += cnt * mp[a / b] * mp[a * b];
            if(b != a / b && mp.count(b) && mp.count(a * a / b)) ans += cnt * mp[b] * mp[a * a / b];
        }
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

卡过去力！