Practice.

A. Polycarp and the Day of Pi

题意

将输入与 "\(314159265358979323846264338327\)" 比对，输出从头开始匹配成功的最大数量。

思路

模拟即可。

时间复杂度：\(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) {
            String a = "314159265358979323846264338327";
            String b = scanner.next();
            int n = b.length(), cnt = 0;
            for(int i=0;i<n;i++){
                if(a.charAt(i) != b.charAt(i)) break;
                cnt ++;
            }
            System.out.println(cnt);
        }
    }

}

题例有给圆周率的值，草

B. Taisia and Dice

题意

给定 \(3\) 个整数 \(n, s, r\)，构造一个数组 \(a\)，满足最大值为 \(s - r\)，数组的长度为 \(n\)，总和为 \(s\)。

思路

从大到小放入能放的最大数即可，上限需要考虑后面是否可以放 \(1\)。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        int s, r;
        cin >> n >> s >> r;
        int maxx = s - r;
        cout << maxx << ' ';
        s -= maxx;
        for(int i=n-2;i>=0;i--){
            int cur = min(6ll, max(1ll, min(maxx, s - i)));
            cout << cur << ' ';
            s -= cur;
        }
        cout << '\n';
    }
}

反正别用DFS就行

C. Premutation

题意

给定 \(n\) 的一种排列分别去掉每一位后构成的 \(n-1\) 个子序列，输出原排列。

思路

考虑第一位即可。

第一位中出现次数最多的数即为原排列的第一个数，而出现最少的数所在子序列即为原排列去掉第一个数后的子序列，拼起来即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N][N];

#define int long long

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --) {
        memset(a, 0, sizeof a);
        cin >> n;
        int h1, h2, c1 = 0, c2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                cin >> a[i][j];
            }
            if(c1 == 0 || h1 == a[i][0]) h1 = a[i][0], c1 ++;
            else h2 = a[i][0], c2 ++;
        }
        int h = c1 > c2 ? h1 : h2;
        for(int i=0;i<n;i++){
            if(a[i][0] != h){
                cout << h << ' ';
                for(int j=0;j<n-1;j++) cout << a[i][j] << ' ';
                break;
            }
        }
        cout << '\n';
    }
}

找规律就行力

D. Matryoshkas

题意

给定一个数组 \(a\)，将其拆分成任意数量的子序列，满足子序列升序排序后相邻元素相差 \(1\)，且无重复元素，输出子序列的最小数量。

思路

我们可以考虑模拟的做法，将所有子序列抽象为序列中最大的数，作为几堆候选区域：

在升序排序数组 \(a\) 后，我们依次将元素 \(a_i\) 放入，放入前，我们先拿出候选中数值最小的，然后分类讨论：

1. 如果满足 \(+1\) 后和\(a_i\) 相同，那么我们直接将元素放入该候选区域；
2. 如果两数相同，那么两数均可作为下一个数的可能候选区域，所以新建一个区域并放入该数；
3. 否则，那么这个候选区域无法再进行匹配，直接取出并计数。

最后，剩下的堆数加上被取出的堆数即为答案。

当然，为了降低复杂度，考虑使用优先队列。

时间复杂度：\(O(nt \log t),t为队列长度\)

对应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];
            PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.comparingInt(o -> o));
            for(int i=0;i<n;i++) a[i] = scanner.nextInt();
            Arrays.sort(a);
            int cnt = 0;
            for(int i=0;i<n;i++){
                boolean ok = false;
                while(!q.isEmpty()){
                    int now = q.poll();
                    if(now + 1 == a[i]) {
                        q.offer(a[i]);
                        ok = true;
                        break;
                    }else if(now == a[i]){
                        q.offer(a[i]);
                        q.offer(a[i]);
                        ok = true;
                        break;
                    }
                    else cnt ++;
                }
                if(!ok) q.offer(a[i]);
            }
            System.out.println(cnt + q.size());
        }
    }

}

其实可以不用这么模拟，太模拟了（（

E. Vlad and a Pair of Numbers

题意

给定一个整数 \(n\)，满足 \(a \oplus b = \frac{a+b}{2}=n\)，输出满足条件的任意一组 \(a,b\)。

思路

我们先来考虑 \(a \oplus b = a+b=t\)：

对于任意二进制数 \(t\)，当我们从高位向低位遍历时，若遇到 \(1\)，那么我们不妨在 \(a\) 的该位填上 \(1\)，在 \(b\) 的该位上填上 \(0\)，这样即可满足异或运算和加法运算的值一致。

而对于 \(a \oplus b = \frac{a+b}{2}=n\)：

我们注意到有除 \(2\) 的运算，该操作等效于将 \(a+b\) 的二进制结果向低位移动一位，此时，若按照上述做法，我们会发现 \(1\) 的位置恰好差了一位，那么我们就希望能出现进位的操作。

