牛客周赛 Round 18 解题报告 | 珂学家 | 分类讨论计数 + 状态DP

前言

alt

整体评价

前三题蛮简单的，T4是一个带状态的DP，这题如果用背包思路去解，不知道如何搞，感觉有点头痛。所以最后还是选择状态DP来求解。

欢迎关注

珂朵莉牛客周赛专栏

珂朵莉牛客小白月赛专栏

A. 游游的整数翻转

这题最好是用API来处理，这样更简洁且准确率高

import java.io.BufferedInputStream;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));String s = sc.next();int k = sc.nextInt();String s1 = s.substring(0, k), s2 = s.substring(k);Long r = Long.valueOf(new StringBuilder(s1).reverse().append(s2).toString());System.out.println(r);}}

B. 游游的排列统计

很有意思的一道题

这题甚至可以用状压DP求解

不过这边还是用暴力dfs, 其一，n<10, 其二，约束强，剪枝大

import java.io.BufferedInputStream;
import java.util.Scanner;public class Main {static boolean[] primes = new boolean[20];static {primes[2] = true;primes[3] = true;primes[5] = true;primes[7] = true;primes[11] = true;primes[13] = true;primes[17] = true;primes[19] = true;}static long dfs(int n, int u, int s) {if (s == ((1 << n) - 1)) {return 1;} else {long res = 0;for (int i = 1; i <= n; i++) {if (((1 << (i - 1)) & s) != 0) continue;if (primes[u + i]) continue;res += dfs(n, i, s | (1 << (i - 1)));}return res;}}public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int n = sc.nextInt();long res = 0;for (int i = 1; i <= n; i++) {res += dfs(n, i, 1 << (i - 1));}System.out.println(res);}}

C. 游游刷题

同余分组计数

然后贪心分类讨论

r = 0, 则单独为一组 cnt(0)
2 * r = k, 则为 cnt® / 2
r < k, 则 min(cnt®, cnt(k - r))

累加即可

import java.io.*;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int n = sc.nextInt();int k = sc.nextInt();Map<Integer, Integer> hash = new HashMap<>();for (int i = 0; i < n; i++) {int v = sc.nextInt();hash.merge(v % k, 1, Integer::sum);}long ans = 0;for (Map.Entry<Integer, Integer> kv : hash.entrySet()) {int k1 = kv.getKey(), v1 = kv.getValue();if (k1 == 0) {ans += v1;} else if (k1 * 2 == k){ans += v1 / 2;} else if (k1 * 2 < k) {int v2 = hash.getOrDefault(k - k1, 0);ans += Math.min(v2, v1);}}System.out.println(ans);}}

D. 游游买商品

状态DP

令 dp[i][j][s], i为前i个项，j表示使用了多少钱，s为0,1表示状态

0表示第i项不购买，或者半价购买

1表示第i项全价购买

那状态转移为

dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1], dp[i - 1][j - cost[i] / 2][1] + happy[i]);

dp[i][j][1] = max(dp[i - 1][j - cost[i]][0], dp[i - 1][j - cost[i]][1]) + happy[i];

最后的结果为 max(dp[n - 1][j][s]), 0<=j<=x, s=0,1

import java.io.BufferedInputStream;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));int n = sc.nextInt(), x = sc.nextInt();int[] cost = new int[n];long[] happy = new long[n];for (int i = 0; i < n; i++) {cost[i] = sc.nextInt();}for (int i = 0; i < n; i++) {happy[i] = sc.nextLong();}// *)long inf = Long.MIN_VALUE / 10;long[][][] opt = new long[n][x + 1][2];for (int i = 0; i < n; i++) {for (int j = 0; j <= x; j++) {opt[i][j][0] = opt[i][j][1] = inf;}}long ans = 0;if (cost[0] <= x) {opt[0][cost[0]][1] = happy[0];}opt[0][0][0] = 0;for (int i = 1; i < n; i++) {for (int j = 0; j <= x; j++) {opt[i][j][0] = Math.max(opt[i - 1][j][0], opt[i - 1][j][1]);if (j - cost[i] / 2 >= 0) {opt[i][j][0] = Math.max(opt[i][j][0], opt[i - 1][j - cost[i] / 2][1] + happy[i]);}if (j - cost[i] >= 0) {opt[i][j][1] = Math.max(opt[i - 1][j - cost[i]][0], opt[i - 1][j - cost[i]][1]) + happy[i];}}}for (int j = 0; j <= x; j++) {ans = Math.max(ans, opt[n - 1][j][0]);ans = Math.max(ans, opt[n - 1][j][1]);}System.out.println(ans);}}