头像

猪八戒




离线:8小时前


最近来访(11)
用户头像
281
用户头像
有机物
用户头像
垫底抽風
用户头像
诺诺
用户头像
麦兜
用户头像
celaodiu
用户头像
辛钦大数定律
用户头像
无痕_45
用户头像
风华_2

活动打卡代码 AcWing 1227. 分巧克力

猪八戒
18小时前

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

/*
 * h(i)/x*w(i)/x等于个数
 */
public class Main {
    static int N = 100010;
    static int[] h = new int[N];
    static int[] w = new int[N];
    static int n, k;

    private static boolean check(int x) {
        int res=0;
        for (int i = 0; i < n; i++) {
            res += (h[i] / x) * (w[i] / x);
        }
        if (res >= k)
            return true;
        return false;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);
        for (int i = 0; i < n; i++) {
            s = br.readLine().split(" ");
            h[i] = Integer.parseInt(s[0]);
            w[i] = Integer.parseInt(s[1]);
        }
        // 操作
        int l = 0, r = 100000;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        System.out.println(l);
    }
}


活动打卡代码 AcWing 1221. 四平方和


import java.util.Scanner;

public class Main {
    static int N=5000010;
    static int h[]=new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        //打表c和d
        for(int c=0;c*c<=n;c++) {
            for(int d=c;c*c+d*d<=n;d++) {
                if(h[c*c+d*d]==0)
                    h[c*c+d*d]=c+1;//防止有0
            }
        }
        //操作
        for(int a=0;a*a<=n;a++) {
            for(int b=a;a*a+b*b<=n;b++) {
                int t=h[n-a*a-b*b];
                if(t!=0) {
                    int c=t-1;
                    int d=(int)Math.sqrt(n-a*a-b*b-c*c);
                    System.out.println(a+" "+b+" "+c+" "+d);
                    return;
                }
            }
        }
    }
}





import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n;
    static int N=100010;
    static int a[]=new int[N];
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    private static boolean check(int e) {
        for(int i=0;i<n;i++) {
            e=e*2-a[i];
            //如果不写会爆掉 极端情况数特别大long也不行
            if(e>100000) return true;
            if(e<0) return false;
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        n=Integer.parseInt(br.readLine());
        String[] s=br.readLine().split(" ");
        for(int i=0;i<n;i++) a[i]=Integer.parseInt(s[i]);
        int l=0,r=100000;
        while(l<r) {
            int mid=l+r>>1;
            //mid如果满足所有大于mid的一定满足,而题目找最小
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        System.out.println(r);
    }

}


活动打卡代码 AcWing 796. 子矩阵的和



import java.util.Scanner;

public class Main {
    static int N=1010;
    static long a[][]=new long[N][N];
    static long s[][]=new long[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                a[i][j]=sc.nextLong();
                s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
            }
        }
        int x1,y1,x2,y2;
        for(int i=0;i<q;i++) {
            x1=sc.nextInt();
            y1=sc.nextInt();
            x2=sc.nextInt();
            y2=sc.nextInt();
            System.out.println(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
        }


    }
}


活动打卡代码 AcWing 795. 前缀和



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N=100010;
    static long a[]=new long[N];
    static long s[]=new long[N];
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        String []st=br.readLine().split(" ");
        int n=Integer.parseInt(st[0]);
        int m=Integer.parseInt(st[1]);
        st=br.readLine().split(" ");
        for(int i=1;i<=n;i++) {
            a[i]=Integer.parseInt(st[i-1]);
            s[i]=s[i-1]+a[i];
        }
        for(int i=0;i<m;i++) {
            st=br.readLine().split(" ");
            int l=Integer.parseInt(st[0]);
            int r=Integer.parseInt(st[1]);
            System.out.println(s[r]-s[l-1]);
        }
    }
}


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



