Rank 906/3920. AC 5/12.

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

题意

在两个闭区间和之间取两个数，，满足。 时交换两者可算作两种选法。输出选法总数。

思路

暴力枚举，。快速签到。

时间复杂度：

对应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)

题意

同题，只有样例数量增加了。

思路

一个取交集的思路：

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

时间复杂度：

对应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)

题意

给定个区间，在不同的区间内分别取，，同，输出方案数。

思路

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

时间复杂度：

对应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

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

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

时间复杂度：

对应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

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

时间复杂度：

#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

题意

给定函数以及区间，输出使最小的最小整数。

思路

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

保留符号后，最小值会在和处取到，我们记为。

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

不过，因为我们需要取，所以我们只需从点向左找转折点，即左边的值大于自身的那个点。

我们先来特判几个情况：

时，输出即可。
时，我们可以将寻找转折点的区间缩小为题给区间。

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

时间复杂度：

对应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)

题意

给定有障碍迷宫，输出从 $，$ 到的所有路径中经过的点的个数，不重复计算。

思路

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

时间复杂度：

对应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

题意

给定数组，将其划分为个非空可不连续的子序列，输出时子序列的总和的最大值。定义子序列的值为只出现一次的数字个数。

思路

定义为出现次的数的个数。

时，显然答案为。

时，我们可以将 $cntp,p \in [k,n] $对应数都留下一个，其余全都取出作为新子序列，此时答案为上一个答案的基础上加上$ cnt_k+(cnt_k+cnt{k+1}+…+cnt_{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

题意

~~对于个，有个判定区间，每个区间有对应分数，输出调整谱面延时后分数的最大值。~~

给定个音符，每个音符有对应判定分，定义五个判定区间 , , , , ，落在区间内可获得对应分数，，，，。输出将所有的加上或减去任意值后判定分总和的最大值。

思路

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

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

时间复杂度：

对应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

题意

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

思路

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

可以贪心的认为，。

时间复杂度：

对应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

题意

给定序列和正整数，对于所有，输出满足条件的三元组的数量。

满足条件：

，，；

思路

因为为级别，所以可以考虑时间复杂度为的做法。

我们可以把式子分解成，因此我们只需计算等式左右两边的配对情况即可。

需要注意的是，不能和，相等，所以最后需要排除。

时间复杂度：

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

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

本文作者 Floating Ocean
本文链接 https://floating-ocean.github.io/blog_old/posts/4009320463/
版权声明本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！