淘天笔试AK（9月16日）

T1 构造：手玩一下就能发现规律。偶数不行，因为所有的a+b加起来后，除n模为0，而c不为0

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if (n%2==0) {
            System.out.println("NO");
            return;
        }
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for (int i = 0; i<n; i++) {
            a[i] = b[i] = i+1;
            c[i] = (a[i]+b[i]) % n;
            if (c[i] == 0) c[i] = n;
        }
        System.out.println("YES");
        for (int i = 0; i<n; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        for (int i = 0; i<n; i++) {
            System.out.print(b[i] + " ");
        }
        System.out.println();
        for (int i = 0; i<n; i++) {
            System.out.print(c[i] + " ");
        }
        System.out.println();
    }
}

T2 钓鱼：贪心

import java.util.*;
public class Main {
    static Scanner in = new Scanner(System.in);
    public static void main(String[] args) {
        int t = in.nextInt();
        while (t-- > 0) solve();
    }
    static void solve(){
        int n = in.nextInt(), m = in.nextInt();
        int[] a = new int[n], b = new int[m];
        for (int i = 0; i<n; i++) a[i] = in.nextInt();
        for (int i = 0; i<m; i++) b[i] = in.nextInt();
        Arrays.sort(a);
        Arrays.sort(b);
        // a>b
        if (n > m) {
            System.out.print("YES ");
        } else if (n==m) {
            boolean flag = false;
            for (int i = 0; i<n; i++)
                if (a[i] > b[i]) flag = true;
            System.out.print(flag?"YES ":"NO ");
        } else if (n < m) {
            boolean flag = false;
            for (int i = n-1, j = m-1; i>=0&&j>=0; i--,j--) {
                if (a[i] > b[j]) flag = true;
            }
            System.out.print(flag?"YES ":"NO ");
        }
        // a<b
        if (n < m) {
            System.out.println("YES");
        } else if (n==m) {
            boolean flag = false;
            for (int i = 0; i<n; i++)
                if (a[i] < b[i]) flag = true;
            System.out.println(flag?"YES":"NO");
        } else if (n > m) {
            boolean flag = false;
            for (int i = n-1, j = m-1; i>=0&&j>=0; i--,j--) {
                if (a[i] < b[j]) flag = true;
            }
            System.out.println(flag?"YES":"NO");
        }
    }
}

T3 单调栈 开四个单调栈记录前面第一个比它大的，第一个比它小的，后面第一个比它大的，第一个比它小的元素，然后枚举区间最大元素x，最小元素为x-k，然后算满足题目要求的子数组数量即可

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int[] a = new int[N];
    int[] pre1 = new int[N];
    int[] pre2 = new int[N];
    int[] suf1 = new int[N];
    int[] suf2 = new int[N];
    int[] pos = new int[N];

    int n = scanner.nextInt();
    int k = scanner.nextInt();

    for (int i = 1; i <= n; ++i) {
        a[i] = scanner.nextInt();
        pos[a[i]] = i;
    }

    Stack<Integer> sk = new Stack<Integer>();
    for (int i = 1; i <= n; ++i) {
        while (!sk.isEmpty() && a[sk.peek()] < a[i]) {
            sk.pop();
        }
        if (!sk.isEmpty()) {
            pre1[i] = sk.peek();
        } else {
            pre1[i] = 0;
        }
        sk.push(i);
    }

    sk.clear();
    for (int i = 1; i <= n; ++i) {
        while (!sk.isEmpty() && a[sk.peek()] > a[i]) {
            sk.pop();
        }
        if (!sk.isEmpty()) {
            pre2[i] = sk.peek();
        } else {
            pre2[i] = 0;
        }
        sk.push(i);
    }

    sk.clear();
    for (int i = n; i >= 1; --i) {
        while (!sk.isEmpty() && a[sk.peek()] < a[i]) {
            sk.pop();
        }
        if (!sk.isEmpty()) {
            suf1[i] = sk.peek();
        } else {
            suf1[i] = n + 1;
        }
        sk.push(i);
    }

    sk.clear();
    for (int i = n; i >= 1; --i) {
        while (!sk.isEmpty() && a[sk.peek()] > a[i]) {
            sk.pop();
        }
        if (!sk.isEmpty()) {
            suf2[i] = sk.peek();
        } else {
            suf2[i] = n + 1;
        }
        sk.push(i);
    }

    long ans = 0;
    for (int i = 1; i <= n; ++i) {
        int minn = a[i] - k;
        if (minn <= 0) continue;
        if (pos[minn] < i) {
            if (pre1[i] > pos[minn] || suf2[pos[minn]] < i) continue;
            ans += (long) (Math.min(suf1[i] - 1, suf2[pos[minn]] - 1) - i + 1) *
                    (pos[minn] - Math.max(pre1[i] + 1, pre2[pos[minn]] + 1) + 1);
        } else {
            if (suf1[i] < pos[minn] || pre2[pos[minn]] > i) continue;
            ans += (long) (Math.min(suf1[i] - 1, suf2[pos[minn]] - 1) - i + 1) *
                    (pos[minn] - Math.max(pre1[i] + 1, pre2[pos[minn]] + 1) + 1);
        }
    }

    System.out.println(ans);
}