头像

xuan




离线:11小时前


新鲜事 原文

xuan
1天前
重学英语第1天...(ノ`Д)ノ
图片



xuan
3天前

公式求解:容斥原理

时间复杂度 $O(1)$

思路

题意是给定两个3位密码(类比两把锁)且相差2以内的数可选。

思路是锁1可选数+锁2可选数-锁1锁2公共可选数。

注意点:

计算可选数时一定是要考虑拨盘总数n !!!

1、计算锁1/锁2分别可选数:

  • 情况一:当不受限于拨盘总数n,即n > 5:
    锁1:A-2~A+2;B-2~B+2;C-2~C+2
    锁2:D-2~D+2;E-2~E+2;F-2~F+2
    所以锁1可选数:5 * 5 * 5,锁2可选数:5 * 5 * 5

  • 情况二:当受限拨盘总数n,即n <= 5,给定的3位密码也一定在n以内,此时可选数为1~n
    所以锁1可选数:n * n * n,锁2可选数:n * n * n
    综上,single = 锁1/锁2可选数:Math.min(n,5) * Math.min(n,5) * Math.min(n,5)

2、计算锁1锁2公共可选数

  • 先计算锁1和锁2密码相同位上数的距离d:
    一般情况下两数之间距离为Math.abs(a - b)
    但是在圆环中当a和b的距离太远,则需要取如图a和b反向的那段较小的距离,即n - Math.abs(a - b)
    因此,d = Math.min(Math.abs(a[i] - b[i]),n - Math.abs(a[i] - b[i]))
    QQ截图20210226152824.png

  • 情况一:当不受限于拨盘总数n,即n > 5:
    枚举可得规律:
    当d > 5,公共可选数0;当d <= 5,公共可选数5 - d
    所以每一位上的公共可选数为:Math.max(0,5-d)

  • 情况二:当受限拨盘总数n,即n <= 5:
    所以每一位上的公共可选数为n

综上:锁1锁2公共可选数为:
both = Math.min(Math.max(0,5-d1),n) * Math.min(Math.max(0,5-d2),n) * Math.min(Math.max(0,5-d3),n)

最终答案为single * 2 - both

Java 代码

import java.util.*;
public class Main{
    static int[] a = new int[3];
    static int[] b = new int[3];
    static int n;
    public static int both(){
        int res = 1;
        for(int i = 0;i < 3;i++){
            int d = Math.min(Math.abs(a[i] - b[i]),n - Math.abs(a[i] - b[i]));
            int r = Math.min(n,Math.max(0,5 - d));
            res *= r;
        }
        return res;
    }
    public static int single(){
        int res = 1;
        for(int i = 0;i < 3;i++){
            res *= Math.min(n,5);
        }
        return res;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0;i < 3;i++){
            a[i] = sc.nextInt();
        }
        for(int i = 0;i < 3;i++){
            b[i] = sc.nextInt();
        }
        int res = single() * 2 - both();
        System.out.println(res);
    }
}

暴力枚举

时间复杂度$O(n^3)$

注意点:

所求答案的三位必须与锁1上的三位数对应满足 或 与锁2上的三位数对应满足,
而不是答案的某几位和锁1对应的那几位满足,而其他位和锁2的对应位满足!

Java 代码

import java.util.*;
public class Main{
    static int[] a = new int[3];
    static int[] b = new int[3];
    static int n;
    static int cnt;
    //检查i 与 c数组的第u位数是否距离在2以内
    public static boolean check(int[] c,int i,int u){
        int d = Math.min(Math.abs(i - c[u]),n - Math.abs(i - c[u]));
        return d <= 2;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0;i < 3;i++){
            a[i] = sc.nextInt();
        }
        for(int i = 0;i < 3;i++){
            b[i] = sc.nextInt();
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                for(int k = 1;k <= n;k++){
                    if(check(a,i,0) && check(a,j,1) && check(a,k,2) || 
                    check(b,i,0) && check(b,j,1) && check(b,k,2)){
                        cnt++;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}


活动打卡代码 AcWing 425. 明明的随机数

xuan
18天前
import java.util.*;
public class Main{
    static List<Integer> list = new ArrayList<>();
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0;i < n;i++){
            list.add(sc.nextInt());
        }
        list = new ArrayList(new HashSet(list));
        Collections.sort(list);
        System.out.println(list.size());
        for(Integer i : list){
            System.out.print(i + " ");
        }
    }
}


活动打卡代码 AcWing 1613. 数独简单版

xuan
21天前
import java.util.*;
public class Main{
    static int N = 10;
    static char[][] g = new char[N][N];
    static boolean[][] row = new boolean[N][N];
    static boolean[][] col = new boolean[N][N];
    static boolean[][][] cell = new boolean[3][3][N];
    public static boolean dfs(int x,int y){
        if(y >= 9){
            x++;
            y = 0;
        }
        if(x > 8){
            for(int i = 0;i < 9;i++){
                for(int j = 0;j < 9;j++){
                    System.out.print(g[i][j]);
                }
                System.out.println();
            }
            return true; 
        }
        if(g[x][y] != '.'){
            return dfs(x,y + 1);
        }
        for(int i = 1;i <= 9;i++){
            if(!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]){
                g[x][y] = (char)(i + '0');
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
                if(dfs(x,y + 1)) return true;
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
                g[x][y] = '.';
            }
        }
        return false;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        for(int i = 0;i < 9;i++){
            String s = sc.next();
            for(int j = 0;j < 9;j++){
                g[i][j] = s.charAt(j);
                if(g[i][j] != '.'){
                    row[i][g[i][j] - '0'] = true;
                    col[j][g[i][j] - '0'] = true;
                    cell[i / 3][j / 3][g[i][j] - '0'] = true;
                }
            }
        }
        dfs(0,0);
    }
}


活动打卡代码 AcWing 417. 不高兴的津津

xuan
21天前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] m = new int[7];
        int k = 0;
        for(int i = 0;i < 7;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            m[i] = a + b;
            if(m[i] > m[k]){
                k = i;
            }
        }
        if(m[k] > 8){
            System.out.println(k + 1);
        }else{
            System.out.println(0);
        }
    }
}


活动打卡代码 AcWing 421. 陶陶摘苹果

xuan
21天前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] a = new int[10];
        for(int i = 0;i < 10;i++){
            a[i] = sc.nextInt();
        }
        int cnt = 0;
        int n = sc.nextInt() + 30;
         for(int i = 0;i < 10;i++){
            if(n >= a[i]){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}


活动打卡代码 AcWing 428. 数列

xuan
21天前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        String s = "";
        while(n > 0){
            s = n % 2 + s;
            n /= 2;
        }
        int res = 0;
        for(int i = 0;i < s.length();i++){
            res = res * k + Integer.parseInt(s.charAt(i) + "");
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 433. ISBN号码

xuan
23天前
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        String s = str.replace("-","");
        int res = 0;
        for(int i = 0;i < 9;i++){
            res = (res + (s.charAt(i) - '0') * (i + 1)) % 11;
        }
        if(res == s.charAt(9) - '0' || (res == 10 && s.charAt(9) == 'X')){
            System.out.println("Right");
        }else{
            System.out.println(str.substring(0,12) + (res == 10 ? "X" : res));
        }
    }
}


活动打卡代码 AcWing 1230. K倍区间

xuan
25天前

利用公式(a - b) % k == 0 => a % k == b % k

(int)(long % int)默认返回int需要强转

import java.util.*;
public class Main{
    static int N = 100010;
    static long[] a = new long[N];
    static int[] cnt = new int[N];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        for(int i = 1;i <= n;i++){
            a[i] = sc.nextInt();
            a[i] += a[i - 1];
        }
        cnt[0] = 1;
        long res = 0;
        for(int i = 1;i <= n;i++){
            res += cnt[(int)(a[i] % k)];
            cnt[(int)(a[i] % k)]++;
        }
        System.out.println(res);
    }
}



xuan
25天前
import java.util.*;
public class Main{
    static int N = 210;
    static char[][] g = new char[N][N];
    static int[][] d = new int[N][N];
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    public static int bfs(int x1,int y1,int x2,int y2,int n,int m){
        d[x1][y1] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x1,y1});
        while(!q.isEmpty()){
            int[] t = q.poll();
            for(int i = 0;i < 4;i++){
                int a = t[0] + dx[i];
                int b = t[1] + dy[i];
                if(a >= 0 && a < n && b >= 0 && b < m && d[a][b] == -1 && g[a][b] != '#'){
                    d[a][b] = d[t[0]][t[1]] + 1;
                    if(a == x2 && b == y2){
                        return d[a][b];
                    }
                    q.add(new int[]{a,b});
                }
            }
        }
        return -1;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int x1 = 0,y1 = 0,x2 = 0,y2 = 0;
            for(int i = 0;i < n;i++){
                String s = sc.next();
                for(int j = 0;j < m;j++){
                    d[i][j] = -1;
                    g[i][j] = s.charAt(j);
                    if(g[i][j] == 'S'){
                        x1 = i;
                        y1 = j;
                    }
                    if(g[i][j] == 'E'){
                        x2 = i;
                        y2 = j;
                    }
                }
            }
            int r = bfs(x1,y1,x2,y2,n,m);
            System.out.println(r == -1 ? "oop!" : r);
        }
    }
}