B 组队
排序+双指针
从小到大排序之后，双指针寻找最大的人数（窗口）。
左右指针从0开始，只要两指针指向的值的差 <= k，右指针后移，每次移动之后都更新一下最大值。
如果不满足差值 <= k，则左指针右移，一直到出界为止。
/** * @author :Changersh * @date : 2023/5/13 19:54 */
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
private static int T, N = (int) 2e5 + 10, n, m, k;
private static int[] a;
public static void main(String[] args) {
T = sc.nextInt();
while (T-- > 0) solve();
pw.close();
}
private static void solve() {
n = sc.nextInt();
k = sc.nextInt();
a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
Arrays.sort(a);
int l = 0, r = 0, mx = 0;
while (l <= r && r < n) {
if (a[r] - a[l] <= k) {
mx = Math.max(mx, r - l + 1);
r++;
} else l++;
}
pw.println(mx);
}
}
D 牛妹吃豆子
二维前缀和+二维差分
模板题
/** * @author :Changersh * @date : 2023/5/13 20:39 */
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
private static int N = 2010, n, m, k, q;
private static long[][] a = new long[N][N];
public static void main(String[] args) {
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
q = sc.nextInt();
int x1, x2, y1, y2;
while (k-- > 0) {
x1 = sc.nextInt();
y1 = sc.nextInt();
x2 = sc.nextInt();
y2 = sc.nextInt();
a[x1][y1] += 1;
a[x2+1][y1] -= 1;
a[x1][y2+1] -= 1;
a[x2+1][y2+1] += 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] += a[i][j-1] + a[i-1][j] - a[i-1][j-1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] += a[i][j-1] + a[i-1][j] - a[i-1][j-1];
}
}
while (q-- > 0) {
x1 = sc.nextInt();
y1 = sc.nextInt();
x2 = sc.nextInt();
y2 = sc.nextInt();
pw.println(a[x2][y2] - a[x2][y1-1] - a[x1-1][y2] + a[x1-1][y1-1]);
}
pw.close();
}
}
F 斗兽棋
map模拟
将对应的谁吃谁的关系存到map中，读入两个人的棋子之后，判断是否存在关系即可
/** * @author :Changersh * @date : 2023/5/13 19:45 */
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
private static String a, b;
private static HashMap<String, String> map = new HashMap<>();
public static void main(String[] args) {
map.put("elephant", "tiger");
map.put("tiger", "cat");
map.put("cat", "mouse");
map.put("mouse", "elephant");
a = sc.next();
b = sc.next();
if (map.get(b).equals(a)) pw.println("tiangou txdy");
else pw.println("tiangou yiwusuoyou");
pw.close();
}
}
G 做题
模拟
注意：没看到m范围是5e10，没有意识到应该用long，导致一直错误，比赛是换成py过的
/** * @author :Changersh * @date : 2023/5/13 19:28 */
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
private static int N = (int) 5e6 + 10;
private static int n;
private static long ans, m;
private static int[] a = new int[N];
public static void main(String[] args) {
n = sc.nextInt();
m = sc.nextLong();
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
Arrays.sort(a, 0, n);
long sum = 0;
for (int i = 0; i < n; i++) {
if (a[i] + sum <= m) {
sum += a[i];
ans++;
} else {
break;
}
}
pw.println(ans);
pw.close();
}
}
J_建设道路
数学
将平方拆开 (a - b) ^ 2 = a^ 2 + b^ 2 - 2ab
如果是三项= 2 ( a^ 2 + b^ 2 + c^ 2) - 2ab - 2ac - 2bc
所以是 ( n-1 ) (aa + bb+…) - (sum - a[i]) * a[i]
至于2ab的 2，是不用乘的，以 (a - b) ^2 为例，后一项是 -2ab，用上面式子计算就是 ab + ba，这个倍数是被算过了
/** * @author :Changersh * @date : 2023/5/17 20:00 */
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
private static int P = (int) 1e9 + 7, N = (int) 5e5 + 10, n;
private static long[] a = new long[N];
public static void main(String[] args) {
n = sc.nextInt();
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long ans = 0, sm = 0;
for (int i = 0; i < n; i++) {
ans += a[i] * a[i] % P;
ans %= P;
sm = (sm + a[i]) % P;
}
ans = (ans * (n - 1)) % P;
for (int i = 0; i < n; i++) {
ans = (ans % P - a[i] * ((sm - a[i]) % P + P) % P) % P;
ans = (ans + P) % P;
}
pw.println(ans);
pw.close();
}
}
文章评论