Cara menggunakan tamak dan penghitungan di Jawa-javaTutorial-php.cn

Kemahiran ujian bertulis: Belajar meneka mata pengetahuan mengikut skop data

Secara amnya had masa 1S, kerumitan masa boleh mencapai kira-kira 1E8 (Python dan Java akan menjadi kurang, jadi anda disyorkan supaya anda gunakan C/C ++ untuk melakukannya.

O(n^3) tr>

n 范围 20 以内：	O(n*2^n)	状压搜索 /dfs 暴搜
n 范围 200 以内：	O(n^3)	三维 dp
n 范围 3000 以内：	O(n^2)	二维 dp 背包枚举二维前缀和等
n 范围 1e5 以内：	O(n√n)	暴力求因子等
n 范围 1e6 以内：	O(nlogn)	二分答案使用各种 stl 并查集欧拉筛等
n 范围 1e7 以内：	O(n)	双指针线性 dp 差分 / 前缀和
n 范围 1e14 以内：	O(√n)	求约数和约数个数

n Julat 20 Dalam:

O(n*2^n)

Carian tekanan /dfs Search

n Julat Dalam 200:

dp tiga dimensi

n Julat Dalam 3000:

O(n^2)

Penghitungan dua dimensi dp Backpack jumlah awalan dua dimensi, dsb.

n Julat 1e5 atau kurang:

O(n√n)

Pencarian ganas untuk faktor, dsb.

n Julat 1e6 🎜>

Jawapan binari menggunakan pelbagai stl dan set ayak Euler, dsb.

n dalam julat 1e7:

n julat 1e14 atau kurang:

O(√n)

Cari nombor pembahagi dan pembahagi

Takus:

Takut bermaksud membuat pilihan terbaik pada setiap langkah. Masalah-masalah yang diselesaikan secara umumnya mempunyai ciri-ciri berikut: optimum tempatan boleh membawa kepada optimum global.

Sila ambil perhatian bahawa ketamakan bukanlah ubat penawar!

Ada n item. Setiap item mempunyai nilai v[i], dan berat w[i].

Sekarang ambil barang yang jumlah beratnya tidak melebihi m. Berapakah nilai maksimum barang yang diambil? (Masalah Knapsack)

Strategi 1: Susun mengikut tertib nilai menurun, mengambil nilai tertinggi setiap kali.
Strategi 2: Susun mengikut tertib berat menaik, mengambil berat paling ringan setiap kali.
Strategi 3: Isih dalam susunan menurun mengikut nilai/berat (iaitu nilai unit), dan ambil yang mempunyai nilai unit tertinggi setiap kali.

Penghitungan:

1. Penghitungan naif

Seperti namanya, gunakan gelung for untuk menghitung semua situasi.

2. Penghitungan status

Gunakan sifat n-asas untuk menghitung.

Senario yang sesuai: Terdapat n item secara keseluruhan, setiap item mempunyai m keadaan, menyenaraikan semua keadaan semua item, kerumitannya ialah O(m^n).

Cara menulis penghitungan keadaan binari:

Masalah klasik: diberi n nombor a1, a2...an, setiap nombor adalah pilihan, senaraikan semua penyelesaian yang mungkin.

for(int i=0;i<1<<n;i++){  //i为1到2^n的状态压缩值   2^n
	int p=i;          //先将i取出
	int sum=0;        //用一个变量维护取出的数之和
	for(j=0;j<n;j++){   //转为二进制进行操作
		sum+=p%2*a[j];    //这句话是求取出来的数之和。p%2为对应二进制位
                  		 //这里也可以进行其他操作，不一一举例。
		p/=2;            //求下一个二进制位
     	}
     //这里可以添加想要的操作。
   }

Salin selepas log masuk

Soalan algoritma 1:

chika dan satsuma (penggunaan PriorityQueue+Comparator)

Kesukaran ⭐⭐

Chika sangat suka makan satsumas. Setiap oren mandarin mempunyai tahap keasidan dan kemanisan tertentu Chika suka makan yang manis, tetapi bukan yang masam.

Chika makan k mandarin ada n mandarin kesemuanya. chika mahu mendapatkan jumlah kemanisan yang paling hebat. Jika terdapat berbilang pilihan, dia mahu jumlah keasidan sekecil mungkin.

Dia ingin tahu, apakah jumlah keasidan dan kemanisan terakhir?

Maklumat soalan: Isih mengikut kemanisan dalam tertib menurun dahulu, kemudian mengikut keasidan dalam tertib menaik (kekalkan tertib menurun kemanisan sebelumnya dahulu, diikuti dengan keasidan menaik)

Masukkan keterangan:

Baris pertama mempunyai dua integer positif n dan k, masing-masing mewakili jumlah bilangan mandarin dan bilangan mandarin yang dimakan oleh Chika. (1≤k≤n≤200000)

Barisan kedua mempunyai n integer positif ai, mewakili keasidan setiap oren mandarin. (1≤ai≤1e9)

Barisan kedua mempunyai n integer positif bi, mewakili kemanisan setiap oren mandarin. (1≤bi≤1e9)

Perihalan output:

Dua integer positif, dipisahkan oleh ruang. Mewakili jumlah keasidan dan jumlah kemanisan masing-masing.

Contoh

Input

3 2
1 3 4
2 2 5

Output

5 7

Penjelasan

Pilih mandarin No. 1 dan No. 3, jumlah keasidan ialah 5, dan jumlah kemanisan ialah 7, yang merupakan penyelesaian optimum.

import java.io.*;
import java.util.*;
public class Main{
    public static class Orange{
            int acid;
            int sweet;
            public Orange(int acid, int sweet){
                this.acid = acid;
                this.sweet = sweet;
            }
            public Orange(){}
        }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = br.readLine().split(" ");
        int n = Integer.parseInt(tmp[0]);
        int k = Integer.parseInt((tmp[1]));
        String[] ai = br.readLine().split(" ");
        String[] bi = br.readLine().split(" ");
        //定义一个优先队列，并根据指定的比较器对其元素进行排序。
        PriorityQueue<Orange> queue = new PriorityQueue<>((Orange o1, Orange o2)->{
            //匿名内部类以lambda的形式定义排序规则
            if(o1.sweet == o2.sweet){
                return o1.acid - o2.acid;
            }else{
                return o2.sweet - o1.sweet;
            }
        });
        for(int i = 0; i < n; i++){
            Orange orange = new Orange();
            orange.acid = Integer.parseInt(ai[i]);
            orange.sweet = Integer.parseInt(bi[i]);
            queue.add(orange);
        }
        long totalAcid = 0;
        long totalSweet = 0;
        for(int i = 0; i < k; i++){
            Orange o = queue.poll();
            totalAcid += o.acid;
            totalSweet += o.sweet;
        }
        System.out.println(totalAcid + " " + totalSweet);
    }
}

