これは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; /* * 始点を指定して各頂点の最短距離を取得する * @param sv 始点とする頂点 */ 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; //もし、始点からuまでの最短距離 + uからvまでの距離cが始点からvまでの距離より小さいなら更新する 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; //もし、始点からuまでの最短距離 + uからvまでの距離cが始点からvまでの距離より小さいなら更新する 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; //http://nishiharayuugo.blog.fc2.com/blog-entry-15.html public class Dijkstra {//頂点数V、辺の数Eに対し、O(E log V) 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; /* * @param sv 始点となる頂点 */ static void dijkstra(int sv) { //初期化 Arrays.fill(dist, INF); dist[sv] = 0; //候補の優先キューを用意 Queue<Candidate> candidates = new PriorityQueue<>(); candidates.offer(new Candidate(sv, 0));//最初に始点と距離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(); //nCr = n!/r!(n-r)! = n ~ r / (n-r)! 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;//ユークリッドの互除法により // a*b = (aとbの最小公倍数) * (aとbの最大公約数) //式変形して a / (aとbの最大公約数) * b = (aと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;//篩に2~nまでの値を入れる } for(int i = 2; i <= Math.sqrt(wantUpper); i++) { for(int j = i+i; j <= wantUpper; j+=i) {//iの倍数は篩落とす furui[j]=0; } } //篩の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;//桁の数 4なら0000 ~ 1111まで for(int i = 0; i < (1<<ketasu); i++) { for(int j = ketasu-1, k = 0; j >= 0; j--, k++) { if(((i>>j) & 1) == 1) {//左からj番目のbitが立っている(1)かどうか } } for(int j = 0; j < ketasu; j++) { if(((i>>j) & 1) == 1) {//右からj番目のbitが立っている(1)かどうか } } }
