[The 2009 ACM-ICPC Asia Harbin Regional Contest]G.Fuzzy Google Suggest

字典树。 CODE: #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <cassert> #include <sstream> #include <map> #include <vector> #include <set> using namespace std;   struct Trie {     Trie* f;     Trie* c[26];     int d; }; Trie pool[4*1024*1024]; Trie* top=pool; Trie* root; #define f(x) ((x)-‘a’)   void calc(Trie* p,char* s,int d,set<Trie*>& get) {     […]

[The 2009 ACM-ICPC Asia Harbin Regional Contest]D.Gold Mines

最小费用流。 CODE: #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <cassert> using namespace std;   #define oo 0x7f7f7f7f #define MAXEDGE 510000 #define MAXV 1002   typedef struct struct_edge* edge; struct struct_edge{int v,c,d;edge n,b;}; struct_edge pool[MAXEDGE]; edge top; int S,T,V; edge adj[MAXV]; int q[MAXV]; bool inq[MAXV]; int head,tail; edge p[MAXV]; int d[MAXV]; void add_edge(int u,int […]

The 2010 Asia Regional Contests

3660 Alice and Bob’s Trip 2010 Asia Regional Harbin (502/2007)25.01%   3661 Assignments 2010 Asia Regional Harbin (455/958)47.49%   3662 3D Convex Hull 2010 Asia Regional Harbin (252/491)51.32%   3663 Power Stations 2010 Asia Regional Harbin (306/1222)25.04%   3664 Permutation Counting 2010 Asia Regional Harbin (378/749)50.47%   3665 Seaside 2010 Asia Regional Harbin (435/647)67.23% 3666 […]

The 2011 Asia Regional Contests

4051 Compress the String HANG, Hang 2011 Asia Dalian Regional Contest (37/198)18.69% 4052 Adding New Machine GUAN, Yao 2011 Asia Dalian Regional Contest (103/520)19.81% 4053 The Last Puzzle WANG, Yelei 2011 Asia Dalian Regional Contest (59/442)13.35% 4054 Hexadecimal View WU, Zejun 2011 Asia Dalian Regional Contest (303/734)41.28% 4055 Number String HONG, Qize 2011 Asia Dalian […]

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]E.Eliminate the Conflict

2-SAT。 CODE: #include <cstring>using namespace std;const int MAXV=20000;const int MAXE=1000000;struct struct_edge{int v;struct_edge* n;};typedef struct_edge* edge;typedef void function(int block,int node);int V;struct_edge pool[MAXE];edge top;edge adj[MAXV];void build_graph(){ top=pool; memset(adj,0,sizeof(adj)); //V; //add_edge(u,v);}void add_edge(int u,int v){ top->v=v,top->n=adj[u],adj[u]=top++;}int stamp;int DFN[MAXV];int LOW[MAXV];int st;int s[MAXV];bool ins[MAXV];bool visited[MAXV];int depth;edge e[MAXV];int root[MAXV];int block;void tarjan(function f){ memset(visited,0,sizeof(visited)); memset(ins,0,sizeof(ins)); st=0; block=0; for (int start=0;start<V;start++) if (!visited[start]) { […]

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]C.Construct the Great Wall

基于连通性状态压缩的动规。 CODE: /*PROGRAM: $PROGRAMAUTHOR: Su JiaoDATE: 2011-11-28DESCRIPTION:$DESCRIPTION*/#include <iostream>#include <cstring>using namespace std;typedef long long int lli;const int MAXN=12;const int MAXSTATE=300001;int N,M;char map[MAXN][MAXN];int sc,SC;int s_[MAXSTATE],S_[MAXSTATE];lli f_[MAXSTATE],F_[MAXSTATE];int* s=s_;int* S=S_;lli* f=f_;lli* F=F_;void qsort(int l,int r){ int i=l,j=r; int mid=S[(l+r)>>1]; while (i<=j) { while (S[i]<mid) i++; while (S[j]>mid) j–; if (i<=j) { int SS; lli SF; SS=S[i],S[i]=S[j],S[j]=SS,SF=F[i],F[i]=F[j],F[j]=SF; i++,j–; } } […]

ACM备忘

