注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

APIO2014题解  

2014-05-07 19:59:09|  分类: apio |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
郭文景说我1.5h能AK
然后我就做了下
发现被屠了

其实这东西真没必要写什么题解的
很多大神AK无压力
不过也不排除我这种逗逼……
写一下来记录自己的逗逼人生

T1
学过manacher就知道……我们可以找出所有的回文串,然后用后缀数组算出出现次数
由于计算次数的时候把rank打成了Sa
所以捆绑数据下爆零了
感觉逗逼的不能多说
也许IOI赛制能救我一命?
后缀数组的方法常数较大,得开O2
我对其进行了一定的常数优化,自我感觉优化不下去了
如果有人是后缀数组的做法能比我的快很多的话请赐教
当然后缀数组的做法不是最优的……以下做法是郭文景教我的
假设一个回文串是A
我们把A开头结尾的字符拿掉成为A',如果A出现A'当然也会出现……我们让A'做A的父亲
很显然这是个树形结构
然后manacher……对于i,找到极长回文串……然后……啊……是吧……树上点到根的链加1……没了
离线可做到O(n)(要用到hash)
(我是这么理解的,如果我理解错她的意思的话就当段话不存在吧)
卡过常数的后缀数组版代码:


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#define maxn 600010
using namespace std;
typedef long long LL;
char str1[maxn],str2[maxn];
int n,m,rank[maxn],Sa[maxn],height[maxn],Log[maxn];
int F[20][maxn];
LL ans;
void read()
{
str1[++n]='#';
char c;
for(c=getchar();isalpha(c);c=getchar())
str1[++n]=c,str1[++n]='#',str2[++m]=c;
for(int i=2;i<=m;++i)
Log[i]=Log[i-1]+(i==(i&-i));
}
void sort(int *a,int *b,int *c,int n,int m)
{
static int cnt[maxn];
memset(cnt,0,sizeof(int)*(m+1));
for(int i=1;i<=n;++i)
++cnt[c[a[i]]];
for(int i=1;i<=m;++i)
cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i)
b[cnt[c[a[i]]]--]=a[i];
}
void Build_Sa(char *str,int n)
{
static int x[maxn],y[maxn];
for(int i=1;i<=n;++i)
rank[i]=i,y[i]=str[i];
sort(rank,Sa,y,n,256);
rank[Sa[1]]=1;
for(int i=2;i<=n;++i)
rank[Sa[i]]=rank[Sa[i-1]]+(y[Sa[i]]!=y[Sa[i-1]]);
for(int i=1;i<=n;i<<=1)
{
for(int j=1;j<=n;++j)
Sa[j]=j,x[j]=rank[j],y[j]=j+i<=n?rank[j+i]:0;
sort(Sa,rank,y,n,n),sort(rank,Sa,x,n,n);
rank[Sa[1]]=1;
for(int j=2;j<=n;++j)
rank[Sa[j]]=rank[Sa[j-1]]+(x[Sa[j]]!=x[Sa[j-1]]||y[Sa[j]]!=y[Sa[j-1]]);
if(rank[Sa[n]]==n)
return ;
}
}
void Build_Height(char *str,int n)
{
for(int i=1,j=0;i<=n;++i)
{
if(j>0)
--j;
if(rank[i]!=1)
while(str[i+j]==str[Sa[rank[i]-1]+j])
++j;
height[rank[i]]=j;
}
}
void ST_Table(int n)
{
for(int i=1;i<=n;++i)
F[0][i]=height[i];
for(int i=1;i<=Log[n];++i)
for(int j=1;j+(1<<i)-1<=n;++j)
{
int a=F[i-1][j],b=F[i-1][j+(1<<(i-1))];
F[i][j]=a<b?a:b;
}
}
LL Query(int st,int len)
{
int pos=rank[st],L=pos,R,r;
for(int i=Log[L];i>=0;--i)
if(F[i][L-(1<<i)+2]>=len)
L=L-(1<<i)+1;
r=L+ans/len-1;
if(r>m)
return 0;
if(r<=m&&r>pos)
{
int h=Log[r-pos],a=F[h][pos+1],b=F[h][r-(1<<h)+1],c=a<b?a:b;
if(c<len)
return 0;
}
R=max(r,pos);
for(int i=Log[m-R+1];i>=0;--i)
if(F[i][R+1]>=len)
R=R+(1<<i);
return R-L+1;
}
void manacher()
{
str1[n+1]='?';
static int rad[maxn];
int R=0,id;
for(int i=1;i<=n;++i)
{
rad[i]=R>i?min(rad[id*2-i],R-i):0;
for(;str1[i-rad[i]]==str1[i+rad[i]];++rad[i])
if(str1[i-rad[i]]=='#'&&rad[i])
ans=max(ans,Query((i-rad[i]+1)/2,rad[i])*rad[i]);
--rad[i];
if(R<i+rad[i])
R=i+rad[i],id=i;
}
}
int main()
{
freopen("palindrome.in","r",stdin);
freopen("palindrome.out","w",stdout);
read();
Build_Sa(str2,m);
Build_Height(str2,m);
ST_Table(m);
manacher();
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}



