wataACM模板v0.9资源-CSDN文库

需积分: 9 63 浏览量 2014-09-12 17:06:51 上传评论 1 收藏 574KB PDF 举报

ACM竞赛，即国际大学生程序设计竞赛（International Collegiate Programming Contest，简称ICPC），是大学生之间的一项计算机科学竞赛。竞赛着重于算法、数据结构和编程技能的较量。在ACM竞赛中，使用模板是一种常见的做法，可以帮助参赛者快速搭建程序框架，并且减少编写冗余代码的时间，从而集中精力在算法设计上。标题“wata ACM 模板 v0.9”中的“wata”可能是一个编写该模板的团队或个人的名称，而“模板 v0.9”则表示这是该模板的第0.9版本，表明它可能是一个尚在完善中的工作版本。在描述中提到“wata模板，著名ACM备战模板”，说明该模板在ACM竞赛领域有一定的知名度和认可度，是很多参加ACM竞赛的同学们备战时所推荐使用的模板之一。内容部分包含了Java编程语言编写的ACM模板代码片段，其中涉及了几个常见的数据结构： 1. 前缀和数据结构BIT（Binary Indexed Tree，二元索引树），又称为Fenwick Tree。它是一种用于高效处理数组区间和查询和单点更新的数据结构。在BIT中，实现了一个构造函数`BIT(int n)`用于初始化数组，并提供了两个主要的操作：`add(int k, int a)`用于更新数组中索引为k的元素增加a，以及`sum(int s, int t)`用于计算区间[s, t]内元素的和。 2. RMQ（Range Minimum/Maximum Query）数据结构，用于解决区间最值查询问题。该数据结构可以预处理数组，在O(1)时间复杂度内回答关于区间最值的问题。代码中实现了`RMQ(int[] vs)`构造函数用于初始化数据结构，以及`query(int from, int to)`函数用于查询区间最小值。 3. 线段树（代码未完整展示）通常用于处理区间更新和查询问题。代码片段中使用了`TreeMap<Integer, Integer>`来模拟线段树的更新操作，尽管这并不是一个纯粹的线段树实现，但它展示了区间更新的基本思路。 4. 代码片段中还包含了调试函数`debug(Object os)`，用于输出调试信息，辅助程序开发过程中快速定位问题。 5. 在代码片段末尾，有`if(LOCAL)`的条件判断，这表明模板支持了本地测试功能，可以在本地文件`in.txt`中读取输入数据进行测试，而不是直接从标准输入读取。 wata ACM模板 v0.9为ACM参赛者提供了一个包含常用数据结构和测试功能的基础框架，通过减少重复编码工作，提升参赛者对算法设计的关注。当然，实际使用时，还需要根据具体的竞赛题目和要求进行相应的修改和扩展。

资源推荐

资源详情

资源评论

2 データ構造 1/25

1 テンプレート

1 import static java.lang.Math.*;

2 import static java.util.Arrays.*;

3 import java.io.*;

4 import java.util.*;

6 public class Main {

7 static boolean LOCAL = System.getSecurityManager() == null;

8 Scanner sc = new Scanner(System.in);

10 void run() {

11 }

13 void debug(Object...os) {

14 System.err.println(deepToString(os));

15 }

17 public static void main(String[] args) {

18 if (LOCAL) {

19 try {

20 System.setIn(new FileInputStream("in.txt"));

21 } catch (Throwable e) {

22 LOCAL = false;

23 }

24 }

25 new Main().run();

26 }

27 }

2 データ構造

2.1 BIT

1 class BIT {

2 int[] vs;

3 BIT(int n) {

4 vs = new int[n + 1];

5 }

6 void add(int k, int a) {

7 for (int i = k + 1; i < vs.length; i += i & -i) {

8 vs[i] += a;

9 }

10 }

11 int sum(int s, int t) {

12 if (s > 0) return sum(0, t) - sum(0, s);

13 int res = 0;

14 for (int i = t; i > 0; i -= i & -i) {

15 res += vs[i];

16 }

17 return res;

18 }

19 //[0,i] の和が k より大きくなる最小の i を求める

20 int get(int k) {

21 int p = Integer.highestOneBit(vs.length - 1);

22 for (int q = p; q > 0; q >>= 1, p |= q) {

23 if (p >= vs.length || k < vs[p]) p ^= q;

24 else k -= vs[p];

25 }

26 return p;

27 }

28 }

