AtCoder Beginner Contest 261
比赛地址： https://atcoder.jp/contests/abc261
比赛只写出了 A-D。前三题比较简单，D 题是一个 DP，也比较明显，注意溢出就行。补一下 E，F（G，Ex 现阶段不考虑），完整代码 (A-F)：Github
E - Many Operations
We have a variable $X$ and $N$ kinds of operations that change the value of $X$ . Operation $i$ is represented as a pair of integers $(T_i,A_i)$ , and is the following operation:
- if $T_i=1$ , it replaces the value of $X$ with $X\ {\rm and}\ A_i$ ;
- if $T_i=2$ , it replaces the value of $X$ with $X\ {\rm or}\ A_i$ ;
- if $T_i=3$ , it replaces the value of $X$ with $X\ {\rm xor}\ A_i$ .
Initialize $X$ with the value of $C$ and execute the following procedures in order:
- Perform Operation $1$ , and then print the resulting value of $X$ .
- Next, perform Operation $1, 2$ in this order, and then print the value of $X$ .
- Next, perform Operation $1, 2, 3$ in this order, and then print the value of $X$ .
- $\vdots$
- Next, perform Operation $1, 2, \ldots, N$ in this order, and then print the value of $X$ .
Constraints
- $1 \leq N \leq 2\times 10^5$
- $1\leq T_i \leq 3$
- $0\leq A_i \lt 2^{30}$
- $0\leq C \lt 2^{30}$
- All values in input are integers.
Sample Input
3 10
3 3
2 5
1 12
Sample Output
9
15
12
The initial value of $X$ is $10$ .
Operation $1$ changes $X$ to $9$ . Next, Operation $1$ changes $X$ to $10$ , and then Operation $2$ changes it to $15$ . Next, Operation $1$ changes $X$ to $12$ , and then Operation $2$ changes it to $13$ , and then Operation $3$ changes it to $12$ .
解法一
题目大致意思是给你一个数，然后输出经过 $i$ 次操作后的值，每次操作都会把前面的操作再执行一遍。一共有三种操作，并，或，异或。
赛后看官方题解看的不是很明白，然后看了别人的讨论，自己琢磨了一下才写出来。
首先这里每次操作对于原数字的任意一位来说都是完全独立的，不会相互影响。所以我们完全可以分开考虑每一位的状态，设置 $f[i][j]$ 为当前位初始为 $j(0/1)$ 经历 $i$ 次操作后的结果。预先计算出当前位为 $0/1$ 时，经过 $i$ 次操作后的状态 $(0/1)$ ，然后进行递推，获得 $i$ 次操作后每一位的状态构成答案。
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] in = read(br);
int N = in[0], C = in[1];
var op = new int[N][2];
for (int i = 0; i < N; i++) {
op[i] = read(br);
}
var res = new int[N+1];
// f[i][j]，当前位初始为 j(0/1) 经历 i 次操作后的结果
var f = new int[N+1][2];
f[0][0] = 0;
f[0][1] = 1;
// 枚举每一位
for (int i = 0; i < 30; i++) {
int cur = (C>>>i) & 1;
// 枚举每种操作
for (int j = 1; j <= N; j++) {
int t = op[j-1][0], a = op[j-1][1];
int x = (a>>>i) & 1;
if (t == 1) {
f[j] = new int[]{ f[j-1][0] & x, f[j-1][1] & x};
}
if (t == 2) {
f[j] = new int[]{ f[j-1][0] | x, f[j-1][1] | x};
}
if (t == 3) {
f[j] = new int[]{ f[j-1][0] ^ x, f[j-1][1] ^ x};
}
// 初始为 cur，经历 j 次操作后的值（重放）
cur = f[j][cur];
res[j] |= (cur<<i);
}
}
for (int i = 1; i <= N; i++) {
out.println(res[i]);
}
out.flush();
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
// AtCoder/AcWing 提交上面部分即可，CF 需要将 JavaMain 移到上面然后提交
public class E {
public static void main(String[] args) throws Exception{
// 输入重定向，通过 jvm 参数判断环境
if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
System.setIn(new FileInputStream("./input.txt"));
}
new Main().main(args);
}
}
F - Sorting Color Balls
There are $N$ balls arranged from left to right. The color of the $i$ -th ball from the left is Color $C_i$ , and an integer $X_i$ is written on it. Takahashi wants to rearrange the balls so that the integers written on the balls are non-decreasing from left to right. In other words, his objective is to reach a situation where, for every $1\leq i\leq N-1$ , the number written on the $(i+1)$ -th ball from the left is greater than or equal to the number written on the $i$ -th ball from the left. For this, Takahashi can repeat the following operation any number of times (possibly zero):
Choose an integer $i$ such that $1\leq i\leq N-1$ . If the colors of the $i$ -th and $(i+1)$ -th balls from the left are different, pay a cost of $1$ . (No cost is incurred if the colors are the same). Swap the $i$ -th and $(i+1)$ -th balls from the left.
Find the minimum total cost Takahashi needs to pay to achieve his objective.
Constraints
- $2 \leq N \leq 3\times 10^5$
- $1\leq C_i\leq N$
- $1\leq X_i\leq N$
- All values in input are integers.
Sample Input
5
1 5 2 2 1
3 2 1 2 1
Sample Output
6
解法一
通过交换相邻元素的操作使一个数组变得有序的最少操作次数就是逆序对的个数，也就是冒泡排序的过程。
但是这题中有一些额外条件，就是相邻的逆序对气球，如果颜色一样，交换就没有消耗。所以我们可以大胆猜测，结果就是总体逆序对数量减去同颜色逆序对的数量，首先让整体交换次数最少，然后考虑减去无消耗的部分。
这里使用数状数组求解逆序对，代码实现如下：
import java.util.*;
import java.io.*;
class Main {
static int[] tree;
static int len;
public static int lowbit(int i){
return i & -i;
}
public static void add(int i, int v) {
while (i < len) {
tree[i] += v;
i += lowbit(i);
}
}
public static long sum(int i) {
long res = 0;
while (i > 0) {
res += tree[i];
i -= lowbit(i);
}
return res;
}
public static void main(String[] args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = read(br)[0];
var C = read(br);
var X = read(br);
tree = new int[N+1];
len = N;
List<Integer>[] cls = new ArrayList[N+1];
for (int i = 0; i < N; i++) {
if (cls[C[i]] == null) {
cls[C[i]] = new ArrayList<>();
}
cls[C[i]].add(X[i]);
}
long res = 0;
for (int i = N-1; i >= 0; i--) {
add(X[i], 1);
res += sum(X[i]-1);
}
// 重置，统计相同气球逆序对
tree = new int[N+1];
// 注意从1开始，在这里WA了好几发
for (int i = 1; i <= N; i++) {
if (cls[i] == null) continue;
int sz = cls[i].size();
for (int j = sz-1; j >= 0; j--) {
int c = cls[i].get(j);
add(c, 1);
res -= sum(c-1);
}
// 还原，用于下一组
for (Integer c : cls[i]) {
add(c, -1);
}
}
out.println(res);
out.flush();
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
还有一种用map记录同色气球数量的做法，但是效率不高，Submission #33508589