Wiki Theory: http://en.wikipedia.org/wiki/Matching_(graph_theory)
ACM ICPC
ACM ICPC Bolivia 2013
[latexpage]Problem Set: ACM ICPC Bolivia 2013 problem-set
Online judge: SPOJ Bolivia Sigue leyendo
UVA 459 – Graph Connectivity (Depth First Search solution)
Simple solution using DFS algorithm.
#include <iostream> #include <sstream> #include <utility> #include <cstdlib> #include <cstdio> #include <cctype> #include <cmath> #include <functional> #include <algorithm> #include <numeric> #include <string> #include <vector> #include <queue> #include <stack> #include <list> #include <map> #include <set> #include <stdio.h> #include <string.h> using namespace std; typedef long long LL; bool G[300][300], vis[300]; void dfs(int x) { if(vis[x]) return; vis[x] = true; for(char i='A'; i<='Z' ;i++) if(G[x][i]) dfs(i); } int main() { int casos; string cad; char N; cin >> casos >> cad; for(int i=0; i<casos ;i++) { memset(vis, 0, sizeof(vis)); memset(G, 0, sizeof(G)); int r = 0; if(i) printf("n"); N = cad[0]; while(cin>>cad && cad.size() != 1) G[ cad[0] ][ cad[1] ] = G[ cad[1] ][ cad[0] ] = true; for(char i='A'; i<=N ;i++) { if(vis[i]) continue; dfs(i); r++; } printf("%dn", r); } }
Scoreboards ACM ICPC 2012 South America/South
Scoreboards ACM ICPC 2012 South America/South
Bolivia (link)
Peru (link)
Chile (link)
Colombia Venezuela (link)
Brazil Final (link)
Solucion del Problema Fibonacci Words
En el pasado Nacional en Bolivia se planteo el problema D del mundial ACM ICPC 2012 el cual tiene una solución explicada por Misof en el siguiente link.
Ranking 2do Online Nacional – Bolivia 2012
ACM ICPC Latin America 2011 – J – Jupiter Attacks!
This problem is a case of RMQ or Interval Trees.
For join two ranges:
[latexpage][ quicklatex{size=20} R_a + R_b]
[ quicklatex{size=20} (B^0f_7 + B^1f_6 + B^2f_5) cup (B^0f_4 + B^1f_3 + B^2f_2) ]
[ quicklatex{size=20} (B^0f_7 + B^1f_6 + B^2f_5) + (B^0f_4 + B^1f_3 + B^2f_2)B^3 ]
[ quicklatex{size=20} B^0f_7 + B^1f_6 + B^2f_5 + B^3f_4 + B^4f_3 + B^5f_2 ]
With that formula we can pre-calculate some intervals and the intervals can join for solve queries, this my implementation.
/* * @author: vudduu - Edwin Guzman * @problem: Problem J - Jupiter Attacks! * @contest: ACM ICPC Latin America Regional 2011 */ #include <iostream> #include <sstream> #include <utility> #include <cstdlib> #include <cstdio> #include <cctype> #include <cmath> #include <functional> #include <algorithm> #include <numeric> #include <string> #include <vector> #include <queue> #include <stack> #include <list> #include <map> #include <set> #include <stdio.h> #include <string.h> using namespace std; #define FOR(i,a,b) for(int i=(a),_##i=(b);i<_##i;++i) #define F(i,a) FOR(i,0,a) #define ALL(x) x.begin(),x.end() #define PB push_back #define MP make_pair #define S size() typedef long long LL; LL T[400000], MOD, B[100005]; void insert(int i, int v, int it, int ini, int end){ if(ini == end){ T[it] = v % MOD; return; } int le = it<<1, ri = le+1, mid = (ini+end)>>1; if(i <= mid) insert(i, v, le, ini, mid); else insert(i, v, ri, mid+1, end); T[it] = ((( T[le]*B[end-mid] ) % MOD) + T[ri]) % MOD; } LL functionH(int x, int y, int it, int ini, int end){ if(x == ini && y == end) return T[it]; int le = it<<1, ri = le+1, mid = (ini+end)>>1; if(y <= mid) return functionH(x, y, le, ini, mid); else if(x > mid) return functionH(x, y, ri, mid+1, end); return ((( functionH(x, mid, le, ini, mid)*B[y-mid] ) % MOD) + functionH(mid+1, y, ri, mid+1, end)) % MOD; } int main(){ int b, p, l, n, x, y; char op; scanf("%d %d %d %d", &b, &p, &l, &n); while(b){ memset(T, 0, sizeof(T)); memset(B, 0, sizeof(B)); B[0] = 1; MOD = p; FOR(i, 1, 100000) B[i] = (B[i-1]*LL(b)) % MOD; F(i, n){ cin>>op>>x>>y; if(op == 'E') insert(x, y, 1, 1, l); else printf("%lldn", functionH(x, y, 1, 1, l)); } printf("-n"); scanf("%d %d %d %d", &b, &p, &l, &n); } }