#A AC 6min
Greedy
#B AC 67min
BFS

#E AC
SSP and MST

2012.12.2 ACME Training One – The 2012 ACM-ICPC Asia Chengdu Regional Contest[team]

This is my first cooperation with my new teammates, WDP and WHD. Our team is called ACME, which can be understood as AC me, or it original meaning the peak.
#A AC 8min 1 wrong try by WHD
#I AC 17min
It is a typical DP problem.
#B AC 76min 1 wrong try
It is a math problem. WDP told me the meaning of the problem, and I come up with a formula soon.
Let f(p) be p*sum{p^n*(1-p)^i*C(i,n+1)*(n-i);i=0 to n}.
The answer will f(p)+f(1-p).
However for some certain i, p^n*(1-p)^i*C(i,n+1)*(n-i) can be too small, to avoid underflow errors we can calculate ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) instead.
When we use it, we use e^ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) and if ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) is too small we just ignore it.
We come up with a n^1.5*logn algorithm for problem C and got TLE. We also used the algorithm proved to be right to solve problem K, but didn’t get AC. I think it must be some bugs when facing edge cases.

[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)

{

if (p)

{

if (*s)

{

calc(p->c[f(*s)],s+1,d,get);

if (d)

{

for (int i=0;i<26;i++)

calc(p->c[i],s,d-1,get);

for (int i=0;i<26;i++)

calc(p,s+1,d-1,get);

for (int i=0;i<26;i++)

calc(p->c[i],s+1,d-1,get);

}

}

else get.insert(p);

}

}

int main()

{

root=top++;

int n,m;

cin>>n;

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

{

char db[16];

cin>>db;

Trie* p=root;

char* s=db;

while (*s)

{

if (!p->c[f(*s)]) top->f=p,p->c[f(*s)]=top++;

p=p->c[f(*s)];

p->d++;

s++;

}

}

cin>>m;

for (int i=0;i<m;i++)

{

char s[1024];

int d;

cin>>s>>d;

set<Trie*> get;

calc(root,s,d,get);

for (set<Trie*>::reverse_iterator it=get.rbegin();it!=get.rend();it++)

{

Trie* p=*it;

int delta=p->d;

while (p!=root)

{

p=p->f;

set<Trie*>::iterator t=get.find(p);

if (t!=get.end()) delta=0;

}

}

}

}

