分类存档：默认分类

[POI2005]Sza-Template 二分+KMP

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1535

【算法分析】

这是一个好题。

我讲讲我的做法。

首先模板一定是整个串的前缀，同时也是整个串的后缀。

那么可以先利用KMP求出所有满足这一条件的位置。

在满足了这一条件以后，答案就满足单调性了。

为什么？反正尾巴是肯定可以匹配的。然后那么多了总比小的可行方案多。。。

哎，难以言表啊。

然后就是二分答案+KMP判定了。

如果KMP比较熟练的话，应该不成问题。

【时间复杂度】O(n lg n)

【空间复杂度】O(n)

【其它】

1Y。我只想说，常数才是王道。

虽然利用扩展KMP+双向链表可以在O(n)做出来，但是常数好像比较沙茶。。。

强力Orz oimaster！！！

1 10278 Matt 3368K 30MS Pascal 1.00K 2010-02-28 13:07:34 2 9414 Matt 3368K 60MS Pascal 1.21K 2010-02-12 22:51:48 3 13806 oimaster 2680K 76MS G++ 0.43K 2010-03-18 22:12:04 4 10277 Matt 3372K 76MS Pascal 1.00K 2010-02-28 13:07:07 5 15893 sos 3652K 91MS G++ 1.02K 2010-03-25 19:54:03 6 25970 luojiewei 11096K 107MS Pascal 0.85K 2010-05-26 14:47:59 7 31701 edward_mj 3524K 121MS G++ 0.82K 2010-06-20 11:37:53 8 16133 sos 4624K 137MS G++ 1.35K 2010-03-26 17:18:43 9 16136 sos 4624K 138MS G++ 1.38K 2010-03-26 17:26:48 10 14202 Sachs 11180K 153MS Pascal 1.56K 2010-03-20 15:36:15 11 29479 zxytim 12316K 153MS G++ 1.45K 2010-06-13 12:06:35 12 29475 hyf042 12516K 154MS G++ 1.54K 2010-06-13 12:04:10 13 13690 wu3412790 11180K 170MS Pascal 1.22K 2010-03-18 12:22:58 14 7421 tracyhenry 5344K 185MS Pascal 1.81K 2009-10-23 18:20:52 15 14204 Jason 11692K 186MS Pascal 1.02K 2010-03-20 15:37:19 16 11454 Jason 11696K 200MS Pascal 1.02K 2010-03-05 14:32:44 17 29484 sonicmisora 12324K 201MS G++ 1.13K 2010-06-13 12:09:57 18 5437 pyf 14712K 231MS Pascal 2.47K 2009-07-09 14:28:26 19 9559 curimit 12900K 246MS Pascal 1.58K 2010-02-17 18:22:06 20 16179 AekdyCoin 10888K 261MS Pascal 2.33K 2010-03-26 19:00:19

【CODE】

#include const int N=500005;
int n;
int next[N],L[N];
char S[N];

bool Can(int Limit){
     int i,j=next[Limit];
     for (i=Limit+1;i<=n;i++){
         while (j && S[j+1]!=S[i]) j=next[j];
         if (S[j+1]==S[i]) j++;
         if (!j) return false;
         if (j==Limit) j=next[j];
     }
}

int main(){
    int i,j,l,r,mid,tot;
    scanf("%s",S+1);
    n=strlen(S+1);
    next[1]=j=tot=0;
    for (i=2;i<=n;i++){
      while (j && S[j+1]!=S[i]) j=next[j];
      if (S[j+1]==S[i]) j++;
      next[i]=j;
    }
    for (i=n;i;i=next[i]) L[++tot]=i;
    l=1; r=tot;
    while (l          mid=(l+r+1)/2;
          if (Can(L[mid])) l=mid;
                      else r=mid-1;
    }
    printf("%dn",L[l]);
}

[USACO2010 Hol 【cowwar】]最大的三重匹配，最大流

【题目链接】

http://ace.delos.com/ioiupload?init=1&a=nejLCFTaRn6

http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1779

【题目大意】

有n个点，m条边的无向图。

上面的点一开始要么是J牛，要么是T牛，要么是E，表示没有牛。

然后J牛有两种选择：

1、直接攻击自己附近的一只T牛，然后停住永远不动。

2、向邻近的点走一步，然后攻击or不攻击附近的一只T牛，然后停住永远不动。

特别得，

J牛不能跑进任何一只本身有牛的点。

T牛不会动。并且只能被打死一次。然后就算他死了，J牛也不能进入他的领土（他的灵魂开无敌了）!!!

然后他们动都有先后顺序，然后问最多能打死多少只T牛。

