Rank 906/3920. AC 5/12.

A. Tokitsukaze and a+b=n (easy)

题意

在两个闭区间 \([L1, R1]\) 和 \([L2, R2]\) 之间取两个数 \(a\)，\(b\)，满足 \(a+b=n\)。\(a \neq b\) 时交换两者可算作两种选法。输出选法总数。

思路

暴力枚举 \(a\)，\(b\)。快速签到。

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

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while(T -- > 0){
            int n = scanner.nextInt();
            int l1 = scanner.nextInt(), r1 = scanner.nextInt();
            int l2 = scanner.nextInt(), r2 = scanner.nextInt();
            int cnt = 0;
            for(int i=l1;i<=r1;i++){
                int j = n - i;
                if(j >= l2 && j <= r2) cnt ++;
            }
            System.out.println(cnt);
        }
    }

}

先签了再说

B. Tokitsukaze and a+b=n (medium)

题意

同\(A\)题，只有样例数量增加了。

思路

一个取交集的思路：

当两个集合有交集时，那么将存在一段值相等的区间，因而我们化 \(a+b=n\) 为 \(a=n-b\) ，求等式两边集合的交集的元素数量即可。

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

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            int n = scanner.nextInt();
            long l1 = scanner.nextInt(), r1 = scanner.nextInt(), l2 = scanner.nextInt(), r2 = scanner.nextInt();
            System.out.println(Math.max(0, Math.min(n - l1, r2) - Math.max(n - r1, l2) + 1));
        }
    }
}

这么好的思路，赛时怎么就没想到呢，淦

C. Tokitsukaze and a+b=n (hard)

题意

给定 \(m\) 个区间，在不同的区间内分别取 \(a\)，\(b\)，同 \(AB\)，输出方案数。

思路

在 \(B\) 题的思路基础上，我们只需先用差分快速求出一个点 \(t_i\) 被多少个区间覆盖，求和后便可很快算出一段区间内有多少元素在交集之内了，这里我们可以使用两次前缀和。注意，这里需要排除在相同区间内取交集。

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

对应AC代码

import java.util.*;

public class Main{

    static final int N = 400010, mod = 998244353;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[] l = new int[m], r = new int[m];
        long[] sum = new long[N + 1];
        for(int i=0;i<m;i++){
            l[i] = scanner.nextInt();
            r[i] = scanner.nextInt();
            sum[r[i] + 1] --;
            sum[l[i]] ++;
        }
        for(int i=1;i<=N;i++) {
            sum[i] += sum[i - 1];
            sum[i] %= mod;
        }
        for(int i=1;i<=N;i++) { //差分转前缀和
            sum[i] += sum[i - 1];
            sum[i] %= mod;
        }
        long ans = 0;
        for(int i=0;i<m;i++){
            int l1 = l[i], r1 = r[i], l2 = n - r[i], r2 = n - l[i];
            if(r2 < 1) continue;
            l2 = Math.max(1, l2);
            ans += sum[r2] - sum[l2 - 1];
            ans -= Math.max(0, Math.min(r1, r2) - Math.max(l1, l2) + 1);
            while(ans < 0) ans += mod;
            ans %= mod;
        }
        System.out.println(ans);
    }
}

想不出来B题那个简单的做法这题就寄咯

D. Tokitsukaze and Energy Tree

题意

给定一个根为 \(1\) 、有 \(n\) 个节点的树，将 \(n\) 个为 \(v_i\) 的能量球放到 \(n\) 个节点上，在每次放置时可获得自己加上子树的所有能量，输出能获得的最大能量。

思路1

显然，我们可以贪心地认为从小到大从顶部往下按层放置即可，这样就可以保证最大的能量在层数最大的叶节点。

因而，我们可以直接用 \(BFS\) 暴力模拟解决问题。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 200020;

int n;
vector<int> e[N];
int w[N], idx = 1;
ll ans = 0;
int v[N];
bool vis[N];

