[FOJ1901 Period II]拓展KMP算法

【题目大意】
给出一个串，让你求出所有满足S[1..n-k+1]=S[k..n]的k-1的值。
【算法分析】
一看到题目。。。这不就是拓展KMP的数组直接判断么。。。
于是直接写了拓展KMP。
虽然KMP也可以。
这个当做是我的拓展KMP例题好了。
【CODE】
#include #include #include #define max(x,y) ((x)>(y)?(x):(y))
const int N=1000005;
int n,ans;
int b[N],ansl[N];
char S[N];

void exkmp(){
int i,j,k,a,p;
b[1]=n;
for (i=2;i<=n && S[i]==S[i-1];i++);
i–;
b[2]=i-2+1;
p=i;
a=2;

for (i=3;i<=n;i++)
if (b[i-a+1]+i-1 b[i]=b[i-a+1];
else{
k=max(p+1-i,0);
while (i+k<=n && S[i+k]==S[k+1]) k++;
b[i]=k;
a=i;
p=i+b[i]-1;
}

ans=0;
for (i=2;i<=n;i++)
if (b[i]==n-i+1) ansl[++ans]=i-1;
ansl[++ans]=n;
printf("%dn",ans);
for (i=1;i<=ans;i++){
printf("%d",ansl[i]);
if (i==ans) printf("n");
else printf(" ");
}
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
printf("Case #%d: ",i);
scanf("%s",S+1);
n=strlen(S+1);
exkmp();
}
}

[COCI 2009/2010 – Constest #7 RESTORAN]AC、随机算法、非完美

【题外话】
这题之前写过一个题解了。
地址是：http://hi.baidu.com/edwardmj/blog/item/592566ad221c3ac07cd92a87.html
之前的算法没有AC。然后看了到处转了一转，又围观了神牛的代码。
各种构造法弄到头晕。。。
Orz。。。还是没看懂。然后我写起了当时扬言要写的随机算法。
【算法分析】
同样是当作树来DFS。
DFS时就判断当前点有没有1这种颜色。没有的话染1。
再判断有没有2这种颜色。没有的话染2。
否则得话，染颜色rand()%2+1。
然后出来以后还没染得，就看两边缺啥就染啥。
如果无解的话，重新染。直到无解10次那就真无解。
否则输出。
【评测结果】
Test # Score Time Memory Result 1 6.5 0.00s 6652 kB Correct! 2 6.5 0.00s 6652 kB Correct! 3 6.5 0.00s 6652 kB Correct! 4 6.5 0.00s 6652 kB Correct! 5 52.0 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 0.01s 6652 kB Correct! 0.00s 6652 kB Correct! 0.00s 6652 kB Correct! 6 52.0 0.50s 9696 kB Correct! 0.09s 6652 kB Correct! 0.00s 6652 kB Correct! 0.13s 9696 kB Correct! 0.12s 7608 kB Correct! 0.19s 8288 kB Correct! 0.11s 7416 kB Correct! 0.12s 7944 kB Correct! 【CODE】
#include #include #include const int N=105555;
struct edge{int x,y,c,next,op;}g[N*2];
int n,e,times=0;
int ls[N],du[N],c1[N],c2[N];
bool v[N];

inline void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].op=e+1; g[e].c=0;
g[++e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].op=e-1; g[e].c=0;
}

void init(){
e=0;
memset(ls,0,sizeof(ls));
memset(du,0,sizeof(du));
int i,x,y,m;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
du[x]++; du[y]++;
}
}

void draw(int t,int co){
g[t].c=co; g[g[t].op].c=co;
if (co==1){c1[g[t].x]++; c1[g[t].y]++;}
else{c2[g[t].x]++; c2[g[t].y]++;}
}

void dfs(int p){
for (int t=ls[p];t;t=g[t].next)
if (!v[g[t].y]){
v[g[t].y]=true;
if (!c1[p]) draw(t,1);
else if (!c2[p]) draw(t,2);
else draw(t,rand()%2+1);
dfs(g[t].y);
}
}