T2:
很容易发现如果划分的区间确定,那么无论什么顺序答案是定值
写写式子可以发现是斜率优化dp(我就不吐槽我的斜率优化dp是复制粘贴的了)
万一考试的时候不会写就233了?


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define maxn 210
#define maxm 100010
using namespace std;
typedef long long LL;
struct Node
{
LL S,G;
int id;
Node() {}
Node(LL S,LL G,int id): S(S),G(G),id(id) {}
};
int pre[maxn][maxm],a[maxm],n,m;
LL sum[maxm],dp[maxm];
void read()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",a+i);
sum[i]=sum[i-1]+a[i];
}
}
void print(int n,int m)
{
if(n==0)
return ;
print(n-1,pre[n][m]);
printf("%d ",pre[n][m]);
}
void Dp()
{
static Node queue[maxm];
for(int i=1;i<=m;++i)
{
int front=1,rear=1;
queue[rear]=Node(dp[i]-sum[i]*sum[i],sum[i],i);
for(int j=i+1;j<=n;++j)
{
while(front<rear&&queue[front].S+sum[j]*queue[front].G<=queue[front+1].S+sum[j]*queue[front+1].G)
++front;
Node now(dp[j]-sum[j]*sum[j],sum[j],j);
dp[j]=queue[front].S+sum[j]*queue[front].G;
pre[i][j]=queue[front].id;
while(front<rear&&(now.S-queue[rear].S)*(queue[rear].G-queue[rear-1].G)>=(queue[rear].S-queue[rear-1].S)*(now.G-queue[rear].G))
--rear;
queue[++rear]=now;
}
}
cout<<dp[n]<<endl;
print(m,n);
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
read();
Dp();
fclose(stdin);
fclose(stdout);
return 0;
}


T3
树p是显然的……一开始想错方向了
想用一些长度为2的链覆盖,样例没法过
然后观察了一下以为等价于这个模型:用一些长度为2的链覆盖,链不能在中间点相交,可以在两端相交
感觉挺麻烦的……写了好一阵子
然后总算写出来了,不过当然是错的
这样子没法做到每条红边连新点

然后被vfk D了
这种题的话必须得想到可以枚举根(最开始的点)啊!!
这样的话,O(n^2)的dp就很显然了
而如何避免枚举根的方法也是很经典的……记一个up记一个down
然后随手写了一发就过掉了
树P太弱系列


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 200010
#define maxm 400010
using namespace std;
typedef long long LL;
int n,down[maxn],up[maxn],val[maxn],father[maxn];
int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
void make(int a,int b,int c)
{
++nEdge,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge,len[nEdge]=c;
}
void read()
{
scanf("%d",&n);
for(int i=2,a,b,c;i<=n;++i)
{
scanf("%d %d %d",&a,&b,&c);
make(a,b,c),make(b,a,c);
}
}
void BFS(int p)
{
static int queue[maxn],in[maxn];
int front=0,rear=1;
queue[rear]=p,father[p]=0;
while(front<rear)
{
int p=queue[++front];
for(int i=start[p];i;i=next[i])
if(to[i]!=father[p])
{
queue[++rear]=to[i];
father[to[i]]=p;
in[to[i]]=len[i];
}
}
for(int i=n;i>=1;--i)
{
int p=queue[i],&ans=down[p];
for(int j=start[p];j;j=next[j])
if(to[j]!=father[p])
{
int q=to[j],tmp=down[q];
for(int k=start[q];k;k=next[k])
if(to[k]!=p)
tmp=max(tmp,down[q]-val[to[k]]+down[to[k]]+len[j]+len[k]);
ans+=tmp,val[q]=tmp;
}
}
for(int i=1;i<=n;++i)
{
int p=queue[i],max1=-1<<30,id=0,max2=-1<<30,v1=0;
if(father[p])
v1=up[father[p]]+down[father[p]]-val[p]+down[p];
for(int j=start[p];j;j=next[j])
if(to[j]!=father[p])
{
int q=to[j],v=down[q]+len[j]-val[q];
up[q]=up[p]+down[p]-val[q];
if(father[p])
up[q]=max(up[q],v1-val[to[j]]+len[j]+in[p]);
if(max1<=v)
max2=max1,max1=v,id=j;
else if(max2<=v)
max2=v;
}
for(int j=start[p];j;j=next[j])
if(to[j]!=father[p])
{
int q=to[j];
if(j==id)
up[q]=max(up[q],up[p]+down[p]-val[q]+max2+len[j]);
else
up[q]=max(up[q],up[p]+down[p]-val[q]+max1+len[j]);
}
}
}
int work()
{
int ans=0;
BFS(1);
for(int i=1;i<=n;++i)
ans=max(ans,up[i]+down[i]);
return ans;
}
int main()
{
freopen("beads.in","r",stdin);
freopen("beads.out","w",stdout);
read();
printf("%d\n",work());
fclose(stdin);
fclose(stdout);
return 0;
}



感觉要我去考的话……打死我都不能AK
T1如果不在IOI赛制下就呵呵了……T2如果不会写斜率优化就呵呵了
T3没想到点子上去,智商太低不能多说

bzoj刚刚添了一个dzy loves Chinese……
挺感兴趣的去看了下,发现不会做……找dzy问了下方法……
我**都*了你就让我看这个?
  评论这张
 
阅读(1803)| 评论(10)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017