头像

ocean6_6

秘密组织




离线:2天前


最近来访(9)
用户头像
wlun
用户头像
GC_3
用户头像
Sundae
用户头像
no_one
用户头像
枫叶AC
用户头像
18553174127




活动打卡代码 AcWing 790. 数的三次方根

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        double n = new Scanner(System.in).nextDouble();

        double l = -10000, r = 10000;
        while(r - l > 1e-8){
            double mid = (l + r) / 2;
            if(mid * mid * mid <= n) l = mid;   //mid比n小,需要放大mid
            else r = mid;
        }

        System.out.println(String.format("%f", r));
    }
}


活动打卡代码 AcWing 789. 数的范围

import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] param = input.readLine().split(" ");
        int n = Integer.parseInt(param[0]), q = Integer.parseInt(param[1]);
        int[] arr = new int[n + 2];

        param = input.readLine().split(" ");
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(param[i]);

        while(q-- > 0){
            int k = Integer.parseInt(input.readLine());

            int l1 = 0, r1 = n - 1;
            while(l1 < r1){
                int mid = l1 + r1 >> 1;
                if(k <= arr[mid]) r1 = mid;
                else l1 = mid + 1;
            }

            if(arr[l1] != k) {
                output.write("-1 -1\n");
                continue;
            }

            int l2 = r1, r2 = n - 1;
            while(l2 < r2){
                int mid = l2 + r2 + 1>> 1;
                if(k >= arr[mid]) l2 = mid;
                else r2 = mid - 1;
            }

            output.write(l1 + " " + l2 + "\n");
        }

        output.flush();
    }
}


活动打卡代码 AcWing 116. 飞行员兄弟

1. 暴搜

1.1 DFS解法

import java.io.*;
import java.util.*;
public class Main{
    static char[][] g = new char[5][5];
    //ans存放最终比较完最小操作后的操作路径, tmp存放每轮叶结点的操作路径
    static LinkedList<int[]> ans = new LinkedList<>(), tmp = new LinkedList<>();

    public static void main(String[] args) throws Exception{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i < 4; i++)
            g[i] = input.readLine().toCharArray();

        dfs(0, 0);

        output.write(ans.size() + "\n");
        for(int[] i : ans)
            output.write((i[0] + 1) + " " + (i[1] + 1) + "\n");

        output.flush();
    }

    //暴搜所有开关的操作,每个开关都有 操作 和 不操作 两种选择
    public static void dfs(int x, int y) throws Exception {
        //到达叶结点,当前已存有一组操作的路径
        if(x == 3 && y == 4){
            //遍历所有开关,若存在关闭(+),则当前这组操作路径不符合
            int flag = 0;
            for(int i = 0; i < 4; i++) 
                for(int j = 0; j < 4; j++)
                    if(g[i][j] == '+'){
                        flag = 1;
                        break;
                    }

            if(flag == 0)
                if(ans.isEmpty() || ans.size() > tmp.size())
                    for(int[] i : tmp)
                        ans.add(i);

            return;
        }

        //y到边界时,换到下一行
        if(y == 4) {
            x++;
            y = 0;
        }

        //1. 操作当前(x, y)的开关
        turn_all(x, y);
        tmp.add(new int[]{x, y});       //保存当前操作格子的路径
        dfs(x, y + 1);                  //进入下一个格子
        turn_all(x, y);                 //回溯时还原,便于下一次操作
        tmp.removeLast();

        //2. 不操作当前(x, y)的开关
        dfs(x, y + 1);                  //进入下一个格子
    }

    //将当前格子(x, y)翻转
    public static void turn_one(int x, int y) {
        if(g[x][y] == '-') g[x][y] = '+';
        else g[x][y] = '-';
    }

    //将当前格子(x, y)所在的行列翻转
    public static void turn_all(int x, int y){
        for(int i = 0; i < 4; i++){
            turn_one(x, i);
            turn_one(i, y);
        }

        //(x, y)格子翻了两次导致结果不变, 需要再翻一次
        turn_one(x, y);
    }
}

1.2 循环解法

import java.io.*;
import java.util.*;
public class Main{
    static char[][] g = new char[5][5], backup = new char[5][5];

    public static void main(String[] args) throws Exception{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        //ans存放最终比较完最小操作后的操作路径
        LinkedList<int[]> ans = new LinkedList<>();

        for(int i = 0; i < 4; i++)
            g[i] = input.readLine().toCharArray();

        /*
        每个开关都有 操作 和 不操作 两种选择,总共有16个开关,因此共有2^16种选择的情况;
        */

        //暴力枚举所有选择的情况
        for(int op = 0; op < 1 << 16; op++){
            //tmp存放每种情况的操作路径
            LinkedList<int[]> tmp = new LinkedList<>();

            //备份原棋盘,因为这又不是最终方案,要把所有情况都试一遍,求最少的情况
            for(int i = 0; i < 4; i++)
                backup[i] = new String(g[i]).toCharArray();

            //枚举当前棋盘
            for(int i = 0; i < 4; i++)
                for(int j = 0; j < 4; j++)
                    //若 当前棋盘的(x, y)格子在当前方案 中为1,就将当前格子(x, y)按一下
                    if((op >> get(i, j) & 1) == 1){
                        tmp.add(new int[]{i, j});
                        turn_all(i, j);
                    }

            //操作完棋盘后,判断开关是否全开
            int flag = 0;
            for(int i = 0; i < 4; i++)
                for(int j = 0; j < 4; j++)
                    if(g[i][j] == '+'){
                        flag = 1;
                        break;
                    }

            if(flag == 0)
                if(ans.isEmpty() || ans.size() > tmp.size())
                    for(int[] i : tmp)
                        ans.add(i);

            //还原棋盘,给下一个情况操作
            for(int i = 0; i < 4; i++)
                g[i] = new String(backup[i]).toCharArray();
        }

        output.write(ans.size() + "\n");
        for(int[] i : ans)
            output.write((i[0] + 1) + " " + (i[1] + 1) + "\n");

        output.flush();
    }

