Ich habe den Code zusammengefasst, der häufig beim Programmieren von Wettbewerben mit Java verwendet wird. Im Vergleich zu C ++ gibt es in Java weniger Leute, die wettbewerbsfähige Programme programmieren, und weniger Informationen. Deshalb habe ich mir diesen Artikel ausgedacht. Es wird davon ausgegangen, dass nur die Standardbibliothek verwendet wird.
Bevor der Wettbewerb beginnt, wird der Code wie folgt vorbereitet.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
System.out.println();
}
}
Es ist auch wie folgt definiert.
static int MOD = 1000000007;
static int INF = Integer.MAX_VALUE;
Mit Arrays.setAll können Sie klarer schreiben als mit der for-Anweisung.
int[] a = new int[N];
Arrays.setAll(a, i -> sc.nextInt());
Die Liste zeigt, welcher Knoten einen Zweig von welchem Knoten hat.
List<Integer>[] edge = new ArrayList[N];
for(int i = 0; i < N; i++)
edge[i] = new ArrayList<>();
for (int i = 0; i < N-1; i++) {
int a = sc.nextInt()-1;
int b = sc.nextInt()-1;
edge[a].add(b);
edge[b].add(a);
}
Wenn Sie die Reihenfolge der Zweige als Information benötigen, z. B. wenn Sie eine Ausgabe benötigen, machen Sie die Zweige zu Ihrer eigenen Klasse und speichern Sie sie in HashMap. Angenommenes Problem: ABC146D Coloring Edges on Tree
static int N;
static Map<Integer, HashSet<edge>> m = new HashMap<>();
static class edge{
int to, id;
edge(int to, int id){
this.to = to;
this.id = id;
}
}
public static void main(String[] args) {
for(int i = 0; i < N-1; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
if(!m.containsKey(a))
m.put(a, new HashSet<>());
m.get(a).add(new edge(b, i));
}
}
Wenn N klein ist (N <ungefähr 20), suchen Sie alle 2 ^ N Wege.
boolean[] x = new boolean[N];
for(int i = 0; i < 1<<N; i++) {
for(int j = 0; j < N; j++) {
if ((1 & i >> j) == 1)
x[j] = true;
else
x[j] = false;
}
}
Speichern Sie den Abstand von einem Knoten v im Array d mithilfe der Suche nach Breitenpriorität
int[] d = new int[N+1];
Arrays.fill(d, INF);
d[v] = 0;
Queue<Integer> q = new ArrayDeque<>();
for(int i : edge.get(v)) {
q.offer(i);
d[i] = 1;
}
while(q.size() > 0) {
int x = q.poll();
for(int i : edge.get(x)) {
if(d[i] > d[x] + 1) {
d[i] = d[x] + 1;
q.offer(i);
}
}
}
Es kann mit Arrays erhalten werden, ohne die for-Anweisung zu drehen.
Arrays.stream([Sequenzname]).min().getAsInt()
Arrays.stream([Sequenzname]).max().getAsInt()
Drücken Sie die euklidische Methode der gegenseitigen Teilung mit einer rekursiven Funktion aus.
public static int gcd(int a, int b) {
return b == 0 ? a: gcd(b, a % b);
}
Verwenden Sie das kleinste gemeinsame Vielfache.
public static int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
Es ist die Basis rekursiver Funktionen.
public static long factorial(long n){
return n <= 0 ? 1 : n * factorial(n-1);
}
Betrachten Sie den Fall der Ausgabe des Restes geteilt durch 10 ^ 9 + 7, wenn Sie die Kombination finden. Wenn N klein ist (ungefähr <2000), kann es durch das dynamische Programmierverfahren unter Berücksichtigung des Pascal-Dreiecks berechnet werden.
int MAX = 2000;
long[][] com = new long[MAX][MAX];
for(int i = 0; i < MAX; i++)
com[i][0] = 1;
for(int i = 1; i < MAX; i++) {
for(int j = 1; j <= i; j++) {
com[i][j] = com[i-1][j-1] + com[i-1][j];
com[i][j] %= MOD;
}
}
Wenn N groß ist, muss das inverse Element gefunden werden. Die Berechnung wird durch Aufrufen von COMinit () in der Hauptmethode durchgeführt, und nCr kann durch Kombination (n, r) erhalten werden.
public static int MOD = 1_000_000_007;
public static int MAX = 100000;
public static long[] fac = new long[MAX];
public static long[] finv = new long[MAX];
public static long[] inv = new long[MAX];
public static void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for(int i = 2; i < MAX; i++) {
fac[i] = fac[i-1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
finv[i] = finv[i-1] * inv[i] % MOD;
}
}
public static long combination(int n, int k){
if(n < k || n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}
public static void main(String[] args) {
COMinit();
System.out.println(combination(2000, 3));
}
Gibt alle Sequenzen in der N! Street aus.
static List<String> z;
public static void permutation(String q, String ans){
if(q.length() <= 1) {
z.add(ans + q);
}
else {
for (int i = 0; i < q.length(); i++) {
permutation(q.substring(0, i) + q.substring(i + 1),
ans + q.charAt(i));
}
}
}
public static void main(String[] args) {
z = new ArrayList<>();
permutation("12345","");
for(int i = 0; i < z.size(); i++)
System.out.println(z.get(i));
}
In Java ist eine Dichotomie mit Arrays.binarySearch möglich. Arrays.binarySearch gibt die Position zurück, wenn das Array einen Schlüssel enthält, andernfalls gibt es die Position zurück, an der der Schlüssel eingefügt werden soll. Da es in C ++ keine Methoden wie Lower_bound und Upper_bound gibt, kann die Anzahl nicht durch Dichotomie gezählt werden. Also habe ich es selbst implementiert.
public static int lowerbound(int[] a, int key) {
if(a[a.length-1] < key)
return a.length;
int lb = 0, ub = a.length-1, mid;
do {
mid = (ub+lb)/2;
if(a[mid] < key)
lb = mid + 1;
else
ub = mid;
}while(lb < ub);
return ub;
}
public static int upperbound(int[] a, int key) {
if(a[a.length-1] <= key)
return a.length;
int lb = 0, ub = a.length-1, mid;
do {
mid = (ub+lb)/2;
if(a[mid] <= key)
lb = mid + 1;
else
ub = mid;
}while(lb < ub);
return ub;
}
public static int count(int[] a, int key) {
return upperbound(a, key) - lowerbound(a, key);
}
Eine Methode, die in HashMap faktorisiert und speichert.
static Map<Integer, Integer> fact = new HashMap<>();
public static void factorization(int N){
for(int i = 2; i <= Math.sqrt(N); i ++) {
if(N % i == 0) {
int n = 0;
while(N % i == 0) {
N /= i;
n++;
}
fact.put(i, n);
}
}
if(N > 1)
fact.put(N, 1);
}
Dieser Artikel wird gerade bearbeitet. Ich werde es von Zeit zu Zeit aktualisieren.
Recommended Posts