【算法分析】

建立一个4层的图。

第一层，给每只J牛赋予1的流量。

第二层，每只J牛要么停在原来这个点，要么走一步，到达另外一个点。

流量可以跟随这只牛的脚步走过去。

当然，到达的点不能是T牛占得点。

第三层，从第二层的对应点中引一条容量为1的边到第三层的对应点，那么就对应于：每个点只能有一只牛。

第四层，那些牛们“站位”已经到了最好状态，开始攻击T牛，即每个“非T牛”的点像每只T牛点连一个容量为1的边，然后T牛们就可以向汇点连容量为1的边。

这样，就完成了最终的匹配。

这个用最大流实现即可。输出方案利用残余图不难得出。当然，我写得是无方案版。

【CODE】

/*
ID:jie22221
TASK:cowwar
LANG:C++
*/
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define clr(a) memset(a,0,sizeof(a))
const int N=30000;
const int INF=1000000000;
struct edge{int x,y,c;edge *next,*op;};
struct Network_t{
       edge *ls[N],*cur[N];
       int vs,vt,d[N],Flow,Q[N];
      
       void addedge(int x,int y,int c){
            edge *p=(edge*)malloc(sizeof(edge));
            edge *q=(edge*)malloc(sizeof(edge));
            p->x=x; p->y=y; p->c=c; p->next=ls[x]; ls[x]=p; p->op=q;
            q->x=y; q->y=x; q->c=0; q->next=ls[y]; ls[y]=q; q->op=p;
       }
      
       int dfs(int p,int nf){
           if (p==vt) return nf;
           int tmp,FF=0;
           for (edge *&t=cur[p];t;t=t->next)
             if (t->c && d[t->x]+1==d[t->y] && (tmp=dfs(t->y,min(nf,t->c)))){
               FF+=tmp;
               t->c-=tmp; t->op->c+=tmp;
               if (!(nf-=tmp)) break;
             }
           if (!cur[p]) d[p]=INF;
           return FF;
       }
      
