Contestant'. Rank 1013. Rating +32.

A. Twin Permutations

题意

给定一个排列 \(a\)，构造另一个排列 \(b\)，满足 \(a_i + b_i\) 不递减。

思路

那也就可以是相等。

因为是长度相等的排列，因而一定可以得到 \(n\) 个和为 \(n + 1\) 的组合。

因而，输出 \(n - a_i + 1\) 即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        cout << (n - cur + 1) << ' ';
    }
    cout << '\n';
}

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

签到签到

B. Array merging

题意

给定两个序列，定义一次操作为选择一个序列，并将序列的头元素取出，放入新序列的尾部。当所有元素被取出后，输出最长相等元素连续子序列的长度。

思路

首先，操作等价于将某个序列的元素按顺序插入另一个序列中，那么可以证明的是，我们只能合并两个连续相等的子序列，无法合并多个。

那么，我们遍历找出每一种元素在两个序列中的连续最大长度，最后将两个序列中的每一个元素的长度加起来，和答案取最大值即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    map<int, int> cnt1, cnt2;
    vector<int> a(n + 1);
    int cnt = 0;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        if (a[i] != a[i - 1]) cnt = 0;
        if (cnt == 0 || a[i] == a[i - 1]) cnt++;
        cnt1[a[i]] = max(cnt1[a[i]], cnt);
    }
    cnt = 0;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        if (a[i] != a[i - 1]) cnt = 0;
        if (cnt == 0 || a[i] == a[i - 1]) cnt++;
        cnt2[a[i]] = max(cnt2[a[i]], cnt);
    }
    int ans = 0;
    for(int i=1;i<=2 * n;i++){
        ans = max(ans, cnt1[i] + cnt2[i]);
    }
    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. Copil Copac Draws Trees

题意

对于一棵 \(n\) 个点的树，给定其 \(n - 1\) 个边。

初始状态下，图中只有点 \(1\)，定义一次操作为按输入顺序枚举所有边，如果这个边有一个端点在图中，那么将这条边和另一个端点加入图中，否则跳过这条边。

输出建立这棵树需要的最小操作数。

思路

首先，显然这是一棵根为 \(1\) 的有根树，只要父节点不存在，这条边也一定不存在。

我们将每条边按照输入顺序编号，那么我们不难发现下面几点：

对于一个节点，它的每个子树的操作是互不干扰的；
只要上一条边的编号小于这条边的编号，那么这两条边都可以在一次操作内完成，否则需要多一次操作

因而，我们考虑树型 \(dp\)。

我们从根节点开始 \(\mathtt{dfs}\)，并遍历所有子树。

对于某一个点，如果它的子节点和它的边的编号小于它的父节点和它的编号，那么这棵子树的 \(dp\) 值需要 \(+1\)。

对于所有子树，我们取 \(dp\) 的最大值即可。

最后，输出 \(dp[1] + 1\)。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    vector<vector<pii>> e(n + 1);
    for(int i=1;i<n;i++){
        int u, v;
        cin >> u >> v;
        e[u].pb(v, i), e[v].pb(u, i);
    }
    vector<int> dp(n + 1);
    vector<bool> st(n + 1);
    auto dfs = [&](auto self, int x, int p, int id) -> void{
        if(st[x]) return;
        st[x] = true;
        for(auto t : e[x]){
            if(t.fs == p) continue;
            self(self, t.fs, x, t.sc);
            dp[x] = max(dp[x], dp[t.fs] + (id > t.sc ? 1 : 0));
        }
    };
    dfs(dfs, 1, -1, -inf);
    cout << dp[1] + 1 << '\n';
}

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

口胡乱写居然过了（

D. The BOSS Can Count Pairs

题意

给定两个序列 \(a, b\)，输出二元组 \((i, j)\) 的个数，满足 \(1 \leq i < j \leq n, a_i \cdot a_j = b_i+b_j\)。

思路1

首先，数据范围很好的将这道签到题变成了难题。

那么，普通的 \(O(n ^ 2)\) 是绝对无法通过的，那么在显然需要二重遍历的情况下，我们考虑优化某一维的计算。

因为 \(b_i \leq n, b_j \leq n\)，所以 \(b_i + b_j = a_i \cdot a_j \leq 2n\)。

因此，\(\min(a_i, a_j) \leq \sqrt{2n}\)。

