比赛地址:https://atcoder.jp/contests/abc189

完整代码(A-F):Github

A - Slot

直接判断就行了

B - Alcoholic

注意避免用除,转换成乘

C - Mandarin Orange

There are dishes arranged in a row in front of Takahashi. The -th dish from the left has oranges on it.

Takahashi will choose a triple of integers satisfying all of the following conditions:

  • for every integer between and (inclusive), .

He will then pick up and eat oranges from each of the -th through -th dishes from the left.

At most how many oranges can he eat by choosing the triple to maximize this number?

Constraints

  • All values in input are integers.

Sample Input 1

6
2 4 4 9 4 9

Sample Output 1

20

解法一

暴力 的方法,枚举所有区间,以及区间最小值,数据范围 ,在 LC 上肯定超时了,但是在这里好像不仅不会超时,速度还很快,180ms

不过这个题放在这个位置正确的解法应该就是下面的暴力,如果放到 D 题,然后数据范围大一点,就没这么简单了,就是下面的解法二了

import java.util.*;
import java.io.*;

class Main {

public static void main(String... args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int N = read(br)[0];
int[] w = read(br);
int res = 0;
for (int i = 0; i < N; i++) {
if (i > 0 && w[i] == w[i-1]) continue;
int min = Integer.MAX_VALUE;
for (int j = i; j < N; j++) {
min = Math.min(w[j], min);
res = Math.max(res, min*(j-i+1));
}
}
System.out.println(res);
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

解法二

单调栈的解法,和 Lc84. 柱状图中最大的矩形 是一道题,时间复杂度

import java.util.*;
import java.io.*;

class Main {

public static void main(String... args) throws Exception {
//2 4 4 9 4 9
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int N = read(br)[0];
int[] w = new int[N+1];
System.arraycopy(read(br), 0, w, 0, N);
w[N] = -1;
//单调递增栈
Deque<Integer> stack = new ArrayDeque<>();
int res = 0;
for (int i = 0; i <= N; i++) {
while (!stack.isEmpty() && w[stack.peek()] > w[i]) {
int cur = stack.pop();
//向左最多扩展到 left+1,向右最多扩展到 i-1 (i-1-left-1+1)
int left = stack.isEmpty() ? -1 : stack.peek();
res = Math.max(res, (i-1-left)*w[cur]);
}
stack.push(i);
}
System.out.println(res);
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

D - Logical Expression

Given are strings , each of which is AND or OR.

Find the number of tuples of variables , where each element is or , such that the following computation results in being :

  • ;
  • for , if is AND, and if is OR.

Here, a b and a b are logical operators.

Constraints

  • is AND or OR.

Sample Input 1

2
AND
OR

Sample Output 1

5

解法一

比赛的时候写了个巨丑的记忆化递归,虽然过了但是并不是很满意,这里实际上很容易直接递推。

:前 个元素使得 的个数(0 为 F,1 为 T)

代码实现

//代码还可以进行空间降维,注意消除前后依赖就行了
import java.util.*;
import java.io.*;

class Main {
public static void main(String... args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
//前 i 个元素,yi 为 F 和 T
long[][] dp = new long[N+1][2];
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i <= N; i++) {
String op = sc.next();
if ("AND".equals(op)) {
dp[i][1] = dp[i-1][1];
dp[i][0] = dp[i-1][1] + dp[i-1][0] + dp[i-1][0];
} else {
dp[i][1] = dp[i-1][0] + dp[i-1][1] + dp[i-1][1];
dp[i][0] = dp[i-1][0];
}
}
System.out.println(dp[N][1]);
}
}

E - Rotate and Flip

There are pieces on a two-dimensional plane. The coordinates of Piece are . There may be multiple pieces at the same coordinates.

We will do operations , one by one. There are four kinds of operations, described below along with their formats in input.

  • 1:Rotate every piece degrees clockwise about the origin;
  • 2:Rotate every piece degrees counterclockwise about the origin;
  • 3 p:Move each piece to the point symmetric to it about the line ;
  • 4 p:Move each piece to the point symmetric to it about the line .

You are given queries. In the -th query, given two integers and , print the coordinates of Piece just after the -th operation. Here, the moment just before the -st operation is considered to be the moment just after “the -th operation”.

Constraints

  • All values in input are integers.
  • is in the format of one of the four kinds of operations.
  • In an operation with the form 3 p or 4 p, .

Sample Input 1

1
1 2
4
1
3 3
2
4 2
5
0 1
1 1
2 1
3 1
4 1

Sample Output 1

1 2
2 -1
4 -1
1 4
1 0

Initially, the only piece - Piece - is at . Each operation moves the piece as follows: .

解法一

题目意思就是:给你 个点,然后给你 个操作(有序),然后给你 个查询,每个查询有两个值 ,返回第 个点在经过第 次操作后的坐标

做法就是将所有的操作叠加起来,这里题目说了操作都是有序的,所以我们按顺序叠加 个操作,然后针对每个查询我们就可以 的求出结果

import java.util.*;
import java.io.*;

class Main {

public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

public static void main(String... args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int N = readOne(br);
int[] x = new int[N];
int[] y = new int[N];
for (int i = 0; i < N; i++) {
int[] t = read(br);
x[i] = t[0]; y[i] = t[1];
}
int M = readOne(br);
//将操作叠加起来
//1.(x, y) --> (y, -x)
//2.(x, y) --> (-y, x)
//3.(x, y) --> (-x+2p, y)
//4.(x, y) --> (x, -y+2p)
boolean[] swap = new boolean[M+1];
long[] addx = new long[M+1];
long[] addy = new long[M+1];
long[] mulx = new long[M+1];
long[] muly = new long[M+1];
mulx[0] = muly[0] = 1;
for (int i = 1; i <= M; i++) {
int[] t = read(br);
if (t[0] == 1) {
swap[i] = !swap[i-1];
mulx[i] = muly[i-1]; muly[i] = -mulx[i-1];
addx[i] = addy[i-1]; addy[i] = -addx[i-1];
} else if (t[0] == 2) {
swap[i] = !swap[i-1];
mulx[i] = -muly[i-1]; muly[i] = mulx[i-1];
addx[i] = -addy[i-1]; addy[i] = addx[i-1];
} else if (t[0] == 3) {
swap[i] = swap[i-1];
mulx[i] = -mulx[i-1]; muly[i] = muly[i-1];
addx[i] = 2l*t[1] - addx[i-1]; addy[i] = addy[i-1];
} else if (t[0] == 4) {
swap[i] = swap[i-1];
mulx[i] = mulx[i-1]; muly[i] = -muly[i-1];
addx[i] = addx[i-1]; addy[i] = 2l*t[1] - addy[i-1];
}
}
int Q = readOne(br);
for (int i = 0; i < Q; i++) {
int[] t = read(br);
int a = t[0], b = t[1]-1;
if (!swap[a]) {
out.println((x[b]*mulx[a] + addx[a]) + " " + (y[b]*muly[a] + addy[a]));
} else {
out.println((y[b]*mulx[a] + addx[a]) + " " + (x[b]*muly[a] + addy[a]));
}
}
out.flush();
out.close();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}

public static int readOne(BufferedReader br) throws Exception {
return Integer.parseInt(br.readLine());
}
}

具体的 addx,addy,mulx… 这些参数的变化最好找一个例子自己代入试一下,空想容易搞错

这里踩了个小坑,Java 的 prinf 效率会比 print 以及 write 慢很多,虽然可以想象到会慢一点,没想到会慢这么多,上面这题一开始用的 printf 打印的结果,然后就 T 了。.. 后面我自己测试了一下,发现确实会慢很多,以后要慎用了
TestCode

这题实际上还有一个利用矩阵的解法,相对来说会比较直接简单,官方题解也是用的矩阵的做法,后面有时间再来补充

F - Sugoroku2

暂时还没搞懂,后面再来补