2.2 RMQ

1 class RMQ {

2 int[] vs;

3 int[][] min;

4 RMQ(int[] vs) {

5 int n = vs.length, m = log2(n) + 1;

6 this.vs = vs;

7 min = new int[m][n];

8 for (int i = 0; i < n; i++) min[0][i] = i;

9 for (int i = 1, k = 1; i < m; i++, k <<= 1) {

10 for (int j = 0; j + k < n; j++) {

11 min[i][j] = vs[min[i - 1][j]] <= vs[min[i - 1][j + k]] ?

12 min[i - 1][j] : min[i - 1][j + k];

13 }

14 }

15 }

16 //最小値が複数存在する場合は一番最初のを返す

17 int query(int from, int to) {

18 int k = log2(to - from);

19 return vs[min[k][from]] <= vs[min[k][to - (1 << k)]] ?

20 min[k][from] : min[k][to - (1 << k)];

21 }

22 int log2(int b)

{

23 return 31 - Integer.numberOfLeadingZeros(b);

24 }

25 }

Shandong University

2 データ構造 2/25

2.3 範囲の更新

1 class Intervals {

2 TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();

3 Intervals() {

4 map.put(Integer.MIN_VALUE, -1);

5 map.put(Integer.MAX_VALUE, -1);

6 }

7 void paint(int s, int t, int c) {

8 int p = get(t);

9 map.subMap(s, t).clear();

10 map.put(s, c);

11 map.put(t, p);

12 }

13 int get(int k) {

14 return map.floorEntry(k).getValue();

15 }

16 }

2.4 Treap

副作用なしの実装

1 class T {

2 final int key, val;

3 final double p;

4 final T left, right;

5 T(int key, int val, double p, T left, T right) {

6 this.key = key;

7 this.val = val;

8 this.p = p;

9 this.left = left;

10 this.right = right;

11 }

12 T change(T left, T right) {

13 return new T(key, val, p, left, right);

14 }

15 T normal() {

16 if (left != null && left.p < p && (right == null || left.p < right.p)) {

17 return left.change(left.left, change(left.right, right));

18 } else if (right != null && right.p < p) {

19 return right.change(change(left, right.left), right.right);

20 }

21 return this;

22 }

23 }

24 T put(T t, int key, int val) {

25 if (t == null) return new T(key, val, random(), null, null);

26 if (key < t.key) return t.change(put(t.left, key, val), t.right).normal();

27 if (key > t.key) return t.change(t.left, put(t.right, key, val)).normal();

28 return new T(key, val, t.p, t.left, t.right);

29 }

30 T remove(T t, int key) {

31 if (t == null) return null;

32 if (key < t.key) return t.change(remove(t.left, key), t.right);

33 if (key > t.key) return t.change(t.left, remove(t.right, key));

34 return merge(t.left, t.right);

35 }

36 T merge(T t1, T t2) {

37 if (t1 == null) return t2;

38 if (t2 == null) return t1;

39 if (t1.p < t2.p) return t1.change(t1.left, merge(t1.right, t2));

40 return t2.change(merge(t1, t2.left), t2.right);

41 }

2.5 セグメント木

配列とループを用いた高速な実装

parent(i) = i/2

left(i) = 2i

size(i) = N/highest(i)

s(i) = size(i)i −N

1 class Seg {

2 int N;

3 Seg(int n) {

4 N = Integer.highestOneBit(n) << 1;

5 }

6 //点を含む区間に対する処理

7 void query(int k) {

8 for (int i = N + k; i > 0; i >>= 1) {

9 //...

10 }

11 }

12 //カバーする区間に対する処理

13 void query(int s, int t) {

14 while (0 < s && s + (s & -s) <= t) {

15 int i = (N + s) / (s & -s);

16 //...

17 s += s & -s;

18 }

19 while (s < t) {

20 int i = (N + t) / (t & -t) - 1;

Shandong University

3 グラフ 3/25

21 //...

22 t -= t & -t;

23 }

24 }

25 }

3 グラフ

3.1 公式集

3.1.1 オイラーの多面体定理

連結な平面グラフについて、頂点数 V , 辺数 E, 面数 F の関係は外面も含めて V − E + F = 2

3.1.2 MaxFlow-MinCut 定理

最大 s-t-フローの流量=最小 s-t-カットの容量

