A. 题目链接
算法标签：模拟。
思路：先计算出arr的sum，然后枚举删除arr[i]判断即可。
public class P1938 {
// https://codefun2000.com/p/P1938
public static void solve() throws IOException {
int n = in.nextInt();
long t = in.nextLong();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = in.nextInt();
long s = Arrays.stream(a).sum();
int ans = 0;
for (int x : a) {
long v = (s - x) - x;
if (v >= 0 && v <= t) ans++;
}
out.println(ans);
}
}B. 题目链接
算法标签：哈希表，模拟。
思路：先计算一个mex值（不在arr中的最小非负整数）。然后统计每个元素出现的次数，枚举删除每个元素arr[i]，如果arr[i]出现次数为1，并且arr[i] < mex， 那么删除后的最小非负整数就是arr[i]，否则是mex。
public class P1939 {
// https://codefun2000.com/p/P1939
public static void solve() throws IOException {
int n = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = in.nextInt();
Map<Integer, Integer> map = new HashMap<>();
for (int v : a) {
if (v < n) map.merge(v, 1, Integer::sum);
}
int mex = 0;
for (int i = 0; i < n; i++) {
if (map.getOrDefault(i, 0) == 0) {
mex = i;
break;
}
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
if (a[i] < n && map.get(a[i]) == 1 && mex > a[i]) {
ans[i] = a[i];
} else {
ans[i] = mex;
}
}
for (long v : ans) out.print(v + " ");
}
}C. 题目链接
算法标签：动态规划、数学。
思路：一个数字如果是3的倍数，那么它的数位和也是3的倍数。知道这个性质后，我们可以枚举每一个 ? [0~9]，然后用dp计算出方案数。这个过程中不断的对数位和取模，因为 (a + b + c) % 3 == ((a % 3) + (b % 3) + (c % 3)) % 3。最后判断下这个数字 % 3 是否为0即可。
public class P1940 {
// https://codefun2000.com/p/P1940
// 一个数字如果是3的倍数，那么它的数位和也是3的倍数
// ext -> 如果一个数字是 9 的倍数，那么它的数位和也是 9 的倍数
// (a + b + c) % 3 == ((a % 3) + (b % 3) + (c % 3)) % 3
static final int MOD = (int) (1e9 + 7);
static String s;
static long[][] dp;
static long dfs(int i, int v) {
if (i >= s.length()) return v % 3 == 0 ? 1 : 0;
if (dp[i][v] != -1) return dp[i][v];
long ans = 0;
if (s.charAt(i) == '?') {
for (int x = 0; x <= 9; x++) {
ans += dfs(i + 1, (v + x) % 3);
}
} else {
ans += dfs(i + 1, (v + (s.charAt(i) - '0')) % 3);
}
ans %= MOD;
return dp[i][v] = ans;
}
public static void solve() throws IOException {
int n = in.nextInt();
s = in.nextLine();
dp = new long[n + 1][3];
for (long[] d : dp) Arrays.fill(d, -1);
long res = dfs(0, 0);
out.println(res);
}
}