Boleyn Su's Blog – 第 6 页

SGU103[Traffic Lights]

最短路。

CODE:

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using namespace std;

const int MAXE=14000*2;

const int MAXV=300+2;

typedef struct struct_edge* edge;

struct struct_edge{int v,d;edge n;};

struct node

{

int c,r,t[2];

int color(int timeline)

{

int alpha=timeline%(t[0]+t[1]);

if (r<=alpha&&alpha<r+t[!c]) return !c;

else return c;

}

int remain(int timeline)

{

int alpha=timeline%(t[0]+t[1]);

if (alpha<r)

return r-alpha;

else if (alpha<r+t[!c])

return r+t[!c]-alpha;

else return t[0]+t[1]-alpha;

}

};

struct_edge pool[MAXE];

edge top=pool;

int S,T;

int V,E;

node vertex[MAXV];

edge adj[MAXV];

const int oo=19930309;

int d[MAXV];

int visited[MAXV];

int pre[MAXV];

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

{

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

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

}

int min(int a,int b)

{

return a<b?a:b;

}

int wait(int u,int v,int now=0,int change_times=0)

{

if (change_times>3) return oo;

if (vertex[u].color(now)==vertex[v].color(now)) return now;

else

{

int wt=wait(u,v,now+min(vertex[u].remain(now),vertex[v].remain(now)),change_times+1);

if (wt==oo) return oo;

else return wt;

}

void dijkstra()

{

for (int u=1;u<=V;u++)

d[u]=oo;

d[S]=0;

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

{

int u,du=oo;

for (int tu=1;tu<=V;tu++)

if (!visited[tu]&&d[tu]<du)

du=d[u=tu];

visited[u]=true;

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

if (!visited[i->v])

{

int tdv=wait(u,i->v,d[u])+i->d;

if (d[i->v]>tdv)

d[i->v]=tdv,

pre[i->v]=u;

}

void print(int u)

{

if (u!=S) print(pre[u]);

cout<<u<<char(u==T?’\n’:’ ‘);

}

int main()

{

ios::sync_with_stdio(false);

cin>>S>>T;

cin>>V>>E;

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

{

char color;

cin>>color>>vertex[i].r>>vertex[i].t[0]>>vertex[i].t[1];

vertex[i].c=(color==’P’);

}

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

{

int a,b,d;

cin>>a>>b>>d;

add_edge(a,b,d);

}

dijkstra();

if (d[T]==oo) cout<<0<<endl;

else

{

cout<<d[T]<<endl;

print(T);

}

SGU102[Coprimes]

求最大公约数。

CODE:

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using namespace std;

int main()

{

int N,answer=0;

cin>>N;

for (int i=1;i<=N;i++)

{

int a=N,b=i,t;

while (b) t=a,a=b,b=t%b;

if (a==1) answer++;

}

cout<<answer<<endl;

}

SGU101[Domino]

欧拉路。

CODE:

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using namespace std;

const int MAXE=100*2;

const int MAXV=6–0+1;

typedef struct struct_edge* edge;

struct struct_edge{int v,id;char dir;edge n;};

struct_edge pool[MAXE];

edge top=pool;

edge adj[MAXV];

int degree[MAXV];

int used[MAXE/2];

int list[MAXE/2+1];

int listtop;

int size[MAXV][MAXV];

edge edges[MAXV][MAXV][MAXE];

int printed[MAXE/2];

void add_edge(int u,int v,int id)

{

degree[u]++,edges[u][v][size[u][v]++]=top,

top->v=v,top->id=id,top->dir=’+’,top->n=adj[u],adj[u]=top++;

degree[v]++,edges[v][u][size[v][u]++]=top,

top->v=u,top->id=id,top->dir=’-‘,top->n=adj[v],adj[v]=top++;

}

void find_circuit(int u)

{

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

if (!used[i->id])

{

used[i->id]=true;

find_circuit(i->v);

}

list[listtop++]=u;

}

void print(int u,int v)

{

for (int i=0;i<size[u][v];i++)

if (!printed[edges[u][v][i]->id])

{

cout<<edges[u][v][i]->id+1<<” “<<edges[u][v][i]->dir<<endl;

printed[edges[u][v][i]->id]=true;

break;

}

int main()

{

int N,a,b;

cin>>N;

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

cin>>a>>b,add_edge(a,b,i);

int odc=0;

int S;

for (int u=0;u<MAXV;u++)

if (degree[u])

S=u;

#define odd(x) ((x)&1)

for (int u=0;u<MAXV;u++)

if (odd(degree[u]))

odc++,S=u;

if (odc==0||odc==2)

{

find_circuit(S);

if (listtop==N+1)

for (int i=1;i<listtop;i++)

print(list[i-1],list[i]);

else cout<<“No solution”<<endl;

}

else cout<<“No solution”<<endl;

}

SGU100[A+B]

经典题目。

CODE:

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

#include <iostream>

int main()

{

int a,b;

std::cin>>a>>b;

std::cout<<a+b<<std::endl;

}

POJ3709[K-Anonymous Sequence]

动态规划，斜率优化，具体见这里。

CODE:

AUTHOR: Su Jiao

DATE: 2010-8-22

DESCRIPTION:

$DESCRIPTION

#include <iostream>

using namespace std;

const long long int oo=0X19930309*19930309;

const int MAXN=500000+2;

int T;

int n,k;

long long int a[MAXN];

long long int s[MAXN];

long long int f[MAXN];

int q[MAXN];

int head,tail;

int main()

{

ios::sync_with_stdio(false);

cin>>T;

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

{

cin>>n>>k;

for (int i=1;i<=n;i++) cin>>a[i];

for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

f[0]=0;

q[head=tail=0]=0;

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

{

#define value(i,j) ((i-j>=k)?(f[j]+s[i]-s[j]-(i-j)*a[j+1]):(oo))

#define ky(j,k) (f[j]-f[k]+s[k]-s[j]+(j)*a[j+1]-(k)*a[k+1])

#define kx(j,k) (a[j+1]-a[k+1])

if (i-k>0)

{

while (head<tail

&&ky(q[tail-1],q[tail])*kx(q[tail],i-k)

>=kx(q[tail-1],q[tail])*ky(q[tail],i-k))

tail–;

q[++tail]=i-k;

}

while (head<tail&&value(i,q[head])>value(i,q[head+1])) head++;

f[i]=value(i,q[head]);

}

cout<<f[n]<<endl;

}

更新：答案有误，因为答案只证明了当$n \to \inf$时，从$1/n, 2/n, \dots, (n-1)/n$中平均要取$e$个数才能让和超过一，而当$n \to \inf$时，$1/n, 2/n, \dots, (n-1)/n$并不能和$(0, 1)$中的实数一一对应。写这个日志的时候才上高中，不知知道可数集不可数集的概念。而且即使把题目改为取有理数，我给出的答案也是不对了。献丑了，哈哈哈。

题目来自Matrix67.com，原文链接http://www.matrix67.com/blog/archives/3507。

Matrix67牛给出了一个用微积分做的解答，当我看到这个题目的时候，我想到了另一个方法。

思考时间，答案在下面（字体是白色的）。

首先，将题目转化为平均要取多少个1到n-1中的随机数才能让和超过n。显然当n趋于无穷大时，这两个问题是等效的。

然后，解：

设f(x)表示平均取多少次才能大于x.
显然 f(x)=0 x<0
     f(x)=1 x=0
对于x>0来说,设之前最后一次取得了i,那么i在1到n-1之间,且取到任意一个数的概率为1/(n-1).
所以 f(x)=sum{(1+f(x-i))/(n-1):1<=i<=n-1}
         =1+sum{f(x-i):1<=i<=n-1}/(n-1)
         =1+sum{f(t):0<=t<=x-1}/(n-1) (如果0<x<n)
         =1+sum{f(t):x-(n-1)<=t<=x-1}/(n-1) (如果x>=n)

对于0<x<n
    令 F(x)=sum{f(i):0<=i<=x}
    则 f(x)=1+F(x-1)/(n-1)     ......[1]
    所以 f(x-1)=1+F(x-2)/(n-1) ......[2]
    [1]式-[2]式得 f(x)-f(x-1)=(F(x-1)-F(x-2))/(n-1)
    所以 (f(x)-f(x-1))*(n-1)=f(x-1)
    所以 f(x)=f(x-1)*n/(n-1)
             =(n/(n-1))^x*f(0)
             =(n/(n-1))^x
所以 f(n)=1+sum{f(t):1<=t<=n-1}/(n-1)
         =1+sum{(n/(n-1))^t:1<=t<=n-1}/(n-1)
         =1+(n/(n-1))^n-n/(n-1)
         =(n/(n-1))^n-1/(n-1)

     lim(n->+oo) f(n)=(1+1/(n-1))^(n-1)*(1+1/(n-1))-1/(n-1)
                     =e*1-0
                     =e

NOI了[2010年7月29日]

后天就要启程去山东参加NOI了，感觉时间真的过的好快。从高一到现在，学信息学竞赛不知不觉已经两年了。从开始自以为是学C++就很了不起的我，变成知道原来算法比语言更美丽的我。对于NOI，之前根本就没有想过，我想的不过是有个NOIP一等奖就可以了。甚至连NOIP一等奖，我都感到畏惧。
高一的时候，第一次参加NOIP，抱着试一试的态度去的，不过路上我还是很自信的说我可能会拿一等奖。结果，最后失望而归。高二到了，我知道这是唯一一次机会了，我不敢松懈。NOIP前的一周，我跟LK,YWS一起向年级主任请假不上晚自习，一起到机房练题。VIJOS，那是一个有趣的题库。它让我明白，我还十分渺小。一次一次的WA，一次一次的提交。然而正因为这样，每一次的AC都让我兴奋，让我觉得满足。记得有一次，我一次提交就AC了一道动态规划的题目，当时我高兴死了，那是我第一次一次提交就AC。还有VIJOS的两场模拟赛，我记得我做得都很糟糕。说实话，我很担心NOIP会不会也那样挂掉。
2009年11月21日，我和同学们乘坐校车向重庆市巴蜀中学鲁能分校区进发。第二次进入那个考场，我只能拼了。最后220分。我是全市并列第五，我马上给我妈妈打电话，告诉她我一等奖拿定了。我高兴了整整一天！
之后，获奖名单出来了，我们学校高二这一届信息学竞赛的4名主力队员中3人获得一等奖。在这之后YWS和LK退出了，他们回到了正常的学习当中，剩下的就我跟WSC。WSC说，我可以冲一下省队，叫我做USACO Training。然后接下来的两个月，我疯狂的刷题。用两个月的时间做完USACO Training的97道题目。在这期间，WSC给了我很多帮助。说实话，要不是WSC，我可能就止步于NOIP。做完USACO Training后，我们一起做了几场USACO的月赛题目，那时都没资格做金组题目，不过正是由于不是金组吧，水题增强了我的自信。然后是一起去山东的NOI冬令营。听国家集训队的大牛们讲题，我感到自己学的真的还是太少了。
不管怎样，漫长而又短暂的时间很快过去。我和WSC就做了几套其它省的省选题和往届重庆的省选题，就去参加重庆市的代表队选拔赛了。这次，我考了全市第一。我知道这意味这什么，我可以去NOI了！WSC和RJ并列第七，最后WSC因为在APIO中发挥失误，只能进夏令营（正式选手名额只有7个，所以WSC和RJ凭APIO的分数来决定谁成为正式队员）。
然后是前不久的APIO，120分，国内银牌。有点失望，因为之前做了一场USACO金组的月赛（这是我做的唯一一场USACO金组月赛），而这次APIO的题目和那次月赛惊人的相似。
最近一两个月，重庆代表队的成员们常常聚到一起练题。我们一起做有道难题，一起做NOI往届的题目，一起交流各自的想法。我们的目标只有一个，在NOI上留下自己的印记！
NOI了，此刻依旧是我独自一人坐在空荡荡的机房，但我知道我不是一个人在战斗！

SDOI2008[郁闷的小J]

数据结构类题目，赤裸裸的平衡树。

然后我自己写了一个随机函数，经过我自己的测试，用这个函数连续输出10^6个数，其中只有10^3多一点点的数重复次数超过1，有0个数重复次数超过2。所以这是一个不错的随机函数。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-27

DESCRIPTION:

山东2008年省选 郁闷的小J

#include <stdio.h>

struct Treap

{

static const int MAXNODE=1000000;

struct struct_node{struct_node* c[1<<1];int p,s,k;};

typedef struct_node* node;

static struct_node pool[MAXNODE];

static node top;

node root,null;

Treap()

{

null=top++;

null->c[0]=null->c[1]=null;

null->p=(~0u)>>1;

null->s=0;

null->k=0;

root=null;

}

int rand()

{

const int a=0x19930309,b=19930309;

static int c,d;

c^=d;

return d=(b*d)+(a^c);

}

void resize(node x)

{

if (x!=null) x->s=x->c[0]->s+x->c[1]->s+1;

}

void rotate(node& x,bool d)

{

node y=x->c[!d];

x->c[!d]=y->c[d];

y->c[d]=x;

resize(x),resize(y);

x=y;

}

void insert(node& x,int k)

{

if (x==null)

{

x=top++;

x->c[0]=x->c[1]=null;

x->p=rand();

x->k=k;

resize(x);

}

else

{

if (x->k==k) return;

bool d=x->k<k;

insert(x->c[d],k);

if (x->c[d]->p<x->p) rotate(x,!d);

else resize(x);

}

void remove(node& x,int k)

{

if (x!=null)

{

if (x->k==k)

{

if (x->c[0]==null&&x->c[1]==null) x=null;

else if (x->c[0]==null) x=x->c[1];

else if (x->c[1]==null) x=x->c[0];

else

{

bool d=x->c[0]->p<x->c[1]->p;

rotate(x,d);

remove(x->c[d],k);

}

else remove(x->c[x->k<k],k);

resize(x);

}

node search(node x,int k)

{

if (x==null) return null;

if (x->k==k) return x;

else return search(x->c[x->k<k],k);

}

node select(node x,int k)

{

if (x==null) return x;

if (x->c[0]->s>=k) return select(x->c[0],k);

k-=x->c[0]->s;

if (k==1) return x;

k-=1;

return select(x->c[1],k);

}

int rank(node x,int k)

{

if (x==null) return 0;

if (k<x->k) return rank(x->c[0],k);

else if (k==x->k) return x->c[0]->s+1;

else return x->c[0]->s+1+rank(x->c[1],k);

}

void for_each(node x,void (*function)(node))

{

if (x==null) return;

for_each(x->c[0],function);

function(x);

for_each(x->c[1],function);

}

void insert(int k)

{

insert(root,k);

}

void remove(int k)

{

remove(root,k);

}

node search(int k)

{

return search(root,k);

}

node select(int k)

{

return select(root,k);

}

int rank(int k)

{

return rank(root,k);

}

void for_each(void (*function)(node))

{

for_each(root,function);

}

};

Treap::struct_node Treap::pool[Treap::MAXNODE];

Treap::node Treap::top=Treap::pool;

const int MAXN=100000+2;

const int MAXM=100000;

typedef Treap::node node;

int N,M;

int a[MAXN];

char order[MAXM];

int A[MAXM],B[MAXM],K[MAXM],P[MAXM];

Treap book;

Treap position[MAXN+MAXM];

void get_id(node x)

{

static int id;

x->s=id++;

}

int main()

{

scanf(“%d%d”,&N,&M);

for (int i=1;i<=N;i++)

scanf(“%d”,a+i);

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

{

scanf(“\n%c”,&order[i]);

if (order[i]==’C’) scanf(“%d%d”,A+i,P+i);

else scanf(“%d%d%d”,A+i,B+i,K+i);

}

for (int i=1;i<=N;i++)

book.insert(a[i]);

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

if (order[i]==’C’) book.insert(P[i]);

else book.insert(K[i]);

book.for_each(get_id);

for (int i=1;i<=N;i++)

{

node x=book.search(a[i]);

position[x->s].insert(i);

}

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

{

if (order[i]==’C’)

{

node x=book.search(a[A[i]]);

position[x->s].remove(A[i]);

node y=book.search(P[i]);

position[y->s].insert(A[i]);

a[A[i]]=P[i];

}

else

{

node x=book.search(K[i]);

printf(“%d\n”,position[x->s].rank(B[i])-position[x->s].rank(A[i]-1));

}

SDOI2008[Sandy的卡片]

赤裸裸的后缀数组。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-27

DESCRIPTION:

山东2008年省选 Sandy的卡片

#include <stdio.h>

#define max(a,b) ((a)>(b)?(a):(b))

const int MAXALPHABET=1000000;

const int MAXLENGTH=1000000;

typedef int string[MAXLENGTH];

typedef int* int_pointer;

int sort[max(MAXALPHABET,MAXLENGTH)];

int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];

int_pointer SA=_SA,rank=_rank,TSA=_TSA,Trank=_Trank;

void get_SA(string s,int length)

{

for (int i=0;i<MAXALPHABET;i++) sort[i]=0;

for (int i=1;i<=length;i++) sort[s[i]]++;

for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];

for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;

rank[SA[1]]=1;

for (int i=2;i<=length;i++)

if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];

else rank[SA[i]]=rank[SA[i-1]]+1;

for (int block=1;block<length;block<<=1)

{

for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;

for (int i=length;i>=1;i–)

if (SA[i]-block>=1)

TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;

for (int i=length-block+1;i<=length;i++)

TSA[sort[rank[i]]–]=i;

int_pointer swap;

swap=SA,SA=TSA,TSA=swap;

swap=rank,rank=Trank,Trank=swap;

rank[SA[1]]=1;

for (int i=2;i<=length;i++)

if (Trank[SA[i]]==Trank[SA[i-1]]

&&Trank[SA[i]+block]==Trank[SA[i-1]+block])

rank[SA[i]]=rank[SA[i-1]];

else rank[SA[i]]=rank[SA[i-1]]+1;

}

int height[MAXLENGTH];

void get_height(string s,int length)

{

for (int i=1,h=0;i<=length;i++)

{

if (h) h–;

if (rank[i]!=1)

{

int j=SA[rank[i]-1];

while (s[i+h]==s[j+h]) h++;

}

height[rank[i]]=h;

}

int N;

string s;

int length;

int id[MAXLENGTH];

int found_time;

int found[MAXLENGTH];

bool check(int value)

{

int i=1;

while (i<=length)

{

while (i<=length&&height[i]<value) i++;

int found_counter=1;

found[id[SA[i-1]]]=++found_time;

while (i<=length&&height[i]>=value)

{

if (found[id[SA[i]]]!=found_time)

{

found[id[SA[i]]]=found_time;

found_counter++;

}

i++;

}

if (found_counter==N) return true;

}

return false;

}

int main()

{

scanf(“%d”,&N);

for (int i=1;i<=N;i++)

{

int M,a,b;

scanf(“%d%d”,&M,&b);

for (int j=1;j<M;j++)

{

a=b;

scanf(“%d”,&b);

s[++length]=b-a+100000;

id[length]=i;

}

s[++length]=i;

id[length]=i;

}

get_SA(s,length);

get_height(s,length);

if (N==1) printf(“%d\n”,length-1);

else

{

int L=0,R=length;

while (L+1!=R)

{

int mid=(L+R)>>1;

if (check(mid)) L=mid;

else R=mid;

}

printf(“%d\n”,L+1);

}

SDOI2009[学校食堂]

状态压缩DP。

f[i][STATE][BEFORE]表示i以前的都已经吃到饭了，然后STATE用二进制压缩表示后面8个人的吃饭情况，BEFORE表示最后一个吃饭的人是谁，可以用相对位置表示，于是-8<=BEFORE<=8。

CODE:

AUTHOR: Su Jiao

DATE: 2010-7-26

DESCRIPTION:

山东2009年省选 学校食堂

#include <stdio.h>

#include <string.h>

const int oo=0x7f7f7f7f;

const int MAXN=1000+10;

const int MAXB=7+1;

const int MAXBEFORE=MAXB*2+1;

const int MAXSTATE=1<<(MAXB+1);

int C;

int N;

int t[MAXN],b[MAXN];

int f[MAXN][MAXSTATE][MAXBEFORE];

int BEFORE(int x)

{

return x+MAXB;

}

int STATE(int x)

{

return 1<<x;

}

int min(int a,int b)

{

return a<b?a:b;

}

int cost(int a,int b)

{

return a^b;

}

int get(int i,int before,int state,int ii,int bbefore,int sstate)

{

int& A=f[i][state][BEFORE(before)];

int B=f[ii][sstate][BEFORE(bbefore)];

A=min(A,B+cost(t[ii+bbefore],t[i+before]));

}

int main()

{

scanf(“%d”,&C);

for (int c=0;c<C;c++)

{

scanf(“%d”,&N);

for (int i=1;i<=N;i++)

scanf(“%d%d”,t+i,b+i);

memset(f,oo,sizeof(f));

for (int before=0;before<=MAXB;before++)

{

bool can_get=true;

for (int k=0;k<MAXB;k++)

if ((1+before)-(1+k)>b[1+k])

{

can_get=false;

break;

}

if (can_get) f[1][STATE(before)][BEFORE(before)]=0;

}

for (int ii=1;ii<=N+1;ii++)

for (int sstate=0;sstate<MAXSTATE;sstate++)

for (int bbefore=-MAXB;bbefore<=MAXB;bbefore++)

if (f[ii][sstate][BEFORE(bbefore)]!=oo)

for (int todo=0;todo<=b[ii];todo++)

{

int i=ii,before=todo,state=sstate|STATE(todo);

bool can_get=true;

for (int k=0;k<MAXB;k++)

if (!(state&STATE(k))&&((i+todo)-(i+k))>b[i+k])

{

can_get=false;

break;

}

if (can_get)

{

int di=0;

while (di<=MAXB&&(state&STATE(di))) di++;

i+=di,before-=di,state>>=di;

get(i,before,state,ii,bbefore,sstate);

}

int answer=oo;

for (int before=-MAXB;before<=0;before++)

if (answer>f[N+1][0][BEFORE(before)])

answer=f[N+1][0][BEFORE(before)];

printf(“%d\n”,answer);

}