void bfs(){
    queue<pair<int, int>> q;
    q.emplace(1, 1);
    ans += v[idx ++];
    vis[1] = true;
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int c : e[t.first]){
            if(vis[c]) continue;
            vis[c] = true;
            ans += (t.second + 1) * v[idx ++];
            q.emplace(c, t.second + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i=1;i<n;i++){
        int f;
        cin >> f;
        e[f].emplace_back(i + 1);
    }
    for(int i=1;i<=n;i++) cin >> v[i];
    sort(v + 1, v + n + 1);
    bfs();
    cout << ans << '\n';
}

思路2

题目输入有限制，在给出节点 \(i\) 的父亲的时候，满足父亲的下标小于 \(i\) ，所以是没必要 \(BFS\) 的，直接用数组即可。

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

#include<bits/stdc++.h>

using namespace std;

const int N = 200010;

#define ll long long

ll v[200005], d[200005];
int main()
{
    int n, f, ans = 0;
    d[1] = 1;
    cin >> n;
    for(int i=2;i<=n;i++)
    {
        cin >> f;
        d[i] = d[f] + 1;
    }
    for(int i=1;i<=n;i++) cin >> v[i];
    sort(v + 1, v + n + 1);
    sort(d + 1, d + n + 1);
    for(int i=1;i<=n;i++)
        ans += v[i] * d[i];
    cout << ans << endl;
    return 0;
}

看清题目的输入啊，完全没必要BFS

E. Tokitsukaze and Function

题意

给定函数 \(f(x)= \lfloor \frac{n}{x} \rfloor + x - 1\) 以及区间 \([L,R]\)，输出 使 \(f(t)\) 最小 的 最小整数 \(t\) 。

思路

首先，去掉向下取整符号后，这是一个对勾函数，那么最小值将在 \(\sqrt x\) 处取到。

保留符号后，最小值会在 \(\lfloor \sqrt x \rfloor\) 和 \(\lceil \sqrt x \rceil\) 处取到，我们记为 \(p\)。

显然，在尝试几个数后，我们可以发现存在至少一段值都为最小值的区间，且 \(p\) 在区间内部。

不过，因为我们需要取 \(t_{\min}\)，所以我们只需从 \(p\) 点向左找转折点，即左边的值大于自身的那个点。

我们先来特判几个情况：

1. \(p \leq L\) 时，输出 \(l\) 即可。

2. \(p > R\) 时，我们可以将寻找转折点的区间缩小为 题给区间 \([L,R]\) 。

我们可以发现，题目给的数据量特别大，而且我们要找的区间是有单调性的，二分查找即可。

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

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while(T -- > 0) {
            long n = scanner.nextLong(), l = scanner.nextLong(), r = scanner.nextLong();
            long p = Math.round(Math.sqrt(n)) + 1;
            if(p <= l){
                System.out.println(l);
                continue;
            }
            if (f(n, p - 1) <= f(n, p)) p --;
            if(p > r) p = r;
            long left = l, right = p, mid;
            while(left < right){
                mid = (left + right) >> 1;
                if(f(n, mid) <= f(n, right)) right = mid;
                else left = mid + 1;
            }
            System.out.println(left);
        }
    }

    private static long f(long n, long x){
        return n / x + x - 1;
    }

}

不要死磕在一道题

F. Tokitsukaze and Gold Coins (easy)

题意

给定 \(n \times 3\) 有障碍迷宫，输出从 \((1，1)\) 到 \((n, 3)\) 的所有路径中经过的点的个数，不重复计算。

思路

正反两遍 \(BFS\)，统计被访问两遍的点的个数即可，无需找规律。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 500010;

int n;
bool have[N][4], vis[N][4][2];