[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;

int q[MAXV];

bool inq[MAXV];

edge p[MAXV];

int d[MAXV];

void add_edge(int u,int v,int c,int d)

{

}

int min_cost_flow(int n,int t)

{

int flow=0,cost=0;

for (;;)

{

memset(d,oo,sizeof(d));

d[S]=0;

p[S]=0;

{

int u;

if (i->c&&d[i->v]>d[u]+i->d)

{

if (!inq[i->v])

inq[q[(++tail)%MAXV]=i->v]=true;

d[i->v]=d[u]+i->d;

p[i->v]=i;

}

}

if (d[T]==oo) break;

else

{

int delta=oo;

for (edge i=p[T];i;i=p[i->b->v])

if (delta>i->c) delta=i->c;

for (edge i=p[T];i;i=p[i->b->v])

i->c-=delta,i->b->c+=delta;

flow+=delta;

cost+=d[T]*delta;

}

}

if (flow!=n) return 1+t;

return cost;

}

int E;

int u[MAXEDGE],v[MAXEDGE];

int n;

int mine[MAXV];

int price[MAXV];

bool source[MAXV];

int total_price;

int result(int t)

{

if (t)

{

if (t==n)

{

source[0]=true;

int get=result(t-1);

source[0]=false;

}

else

{

int k=n-t;

while (k) if (source[i++]) k–;

while (i<n*2)

{

if (!source[i])

{

source[i]=true;

int get=result(t-1);

source[i]=false;

}

i++;

}

}

}

else

{

top=pool;

S=V+V,T=V+V+1;

for (int i=0;i<E;i++)

for (int i=0;i<V;i++)

for (int i=0;i<n*2;i++)

}

}

int main()

{

int T;

cin>>T;

for (int t=0;t<T;t++)

{

cin>>V>>E;

for (int i=0;i<E;i++)

cin>>u[i]>>v[i];

cin>>n;

for (int i=0;i<n*2;i++) cin>>mine[i];

total_price=0;

for (int i=0;i<V;i++) cin>>price[i],total_price+=price[i];

cout<<result(n)<<endl;

}

}

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 MATRIX PROBLEM 2010 Asia Regional Harbin (1009/3915)25.77% 3667 Transportation 2010 Asia Regional Harbin (492/1275)38.59% 3668 Volume 2010 Asia Regional Harbin (237/805)29.44% 3669 Cross the Wall 2010 Asia Regional Harbin (520/2942)17.68% 3680 Naughty fairies 2010 Asia Hangzhou Regional Contest (104/767)13.56% 3681 Prison Break 2010 Asia Hangzhou Regional Contest (370/1461)25.33% 3682 To Be an Dream Architect 2010 Asia Hangzhou Regional Contest (356/1292)27.55% 3683 Gomoku 2010 Asia Hangzhou Regional Contest (182/713)25.53% 3684 Gunshots 2010 Asia Hangzhou Regional Contest (64/482)13.28% 3685 Rotational Painting 2010 Asia Hangzhou Regional Contest (352/1204)29.24% 3686 Traffic Real Time Query System 2010 Asia Hangzhou Regional Contest (150/873)17.18% 3687 National Day Parade 2010 Asia Hangzhou Regional Contest (338/801)42.20% 3688 Searchlights 2010 Asia Hangzhou Regional Contest (74/269)27.51% 3689 Infinite monkey theorem 2010 Asia Hangzhou Regional Contest (299/520)57.50% 3690 Knight’s Problem 2010 Asia Fuzhou Regional Contest (0/264)0.00% 3691 Nubulsa Expo 2010 Asia Fuzhou Regional Contest (102/249)40.96% 3692 Shade of Hallelujah Mountain 2010 Asia Fuzhou Regional Contest (61/273)22.34% 3693 Math teacher’s homework 2010 Asia Fuzhou Regional Contest (27/91)29.67% 3694 Fermat Point in Quadrangle 2010 Asia Fuzhou Regional Contest (113/762)14.83% 3695 Computer Virus on Planet Pandora 2010 Asia Fuzhou Regional Contest (252/926)27.21% 3696 Farm Game 2010 Asia Fuzhou Regional Contest (74/161)45.96% 3697 Selecting courses 2010 Asia Fuzhou Regional Contest (111/502)22.11% 3698 Let the light guide us 2010 Asia Fuzhou Regional Contest (73/240)30.42% 3699 A hard Aoshu Problem 2010 Asia Fuzhou Regional Contest (134/264)50.76% 3709 Balanced Number GAO, Yuan 2010 Asia Chengdu Regional Contest (134/385)34.81% 3710 Battle over Cities GUAN, Yao 2010 Asia Chengdu Regional Contest (18/60)30.00% 3711 Binary Number CAO, Peng 2010 Asia Chengdu Regional Contest (261/382)68.32% 3712 Detector Placement GUAN, Yao 2010 Asia Chengdu Regional Contest (43/151)28.48% 3713 Double Maze GAO, Yuan 2010 Asia Chengdu Regional Contest (129/342)37.72% 3714 Error Curves LIN, Yue 2010 Asia Chengdu Regional Contest (258/679)38.00% 3715 Go Deeper CAO, Peng 2010 Asia Chengdu Regional Contest (253/663)38.16% 3716 Jenga XIAO, Dong 2010 Asia Chengdu Regional Contest (10/37)27.03% 3717 Rescue HANG, Hang 2010 Asia Chengdu Regional Contest (30/113)26.55% 3718 Similarity LIN, Yue 2010 Asia Chengdu Regional Contest (197/473)41.65% 3719 Snooker Referee XIAO, Dong 2010 Asia Chengdu Regional Contest (1/16)6.25% 3720 Arranging Your Team 2010 Asia Tianjin Regional Contest (123/394)31.22% 3721 Building Roads 2010 Asia Tianjin Regional Contest (93/282)32.98% 3722 Card Game 2010 Asia Tianjin Regional Contest (184/445)41.35% 3723 Delta Wave 2010 Asia Tianjin Regional Contest (76/195)38.97% 3724 Encoded Barcodes 2010 Asia Tianjin Regional Contest (210/656)32.01% 3725 Farm 2010 Asia Tianjin Regional Contest (2/14)14.29% 3726 Graph and Queries 2010 Asia Tianjin Regional Contest (41/321)12.77% 3727 Jewel 2010 Asia Tianjin Regional Contest (46/291)15.81% 3728 Hyperspace Travel 2010 Asia Tianjin Regional Contest (8/89)8.99% 3729 I’m Telling the Truth 2010 Asia Tianjin Regional Contest (215/425)50.59%

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 Regional Contest (271/629)43.08% 4056 Draw a Mess HU, Jun 2011 Asia Dalian Regional Contest (79/402)19.65% 4057 Rescue the Rabbit HONG, Qize 2011 Asia Dalian Regional Contest (186/648)28.70% 4058 Advanture of Xiaoxingxing GUAN, Yao 2011 Asia Dalian Regional Contest (2/46)4.35% 4059 The Boss on Mars ZHANG, Chao 2011 Asia Dalian Regional Contest (226/779)29.01% 4060 Chess Board GUAN, Yao 2011 Asia Dalian Regional Contest (30/130)23.08% 4081 Qin Shi Huang’s National Road System 2011 Asia Beijing Regional Contest (310/818)37.90% 4082 Hou Yi’s secret 2011 Asia Beijing Regional Contest (268/821)32.64% 4083 Three Kingdom Chess 2011 Asia Beijing Regional Contest (26/140)18.57% 4084 The Voyages of Zheng He 2011 Asia Beijing Regional Contest (0/0)0.00% 4085 Peach Blossom Spring 2011 Asia Beijing Regional Contest (236/637)37.05% 4086 Harry Potter and the holy banquet 2011 Asia Beijing Regional Contest (1/15)6.67% 4087 ALetter to Programmers 2011 Asia Beijing Regional Contest (94/316)29.75% 4088 Healing 2011 Asia Beijing Regional Contest (0/16)0.00% 4089 Activation 2011 Asia Beijing Regional Contest (170/503)33.80% 4090 GemAnd Prince 2011 Asia Beijing Regional Contest (133/375)35.47% 4091 Zombie’s Treasure Chest 2011 Asia Shanghai Regional Contest (494/2479)19.93% 4092 Yummy Triangular Pizza 2011 Asia Shanghai Regional Contest (26/48)54.17% 4093 Xavier is Learning to Count 2011 Asia Shanghai Regional Contest (28/199)14.07% 4094 Winmine.exe 2011 Asia Shanghai Regional Contest (0/21)0.00% 4095 Very Boring Homework 2011 Asia Shanghai Regional Contest (26/86)30.23% 4096 Universal Question Answering System 2011 Asia Shanghai Regional Contest (96/424)22.64% 4097 Triangles and Quadrangle 2011 Asia Shanghai Regional Contest (166/733)22.65% 4098 Share the Cakes 2011 Asia Shanghai Regional Contest (4/121)3.31% 4099 Revenge of Fibonacci 2011 Asia Shanghai Regional Contest (215/950)22.63% 4100 Quelling Blade 2011 Asia Shanghai Regional Contest (26/54)48.15% 4111 Alice and Bob 2011 Asia ChengDu Regional Contest (216/608)35.53% 4112 Break the Chocolate 2011 Asia ChengDu Regional Contest (565/1745)32.38% 4113 Construct the Great Wall 2011 Asia ChengDu Regional Contest (24/77)31.17% 4114 Disney’s FastPass 2011 Asia ChengDu Regional Contest (220/867)25.37% 4115 Eliminate the Conflict 2011 Asia ChengDu Regional Contest (247/625)39.52% 4116 Fruit Ninja 2011 Asia ChengDu Regional Contest (58/422)13.74% 4117 GRE Words 2011 Asia ChengDu Regional Contest (213/1203)17.71% 4118 Holiday’s Accommodation 2011 Asia ChengDu Regional Contest (270/1028)26.26% 4119 Isabella’s Message 2011 Asia ChengDu Regional Contest (251/759)33.07% 4120 Ji-Tu Problem 2011 Asia ChengDu Regional Contest (30/189)15.87% 4121 Xiangqi 2011 Asia Fuzhou Regional Contest (353/1390)25.40% 4122 Alice’s mooncake shop 2011 Asia Fuzhou Regional Contest (294/1244)23.63% 4123 Bob’s Race 2011 Asia Fuzhou Regional Contest (253/841)30.08% 4124 My World Cup 2011 Asia Fuzhou Regional Contest (10/13)76.92% 4125 Moles 2011 Asia Fuzhou Regional Contest (274/980)27.96% 4126 Genghis Khan the Conqueror 2011 Asia Fuzhou Regional Contest (141/503)28.03% 4127 Flood-it! 2011 Asia Fuzhou Regional Contest (121/367)32.97% 4128 Running relay 2011 Asia Fuzhou Regional Contest (120/523)22.94% 4129 Porcelain Exhibitions 2011 Asia Fuzhou Regional Contest (16/55)29.09% 4130 Shadow 2011 Asia Fuzhou Regional Contest (8/43)18.60%

[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])         {            depth=0;            root[depth]=start;            e[depth]=adj[root[depth]];            DFN[root[depth]]=LOW[root[depth]]=++stamp;            ins[s[st++]=root[depth]]=true;            visited[root[depth]]=true;            do            {              if (e[depth])              {                 if (!visited[e[depth]->v])                 {                    int depth_=depth+1;                    e[depth_]=adj[root[depth_]=e[depth]->v];                    DFN[root[depth_]]=LOW[root[depth_]]=++stamp;                    ins[s[st++]=root[depth_]]=true;                    visited[root[depth_]]=true;                    e[depth]=e[depth]->n;                    depth++;                 }                 else if (ins[e[depth]->v])                 {                     if (LOW[root[depth]]>DFN[e[depth]->v])                        LOW[root[depth]]=DFN[e[depth]->v];                     e[depth]=e[depth]->n;                 }                 else e[depth]=e[depth]->n;              }              else              {                  if (LOW[root[depth]]==DFN[root[depth]])                  {                     do                     {                       ins[s[--st]]=false;                       f(block,s[st]);                     }                     while (s[st]!=root[depth]);                     block++;                  }                  if (depth>0)                  {                     int depth_=depth-1;                     if (LOW[root[depth_]]>LOW[root[depth]])                        LOW[root[depth_]]=LOW[root[depth]];                  }                  depth--;              }            }            while (depth>=0);         }}typedef struct_edge struct_list;typedef edge list;int block_id[MAXV];struct_list spool[MAXV];list stop;list set[MAXV];#define T(x) ((x)<<1)#define F(x) (((x)<<1)|1)void build_2sat(){     stop=spool;     memset(set,0,sizeof(set));     build_graph();     //add_edge(u,v);}void function_2sat(int block,int node){     block_id[node]=block;     stop->v=node,stop->n=set[node],set[node]=stop++;}#include <iostream>using namespace std;bool possible_2sat(){     tarjan(function_2sat);     for (int i=0;i<(V>>1);i++)         if (block_id[T(i)]==block_id[F(i)])            return false;     return true;}int N,M;int B[MAXV];int main(){    int T;    cin>>T;    for (int t=1;t<=T;t++)    {        cin>>N>>M;        V=N*2;        build_2sat();        for (int i=0;i<N;i++)            cin>>B[i],B[i]--;        for (int i=0;i<M;i++)        {            int a,b,k;            cin>>a>>b>>k;            a--,b--;            if (k)            {               if (B[a]==B[b])               {                  add_edge(T(a),F(b));                  add_edge(F(b),T(a));                  add_edge(F(a),T(b));                  add_edge(T(b),F(a));               }               else if ((B[a]+1)%3==B[b]) add_edge(F(a),F(b));               else add_edge(F(b),F(a));            }            else            {                if (B[a]==B[b])                {                   add_edge(T(a),T(b));                   add_edge(T(b),T(a));                   add_edge(F(a),F(b));                   add_edge(F(b),F(a));                }                else if ((B[a]+1)%3==B[b])                {                     add_edge(F(a),T(b));                     add_edge(T(b),F(a));                     add_edge(T(a),F(a));                     add_edge(F(b),T(b));                }                else                {                    add_edge(F(b),T(a));                    add_edge(T(a),F(b));                    add_edge(T(b),F(b));                    add_edge(F(a),T(a));                }            }        }        cout<<"Case #"<<t<<": "<<(possible_2sat()?"yes":"no")<<endl;    }}`