import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double n=sc.nextDouble();
        double l=-10000,r=100000;
        //保留6位多两位比较好
        while(r-l>=1e-8) {
            double mid=(l+r)/2;
            if(mid*mid*mid>=n) r=mid;
            else l=mid;
        }
        System.out.printf("%.6f",r);
    }
}


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



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int a[]=new int[100010];
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s=br.readLine().split(" ");
        int n=Integer.parseInt(s[0]);
        int q=Integer.parseInt(s[1]);
        s=br.readLine().split(" ");
        for(int i=0;i<n;i++) a[i]=Integer.parseInt(s[i]);
        for(int i=0;i<q;i++) {
            int x=Integer.parseInt(br.readLine());
            int l=0,r=n-1;
            while(l<r) {
                int mid=l+r>>1;
                if(a[mid]>=x) r=mid;//说明mid在x右边
                else l=mid+1;
            }
            //找到左端点
            if(a[r]==x) {
                System.out.print(r+" ");
                r=n-1;
                while(l<r) {
                    int mid=l+r+1>>1;
                    if(a[mid]<=x) l=mid;
                    else r=mid-1;
                }
                System.out.print(l+" ");
                System.out.println();
            }
            else System.out.println("-1 -1");
        }
    }

}


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



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int N=5;
    static char g[][]=new char[N][N];
    static char backup[][]=new char[N][N];
    static ArrayList<PII> res=new ArrayList<PII>();//存答案

    private static int get(int x, int y) {
        return 4*x+y;
    }
    private static void turn_all(int x, int y) {
        for(int i=0;i<4;i++) {
            turn_one(x,i);
            turn_one(i,y);
        }
        turn_one(x,y);
    }
    private static void turn_one(int x, int y) {
        if(g[x][y]=='+') g[x][y]='-';
        else g[x][y]='+';

    }
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        //读入
        for(int i=0;i<4;i++) g[i]=br.readLine().toCharArray();
        for(int op=0;op<1<<16;op++) {
            ArrayList<PII> temp=new ArrayList<PII>();
            //备份g
            for(int i=0;i<4;i++) backup[i]=Arrays.copyOf(g[i], 4);
            //操作
            for(int i=0;i<4;i++) {
                for(int j=0;j<4;j++) {
                    if((op>>get(i,j)&1)!=0) {
                        PII pii = new PII();
                        pii.setX(i);
                        pii.setY(j);
                        temp.add(pii);
                        turn_all(i,j);
                    }
                }
            }

            //判断是否全关
            boolean has_close=false;
            for(int i=0;i<4;i++) {
                for(int j=0;j<4;j++) {
                    if(g[i][j]=='+') {
                        has_close=true;

                    }
                }
            }

            if(!has_close) {
                if(res.isEmpty()||res.size()>temp.size()) {
                    //res.clear();
                    res=temp; 
                }
            }
            //还原
            for(int i=0;i<4;i++) g[i]=Arrays.copyOf(backup[i], 4);
        }
        //输出
        System.out.println(res.size());


        for (PII p : res)
            System.out.println(p.x + 1 + " " + (p.y + 1));
    }


}
class PII {
    int x;
    int y;
    public PII() {}
    public PII(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }

}


活动打卡代码 AcWing 95. 费解的开关

 **

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 6;
    static int[] dx ={-1,0,1,0,0};
    static int[] dy ={0,1,0,-1,0};//上下左右中  偏移量
    static char[][] g = new char[N][N];
    static char[][] backup = new char[N][N];

    // 这个操作是把(x, y)以及上下左右的灯都变成相反的颜色
    static void turn (int x, int y)
    {
        for (int i = 0; i < 5; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];

            //如果在边界外边,直接忽略即可
            if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
            //等价于 g[a][b] = '0' + ('1'  - g[a][b])
            g[a][b] ^= 1;   //异或,不同的时候就变成相反的数
            //【‘0’ ASCII值48 ‘1’ 49】


        }

    }

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

        while(n-- >0) {
            // 按行输入,把每一行当成一个字符串 然后转换成字符数组
            for(int i=0;i<5;i++) g[i] = in.next().toCharArray();

            int res = 7;

            //第一行覆盖所有状态
            for(int op=0;op<32;op++){
            // 我在对这种情况操作的时候,得先备用一下
            // 把原始数组备份一下,然后操作g,操作完了还原,然后再操作
                for(int j=0;j<5;++j)
                {
                    backup[j]=Arrays.copyOf(g[j], 5);
                }


                int step = 0;

                //计算翻转操作的step
                for (int i = 0; i < 5; ++i)
                {
                    if ((op>>i & 1) == 1)
                    {
                        step++;
                        turn(0,i);
                    }
                }

                //然后通过第一行按完之后的状态,按234行  递推
                for (int i = 0; i < 4; ++i)
                    for (int j = 0; j < 5; ++j)
                    {
                        if (g[i][j] == '0')
                        {
                            step++;
                            // 如果这个位置是灭的,就按下一行对应的位置
                            turn(i+1,j);
                        }
                    }

                boolean dark  = false;

                for (int j = 0; j < 5; j ++ )
                        if (g[4][j] == '0')
                        {
                            dark = true;
                            break;
                        }

                // 判断可行性 可行的话 是否更优
                if (!dark) res = Math.min(res, step);

                for(int j=0;j<5;++j)
                {
                    g[j]=Arrays.copyOf(backup[j], 5);
                }

             }

            if(res > 6) res = -1;
            System.out.println(res);    
        }

    }
}


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



import java.util.Scanner;

public class Main {
    static char start[]=new char[100];
    static char end[]=new char[100];
    static int ans=0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        start=sc.next().toCharArray();
        end=sc.next().toCharArray();        
        for(int i=0;i<start.length;i++) {
            if(start[i]!=end[i]) {
                ans++;
                turn(i);
                turn(i+1);
            }
        }
        System.out.println(ans);
    }
    private static void turn(int i) {
        if(start[i]=='*') start[i]='o';
        else start[i]='*';
    }
}