       bool bfs(){
            for (int i=0;i<=vt;i++){
                d[i]=INF;
                cur[i]=ls[i];
            }
            d[vs]=1; Q[1]=vs;
            for (int st=1,ed=1;d[Q[st]]              for (edge *t=ls[Q[st]];t;t=t->next)
                if (t->c && d[t->y]==INF) d[ Q[++ed]=t->y ]=d[t->x]+1;
            if (d[vt]==INF) return false;
            return true;
       }
      
       void dinic(){
            Flow=0;
            int tmp;
            while (bfs())
              while (tmp=dfs(vs,INF)) Flow+=tmp;
       }
}Network;
struct Node{int y;Node *next;};
struct Link_t{
       Node *ls[N];
       void addedge(int x,int y){
            Node *p=(Node*)malloc(sizeof(Node));
            p->y=y; p->next=ls[x]; ls[x]=p;
       }
}Link;

int n,m;
char str[N];

void init(){
     clr(Link.ls);
     clr(Network.ls);
     scanf("%d%d%s",&n,&m,str+1);
     for (int x,y,i=1;i<=m;i++){
         scanf("%d%d",&x,&y);
         Link.addedge(x,y);
         Link.addedge(y,x);
     }
}

void build(){
     Network.vs=0; Network.vt=n*4+1;
     for (int i=1;i<=n;i++){
       if (str[i]==’J’){
         Network.addedge(Network.vs,i,1);
         Network.addedge(i,n+i,1);
         for (Node *t=Link.ls[i];t;t=t->next)
           if (str[t->y]!=’T’)
             Network.addedge(i,n+t->y,1);
       }
       if (str[i]==’T’)
         Network.addedge(3*n+i,Network.vt,1);
       else{
         for (Node *t=Link.ls[i];t;t=t->next)
           if (str[t->y]==’T’)
             Network.addedge(2*n+i,3*n+t->y,1);
         Network.addedge(n+i,2*n+i,1);
       }
     }
}

int main(){
    freopen("cowwar.in","r",stdin);
    freopen("cowwar.out","w",stdout);
    init();
    build();
    Network.dinic();
    printf("%dn",Network.Flow);
}

[POJ3691 DNA repair]AC自动机、动态规划

【题目大意】

给定N个串，再给定一个主串，问将主串改为不含这个N个串为子串的串，至少需改动多少个字母？

【算法分析】

嗯，我又在刷水题。。。

就是建一个AC自动机（DFA）。

然后用F[i,j]表示已处理串长为i，然后在自动机中的状态j，至少要改动多少个字母。

转移就是用自动机啦。

【其它】

1Y

注意如果自动机中的next结点有终结标记，自己也应当标为终止。

【CODE】

#include

[USACO2010 Mar 【starc】]半平面交、~我写的是O(n^2)的

【题目链接】http://ace.delos.com/ioiupload?init=1&a=uNRSh9JKRlk
【题目大意】
给定n<=300个形如ax+by+cz>=0的不等式。(将<=0的乘一个 -1来改变不等号方向)
求在其满足的前提下，给出m个询问，
看能不能确定另外给出的式子ax+by+cz是>0还是<0还是无法确定。
它很猥琐的还有常量条件。
x>0
y>0
z>0
x<=100y
x<=100z
y<=100x
y<=100z
z<=100x
z<=100y
就这么多。
【算法分析】
由于x,y,z>0，所以我们将不等式两边同除以z，不用变号。
那么不等式变成：a(x/z)+b(x/z)+c>=0
我们令X=x/z,Y=x/z。
那么不等式变为aX+bY+c>=0。
然后？
半平面交！
就是先对给出的条件全部变为这种限制，然后求出其半平面交。
然后这个半平面交的算法是我自己YY出来的,O(n^2)。。。小有成就感。
当然，众神牛估计要笑而不语了。
好了，半平面交完以后呢，就只要对每个给出的限制转化为直线。然后看这个直线是“穿过”这个半平面交。
如果穿过，表示两边的取值都可能，所以不能确定他的不等号方向。
否则，看就看它在哪一边就行了。
【其它】
好有好多好多小细节。。。然后我写成的程序，精度要卡得刚好才能过= =
如果要学习半平面交的话。。。还是别看我这。因为写得实在太水，太长了。
我看过师傅的模板，不禁为其短小精悍而叹服。
但是毕竟是自己推得算法。。。再水也是自己的= =
【CODE】
/*
ID:jie22221
TASK:starc
LANG:C++
*/
#include #include #include #include #define N 355
#define INF 100
#define eps 1e-6
#define seps 1e-2
using namespace std;
struct Line{double a,b,c;}LL[N];
struct Point{double x,y;}p[N*N],tp[N*N];
int n,Ln,m,tn;

void init(){
int i,A1,B1,C1,A2,B2,C2;
char ch;
cin >> Ln >> m;
for (i=1;i<=Ln;i++){
cin >> ch >> A1 >> B1 >> C1 >> A2 >> B2 >> C2;
if (ch==’J’){
LL[i].a=A1-A2;
LL[i].b=B1-B2;
LL[i].c=C1-C2;
}else{
LL[i].a=A2-A1;
LL[i].b=B2-B1;
LL[i].c=C2-C1;
}
}
Ln++;
LL[Ln].a=-1;
LL[Ln].b=100;
LL[Ln].c=0;
Ln++;
LL[Ln].a=100;
LL[Ln].b=-1;
LL[Ln].c=0;
n=4;
p[1].x=seps; p[1].y=seps;
p[2].x=INF; p[2].y=seps;
p[3].x=INF; p[3].y=INF;
p[4].x=seps; p[4].y=INF;
}

inline double f(Line L,Point pp){
return L.a*pp.x+L.b*pp.y+L.c;
}
inline double cj(Point A,Point B){return A.x*B.y-A.y*B.x;}
inline void dec(int &x){x–; if (x<1) x=n;}
inline void inc(int &x){x++; if (x>n) x=1;}

Line Get_Line(Point A,Point B){
Line res;
res.a=A.y-B.y;
res.b=B.x-A.x;
res.c=cj(A,B);
return res;
}

Point Cross_Point(Line A,Line B){
Point res;
res.x=(B.b*A.c-A.b*B.c)/(B.a*A.b-A.a*B.b);
res.y=(B.a*A.c-A.a*B.c)/(A.a*B.b-B.a*A.b);
return res;
}

double fabs(double x){
if (x<0) return -x;
return x;
}

void Cut(Line L){
int i,j,k,st=1;
bool flag=false;
for (i=1;i<=n;i++)
if (f(L,p[i])<-eps) flag=true;
if (!flag){
for (i=1;i<=n;i++) tp[i]=p[i];
tn=n;
return;
}
while (f(L,p[st])<-eps) st++;
for (i=st;;inc(i))
if (f(L,p[i])<-eps) break;
for (j=st;;dec(j))
if (f(L,p[j])<-eps) break;
tn=0;
for (k=j%n+1;k!=i;inc(k))
tp[++tn]=p[k];
dec(i);
if (fabs(f(L,tp[tn]))>eps){
Line tmp=Get_Line(p[i],p[i%n+1]);
tp[++tn]=Cross_Point(tmp,L);
}
if (fabs(f(L,tp[ 1]))>eps){
Line tmp=Get_Line(p[j],p[j%n+1]);
tp[++tn]=Cross_Point(tmp,L);
}
}

void half_plane(){
int i,j;
for (i=1;i<=Ln;i++){
Cut(LL[i]);
for (j=1;j<=tn;j++) p[j]=tp[j];
n=tn;
}
}

void solve(){
int A1,B1,C1,A2,B2,C2,t1,t2,i,j;
for (i=1;i<=m;i++){
t1=t2=0;
cin >> A1 >> B1 >> C1 >> A2 >> B2 >> C2;
Line L;
L.a=A1-A2;
L.b=B1-B2;
L.c=C1-C2;
for (j=1;j<=n;j++){
if (f(L,p[j])<-1e-8) t1++;
if (f(L,p[j])> 1e-8) t2++;
}
if (t1==0 && t2==0 || t1+t2!=n) puts("U"); else
if (!t1) puts("J"); else
if (!t2) puts("B"); else
puts("U");
}
}

int main(){
freopen("starc.in","r",stdin);
freopen("starc.out","w",stdout);
ios::sync_with_stdio(false);
init();
half_plane();
solve();
return 0;
}

[Usaco2010 Hol]rocks 石头木头 【博弈、NIM和、SG函数】

【题目链接】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1777
http://ace.delos.com/ioiupload?d=gold&a=nejLCFTaRn6&lang=ch
【Experience】
呃，今天弄了一下那个论文，以及参详了DD——崔牛的神文的一部分。
神文地址：http://hi.baidu.com/yufuwan1/blog/item/4bb477443c425d4a500ffe2d.html
此乃转载地址，好像原地址已经消失不见了。。。
于是论文自然就是WC2009的：《从“k倍动态减法游戏”出发探究一类组合游戏问题》
然后表示，NIM积依然不懂，第一个例子就不懂。。。
幸好这题不用NIM积。。。
【算法分析】
首先我们可以发现，如果是离根距离为偶数的点上面的石头是不可能决定胜负的。
因为，假设一个人把一些石头从偶点移动一次，那么就到达一个奇点，然后另外一个人就能再从这个奇点移同样数目的石头到偶点。直到这些石头到根。
如果按照这个策略做的话，结果不会发现任何改变。
所以偶点的石头与胜负无关。
然后接下来我们来看奇点的石头。
假设我们从这个奇点移了一些石头，那么再偶数点上的石头再次对结果无关。
所以，每个奇点上的石头是独立的。
有了独立这个性质，那么我们就可以利用Sprague-Grundy Theorem
来处理。如果你看了上面崔牛那篇的第二部分，那么就很容易想到了。
因为是独立的游戏，那么SG(X)=SG(a1)^SG(a2)^…^SG(an)。(^即xor)
如果SG(X)=0，那么证明X是先手必败态。
然后每次只能移L这么多个石头，有一种很简单的方法得出每一个奇点的SG函数值。
就是SG=Rocks_Num%(L+1)。
如果你看了DD那篇神文。
就容易知道SG是怎么求出来的了。
就是画一个有向图，每个点代表剩下x个石子时候的局面，然后再连转移的有向边，然后。。。就能发现规律了。
于是根据Sprague-Grundy Theorem，我们可以轻易得到整个局面的SG函数。
然后剩下的问题是关心在它变那些值的时候我们怎么处理。
由于我们实际上就是需要维护整个局面的SG值，于是我们可以围观到这样的式子：
Ans=k ^ Ai
Ans’=k ^ Ai‘
于是Ans’=k ^ Ai ^ Ai ^ Ai’=Ans ^ Ai ^ Ai’
嗯，就这样。
【CODE】
/*
ID:jie22221
TASK:rocks
LANG:C++
*/
#include int N,T,L,ans,fa,i,w,x;
int d[10005],SG[10005];

int main(){
freopen("rocks.in","r",stdin);
freopen("rocks.out","w",stdout);
scanf("%d%d%d",&N,&T,&L);
d[1]=0; SG[1]=ans=0;
for (i=2;i<=N;i++){
scanf("%d%d",&fa,&w);
d[i]=d[fa]+1;
SG[i]=w%(L+1);
if (d[i]%2==1) ans^=SG[i];
}
for (i=1;i<=T;i++){
scanf("%d%d",&x,&w);
if (d[x]%2==1){
w%=(L+1);
ans^=SG[x]^w;
SG[x]=w;
}
if (ans==0) puts("No");
else puts("Yes");
}
}