做题列表 2011-11-25 基于连通性状态压缩的动规专练 http://acm.timus.ru/problem.aspx?space=1&num=1519 2011-11-26 基于连通性状态压缩的动规专练 http://poj.org/problem?id=1739 http://acm.hdu.edu.cn/showproblem.php?pid=1964 “触宝CooTek杯” USTC Monthly Contest 2011-11-26 http://acm.ustc.edu.cn/ustcoj/contest.php?contest=21 Accepted:BDEH(rank30) 2011-11-28 基于连通性状态压缩的动规专练 http://acm.hdu.edu.cn/showproblem.php?pid=4113 2011-12-01 2-SAT专练 http://acm.hdu.edu.cn/showproblem.php?pid=4115 http://poj.org/problem?id=3207 http://poj.org/problem?id=3678 2011-12-03 http://acm.sgu.ru/problem.php?contest=0&problem=108 http://acm.sgu.ru/problem.php?contest=0&problem=109  中国地质大学(北京)第五届程序设计竞赛现场决赛(网络同步赛) http://acm.cugb.edu.cn/JudgeOnline/showcontest?contest_id=1044 Accepted:ABCDEFGHJ(rank1) 2011-12-10 http://codeforces.com/problemset/problem/135/C 2011-12-15 划分树专练 http://poj.org/problem?id=2104 2012-1-8 http://acm.hdu.edu.cn/showproblem.php?pid=4116 2012-1-21 http://acm.hdu.edu.cn/showproblem.php?pid=4121 http://acm.hdu.edu.cn/showproblem.php?pid=4122 2012-2-23 http://acm.hdu.edu.cn/showproblem.php?pid=4123 2012-2-24 http://acm.hdu.edu.cn/showproblem.php?pid=4125 http://acm.hdu.edu.cn/showproblem.php?pid=4127 2012-2-25 http://acm.hdu.edu.cn/showproblem.php?pid=4082 http://acm.hdu.edu.cn/showproblem.php?pid=4087 2012-2-27 http://acm.hdu.edu.cn/showproblem.php?pid=4081 http://acm.hdu.edu.cn/showproblem.php?pid=4089 2012-2-29 http://acm.hdu.edu.cn/showproblem.php?pid=3720 2012-3-1 http://acm.hdu.edu.cn/showproblem.php?pid=3722 http://acm.hdu.edu.cn/showproblem.php?pid=3727 […]

URAL1519[Formula 1]

基于连通性状态压缩的动规。 推荐读一下2008年国家集训队论文(陈丹琦《基于连通性状态压缩的动态规划问题》)。 CODE: /*PROGRAM: $PROGRAMAUTHOR: Su JiaoDATE: 2011-11-25DESCRIPTION:$DESCRIPTION*/#include <iostream>#include <cstring>using namespace std;typedef long long int lli;const int MAXN=12;const int MAXSTATE=300001;int N,M;char map[MAXN][MAXN];int sc,SC;int s_[MAXSTATE],S_[MAXSTATE];lli f_[MAXSTATE],F_[MAXSTATE];int* s=s_;int* S=S_;lli* f=f_;lli* F=F_;void qsort(int l,int r){ int i=l,j=r; int mid=S[(l+r)>>1]; while (i<=j) { while (S[i]<mid) i++; while (S[j]>mid) j–; if (i<=j) { int SS; lli SF; SS=S[i],S[i]=S[j],S[j]=SS,SF=F[i],F[i]=F[j],F[j]=SF; i++,j–; } […]

URAL1106[Two Teams]

水题。 给一个无向图(可能不连通),求一个子图,要求这个子图是二分图。 CODE: #include <iostream>using namespace std;int N;int adjs[100+1];int adj[100+1][100];int BLACKS;int color[100+1];void dfs(int u,int c){ if (!color[u]) { color[u]=c; if (c==1) BLACKS++; for (int e=0;e<adjs[u];e++) dfs(adj[u][e],-c); }}int main(){ cin>>N; for (int i=1;i<=N;i++) { for (;;) { cin>>adj[i][adjs[i]]; if (adj[i][adjs[i]]) adjs[i]++; else break; } } for (int i=1;i<=N;i++) dfs(i,1); cout<<BLACKS<<endl; for (int i=0,j=0;i<BLACKS;i++) { while (color[++j]!=1) […]

URAL1105[Observers Coloring]

离散化+线段树+动规。 CODE: /*PROGRAM: $PROGRAMAUTHOR: Su JiaoDATE: 2011-11-22DESCRIPTION:$DESCRIPTION*/#include <iostream>#include <utility>#include <algorithm>using namespace std;#define end first#define begin second#define segment first#define id secondtypedef pair<double,double> segment;typedef pair<segment,int> segment_with_id;int N;segment_with_id one[10000+1];double t[2][10000+1];int rid[10000+1];int d2ic;pair<int,int> d2i[20000+2];int tidc;int tid[2][10000+1];double i2d[20000+2];double f[10000+1];int pre[10000+1];int best_id;int st1[(20000+2)*4];int st2[(20000+2)*4];int answerc;int answer[10000+1];bool sort_rule(const pair<int,int>& a,const pair<int,int>& b){ return t[a.first][a.second]<t[b.first][b.second];}void insert1(int L,int R,int p,int v,int root=1){ if (L<=p&&p<=R) […]