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

       int answer=0;

       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;

           }

           answer+=delta;

       }

       cout<<answer<<endl;

    }

}

 

[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 v,int c,int d)

{

     top->v=v,top->c=c,top->d=d,top->n=adj[u],adj[u]=top++;

     top->v=u,top->c=0,top->d=-d,top->n=adj[v],adj[v]=top++;

     adj[u]->b=adj[v];

     adj[v]->b=adj[u];

}

int min_cost_flow(int n,int t)

{

    int flow=0,cost=0;

    for (;;)

    {

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

        inq[q[head=tail=0]=S]=true;

        d[S]=0;

        p[S]=0;

        while (head<=tail)

        {

              int u;

              inq[u=q[(head++)%MAXV]]=false;

              for (edge i=adj[u];i;i=i->n)

                  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)

    {

       int answer=-1,i=0;

       if (t==n)

       {

           source[0]=true;

           int get=result(t-1);

           if (get>answer) answer=get;

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

                  if (get>answer) answer=get;

                  source[i]=false;

              }

              i++;

           }

       }

       return answer;

    }

    else

    {

       memset(adj,0,sizeof(adj));

       top=pool;

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

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

           add_edge(u[i]+V,v[i],1,0),

           add_edge(v[i]+V,u[i],1,0);

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

           add_edge(i,i+V,1,price[i]);

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

           if (source[i]) add_edge(S,mine[i],1,0);

           else add_edge(mine[i]+V,T,1,0);

       return total_price-min_cost_flow(n,total_price);

    }

}

 

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

You has solved this problem :-) 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%
You has solved this problem :-) 3666 THE MATRIX PROBLEM 2010 Asia Regional Harbin (1009/3915)25.77%
You has solved this problem :-) 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%
You has solved this problem :-) 3720 Arranging Your Team 2010 Asia Tianjin Regional Contest (123/394)31.22%
You has solved this problem :-) 3721 Building Roads 2010 Asia Tianjin Regional Contest (93/282)32.98%
You has solved this problem :-) 3722 Card Game 2010 Asia Tianjin Regional Contest (184/445)41.35%
You has solved this problem :-) 3723 Delta Wave 2010 Asia Tianjin Regional Contest (76/195)38.97%
You has solved this problem :-) 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%
You has solved this problem :-) 3727 Jewel 2010 Asia Tianjin Regional Contest (46/291)15.81%
  3728 Hyperspace Travel 2010 Asia Tianjin Regional Contest (8/89)8.99%
You has solved this problem :-) 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%
You has solved this problem :-) 4052 Adding New Machine GUAN, Yao 2011 Asia Dalian Regional Contest (103/520)19.81%
You has solved this problem :-) 4053 The Last Puzzle WANG, Yelei 2011 Asia Dalian Regional Contest (59/442)13.35%
You has solved this problem :-) 4054 Hexadecimal View WU, Zejun 2011 Asia Dalian Regional Contest (303/734)41.28%
You has solved this problem :-) 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%
You has solved this problem :-) 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%
You has solved this problem :-) 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%
You has solved this problem :-) 4081 Qin Shi Huang’s National Road System 2011 Asia Beijing Regional Contest (310/818)37.90%
You has solved this problem :-) 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%
You has solved this problem :-) 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%
You has solved this problem :-) 4087 ALetter to Programmers 2011 Asia Beijing Regional Contest (94/316)29.75%
  4088 Healing 2011 Asia Beijing Regional Contest (0/16)0.00%
You has solved this problem :-) 4089 Activation 2011 Asia Beijing Regional Contest (170/503)33.80%
You has solved this problem :-) 4090 GemAnd Prince 2011 Asia Beijing Regional Contest (133/375)35.47%
You has solved this problem :-) 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%
You has solved this problem :-) 4096 Universal Question Answering System 2011 Asia Shanghai Regional Contest (96/424)22.64%
You has solved this problem :-) 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%
You has solved this problem :-) 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%
You has solved this problem :-) 4111 Alice and Bob 2011 Asia ChengDu Regional Contest (216/608)35.53%
You has solved this problem :-) 4112 Break the Chocolate 2011 Asia ChengDu Regional Contest (565/1745)32.38%
You has solved this problem :-) 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%
You has solved this problem :-) 4115 Eliminate the Conflict 2011 Asia ChengDu Regional Contest (247/625)39.52%
You has solved this problem :-) 4116 Fruit Ninja 2011 Asia ChengDu Regional Contest (58/422)13.74%
You has solved this problem :-) 4117 GRE Words 2011 Asia ChengDu Regional Contest (213/1203)17.71%
You has solved this problem :-) 4118 Holiday’s Accommodation 2011 Asia ChengDu Regional Contest (270/1028)26.26%
You has solved this problem :-) 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%
You has solved this problem :-) 4121 Xiangqi 2011 Asia Fuzhou Regional Contest (353/1390)25.40%
You has solved this problem :-) 4122 Alice’s mooncake shop 2011 Asia Fuzhou Regional Contest (294/1244)23.63%
You has solved this problem :-) 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%
You has solved this problem :-) 4125 Moles 2011 Asia Fuzhou Regional Contest (274/980)27.96%
You has solved this problem :-) 4126 Genghis Khan the Conqueror 2011 Asia Fuzhou Regional Contest (141/503)28.03%
You has solved this problem :-) 4127 Flood-it! 2011 Asia Fuzhou Regional Contest (121/367)32.97%
You has solved this problem :-) 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: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-28
DESCRIPTION:
$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]