void work(){
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
memset(v,false,sizeof(v));
for (int i=1;i<=e;i++) g[i].c=0;
for (int i=1;i<=n;i++)
if (!v[i]){
v[i]=true;
dfs(i);
}
for (int t=1;t<=e;t++)
if (!g[t].c)
if (!c1[g[t].x] && du[g[t].x]>1 || !c1[g[t].y] && du[g[t].y]>1) draw(t,1);
else draw(t,2);
bool flag=true;
for (int i=1;i<=n;i++)
if (du[i]>1 && (!c1[i] || !c2[i])) flag=false;
if (!flag){
if (times<10){
times++;
work();
return;
}
printf("0n");
}
else
for (int i=1;i printf("%dn",g[i].c);
}

int main(){
srand(19930505);
// freopen("input2.txt","r",stdin);
// freopen("output.txt","w",stdout);
init();
work();
}

[SGU 217 && HDOJ 3310]微积分

【题目大意】
给两个圆柱体，他们的中轴线共面且垂直。而且这两个圆柱体的高是无限大的。
然后分别给出他们底面的半径r1和r2。
求他们相交的体积。
【算法分析】
按X或Y轴积分怎么搞都搞不过。。。。我倒。。。
按Z轴一积就过了。
还是两个都啰嗦一下吧。
按X或Y轴切得话，切面就是这种形状：“|○|” 然后分类讨论一下那两个竖线夹得地方算面积就可以了。
按Z轴切得话，切面就是”井“字形。然后算矩形面积即可。
【其它】
估计是按X或Y轴切时算面积涉及到arccos和π，所以使误差加大了。。。
【CODE】
#include #include #include #include #define sqr(x) ((x)*(x))
const double pi=acos(-1);
double r1,r2,ans,len,eps,tmp;

inline double f(double x){return sqrt((sqr(r1)-sqr(x))*(sqr(r2)-sqr(x)));}

void work(){
ans=0;
for (double x=0;x+eps ans+=(f(x)+f(x+eps)+f(x+eps/2))/3*eps;
ans*=8;
printf("%.2lfn",ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%lf%lf",&r1,&r2);
if (r1>r2){tmp=r1; r1=r2; r2=tmp;}
eps=r1/1500000;
work();
}
}

[APIO2010 signaling]计算几何、性质->经典模型

【题目地址】http://www.apio.olympiad.org/
【算法分析】
取4个点，可以推出：
如果是构成凸四边形的话，有两种取法会覆盖完4个点。
如果是构成凹四边形的话，有1种取法会覆盖完4个点。
不要说正方形、矩形。。。题目说明不会有点在外接圆上的。
然后设取4个点中，构成凸四边形的有P个，凹四边形有Q个。
那么P+Q=C(n,4)
然后最终答案ans=(2*P+Q)/C(n,3)+3。
至于求Q。那么就是枚举那个凹四边形中的中心点，然后将其平移至原点，
问题转化成：求N个点中取三个点，过原点的三角形有多少个？
这个是一个经典问题。可以参考这里来解决：
http://hi.baidu.com/edwardmj/blog/item/40751a1454c50414962b4367.html
【CODE】
#include #include #include #include #define next(j) ((j)==n?1:j+1)
using namespace std;
typedef long long lld;
const int N=1505;
struct Point{int x,y;}a[N],tt[N];
int n;
int xx1,xx2;
lld F[N],ans,FM,P,Q;

void input(){
scanf("%d",&n);
int i;
for (i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
}

inline int get_xx(Point p){
if (p.x>=0 && p.y>0) return 1;
if (p.x>0 && p.y<=0) return 2;
if (p.x<=0 && p.y<0) return 3;
return 4;
}

inline int cj(Point &p0,Point &p1,Point &p2){
lld res=(lld)(p1.x-p0.x)*(lld)(p2.y-p0.y)-(lld)(p1.y-p0.y)*(lld)(p2.x-p0.x);
if (res<0) return -1;
if (res==0) return 0;
return 1;
}

inline bool cmp(Point x,Point y){
xx1=get_xx(x),xx2=get_xx(y);
if (xx1!=xx2) return xx1 return cj(a[0],x,y)<0;
}

void solve(){
sort(a+1,a+1+n,cmp);
ans+=(lld)(n)*(n-1)*(n-2)/6;
lld total;
int i,j=1;
for (i=1;i<=n;i++){
if (i==j) j=next(j);
while (i!=next(j) && cj(a[0],a[i],a[next(j)])<0) j=next(j);
if (j else total=j-i;
ans-=total*(total-1)/2;
}
}

inline void swap(Point &X,Point &Y){Point tmp=X; X=Y; Y=tmp;}

void work(){
FM=(lld)(n)*(n-1)*(n-2)/6;
ans=0;
memcpy(tt,a,sizeof(tt));
int i,j;
n;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++) a[j]=tt[j];
swap(a[n],a[i]);
for (j=1;j a[j].x-=a[n].x;
a[j].y-=a[n].y;
}
n–;
solve();
n++;
}
Q=ans;
P=(lld)(n)*(n-1)*(n-2)*(n-3)/24-Q;
ans=2*P+Q;
printf("%.3lfn",(double)ans/(double)(FM)+3);
}

int main(){
freopen("signaling.in","r",stdin);
freopen("signaling.out","w",stdout);
input();
work();
}

[APIO2010 patrol]树形动态规划

【题目地址】http://www.apio.olympiad.org/
【算法分析】
就是求两（一）条不相交的最长链。
F[i][j][k]表示i这个结点，已完成的链有j条，k表示有无一条只有一边的可延伸链，所得到的最大长度。
然后就像背包一样转移。
【CODE】
#include #include #include const int N=100005;
struct edge{int x,y;edge *next;}sp[N*2],*ls[N];
int n,L,e,tot;
int F[N][3][2],pF[3][2];

inline void addedge(int x,int y){
sp[++e].x=x; sp[e].y=y; sp[e].next=ls[x]; ls[x]=&sp[e];
}

void init(){
e=0;
memset(ls,0,sizeof(ls));
int i,x,y;
scanf("%d%d",&n,&L);
for (i=1;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
}

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa) dp(t->y,t->x);
F[p][0][0]=0;
F[p][0][1]=0;
int j,k,pj,pk;
tot=0;
for (edge *t=ls[p];t;t=t->next) if (t->y!=fa){
memcpy(pF,F[p],sizeof(pF));
for (j=0;j<=L;j++)
for (pj=0;pj+j<=L;pj++){
F[p][pj+j][0]=max(F[p][pj+j][0],pF[pj][0]+F[t->y][j][0]);
F[p][pj+j][1]=max(F[p][pj+j][1],pF[pj][0]+F[t->y][j][1]+1);
F[p][pj+j][1]=max(F[p][pj+j][1],pF[pj][1]+F[t->y][j][0]);
if (pj+j+1<=L)
F[p][pj+j+1][0]=max(F[p][pj+j+1][0],pF[pj][1]+F[t->y][j][1]+1);
}
}
}

void solve(){
int ans=0;
memset(F,200,sizeof(F));
dp(1,0);
ans=max(ans,F[1][1][0]);
ans=max(ans,F[1][0][1]);
if (L==2){
ans=max(ans,F[1][1][1]);
ans=max(ans,F[1][2][0]);
}
printf("%dn",2*n-2-ans+L);
}

int main(){
freopen("patrol.in","r",stdin);
freopen("patrol.out","w",stdout);
init();
solve();
return 0;
}