Cara menggunakan tamak dan penghitungan di Jawa

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;            //求下一个二进制位
     	}
     //这里可以添加想要的操作。
   }

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);
    }
}

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

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));
    }
}

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

Contoh 1

Input

1234567

Output

Ya

Arahan

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

Contoh 2

Input

23

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");
    }
}

这题使用的是状压枚举

只有两种状态就拟成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++){}

当然这题也可以使用背包或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);
    }
}

Atas ialah kandungan terperinci Cara menggunakan tamak dan penghitungan di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!