Salin selepas log masuk

Tujuan:

Fahami apa itu tamak, dan anda boleh mempertimbangkan untuk menggunakan PriorityQueue+Comparator apabila mereka bentuk dengan keutamaan.

Soalan algoritma 2:

anda dan perahu layar

Kesukaran ⭐⭐

Ayah kamu seorang kapten. Jadi anda suka laut sejak anda kecil. Hari itu, dia bertolak menaiki bot layar.

Terdapat banyak khazanah di laut, dan koordinat setiap khazanah diketahui. Koordinat awal anda ialah (0,0). Dia mahu meneroka dua khazanah dan kemudian kembali ke titik permulaan.

Anda mahu laluan itu sesingkat mungkin. Dia ingin tahu, berapakah panjang laluan terpendek itu?

Maklumat soalan: Hitungkan dua untuk gelung dan simpan laluan terpendek.

Penerangan input:

Baris pertama ialah integer n positif, mewakili bilangan khazanah. (2≤n≤2000)

n baris seterusnya, setiap baris mengandungi 2 integer positif xi, yi, mewakili koordinat khazanah ke-i (-3000≤xi,yi≤3000)

Tiada jaminan bahawa tidak akan ada dua khazanah dengan lokasi yang sama. Maksudnya, anda boleh meneroka kedua-dua khazanah di lokasi yang sama.

Perihalan output:

Panjang laluan terpendek. Simpan 6 digit selepas titik perpuluhan.

Contoh

Input

2
1 0
0 1

Output

3.414214

Penjelasan

Cara menggunakan tamak dan penghitungan di Jawa

import java.io.*;
import java.util.*;
 
class Point{
    double x;
    double y;
}
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Point[] points = new Point[n];
        for(int i=0;i<n;i++){
            String[] strings = br.readLine().split(" ");
            Point point = new Point();
            point.x = Integer.parseInt(strings[0]);
            point.y = Integer.parseInt(strings[1]);
            points[i] = point;
        }
        double min = Double.MAX_VALUE;//定义最大值，寻找较小值
        //双层遍历枚举
        for (int i=0;i<n-1;i++) {
            for (int j=i+1;j<n;j++) {
                double temp = Math.sqrt(points[i].x*points[i].x + points[i].y*points[i].y) 
                        + Math.sqrt(points[j].x*points[j].x + points[j].y*points[j].y) 
                        + Math.sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x) + (points[i].y-points[j].y)*(points[i].y-points[j].y));
                min = Math.min(min, temp);
            }
        }
        System.out.println(String.format("%.6f", min));
    }
}

Salin selepas log masuk

Tujuan:

Fahami apa itu penghitungan Walaupun ia disenaraikan satu persatu, masih ada cara untuk mengoptimumkannya berdasarkan realiti.

Sebagai contoh, gelung dua peringkat dalam soalan ini hanya menyenaraikan separuh daripada situasi: kerana apa yang dicari ialah jarak, yang tiada kaitan dengan dua titik akhir.