基于连通性状态压缩的动规。
推荐读一下2008年国家集训队论文(陈丹琦《基于连通性状态压缩的动态规划问题》)。

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-25
DESCRIPTION:
$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;
}

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) ;
cout<<j<<char(i==BLACKS?'\n':' ');
}

return
0;
}

URAL1105[Observers Coloring]

离散化+线段树+动规。

CODE:

/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2011-11-22
DESCRIPTION:
$DESCRIPTION
*/

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

#define end first
#define begin second
#define segment first
#define id second
typedef 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)
{

if
(f[st1[root]]<f[v])
st1[root]=v;
if
(L==R) return;
int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
insert1(LL,LR,p,v,Lroot);
insert1(RL,RR,p,v,Rroot);
}
}

int
query1(int L,int R,int p,int root=1)
{

if
(p<L) return 0;
else if
(R<=p) return st1[root];
else

{

int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
int
a=query1(LL,LR,p,Lroot),b=query1(RL,RR,p,Rroot);
return
f[a]>f[b]?a:b;
}
}

void
insert2(int L,int R,int p,int v,int root=1)
{

if
(L<=p&&p<=R)
{

if
(f[st2[root]]-i2d[tid[1][st2[root]]]*2.0<f[v]-i2d[tid[1][v]]*2.0)
st2[root]=v;
if
(L==R) return;
int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
insert2(LL,LR,p,v,Lroot);
insert2(RL,RR,p,v,Rroot);
}
}

int
query2(int L,int R,int p,int root=1)
{

if
(R<p) return 0;
else if
(p<=L) return st2[root];
else

{

int
LL=L,LR=(L+R)>>1,Lroot=root<<1;
int
RL=LR+1,RR=R,Rroot=Lroot|1;
int
a=query2(LL,LR,p,Lroot),b=query2(RL,RR,p,Rroot);
return
f[a]-i2d[tid[1][a]]*2.0>f[b]-i2d[tid[1][b]]*2.0?a:b;
}
}


int
main()
{

cin>>t[0][0]>>t[1][0]
>>
N;
d2i[d2ic++]=make_pair(0,0),
d2i[d2ic++]=make_pair(1,0);
for
(int i=1;i<=N;i++)
{

cin>>one[i].segment.begin>>one[i].segment.end;
one[i].id=i;
}

sort(one+1,one+N+1);
for
(int i=1;i<=N;i++)
{

t[0][i]=one[i].segment.begin,
t[1][i]=one[i].segment.end;
rid[i]=one[i].id;
d2i[d2ic++]=make_pair(0,i),
d2i[d2ic++]=make_pair(1,i);
}

sort(d2i,d2i+d2ic,sort_rule);
for
(int i=0;i<d2ic;i++)
{

if
(i&&t[d2i[i].first][d2i[i].second]!=t[d2i[i-1].first][d2i[i-1].second]) tidc++;
tid[d2i[i].first][d2i[i].second]=tidc;
i2d[tidc]=t[d2i[i].first][d2i[i].second];
}

f[best_id=0]=0;
for
(int i=1;i<=N;i++)
{

int
npre;
double
nf;
npre=0;
nf=i2d[tid[1][i]]-i2d[tid[0][i]];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

npre=query1(0,tidc,tid[0][i]);
nf=i2d[tid[1][i]]-i2d[tid[0][i]]+f[npre];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

npre=query2(0,tidc,tid[0][i]);
nf=f[npre]-i2d[tid[1][npre]]*2.0+i2d[tid[0][i]]+i2d[tid[1][i]];
if
(nf>f[i])
{

pre[i]=npre;
f[i]=nf;
}

if
(f[i]>f[best_id]) best_id=i;
insert1(0,tidc,tid[1][i],i);
insert2(0,tidc,tid[1][i],i);
}

if
(f[best_id]>=(i2d[tid[1][0]]-i2d[tid[0][0]])*2.0/3.0)
{

answer[answerc=1]=best_id;
while
(pre[answer[answerc]])
{

answer[answerc+1]=pre[answer[answerc]];
answerc++;
}

cout<<answerc<<endl;
for
(int i=1;i<=answerc;i++)
cout<<rid[answer[i]]<<endl;
}

else
cout<<0<<endl;
return
0;
}