これはgitを使えない人がライブラリをオンラインでどう保管するか考えた結果、記事にコピペするに帰着したクソなので、読むこと見ることを想定していません
基本こっから書く
自動テスト？知らない子ですね...(汗
import java.util.Scanner;
public class Base {
public static void main(String[] args) {
final Scanner sc = new Scanner(System.in);
System.out.println();
}
}
ベルマンフォード法
import java.util.Arrays;
import java.util.Scanner;
public class Bellman_ford {
public static void main(String[] args) {
final Scanner sc = new Scanner(System.in);
System.out.println();
}
static class Edge {
int from;
int to;
int cost;
}
static int V;
static int E;
static Edge[] edges;
static int[] d;
static int INF = Integer.MAX_VALUE / 2;
static void bellman_ford(int sv) {
d = new int[V];
Arrays.fill(d, INF);
d[sv] = 0;
while(true) {
boolean update = false;
for(int i = 0; i < E; i++) {
int u = edges[i].from;
int v = edges[i].to;
int c = edges[i].cost;
if(d[u] + c < d[v]) {
d[v] = d[u] + c;
update = true;
}
}
if(!update) {
break;
}
}
}
static boolean bellman_ford2(int sv) {
d = new int[V];
Arrays.fill(d, INF);
d[sv] = 0;
for(int count = 0; count < V; count++) {
for(int i = 0; i < E; i++) {
int u = edges[i].from;
int v = edges[i].to;
int c = edges[i].cost;
if(d[u] + c < d[v]) {
d[v] = d[u] + c;
if(count==v-1) {
return false;
}
}
}
}
return true;
}
}
キューを使ったダイクストラ(正直仕組みわからん)
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Dijkstra {
public static void main(String[] args) {
final Scanner sc = new Scanner(System.in);
System.out.println();
}
static class Candidate implements Comparable<Candidate> {
int d;
int v;
public Candidate(int v, int d) {
this.d = d;
this.v = v;
}
@Override
public int compareTo(Candidate o) {
return this.d - o.d;
}
}
static class Edge {
int to;
int cost;
Edge(int to, int cost) {
this.to = to;
this.cost = cost;
}
}
static List<List<Edge>> G;
static int[] dist;
static int INF = Integer.MAX_VALUE / 2;
static void dijkstra(int sv) {
Arrays.fill(dist, INF);
dist[sv] = 0;
Queue<Candidate> candidates = new PriorityQueue<>();
candidates.offer(new Candidate(sv, 0));
while(!candidates.isEmpty()) {
Candidate c = candidates.poll();
int v = c.v;
int d = c.d;
if(dist[v] < d) {
continue;
}
List<Edge> edges = G.get(v);
for(Edge e : edges) {
if(dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
candidates.offer(new Candidate(e.to, dist[e.to]));
}
}
}
}
}
UnionFind、簡単だけど改造するの大変そうだね(他人事)
import java.util.Scanner;
public class UnionFind {
static int[] par = new int[100000];
public static void main(String[] args) {
final Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 0; i <= n; i++) {
par[i] = i;
}
System.out.println();
}
static int root(int x) {
if(par[x]==x) {
return x;
} else {
return par[x] = root(par[x]);
}
}
static boolean same(int x, int y) {
return root(x)==root(y);
}
static void unite(int x, int y) {
x = root(x);
y = root(y);
if(x == y) return;
par[x] = y;
}
}
nCr mod(109+7)を計算するやつ、逆弦かなんか使っててThe・数学なので理解する木はない
ちょっと洗練されてないね...、木が向いたら手直ししよ
import java.util.Scanner;
public class nCr {
public static void main(String[] args) {
final Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long r = sc.nextLong();
long n_r = n - r;
System.out.println(String.format("n:%d\nr:%d\nn-r:%d", n, r, n_r));
long a = 1, b = 1;
int mod = 1000000007;
for(int i = 1; i <= n_r; i++) {
a = a * (r + i) % mod;
b = b * i % mod;
}
long ans = a * func(b, mod - 2, mod) % mod;
System.out.println(ans);
}
static long func(long a, long b, int mod) {
if(b == 0) {
return 1;
}
if(b % 2 == 0) {
return func(a * a % mod, b / 2, mod);
} else {
return a * func(a, b-1, mod) % mod;
}
}
}
最小公倍数、最大公約数を求めるやつ。コード短いのすごいよね
public class lcm_gcd {
static int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a%b);
}
static int lcm(int a, int b) {
int g = gcd(a, b);
return a / g * b;
}
}
エラトステネスの篩。この名前覚えられない
import java.util.Scanner;
public class エラトステネスの篩 {
public static void main(String[] args) {
final Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int wantUpper = n;
int furui[] = new int[wantUpper+1];
for(int i = 2; i <= wantUpper; i++) {
furui[i]=i;
}
for(int i = 2; i <= Math.sqrt(wantUpper); i++) {
for(int j = i+i; j <= wantUpper; j+=i) {
furui[j]=0;
}
}
}
}
ab (mod p)、一生使わないだろうね(数学すぎる)
static long func(long a, long b, int mod) {
if(b == 0) return 1;
if(b % 2 == 0) return func(a * a % mod, b / 2, mod);
else return a * func(a, b - 1, mod) % mod;
}
stackでのdfs、コードじゃなく雰囲気を書きます
コードは２次元平面上でのdfsですが、基本的にコメントのように実装するとグラフでも動く
ArrayDeque<Point> deq = new ArrayDeque<>();
deq.push(start);
while(deq.size()!=0) {
Point p = deq.poll();
if(p.equals(goal)) {
System.out.println("Yes");
return;
}
if(p.x >= h || p.x < 0 || p.y >= w || p.y < 0) {
continue;
}
if(map[p.x][p.y] == '#') {
continue;
}
map[p.x][p.y] = '#';
for(int i = 0; i < 4; i++) {
deq.push(new Point(p.x + x[i], p.y + y[i]));
}
}
System.out.println("No");
bit全探索、実装結構軽いよね
int ketasu = 4;
for(int i = 0; i < (1<<ketasu); i++) {
for(int j = ketasu-1, k = 0; j >= 0; j--, k++) {
if(((i>>j) & 1) == 1) {
}
}
for(int j = 0; j < ketasu; j++) {
if(((i>>j) & 1) == 1) {
}
}
}