Berfikir:

Bagaimana jika terdapat lebih daripada dua peti harta karun yang perlu diperolehi? ? ? Boleh rujuk soalan seterusnya.

Soalan algoritma 3:

Pewarnaan digital

Kesukaran ⭐⭐⭐

Xiaohong mendapat integer positif X. Dia boleh mewarnakan beberapa digit merah. Kemudian dia mahu jumlah semua digit yang berwarna merah sama dengan jumlah digit yang tidak dicelup.

Dia tidak tahu sama ada dia boleh mencapai matlamatnya. Boleh awak beritahu dia?

Penerangan input:

Integer positif X, 1<= Atas premis bahawa Xiaohong boleh melengkapkan pencelupan seperti yang diperlukan. Jika tidak, "Tidak" ialah output.

Contoh 1

Input

1234567

Output

Arahan
Cuma warnakan 3, 4 dan 7 merah, jadi 3+4+7=1+2+5+6

Contoh 2

Input

Output

Tidak

Penjelasan
显然无论如何都不能完成染色。
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Long x= Long.parseLong(br.readLine());
        //循环0到2^18来展现所有的可能性
        for(int i=0;i<1<<19;i++){
            long p=i,s1=0,s2=0,temp=x;
 
            //将p拟化为2进制，通过j来寻尾。寻一次p就对应的二进制数就少一位。
            for(int j=0;j<19;j++){
                if(p%2==1)s1+=temp%10;
                else s2+=temp%10;
                p/=2;
                temp/=10;
            }
            if(s1==s2){
                System.out.println("Yes");
                System.exit(0);
            }
        }
        System.out.println("No");
    }
}
Salin selepas log masuk
这题使用的是状压枚举
只有两种状态就拟成2进制，假如有3种状态就拟成3进制（上面的代码会有些许改变，n种状态也一样）
 for(int i=0;i<1<<19;i++)  
//修改成
 for(int i=0;i<19;i++) p1[i]=p1[i-1]*3;
 for(int i=0;i<p1[i];i++){}
Salin selepas log masuk
当然这题也可以使用背包或dfs来解答。
算法题4：
ranko的手表
难度 ⭐⭐⭐⭐
ranko 的手表坏了，正常应该显示 xx:xx 的形式（4 个数字），比如下午 1 点半应该显示 13:30 ，但现在经常会有一些数字有概率无法显示。
Ranko checked the time at t1 and then again at t2 after some time had passed.。她想弄清楚t1和t2两个时间点之间的最大和最小时间间隔是多少
保证t1在t2之前（且t1和t2不等）。 t1和t2在同一天的 00:00 到 23:59 之间。
输入描述:
两行输入两个时间，为 xx:xx 的形式。x可以是数字或字符'?'，当为'?'时表示该数字未显示。保证输入是合法的。
输出描述:
一行输出两个整数，分别代表 t1 和 t2 相距时间的最小值和最大值（单位分钟）。
示例1
输入
18:0?
2?:1?
输出
121 319
说明
相距最小的时间为 18:09 到 20:10 ，相距121分钟。
相距最大的时间为 18:00 到 23:19 ，相距319分钟。
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        ArrayList<Integer> a1 = new ArrayList<>();
        ArrayList<Integer> a2 = new ArrayList<>();
        for(int i = 0; i < 60*24; i++){
            int hour = i/60, minute = i%60;
            if((hour/10 == s1.charAt(0)-&#39;0&#39; || s1.charAt(0) == &#39;?&#39;) &&
               (hour%10 == s1.charAt(1)-&#39;0&#39; || s1.charAt(1) == &#39;?&#39;) &&
               (minute/10 == s1.charAt(3)-&#39;0&#39; || s1.charAt(3) == &#39;?&#39;) &&
               (minute%10 == s1.charAt(4)-&#39;0&#39; || s1.charAt(4) == &#39;?&#39;)) a1.add(i);
            if((hour/10 == s2.charAt(0)-&#39;0&#39; || s2.charAt(0) == &#39;?&#39;) &&
               (hour%10 == s2.charAt(1)-&#39;0&#39; || s2.charAt(1) == &#39;?&#39;) &&
               (minute/10 == s2.charAt(3)-&#39;0&#39; || s2.charAt(3) == &#39;?&#39;) &&
               (minute%10 == s2.charAt(4)-&#39;0&#39; || s2.charAt(4) == &#39;?&#39;))a2.add(i);
        }
        int min= Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int i = 0; i<a1.size();i++){
            for(int j = 0; j<a2.size();j++){
                if(a1.get(i)<a2.get(j)){
                    min = Math.min(min,a2.get(j)-a1.get(i));
                    max = Math.max(max,a2.get(j)-a1.get(i));
                }
            }
        }
        System.out.print(min + " " + max);
    }
}
Salin selepas log masuk
Atas ialah kandungan terperinci Cara menggunakan tamak dan penghitungan di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!