[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--;           }     }     if (l<j) qsort(l,j);     if (i<r) qsort(i,r);}lli min(lli a,lli b){    return a<b?a:b;}int run(){    cin>>N>>M;    int lasti=0,lastj=0;    for (int i=1;i<=N;i++)        for (int j=1;j<=M;j++)        {            cin>>map[i][j];            if (map[i][j]=='o') lasti=i,lastj=j;        }    N++,M++;    lli answer=(~0u);    SC=0;    S[SC]=0;    F[SC]=0;    SC++;    for (int i=0;i<N;i++)    {        for (int j=0;j<M;j++)        {            int* ss;            lli* sf;            ss=s,s=S,S=ss,sf=f,f=F,F=sf;            sc=SC,SC=0;            #define getp(state,p) (((state)>>((p)<<1))&3)            #define replace(state,p,n) (((state)&(~(3<<((p)<<1))))|n<<((p)<<1))            #define getl(state) getp(state,j)            #define getu(state) getp(state,j+1)            #define replacedr(state,d,r) replace(replace(state,j,d),j+1,r)            #define getcl(state,p,ns)\            do\            {\              ns=replacedr(state,0,0);\              int get=2;\              for (int i=p+2;i<=M;i++)\              {\                  if (getp(ns,i)==1) get++;\                  else if (getp(ns,i)==2) get--;\                  if (get==1)\                  {\                     ns=replace(ns,i,1);\                     break;\                  }\              }\            }\            while (false)            #define getcr(state,p,ns)\            do\            {\              ns=replacedr(state,0,0);\              int get=2;\              for (int i=p-1;i>=0;i--)\              {\                  if (getp(ns,i)==2) get++;\                  else if (getp(ns,i)==1) get--;\                  if (get==1)\                  {\                     ns=replace(ns,i,2);\                     break;\                  }\              }\            }\            while (false)            for (int si=0;si<sc;si++)            {                bool out=true;                for (int p=0;p<=j;p++)                    if (getp(s[si],p)) out=!out;                if (map[i][j]=='o'&&out) continue;                if (map[i][j]=='x'&&!out) continue;                int l=getl(s[si]),u=getu(s[si]);                if (l&&u)                {                   int ns;                   if (l==2&&u==1) ns=replacedr(s[si],0,0);                   else if (l==1&&u==1) getcl(s[si],j,ns);                   else if (l==2&&u==2) getcr(s[si],j,ns);                   else                   {                       if (((i>lasti)||(i==lasti&&j>=lastj))&&replacedr(s[si],0,0)==0) answer=min(answer,f[si]);                         continue;                   }                   S[SC]=ns;                   F[SC]=f[si];                   SC++;                }                else if (l)                {                     int ns;                     ns=replacedr(s[si],l,u);                     S[SC]=ns;                     F[SC]=f[si]+1;                     SC++;                     ns=replacedr(s[si],u,l);                     S[SC]=ns;                     F[SC]=f[si]+1;                     SC++;                }                else if (u)                {                     int ns;                     ns=replacedr(s[si],l,u);                     S[SC]=ns;                     F[SC]=f[si]+1;                     SC++;                     ns=replacedr(s[si],u,l);                     S[SC]=ns;                     F[SC]=f[si]+1;                     SC++;                }                else                {                     int ns;                                          //there can be a box without plug                     ns=replacedr(s[si],0,0);                     S[SC]=ns;                     F[SC]=f[si];                     SC++;                                          ns=replacedr(s[si],1,2);                     S[SC]=ns;                     F[SC]=f[si]+2;                     SC++;                }            }            {                qsort(0,SC-1);                int RSC=0;                int i=0;                while (i<SC)                {                      int j=i+1;                      while (j<SC&&S[i]==S[j]) F[i]=min(F[j],F[i]),j++;                      S[RSC]=S[i];                      F[RSC++]=F[i];                      i=j;                }                SC=RSC;            }        }        {            int RSC=0;            int i=0;            while (i<SC)            {                  while (i<SC&&getp(S[i],M)) i++;                  if (i<SC) S[RSC]=S[i]<<(1<<1),F[RSC++]=F[i++];            }            SC=RSC;        }    }    static int casen;    cout<<"Case #"<<++casen<<": "<<int(answer)<<endl;    return 0;}int main(){    int T;    for (cin>>T;T;T--) run();}`

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
2012-3-3
http://acm.hdu.edu.cn/showproblem.php?pid=4057
2012-3-4
http://acm.hdu.edu.cn/showproblem.php?pid=4053
2012-6-3
Polya定理的应用专练
http://poj.org/problem?id=1286
http://poj.org/problem?id=2409
http://poj.org/problem?id=2154
http://acm.hdu.edu.cn/showproblem.php?pid=3923

1.一般图的最大基数匹配(done)
2. 基于连通性状态压缩的动规(done)
3.2-SAT(done)
4.划分树(doing)
5.Polya定理的应用(done)

URAL1519[Formula 1]

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--;           }     }     if (l<j) qsort(l,j);     if (i<r) qsort(i,r);}int main(){    cin>>N>>M;    int lasti=-1,lastj=-1;    for (int i=0;i<N;i++)        for (int j=0;j<M;j++)        {            cin>>map[i][j];            if (map[i][j]!='*') lasti=i,lastj=j;        }        lli answer=0;        SC=0;    S[SC]=0;    F[SC]=1;    SC++;    for (int i=0;i<N;i++)    {        for (int j=0;j<M;j++)        {            int* ss;            lli* sf;            ss=s,s=S,S=ss,sf=f,f=F,F=sf;            sc=SC,SC=0;                        #define getp(state,p) (((state)>>((p)<<1))&3)            #define replace(state,p,n) (((state)&(~(3<<((p)<<1))))|n<<((p)<<1))            #define getl(state) getp(state,j)            #define getu(state) getp(state,j+1)            #define replacedr(state,d,r) replace(replace(state,j,d),j+1,r)            #define getcl(state,p,ns)\            do\            {\              ns=replacedr(state,0,0);\              int get=2;\              for (int i=p+2;i<=M;i++)\              {\                  if (getp(ns,i)==1) get++;\                  else if (getp(ns,i)==2) get--;\                  if (get==1)\                  {\                     ns=replace(ns,i,1);\                     break;\                  }\              }\            }\            while (false)            #define getcr(state,p,ns)\            do\            {\              ns=replacedr(state,0,0);\              int get=2;\              for (int i=p-1;i>=0;i--)\              {\                  if (getp(ns,i)==2) get++;\                  else if (getp(ns,i)==1) get--;\                  if (get==1)\                  {\                     ns=replace(ns,i,2);\                     break;\                  }\              }\            }\            while (false)            if (map[i][j]=='*')            {               for (int si=0;si<sc;si++)               {                   int l=getl(s[si]),u=getu(s[si]);                   if (!(l|u))                   {                      int ns;                      ns=replacedr(s[si],0,0);                      S[SC]=ns;                      F[SC]=f[si];                      SC++;                   }               }            }            else            {                for (int si=0;si<sc;si++)                {                    int l=getl(s[si]),u=getu(s[si]);                    if (l&&u)                    {                       int ns;                       if (l==2&&u==1) ns=replacedr(s[si],0,0);                       else if (l==1&&u==1) getcl(s[si],j,ns);                       else if (l==2&&u==2) getcr(s[si],j,ns);                       else                        {                                                        if ((!replacedr(s[si],0,0))&&i==lasti&&j==lastj) answer+=f[si];                            continue;                       }                       S[SC]=ns;                       F[SC]=f[si];                       SC++;                    }                    else if (l)                    {                         int ns;                         ns=replacedr(s[si],l,u);                         S[SC]=ns;                         F[SC]=f[si];                         SC++;                         ns=replacedr(s[si],u,l);                         S[SC]=ns;                         F[SC]=f[si];                         SC++;                    }                    else if (u)                    {                         int ns;                         ns=replacedr(s[si],l,u);                         S[SC]=ns;                         F[SC]=f[si];                         SC++;                         ns=replacedr(s[si],u,l);                         S[SC]=ns;                         F[SC]=f[si];                         SC++;                    }                    else                    {                         int ns;                         /*                         //there can not be a box without plug                         ns=replacedr(s[si],0,0);                         S[SC]=ns;                         F[SC]=f[si];                         SC++;                         */                         ns=replacedr(s[si],1,2);                         S[SC]=ns;                         F[SC]=f[si];                         SC++;                    }                }            }            {                qsort(0,SC-1);                int RSC=0;                int i=0;                while (i<SC)                {                      int j=i+1;                      while (j<SC&&S[i]==S[j]) F[i]+=F[j],j++;                      S[RSC]=S[i];                      F[RSC++]=F[i];                      i=j;                }                SC=RSC;            }        }        {            int RSC=0;            int i=0;            while (i<SC)            {                  while (i<SC&&getp(S[i],M)) i++;                  if (i<SC) S[RSC]=S[i]<<(1<<1),F[RSC++]=F[i++];            }            SC=RSC;        }    }    cout<<answer<<endl;}`