I have summarized the code that is often used when programming competitions in java. Compared to C ++, there are fewer people doing competitive programming in java and less information, so I came up with this article. It is assumed that only the standard library will be used.
Before the contest starts, the code is prepared as follows.
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();
}
}
In addition, it is defined as follows.
static int MOD = 1000000007;
static int INF = Integer.MAX_VALUE;
By using Arrays.setAll, you can write more clearly than using the for statement.
int[] a = new int[N];
Arrays.setAll(a, i -> sc.nextInt());
The list shows which node has a branch from which node.
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);
}
If you need the order of the branches as information, such as when you need output, make the branch your own class and save it in HashMap. Assumed 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));
}
}
When N is small (N <about 20), search all 2 ^ N ways.
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;
}
}
Using breadth-first search, store the distance from a node v in the array d
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);
}
}
}
You can get it with Arrays without turning the for statement.
Arrays.stream([Array name]).min().getAsInt()
Arrays.stream([Array name]).max().getAsInt()
Express the Euclidean algorithm with a recursive function.
public static int gcd(int a, int b) {
return b == 0 ? a: gcd(b, a % b);
}
Use the least common multiple.
public static int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
It is the basis of recursive functions.
public static long factorial(long n){
return n <= 0 ? 1 : n * factorial(n-1);
}
Consider the case of outputting the remainder divided by 10 ^ 9 + 7 when finding the combination. When N is small (about <2000), it can be calculated by dynamic programming, considering Pascal's triangle.
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;
}
}
If N is large, it is necessary to find the inverse element. Calculation is performed by calling COMinit () in the main method, and nCr can be obtained by combination (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));
}
Output all permutations according to N !.
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, binary search is possible with Arrays.binarySearch. Arrays.binarySearch returns the position if the array contains a key, otherwise it returns the position where the key should be inserted. Since there are no methods such as lower_bound and upper_bound in C ++, the number cannot be counted by binary search. So I implemented it myself.
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);
}
A method that factorizes and saves in 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);
}
This article is in the process of being edited. I will update it from time to time.
Recommended Posts