import java.io.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception{
char[] a = read.readLine().toCharArray(), b = read.readLine().toCharArray();
int n = a.length;
int ans = 0;
for(int i = 0; i < n; i++){
if(a[i] != b[i]){
ans++;
a[i] = b[i];
a[i+1] = a[i+1] == '*' ? 'o': '*';
}
}
System.out.println(ans);
}
}
import java.io.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args ) throws Exception{
String[] ss = read.readLine().split(" ");
int n = Integer.valueOf(ss[0]), k = Integer.valueOf(ss[1]);
int[][] a = new int[n][2];
for(int i = 0; i < n; i++){
ss = read.readLine().split(" ");
int h = Integer.valueOf(ss[0]), w = Integer.valueOf(ss[1]);
a[i][0] = h; a[i][1] = w;
}
int l = 1, r = 100000;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(a, mid, k)) l = mid;
else r = mid - 1;
}
System.out.println(l);
}
public static boolean check(int[][] a, int size, int k){
int ans = 0;
for(int i = 0; i < a.length; i++){
int h = a[i][0], w = a[i][1];
for(int row = 0; row + size <= h; row += size){
for(int col = 0; col + size <= w; col += size){
ans++;
}
}
}
return ans >= k;
}
}
本题使用一个常用技巧: 前后缀分解
该技巧的常用套路如下：
1. 求前缀数组
2. 求后缀数组
3. 枚举前后缀数组的分界点
对于本题，可以分解为求连续数组前缀和的最大值和， 求连续数组后缀和的最大值
可以定义如下：
dp1[i]: 从1~i从前往后枚举，以数字a[i]结尾的，连续和的最大值
dp2[i]: 从n~i从后往前枚举，以数字a[i]结尾的，连续和的最大值
maxLeft[i]: 从1~i从前往后枚举，前1~i个数字连续和的最大值
maxRight[i]: 从n~i从后往前枚举，后n~i个数字连续和的最大值
状态计算如下：
dp1[i] = max( dp1[i - 1] + a[i], a[i])
maxLeft[i] = max(maxLeft[i - 1], dp1[i])
dp2[i] = max( dp2[i + 1] + a[i], a[i])
maxRight[i] = max(maxRight[i + 1], dp2[i])
最后枚举前后缀数组的分界点
总体时间复杂度: O(N)
import java.io.*;
import java.util.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static int N = 50010, INF = 10010;
static int[] a = new int[N], dp1 = new int[N], dp2 = new int[N], maxLeft = new int[N], maxRight = new int[N];
public static void main(String[] args) throws Exception{
int t = Integer.valueOf(read.readLine());
while(t -- > 0){
Arrays.fill(dp1, -INF); Arrays.fill(dp2, -INF);
Arrays.fill(maxLeft, -INF); Arrays.fill(maxRight, -INF);
int n = Integer.valueOf(read.readLine());
String[] ss = read.readLine().split(" ");
for(int i = 1; i <= n; i++) a[i] = Integer.valueOf(ss[i - 1]); //读取输入数组到a
for(int i = 1; i <= n; i++){ //处理前缀
dp1[i] = Math.max(dp1[i - 1] + a[i], a[i]);
maxLeft[i] = Math.max(maxLeft[i - 1], dp1[i]);
}
for(int i = n; i >= 1; i--) { //处理后缀
dp2[i] = Math.max(dp2[i + 1] + a[i], a[i]);
maxRight[i] = Math.max(maxRight[i + 1], dp2[i]);
}
int out = -INF;
//枚举前后缀的分界点
for(int i = 1; i <= n; i++){
out = Math.max(maxLeft[i - 1] + maxRight[i], out);
}
System.out.println(out);
}
}
}
欧拉函数： 一个数n， 从1~n-1中与n互质的数的个数（互质：最大公约数为1）
思路： 对n进行质因数分解 n = p1^k1 * p2^k2 * … * pn^kn
答案： n * (1 - 1/p1) * (1 - 1/p2) * … * (1 - 1/pn)
等价： n * (p1 - 1)/p1 * (p2 - 1)/p2 * … * (pn - 1)/pn
一个数n的约数的个数 = (k1 + 1) * (k2 + 1) * … * (kn + 1)
一个数n的约数的和 = (p1^0 + p1^1 + … + p1^k1) * (p2^0 + p2^1 + … + p2^k2) * (pn^0 + pn^1 + … + pn^kn)
import java.io.*;
import java.util.*;
class Main {
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception {
int t = Integer.valueOf(read.readLine());
while (t -- > 0){
int a = Integer.valueOf(read.readLine());
log.write(getEula(a) + "\n");
}
log.flush();
}
public static long getEula(int a){
int t = a;
Map<Integer, Integer> map = new HashMap();
for(int i = 2; i <= a / i; i++){
if(a % i == 0){
int cnt = 0;
while (a % i == 0){
cnt++;
a /= i;
}
map.put(i, map.getOrDefault(i, 0) + cnt);
}
}
if(a > 1) map.put(a, map.getOrDefault(a, 0) + 1);
long eula = t;
for(Integer key: map.keySet()){
eula = eula * (key - 1) / key;
}
return eula;
}
}
活动打卡代码
AcWing 125. 耍杂技的牛
按照w + s的和从小到大进行排序，求最大值即可，用反证法证明
import java.io.*;
import java.util.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args)throws Exception{
int n = Integer.valueOf(read.readLine());
int[][] e = new int[n][2];
for(int i = 0; i < n; i++){
String[] ss = read.readLine().split(" ");
int w = Integer.valueOf(ss[0]), s = Integer.valueOf(ss[1]);
e[i][0] = w; e[i][1] = s;
}
Arrays.sort(e, (o1, o2) -> o1[0] + o1[1] - o2[0] - o2[1]);
long sum = 0, ans = Long.MIN_VALUE;
for(int i = 0; i < n; i++){
ans = Math.max(ans, sum - e[i][1]);
sum += e[i][0];
}
System.out.println(ans);
}
}
活动打卡代码
AcWing 104. 货仓选址
import java.io.*;
import java.util.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception{
int n = Integer.valueOf(read.readLine());
int[] a = new int[n];
String[] ss = read.readLine().split(" ");
for(int i = 0; i < n; i++) a[i] = Integer.valueOf(ss[i]);
Arrays.sort(a);
int ans = 0;
for(int i = 0; i < n; i++){
ans += Math.abs(a[n / 2] - a[i]);
}
System.out.println(ans);
}
}
活动打卡代码
AcWing 913. 排队打水
假设有n个人，每个人花费的时间为：
x1 x2 x3 … xn
那么，总共的花费时间为：
x1(n-1) + x2(n-2) + x3*(n-3) + … + xn-1 （公式1）
PS： 后面的人要等前面的人完成才能开始，最后一个人就要等前面所有的人完成才能开始
观察发现，越排在前面的人，花费时间所占的权重越大
算法思路：
升序排序所有的人，按公式1累加即可得到答案
import java.io.*;
import java.util.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception{
int n = Integer.valueOf(read.readLine());
int[] a = new int[n];
String[] ss = read.readLine().split(" ");
for(int i = 0; i < n; i++) a[i] = Integer.valueOf(ss[i]);
Arrays.sort(a);
long ans = 0;
for(int i = 0; i < n - 1; i++){
ans += a[i] * (n - i - 1);
}
System.out.println(ans);
}
}
假设有n个人，每个人花费的时间为：
x1 x2 x3 … xn
那么，总共的花费时间为：
x1(n-1) + x2(n-2) + x3*(n-3) + … + xn-1 （公式1）
PS： 后面的人要等前面的人完成才能开始，最后一个人就要等前面所有的人完成才能开始
观察发现，越排在前面的人，花费时间所占的权重越大
算法思路：
升序排序所有的人，按公式1累加即可得到答案
import java.io.*;
import java.util.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception{
int n = Integer.valueOf(read.readLine());
int[] a = new int[n];
String[] ss = read.readLine().split(" ");
for(int i = 0; i < n; i++) a[i] = Integer.valueOf(ss[i]);
Arrays.sort(a);
long ans = 0;
for(int i = 0; i < n - 1; i++){
ans += a[i] * (n - i - 1);
}
System.out.println(ans);
}
}
import java.io.*;
import java.util.Arrays;
class Main {
static int N = 20, M = 1 << N;
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static int[][] dp = new int[N][M];
static int[][] w = new int[N][N];
public static void main(String[] args) throws Exception {
int n = Integer.valueOf(read.readLine());
for(int i = 0; i < n; i++){
String[] ss = read.readLine().split(" ");
for(int j = 0; j < n; j++){
w[i][j] = Integer.valueOf(ss[j]);
}
}
for(int i = 0; i < n; i++) Arrays.fill(dp[i], 0x3f3f3f3f);
dp[0][1] = 0;
for(int j = 0; j < 1 << n; j++){
for(int i = 0; i < n; i++){
if((j & (1 << i)) == 0) continue;
for(int k = 0; k < n; k++){
if((j & (1 << k)) == 0 || k == i) continue;
dp[i][j] = Math.min(dp[i][j], dp[k][j - (1 << i)] + w[k][i]);
}
}
}
System.out.println(dp[n - 1][(1 << n) - 1]);
}
}
完全背包问题
/**
* 完全背包问题， 数字从1~n，可以选0~k次
* dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]] + dp[i - 1][j - 2 * a[i]] + ... + dp[i - 1][j - k * a[i]]
* dp[i][j - a[i]] = dp[i - 1][j - a[i]] + dp[i - 1][j - 2 * a[i]] + ... + dp[i - 1][j - k * a[i]]
* dp[i][j] - dp[i][j - a[i]] = dp[i - 1][j]
* 相减得 dp[i][j] = dp[i - 1][j] + dp[i][j - a[i]]
* dp[j] = dp[j] + dp[j - a[i]]
*/
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), mod = (int) 1e9 + 7;
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
dp[j] = (dp[j] + dp[j - i]) % mod;
}
}
System.out.println(dp[n]);
}
}
计数dp
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), mod = (int) 1e9 + 7;
int[][] dp = new int[n + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = (dp[i - 1][j - 1] +dp[i - j][j]) % mod;
}
}
int ans = 0;
for(int i = 1; i <= n; i++) ans = (ans + dp[n][i]) % mod;
System.out.println(ans);
}
}
