黑白切换 (ac)
抱歉抱歉,贴的是交卷后自己又精简了的代码,当时有点迷糊,代码写错了。现在已修复,谢谢各位指正。
思路是这样的:
总共三个操作:交换,变值,翻转。
交换一次可以变两个数字,而变值一次只可以变一个数字,所以优先交换。
翻转也就多一次操作,所以比较一下考虑翻转和不考虑翻转的情况就行了。
若不考虑翻转的话:
在 A 串中有 n 个 '0' 需要变成 '1', m 个 ‘1’ 需要变成 '0'. 那么交换 min(n, m) 次,之后还剩 max(n, m) - min(n, m) 个值需要变值。所以一共 max(n, m) 次。
考虑翻转的话,就先翻转,再进行上述的操作。import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = Integer.parseInt(sc.nextLine()); String A = sc.nextLine(); String B = sc.nextLine(); System.out.print(new Solution().solve(n, A, B)); } } class Solution{ public int solve(int n, String A, String B) { int[] n1 = new int[2], n2 = new int[2]; for(int i = 0; i < n; i++) { char c = A.charAt(i); if(c != B.charAt(i)) n1[c - '0']++; if(c != B.charAt(n - 1- i)) n2[c - '0']++; } return Math.min(Math.max(n1[0], n1[1]), Math.max(n2[0], n2[1]) + 1); } }
n 排列后能整除 m 的个数 (原代码 a 了0.4,这个刚要粘贴时间到了……不知道能不能a)
ps1: 经评论区大佬指正,此代码实测超时,自闭……
ps2: 评论区大佬指出 C++ 可以调用库函数 next_permutation 来做
ps3: 等我想到方法再来更新,如果有大佬 a 了的请不吝赐教,感谢
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); int m = sc.nextInt(); System.out.print(new Solution().solve(n, m)); } } class Solution{ int ans = 0; int m; public int solve(long n, int m) { this.m = m; int len = (n + "").length(); int[] hash = new int[10]; while(n != 0) { hash[(int)(n % 10)]++; n /= 10; } dfs(hash, len, 0, 0); return ans; } void dfs(int[] hash, int len, int index, int temp){ if(index == len - 1) { if(temp % m == 0) ans++; return; } for(int i = 0; i < 10; i++) { if(index == 0 && i == 0) continue; if(hash[i] > 0) { hash[i]--; dfs(hash, len, index + 1, temp * 10 + i); hash[i]++; } } } }
全部评论
(9) 回帖