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);
}
#淘宝##淘天##天猫国际##笔试#