void bfs(pair<int, int> s, int w) {
    queue<pair<int, int>> q;
    q.emplace(s);
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        if(vis[t.first][t.second][w]) continue;
        vis[t.first][t.second][w] = true;
        if (w) {
            if (t.first - 1 > 0 && !have[t.first - 1][t.second]) q.emplace(t.first - 1, t.second);
            if (t.second - 1 > 0 && !have[t.first][t.second - 1]) q.emplace(t.first, t.second - 1);
        } else {
            if (t.first + 1 <= n && !have[t.first + 1][t.second]) q.emplace(t.first + 1, t.second);
            if (t.second + 1 <= 3 && !have[t.first][t.second + 1]) q.emplace(t.first, t.second + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t, k, x, y;
    cin >> t;
    while (t--) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= 3; j++) {
                vis[i][j][0] = vis[i][j][1] = have[i][j] = false;
            }
        cin >> n >> k;
        while (k--) {
            cin >> x >> y;
            have[x][y] = !have[x][y];
        }
        bfs({1, 1}, 0);
        bfs({n, 3}, 1);
        vis[1][1][0] = vis[1][1][1] = false;
        long long cnt = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= 3; j++)
                if (vis[i][j][0] && vis[i][j][1])
                    cnt++;
        cout << cnt << '\n';
    }
}

先试试暴力啊，怎么会t呢？

G. Tokitsukaze and Gold Coins (hard)

待补充

H. Tokitsukaze and K-Sequence

题意

给定数组 \(a\)，将其划分为 \(k\) 个非空可不连续的子序列，输出 \(k \in [1, n]\) 时子序列的总和的最大值。定义子序列的值为只出现一次的数字个数。

思路

定义 \(cnt_i\) 为出现 \(i\) 次的数的个数。

\(k=1\) 时，显然答案为 \(cnt_1\)。

\(k>1\) 时，我们可以将 \(cnt_p,p \in [k,n]\) 对应数都留下一个，其余全都取出作为新子序列，此时答案为上一个答案的基础上加上 \(cnt_k+(cnt_k+cnt_{k+1}+...+cnt_{n})\)。

可以证明此时的个数最大。

因此，我们可以用类似于后缀和的方法写。

当然也有更简单的写法。

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

对应AC代码

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main{

    //快读，此处略过
    //public static class Console implements Closeable {}

    public static void main(String[] args) throws Throwable{
        Console scanner = new Console();
        int T = scanner.nextInt();
        while(T -- > 0){
            int n = scanner.nextInt();
            Map<Integer, Integer> cnt = new HashMap<>();
            int max = 0;
            for(int i=0;i<n;i++) {
                int b = scanner.nextInt();
                int p = cnt.getOrDefault(b, 0) + 1;
                cnt.put(b, p);
                max = Math.max(max, p);
            }
            int[] p = new int[max + 1], suf = new int[max + 1];
            for(int e : cnt.keySet()) p[cnt.get(e)] ++;
            suf[max] = p[max];
            for(int i=max-1;i>=1;i--) suf[i] = suf[i + 1] + p[i];
            long ans = p[1];
            scanner.println(ans);
            for(int i=2;i<=max;i++){
                ans += suf[i] + p[i];
                scanner.println(ans);
            }
            for(int i=max+1;i<=n;i++) scanner.println(ans);
        }
        scanner.close();
    }
}

很签的题呢

I. Tokitsukaze and Musynx

题意

对于 \(n\) 个 \(Note\)，有 \(5\) 个判定区间，每个区间有对应分数，输出调整谱面延时后分数的最大值。

给定 \(n\) 个音符，每个音符有对应判定分 \(x\)，定义五个判定区间 \((- \infty,a)\), \([a,b)\), \([b,c)\), \([c,d]\), \((d,+\infty)\)，\(x\) 落在区间内可获得对应分数 \(v_1\)，\(v2\)，\(v3\)，\(v4\)，\(v5\)。输出将所有的 \(x\) 加上或减去任意值后判定分总和的最大值。

思路

考虑到枚举 \(h\) 的时间复杂度过大，我们尝试另一种暴力枚举的方法：