所以，我们转而考虑对 \(a_j\) 的可能的值的枚举。

定义 \(fr[x][y]\) 为 \((x, y)\) 二元组的个数，\(lim = \sqrt{2n}\)。

针对重复计算，我们枚举 \(a_i\)，对 \(a_j\) 进行分讨：

\(a_j = a_i\)，那么有 \(\displaystyle{\frac{\sum_{i=1}^{n}fr[a_i][a_i \cdot a_i - b_i]-\sum_{i=1}^{lim}fr[i][\frac{i \cdot i}{2}]}{2}}\) 在上式中，我们筛除了 \(a_i\) 和 \(a_j\) 互换的重复和 \((a_i, b_i) = (a_j, b_j) \rightarrow b_i = b_j\) 的重复；
\(a_j \neq a_i\)，因为重复的原因，我们直接计算 \(a_i > a_j\) 的情况，那么有： \(\displaystyle{\sum_{i=1}^n \sum_{j=1}^{min(a_i-1,\frac{2\cdot n}{a_i})}fr[j][a_i \cdot j-b_i]}\)

最后，答案就是两者之和。

时间复杂度：\(O(n \sqrt{n})\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n + 1), b(n + 1);
    for(ll i=1;i<=n;i++) cin >> a[i];
    for(ll i=1;i<=n;i++) cin >> b[i];
    ll lim = (ll) sqrt(2 * n);
    vector<vector<int>> fr(lim + 1, vector<int>(n + 1));
    for(ll i=1;i<=n;i++)
        if(a[i] <= lim)  fr[a[i]][b[i]] ++;
    ll ans1 = 0, ans2 = 0;
    for(ll i=1;i<=n;i++){
        if(a[i] * a[i] - b[i] >= 0 && a[i] * a[i] - b[i] <= n)
            ans1 += fr[a[i]][a[i] * a[i] - b[i]];
        if(i <= lim && i % 2 == 0) ans1 -= fr[i][i * i / 2];
        for(ll j=1;j<=min(a[i] - 1, 2 * n / a[i]);j++){
            if(a[i] * j - b[i] >= 0 && a[i] * j - b[i] <= n)
                ans2 += fr[j][a[i] * j - b[i]];
        }
    }
    cout << ans1 / 2 + ans2 << '\n';
}

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

思路2

这边放一个队友的简要思路：

首先，我们固定 \(a_i\)，那么只要 \(a_j + 1\)，\(b_j\) 就会加上 \(a_i\)。

也就是说，这一趟我们只需枚举 \(\frac{n}{a_i}\)，而如果 \(a_i\) 比较小，那么这一趟枚举的次数是可观的。

那么，我们考虑预处理一部分的答案，即使用 \(O(nk)\) 的复杂度先暴力跑一部分的答案。

如上，加上数组的初始化，我们得到该思路的复杂度约为：\(O(2nk + \frac{n ^ 2}{k})\)，因而 \(k = \sqrt{2n}\) 时取到较优解。

时间复杂度：约\(O(2n \sqrt{2n} + \frac{2n}{k})\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const ll N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

ll hs(ll x, ll y){
    return x * 979797 + y;
}

void solve() {
    ll n;
    cin >> n;
    ll lim = (ll) sqrt(2 * n);
    vector<ll> a(n + 1), b(n + 1);
    vector<vector<int>> q(lim + 1, vector<int>(n + 1));
    unordered_map<ll, ll> cnt;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i], cnt[hs(a[i], b[i])]++;
    for (int k = 1; k <= lim; k++) {
        for (int i = 1; i <= n; i++) {
            ll bj = a[i] * k - b[i];
            if (a[i] * k > b[i] && bj <= n) q[k][bj]++;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] * a[i] == b[i] + b[i]) ans--;
        if (a[i] <= lim) {
            ans += q[a[i]][b[i]];
            continue;
        }
        ll y = (-b[i]) % a[i], x = (b[i] + y) / a[i];
        for (; x <= n && y <= n && a[i] * x <= 2 * n && b[i] + y <= 2 * n; x++, y += a[i]) {
            if (y > 0 && cnt.count(hs(x, y))) ans += cnt[hs(x, y)];
        }
    }
    cout << ans / 2 << '\n';
}

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

傻逼题，卡全局long long