黑白切换 (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) 回帖