1. 将所有 \(x\) 减去一个较大的值，使所有的音符全都落在第一个判定区间内；
2. 用数组存储每一个音符达到下一个判定区间的 \(\Delta x\)，以及对应的分数改变量；
3. 按 \(\Delta x\) 升序排序，枚举所有改变量并算出分数的最大值即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll N = 200010, inf = 1e18;

ll x[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --) {
        int n, a, b, c, d, v1, v2, v3, v4, v5;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> x[i];
            x[i] -= 2ll * 1e9;
        }
        cin >> a >> b >> c >> d >> v1 >> v2 >> v3 >> v4 >> v5;
        vector<pair<ll, int>> p;
        for (int i = 0; i < n; i++) {
            p.emplace_back(a - x[i], v2 - v1);
            p.emplace_back(b - x[i], v3 - v2);
            p.emplace_back(c - x[i], v4 - v3);
            p.emplace_back(d + 1 - x[i], v5 - v4);
        }
        sort(p.begin(), p.end());
        ll cur = v1 * n, ans = cur;
        for (auto &e: p) {
            cur += e.second;
            ans = max(ans, cur);
        }
        cout << ans << '\n';
    }
}

一个音游人居然没开这题

J. Tokitsukaze and Sum of MxAb

题意

给定数组 \(a\)，定义 \(MxAb(i,j)=\max(|a_i-a_j|,|a_i+a_j|)\)，求 \(\displaystyle{\sum_{i=1}^n\sum_{j=1}^nMxAb(i,j)}\)。

思路

很显然，同号取和的绝对值，异号取差的绝对值，总和显然是和所有 \(|a_i|\) 的总和有关的。

可以贪心的认为，\(ans=sum\{|a_i|\} \times 2n\)。

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

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while(T -- > 0){
            int n = scanner.nextInt();
            int[] a = new int[n];
            long ans = 0;
            for(int i=0;i<n;i++) {
                a[i] = scanner.nextInt();
                ans += Math.abs(a[i]);
            }
            System.out.println(ans * 2 * n);
        }
    }

}

签到题呢

K. Tokitsukaze and Synthesis and Traits

待补充

L. Tokitsukaze and Three Integers

题意

给定序列 \(a\) 和正整数 \(p\)，对于所有 \(x=0...p-1\)，输出满足条件的三元组 \([i,j,k]\) 的数量。

满足条件：

1. $i j \(，\)i k\(，\)j k$；

2. \((a_i·a_j+a_k) \equiv x \pmod p\)

思路

因为 \(n\) 为 \(1e3\) 级别，所以可以考虑时间复杂度为 \(n^2\) 的做法。

我们可以把式子分解成 \((a_i·a_j) \bmod p =(x-a_k) \bmod p\)，因此我们只需计算等式左右两边的配对情况即可。

需要注意的是，\(k\) 不能和 \(i\)，\(j\) 相等，所以最后需要排除。

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

对应AC代码

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main{

    //快读，此处略过
    //public static class Console implements Closeable {}

    public static void main(String[] args) throws Throwable{
        Console console = new Console();
        int n = console.nextInt(), p = console.nextInt();
        long[] a = new long[n + 1];
        for(int i=1;i<=n;i++) a[i] = console.nextInt();
        long[] cnt = new long[p];
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                cnt[(int)((a[i] * a[j]) % p)] += 2;
        long[] ans = new long[p];
        for(int x=0;x<p;x++)
            for(int k=1;k<=n;k++){
                long i = x - a[k];
                if (i < 0) i += (-i / p + 1) * p;
                ans[x] += cnt[(int)(i % p)];
            }
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++){
                ans[(int)((a[i] * a[j] + a[i]) % p)] -= 2;
                ans[(int)((a[i] * a[j] + a[j]) % p)] -= 2;
            }
        for(int i=0;i<p;i++) console.print(ans[i] + " ");
        console.close();
    }
}

别看了仔细想想就切题啊喂