グラフ G の最小カットの辺集合は残容量グラフ G

で s から到達可能な点の集合を X とすると δ

(X)

3.1.3 マッチングなどの関係式

| 最大マッチング | ≤ | 最小点カバー | (二部グラフでは等号成立)

| 最大安定集合 | + | 最小点カバー | = V

孤立点のないグラフについて | 最大マッチング | + | 最小辺カバー | = V

二部グラフについて | 最小辺カバー | = | 最大安定集合 |

X ⊆ V (G) が G の点カバー ⇔ V (G) \X は G の安定集合

3.1.4 行列木定理

グラフ G の全域木の総数は (G の次数行列 − G の隣接行列) の任意の余因子に等しい

3.1.5 次数列木の総数

の全域木で、頂点 i の次数が d

であるようなものの総数は、

(n − 2)!

− 1)!(d

− 1)! . . . (d

− 1)!

3.1.6 Kasteleyn の公式

全ての偶数長閉路を奇数的に向きづけらようなグラフについて、その隣接行列 (逆向きの辺は-1 とする) の行列

式は完全マッチングの個数の二乗に等しい

平面グラフには必ずこのような向き付けが存在する

二部グラフの場合は、二部隣接行列の行列式が完全マッチングの個数と等しくなる

3.1.7 Tutte 行列

Tutte 行列とは V × V の行列で、グラフ G の各辺を勝手に向き付けて得られる有向グラフ G

′

の辺 (v, u) に対

し、変数 x

を割り当て、t

= x

, t

= −x

としたもの

一般のグラフに対して、Tutte 行列のランクはマッチングの大きさの二倍と等しい

x をランダムにとれば十分な確率で正しい解が得られる

3.2 トポロジカルソート

トポロジカル順序とは v[i] から v[j] に辺がある ⇒ i < j が成立するもののことをいう

深さ優先探索を行い、帰りがけに番号を振ると、それが逆トポロジカル順序になる

1 V[] topologicalSort(V[] vs) {

2 n = vs.length;

3 us = new V[n];

4 for (V v : vs) {

5 if (v.state == 0 && !dfs(v)) return null;

6 }

7 return us;

8 }

9 boolean dfs(V v) {

10 v.state = 1;

11 for (V u : v) {

12 if (u.state == 1 || u.state == 0 && !dfs(u)) return false;

13 }

14 us[--n] = v;

15 v.state = 2;

16 return true;

17 }

3.3 強連結成分分解

まずトポロジカル順序を求め (この際に閉路は無視する)、その順に逆辺を深さ優先探索する

このときに得られた極大な探索木が強連結成分である

強連結成分の個数 k が返り、comp にはトポロジカル順序 [0,k) が入る

1 int scc(V[] vs) {

2 n = vs.length;

3 us = new V[n];

4 for (V v : vs) if (!v.visit) dfs(v);

5 for (V v : vs) v.visit = false;

6 for (V u : us) if (!u.visit) dfsrev(u, n++);

7 return n;

8 }

9 void dfs(V v) {

10 v.visit = true;

11 for (V u : v.fs) if (!u.visit) dfs(u);

12 us[--n] = v;

13 }

14 void dfsrev(V v, int k) {

15 v.visit = true;

16 for (V u : v.rs) if (!u.visit) dfsrev(u, k);

17 v.comp = k;

18 }

3.4 関節点・橋

任意に根を選んで DFS を行い、行きがけに番号 num を振る

以下のうちの最小値として low を計算する

・num[v]

・直前の辺以外で v に隣接するすでに訪れた頂点 u における num[u]

・v の子供 u における low[u]

このとき、

根: r が関節点 ⇔ r が 2 つ以上の子供を持つ

Shandong University

3 グラフ 4/25

根以外: v が関節点 ⇔ v の子供 u に対して num[v] ≤ low[u]

(v,u) が橋 ⇔ num[v] < low[u]

count にはその頂点が取り除かれたときにできる分裂の個数が入り、橋集合が返る

1 ArrayList<E> connection(V[] vs) {

2 bridge = new ArrayList<E>();

3 for (V v : vs) if (v.num < 0) {

4 dfs(v, 0);

5 if (v.count > 0) v.count--;

6 }

7 return bridge;

8 }

