模拟。
1
2
3
4
5
6
7
8
9
10
| public static void solve() {
int n = io.nextInt(), l = io.nextInt();
int ans = 0;
for (int i = 0; i < n; i++) {
if (io.nextInt() >= l) {
ans++;
}
}
io.println(ans);
}
|
等价于求 \(y=|x-a_{i}|\) 在区间 \([L,R]\) 内的最小值对应的 \(x\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static void solve() {
int n = io.nextInt(), l = io.nextInt(), r = io.nextInt();
for (int i = 0; i < n; i++) {
int a = io.nextInt();
if (l <= a && a <= r) {
io.print(a + " ");
} else if (a < l) {
io.print(l + " ");
} else {
io.print(r + " ");
}
}
io.println();
}
|
对于每个固定的 \(x\)，可以在 \(O(1)\) 时间内求出 \(|y^{2}+(x^{2}-D)|\) 的最小值（也可以二分），我们枚举 \([0,\lceil\sqrt{D}\rceil]\) 范围内的所有 \(x\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static void solve() {
long d = io.nextLong();
long ans = Long.MAX_VALUE;
long up = (long) Math.sqrt(d) + 1;
for (long x = 0; x <= up; x++) {
long t = x * x - d;
if (t >= 0) {
ans = Math.min(ans, t);
} else {
long y = (long) Math.sqrt(-t);
ans = Math.min(ans, Math.abs(y * y + x * x - d));
ans = Math.min(ans, Math.abs((y + 1) * (y + 1) + x * x - d));
}
}
io.println(ans);
}
|
对行列计数，然后枚举交叉点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public static void solve() {
int n = io.nextInt();
char[][] s = new char[n][];
for (int i = 0; i < n; i++) {
s[i] = io.next().toCharArray();
}
int[] row = new int[n];
int[] col = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (s[i][j] == 'o') {
row[i]++;
col[j]++;
}
}
}
long ans = 0L;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (s[i][j] == 'o' && col[j] > 1) {
ans += (long) (col[j] - 1) * (row[i] - 1);
}
}
}
io.println(ans);
}
|
因为只有 \(n\) 个数，所以只需要考虑 \([0,n]\) 范围的数的增删，这样集合就可以存储单个数。比赛时没注意，使用的是区间，然后删除区间中的数，需要进行分裂，会麻烦很多，还需要排序以及考虑最左和最右的特殊区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| public static void solve() {
int n = io.nextInt(), q = io.nextInt();
int[] a = new int[n];
int[] cnt = new int[n + 1];
for (int i = 0; i < n; i++) {
a[i] = io.nextInt();
if (a[i] <= n) {
cnt[a[i]]++;
}
}
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i <= n; i++) {
if (cnt[i] == 0) {
set.add(i);
}
}
while (q-- != 0) {
int i = io.nextInt() - 1, x = io.nextInt();
if (a[i] <= n && --cnt[a[i]] == 0) {
set.add(a[i]);
}
a[i] = x;
if (a[i] <= n && cnt[a[i]]++ == 0) {
set.remove(a[i]);
}
io.println(set.first());
}
}
|