考虑到对于二进制运算，\(11+01=100\)，那么我们不妨在上述做法的基础上，在 \(1\) 后面一位对应的 \(a,b\) 位置上分别填上 \(1,0\)，这样就可以满足我们的需求了。

而显而易见，当 \(1\) 出现在最后一位（奇数），或者有连续的 \(1\) 存在时，即为无解。

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

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        nxt:
        while (t-- > 0) {
            int n = scanner.nextInt(); //有连着的1就不行
            if(n % 2 == 1){
                System.out.println(-1);
                continue nxt;
            }
            int a = 0, b = 0;
            boolean f = false;
            for(char e : Integer.toBinaryString(n).toCharArray()){
                int p = e - '0';
                if (f) {
                    if (p == 1) {
                        System.out.println(-1);
                        continue nxt;
                    } else {
                        a = a * 2 + 1;
                        b = b * 2 + 1;
                        f = false;
                    }
                } else {
                    f = p == 1;
                    a *= 2;
                    b *= 2;
                    if(f) a ++;
                }
            }
            System.out.printf("%d %d\n", a, b);
        }
    }

}

真的不是找规律题么（（

F. Timofey and Black-White Tree

题意

对于一个 \(n\) 个点 \(n-1\) 个边的无向无环图，给定操作顺序，将 \(n\) 个点按照顺序涂成黑色，输出从第 \(2\) 个操作开始，对于每次操作后，所有任意两个黑点的距离的最小值。

思路

我们可以考虑树形 \(dp\) 的写法，其中 \(dp[i]\) 表示第 \(i\) 个点 在涂色前 该点的所有子节点中 黑色的点到该点的最短距离。

难道我们要把子节点全都遍历一遍吗？显然不用。

这是一个无向无环图，那么显然一个点只有一个父节点，只要根节点确定了，我们构建一个数组即可。

因此，我们不妨从要涂色的点开始，向上 \(Dfs\) 到根节点，在遍历的同时记录当前已经遍历的边数 \(st\)。在遍历到节点 \(i\) 时，我们以这个点为跳板，用 \(dp[i]+st\) 更新最终答案，并将 \(dp[i]\) 更新为 \(\min(dp[i],st)\) 即可。

深搜剪枝

1. 根节点的确定：在绝大多数情况下，取子节点最多的点作为根节点是更优的，这样可以让链条结构更多，从而一定程度降低时间复杂度；
2. 只遍历父节点
3. \(st>=ans\) 时，结束遍历：显然，我们需要求答案的最小值，那么就算我们继续遍历，最后更新的 \(dp\) 值是一定大于等于 \(ans\) 的，因而我们就没必要 让其他将要涂黑的点 以这个点为跳板 来更新 \(ans\) 了。而恰恰因为我们至少遍历了 \(ans-1\) 个，可以保证 最小路径所在边 一定被我们遍历过了，因而答案没有问题。

整体来看

1. 确定根节点；
2. 从根节点开始向下 \(Dfs\) 一遍，求出每个点的父节点；
3. 依次遍历要涂黑的点，向上 \(Dfs\) 并更新 \(dp\) 值。

时间复杂度：不会分析

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010, inf = 0x3f3f3f3f;

#define int long long

vector<int> e[N];
int dp[N], c[N], root, ans, vis[N], f[N];//cut2: 只遍历爹，因为爹只有一个（无环

void dfs1(int fa){
    for(int p : e[fa]){
        if(vis[p]) continue;
        vis[p] = true;
        f[p] = fa;
        dfs1(p);
    }
}

void dfs2(int child, int st){
    if(st >= ans) return; //cut3: 步数那么多就没必要继续走，防止每次都被卡O(n)
    if(dp[child] != inf) ans = min(ans, dp[child] + st);
    dp[child] = min(st, dp[child]);
    if(child != root) dfs2(f[child], st + 1);
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --) {
        cin >> n >> c[0];
        for(int i=1;i<n;i++) {
            cin >> c[i];
            dp[i] = inf;
            vis[i] = false;
            e[i].clear();
        }
        dp[n] = inf;
        vis[n] = false;
        e[n].clear();
        int maxx = -1;
        root = 1; //cut1: 根节点选分支最多的
        for(int i=1;i<n;i++){
            int u, v;
            cin >> u >> v;
            e[u].emplace_back(v);
            e[v].emplace_back(u);
            int s1 = e[u].size(), s2 = e[v].size();
            if(max(s1, s2) > maxx) {
                maxx = max(s1, s2);
                root = s1 > s2 ? u : v;
            }
        }
        dfs1(root);
        ans = inf;
        dfs2(c[0], 0);
        for(int i=1;i<n;i++){
            dfs2(c[i], 0);
            cout << ans << ' ';
        }
        cout << '\n';
    }
}

我趣，怎么一遍过