J'ai résumé le code qui est souvent utilisé lors de la programmation de concours avec java. Comparé au C ++, il y a moins de gens qui font de la programmation compétitive en java et moins d'informations, donc j'ai créé cet article. On suppose que seule la bibliothèque standard sera utilisée.
Avant le début du concours, le code est préparé comme suit.
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();
}
}
Il est également défini comme suit.
static int MOD = 1000000007;
static int INF = Integer.MAX_VALUE;
En utilisant Arrays.setAll, vous pouvez écrire plus clairement qu'en utilisant l'instruction for.
int[] a = new int[N];
Arrays.setAll(a, i -> sc.nextInt());
La liste montre quel nœud a une branche à partir de quel nœud.
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);
}
Si vous avez besoin de l'ordre des branches comme information, par exemple lorsque vous avez besoin de la sortie, créez votre propre classe et enregistrez-les dans HashMap. Problème supposé: ABC146D Coloration des bords sur l'arbre
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));
}
}
Lorsque N est petit (N <20), recherchez les 2 ^ N voies.
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;
}
}
Stocker la distance d'un nœud v dans le tableau d en utilisant la recherche de priorité de largeur
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);
}
}
}
Il peut être obtenu avec des tableaux sans tourner l'instruction for.
Arrays.stream([Nom de la séquence]).min().getAsInt()
Arrays.stream([Nom de la séquence]).max().getAsInt()
Exprimez la méthode de division mutuelle euclidienne avec une fonction récursive.
public static int gcd(int a, int b) {
return b == 0 ? a: gcd(b, a % b);
}
Utilisez le plus petit multiple commun.
public static int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
C'est la base des fonctions récursives.
public static long factorial(long n){
return n <= 0 ? 1 : n * factorial(n-1);
}
Prenons le cas de la sortie du reste divisé par 10 ^ 9 + 7 lors de la recherche de la combinaison. Lorsque N est petit (environ <2000), il peut être calculé par la méthode de programmation dynamique en considérant le triangle de Pascal.
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;
}
}
Si N est grand, il est nécessaire de trouver l'élément inverse. Le calcul est effectué en appelant COMinit () dans la méthode principale, et nCr peut être obtenu par combinaison (n, r).
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));
}
Sort toutes les séquences dans N! Street.
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));
}
En java, une dichotomie est possible avec Arrays.binarySearch. Arrays.binarySearch renvoie la position si le tableau contient une clé, sinon il retourne la position où la clé doit être insérée. Puisqu'il n'y a pas de méthodes telles que C ++ limite inférieure et limite supérieure, le nombre ne peut pas être compté par dichotomie. Alors je l'ai mis en œuvre moi-même.
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);
}
Une méthode qui factorise et enregistre dans HashMap.
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);
}
Cet article est en cours de rédaction. Je vais le mettre à jour de temps en temps.
Recommended Posts