9 int dfs(V v, int c) {

10 v.num = c;

11 int low = c;

12 boolean rev = false;

13 for (V u : v) {

14 if (u.num < 0) {

15 int t = dfs(u, c + 1);

16 low = min(low, t);

17 if (v.num <= t) v.count++;

18 if (v.num < t) bridge.add(new E(v, u));

19 } else if (u.num != v.num - 1 || rev) low = min(low, u.num);

20 else rev = true;

21 }

22 return low;

23 }

3.5 最小平均長閉路

負の辺があってもよい

prev をたどって得られるパスに含まれる任意の閉路が最小平均長の閉路である

O(V E)

1 double mmc(int[] ss, int[] ts, double[] cs, int n) {

2 int m = ss.length;

3 double[][] dp = new double[n + 1][n];

4 for (int i = 0; i < n; i++) {

5 fill(dp[i + 1], INF);

6 for (int j = 0; j < m; j++) {

7 dp[i + 1][ts[j]] = min(dp[i + 1][ts[j]], dp[i][ss[j]] + cs[j]);

8 }

9 }

10 double res = INF;

11 for (int i = 0; i < n; i++) if (dp[n][i] < INF) {

12 double max = -INF;

13 for (int j = 0; j < n; j++) {

14 max = max(max, (dp[n][i] - dp[j][i]) / (n - j));

15 }

16 res = min(res, max);

17 }

18 return res;

19 }

3.6 最小根指定有向木

根以外の各点に入る最小の辺を貪欲に選び、閉路ができたら圧縮して再帰的に処理している

有向木自体を求めるには、圧縮時にもともとの辺を覚えておけばよい

根が指定されないときは、十分大きな値をを各辺からから引き、根から他の全ての頂点にコスト０の辺を加えれ

ばよい

最大有向森を求めるには辺の重みを反転し、根から他の全ての頂点にコスト０の辺を加えればよい

O(V E)

1 int arborescence(V[] vs, V r) {

2 int res = 0;

3 for (V v : vs) for (E e : v.es) e.to.min = min(e.to.min, e.cost);

4 for (V v : vs) if (v != r) {

5 if (v.min == INF) return INF;

6 res += v.min;

7 }

8 for (V v : vs) for (E e : v.es) if (e.to != r) {

9 e.cost -= e.to.min;

10 if (e.cost == 0) {

11 v.fs.add(e.to);

12 e.to.rs.add(v);

13 }

14 }

15 int m = scc(vs);

16 if (m == vs.length) return res;

17 V[] us = new V[m];

18 for (int i = 0; i < m; i++) us[i] = new V();

19 for (V v : vs) for (E e : v.es) {

20 if (v.comp != e.to.comp) us[v.comp].add(us[e.to.comp], e.cost);

21 }

22 return min(INF, res + arborescence(us, us[r.comp]));

23 }

3.7 シュタイナー木

非負の無向グラフに対し、ターミナル ts の要素を全て含む最小の木のコストを求める

dp[S][v] := S ⊂ T と v ∈ V を含む最小シュタイナー木のコスト

O(3

n + 2

+ n

)

1 int steiner(int[][] g, int[] ts) {

2 int n = g.length, m = ts.length;

Shandong University

剩余24页未读，继续阅读

评论收藏

内容反馈

clangpp

粉丝: 14
资源: 2

wata ACM 模板 v0.9

ACM比赛必带模板

ACM会议模板

ＡＣＭ模板

ACM模板

ACM计算机模板

acm部分模板

packer-post-processor-amazon-ami-management：用于AMI管理的Packer-post-processor插件

packer-plugin-amazon-ami-management:用于Amazon AMI管理的Packer后处理器插件

tf_aws_ecs_on_spotfleet：用于在Spot Fleet上创建ECS的Terraform模块

wata:瓦塔

由操纵杆控制的SCARA臂-项目开发

tflint：可插拔的地形Linter

WATA_BLE.rar

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

XCP协议的规范文档

GD32替换STM32注意事项.pdf

NPPJSONViewer.zip

蓝牙BLE协议中文版.pdf

CANoe通过CAPL脚本实现自动测试

AD20官方中文教程.pdf

完整版 Microsoft.ACE.OLEDB.12.0 驱动下载.rar

电路分析基础第二版PDF电子书免费下载

Tangent免费.rar

qt样式表一键生成（花狗Fdog）

CMSIS-DAP使用说明及驱动.rar

Matlab安装MinGW-w64 C/C++ 编译器

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）