    //将当前格子(x, y)翻转
    public static void turn_one(int x, int y) {
        if(g[x][y] == '-') g[x][y] = '+';
        else g[x][y] = '-';
    }

    //将当前格子(x, y)所在的行列翻转
    public static void turn_all(int x, int y){
        for(int i = 0; i < 4; i++){
            turn_one(x, i);
            turn_one(i, y);
        }

        //(x, y)格子翻了两次导致结果不变, 需要再翻一次
        turn_one(x, y);
    }

    //将坐标转换成一维坐标
    public static int get(int x, int y){
        return x * 4 + y;
    }
}

2. 位运算



活动打卡代码 AcWing 1208. 翻硬币

翻硬币.png

首次AC代码——JAVA

import java.io.*;
public class Main{
    static char a[], b[];

    public static void main(String[] args) throws Exception{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        //from a to b
        a = input.readLine().toCharArray();
        b = input.readLine().toCharArray();
        int length = a.length;

        int res = 0;
        for(int i = 0; i < length - 1; i ++){
            //若源串的硬币与目标串的硬币不同,则当前开关需要翻转
            if(a[i] != b[i]){
                turn(i);
                turn(i + 1);
                res++;
            }
        }

        System.out.println(res);
    }

    public static void turn(int x){
        if(a[x] == '*') a[x] = 'o';
        else a[x] = '*';
    }
}





活动打卡代码 AcWing 717. 简单斐波那契

import java.io.*;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();

        int a = 0, b = 1;

        System.out.print(a + " ");
        for(int i = 1; i < n; i++){
            System.out.print(b + " ");
            b = a + b;
            a = b - a;
        }
    }
}


活动打卡代码 AcWing 1209. 带分数

首次AC代码——JAVA

1. 全排列暴力枚举

import java.io.*;
import java.util.Scanner;
public class Main{
    static int target, cnt, way[], vst[];

    public static void main(String[] args) {
        target = new Scanner(System.in).nextInt();
        way = new int[10];
        vst = new int[10];

        dfs(1);

        System.out.println(cnt);
    }

    public static void dfs(int x){
        if(x >= 10) {
            //将每次的全排列分成3段, 判断是否满足a + b / c = N
            for(int i = 1; i < 8; i++){
                for(int j = i + 1; j < 9; j++){
                    int a = calculate(0, i), b = calculate(i + 1, j), c = calculate(j + 1, 9);
                    //将 a + b / c = N 等式两边同时乘c, a * c + b = N * c, 两式等价
                    if((a * c + b) == c * target) cnt++;
                }
            }

            return;
        }

        //1~9的全排列 (保证了1~9每个数只出现一次)
        for(int i = 1; i < 10; i++){
            if(vst[i] == 0) {
                way[x] = i;
                vst[i] = 1;
                dfs(x + 1);
                vst[i] = 0;
            }
        }
    }

    //计算全排列中划分出来的每一段的值
    public static int calculate(int l, int r){
        int tmp = 0;
        for(int i = l; i <= r; i++)
            tmp = tmp * 10 + way[i];

        return tmp;
    }
}

2. dfs嵌套+剪枝

。。。




ocean6_6
13天前
import java.io.*;
public class Main{
    static int n, m, arr[];
    static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        String[] param = input.readLine().split(" ");
        n = Integer.parseInt(param[0]); m = Integer.parseInt(param[1]);
        arr = new int[n + 2];

        dfs(1, 1);

        output.flush();
    }

    public static void dfs(int x, int start) throws Exception {
        //当前x层,即已选x-1个数; 当前从start开始选到n,共有n - start + 1个数
        //因此, 若 已选的数 + 剩余可选的数 < 共要选m个数, 则无解, 从而可以剪枝
        if(x + n - start < m) return;

        if(x > m){
            for(int i = 1; i <= m; i++)
                output.write(arr[i] + " ");
            output.write("\n");
            return;
        }

        for(int i = start; i <= n; i++){
            arr[x] = i;
            dfs(x + 1, i + 1);  //进入下一层, 当前层+1作为下一侧的开始值
        }
    }
}



ocean6_6
15天前
import java.io.*;
public class Main{
    static int n, arr[],vst[];
    static BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(input.readLine());
        arr = new int[n + 2];
        vst = new int[n + 2];

        dfs(1); //从第一层开始

        output.flush();
    }

    public static void dfs(int x) throws Exception{
        if(x > n){
            for(int i = 1; i <= n; i++) output.write(arr[i] + " ");
            output.write("\n");
            return;
        }

        for(int i = 1; i <= n; i++){    //每层遍历n个数
            if(vst[i] == 0){
                arr[x] = i;
                vst[i] = 1;
                dfs(x + 1);
                vst[i] = 0;
            }
        }
    }
}