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();
}

卡过去力!