网站建设卖手机代码江山企业自适应网站建设首选
前言
整体评价
前三题蛮简单的，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);}}
写在最后
