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

ydc的博客

 
 
 

日志

 
 

AHOI2013题解  

2013-12-16 20:58:43|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
找硬币:
大神直接dp秒
我表示不会dp做
很容易发现他有贪心的性质,加上n不大,而且数列不会很长,所以写了个搜索,发现TLE了
想不到剪枝,于是看了mato_no1的题解,有一个很重要的剪枝:
可以强制要求两个相邻数的比值为质数!!!
显然不是质数我可以在中间插数字答案不会变劣
于是就能卡过去了
这都没想到太弱了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define maxn 60
#define maxm 100010
#define lowbit(x) (x&(-x))
using namespace std;
bool isPrime[maxm];
int ans=1<<30,F[maxn],n,tmp[maxn][maxn],coin[maxn],cnt;
vector<int> di[maxm];
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&coin[i]);
sort(coin+1,coin+n+1);
F[1]=1;
for(int i=2;i<=coin[n];++i)
{
int s=0,m=1;
for(;F[m]<=coin[n]/i;++m)
F[m+1]=F[m]*i;
for(int j=1;j<=n;++j)
{
for(int k=m,p=coin[j];k>=1;--k)
s=s+p/F[k],p%=F[k];
if(s>ans)
break;
}
ans=min(ans,s);
}
memset(isPrime,true,sizeof(isPrime));
for(int i=2;i<=coin[n];++i)
if(isPrime[i])
for(int j=i;j<=coin[n];j+=i)
di[j].push_back(j/i),isPrime[j]=false;
}
void DFS(int p,int now)
{
int sum=now,cnt=0;
for(int i=n;i>=1;--i)
{
if(tmp[p-1][i]>=F[p])
sum=sum+tmp[p-1][i]/F[p],tmp[p][i]=tmp[p-1][i]%F[p];
else
tmp[p][i]=tmp[p-1][i];
cnt=cnt+(tmp[p][i]!=0);
}
if(sum+cnt>=ans)
return ;
if(cnt==0)
{
ans=sum;
return ;
}
for(vector<int>::iterator i=di[F[p]].begin();i!=di[F[p]].end();++i)
{
F[p+1]=*i;
DFS(p+1,sum);
}
}
void work()
{
memcpy(tmp[0],coin,sizeof(tmp[0]));
for(int i=coin[n];i*2>=coin[n];--i)
{
F[1]=i;
DFS(1,0);
}
}
int main()
{
read();
work();
printf("%d\n",ans);
return 0;
}


立方体
一开始的想法是枚举每个面,求出他有多大面积没有被覆盖
正打算去写的,得知神一般的lyy竟然WA了
原来他要算的是外表面积……如果你弄几个立方体拼起来内部有个洞洞那么那个洞洞是不能算得,但这个做法是会算的
于是剑哥哥告诉了我做法,是一个挺正常的思路……可惜又没想到
找一个没被覆盖的单位立方体开始BFS,遇到被覆盖的单位立方体就ans++
正确性还是比较显然的……
判断是否被覆盖的话前缀和就行了,既然一维二维会做,三维自然也会做了
什么?空间想象力不够想不清楚?
其实没关系,前缀和的那个递推过程其实就是容斥原理……所以往容斥原理去想的话就很显然了
他们说这题卡空间……所以要用queue才能过
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 210
using namespace std;
struct Node
{
int x,y,z;
Node() {}
Node(int x,int y,int z): x(x),y(y),z(z) {}
};
queue<Node> Q;
bool vis[maxn][maxn][maxn];
int sum[maxn][maxn][maxn];
int sx,sy,sz;
int movex[]={1,-1,0,0,0,0};
int movey[]={0,0,1,-1,0,0};
int movez[]={0,0,0,0,1,-1};
void read()
{
int n,mx=1<<30,my=1<<30,mz=1<<30;
scanf("%d",&n);
for(int i=1,a,b,c,d,e,f;i<=n;++i)
{
scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f);
++a,++b,++c,++d,++e,++f;
sx=max(sx,d+1),sy=max(sy,e+1),sz=max(sz,f+1);
++sum[a][b][c];
--sum[d][b][c],--sum[a][e][c],--sum[a][b][f];
++sum[d][e][c],++sum[d][b][f],++sum[a][e][f];
--sum[d][e][f];
mx=min(mx,a),my=min(my,b),mz=min(mz,c);
}
for(int i=mx;i<=sx;++i)
for(int j=my;j<=sy;++j)
for(int k=mz;k<=sz;++k)
{
sum[i][j][k]=sum[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1];
sum[i][j][k]=sum[i][j][k]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1];
sum[i][j][k]=sum[i][j][k]+sum[i-1][j-1][k-1];
}
}
int BFS()
{
Q.push(Node(sx,sy,sz));
vis[sx][sy][sz]=true;
Node p;
int ans=0;
while(!Q.empty())
{
p=Q.front(),Q.pop();
for(int i=0;i<6;++i)
{
Node q=Node(p.x+movex[i],p.y+movey[i],p.z+movez[i]);
if(q.x>=0&&q.x<=sx&&q.y>=0&&q.y<=sy&&q.z>=0&&q.z<=sz&&vis[q.x][q.y][q.z]==false)
{
if(sum[q.x][q.y][q.z])
++ans;
else
Q.push(q),vis[q.x][q.y][q.z]=true;;
}
}
}
return ans;
}
int main()
{
read();
printf("%d\n",BFS());
return 0;
}


好方的蛇
其实是一道很传统的题
一切都是那么的中规中矩
这种计数问题,就那几个常用做法,什么补集转化拉容斥原理拉强制要求最XX的一个来更新拉
把这几个方法往里面套就行了
我的做法是非常简单地求出sum1[i][j],sum2[i][j],sum3[i][j],sum4[i][j]表示分别以(i,j)为左上左下右上右下的面积非1矩形数
这几个数组能用悬线法+单调栈求出
于是这么来计数:
枚举i,加上左下角在第i列的矩形*右上角在第i列之前的矩形
枚举i,加上右上角在第i行的矩形*左下角在第i行之前的矩形
枚举(i,j),剪去左上角在(i,j)的矩形*右下角在(1,1)->(i-1,j-1)的矩形
枚举(i,j),剪去右上角在(i,j)的矩形*左下角在(1,j+1)->(i-1,n)的矩形
思路是秒出的,代码是相似的
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mod 10007
#define maxn 1010
using namespace std;
typedef long long LL;
char map[maxn][maxn];
int n,sum1[maxn][maxn],sum2[maxn][maxn],sum3[maxn][maxn],sum4[maxn][maxn];
int cnt1[maxn][maxn],cnt2[maxn][maxn];
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%s",map[i]+1);
}
void prepare()
{
static int stack[maxn],h[maxn];
//sum1以(i,j)为左下角的矩形数
for(int i=1;i<=n;++i)
{
int area=0,top=0;
stack[0]=n+1;
for(int j=n;j>=1;--j)
{
h[j]=map[i][j]=='W'?0:h[j]+1;
if(top==0)
area=h[j],stack[++top]=j;
else
{
area+=h[j];
while(top&&h[stack[top]]>=h[j])
area=area-(stack[top-1]-stack[top])*(h[stack[top]]-h[j]),--top;
stack[++top]=j;
}
sum1[i][j]=max(0,area%mod-1);
}
}
memset(h,0,sizeof(h));
//sum2以(i,j)为右上角的矩形数
for(int i=n;i>=1;--i)
{
int area=0,top=0;
stack[0]=0;
for(int j=1;j<=n;++j)
{
h[j]=map[i][j]=='W'?0:h[j]+1;
if(top==0)
area=h[j],stack[++top]=j;
else
{
area+=h[j];
while(top&&h[stack[top]]>=h[j])
area=area-(stack[top]-stack[top-1])*(h[stack[top]]-h[j]),--top;
stack[++top]=j;
}
sum2[i][j]=max(0,area%mod-1);
}
}
memset(h,0,sizeof(h));
//sum3以(i,j)为右下角
for(int i=1;i<=n;++i)
{
int area=0,top=0;
stack[0]=0;
for(int j=1;j<=n;++j)
{
h[j]=map[i][j]=='W'?0:h[j]+1;
if(top==0)
area=h[j],stack[++top]=j;
else
{
area+=h[j];
while(top&&h[stack[top]]>=h[j])
area=area-(stack[top]-stack[top-1])*(h[stack[top]]-h[j]),--top;
stack[++top]=j;
}
sum3[i][j]=max(0,area%mod-1);
}
}
memset(h,0,sizeof(h));
//sum4以(i,j)为左上角
for(int i=n;i>=1;--i)
{
int area=0,top=0;
stack[0]=n+1;
for(int j=n;j>=1;--j)
{
h[j]=map[i][j]=='W'?0:h[j]+1;
if(top==0)
area=h[j],stack[++top]=j;
else
{
area+=h[j];
while(top&&h[stack[top]]>=h[j])
area=area-(stack[top-1]-stack[top])*(h[stack[top]]-h[j]),--top;
stack[++top]=j;
}
sum4[i][j]=max(0,area%mod-1);
}
}
}
int calc1(int a,int b,int c,int d)
{
return (cnt1[c][d]-cnt1[a-1][d]-cnt1[c][b-1]+cnt1[a-1][b-1]+mod+mod)%mod;
}
int calc2(int a,int b,int c,int d)
{
return (cnt2[c][d]-cnt2[a-1][d]-cnt2[c][b-1]+cnt2[a-1][b-1]+mod+mod)%mod;
}
void work()
{
static int F[maxn];
int ans=0;
for(int j=n;j>=1;--j)
{
int s=0;
for(int i=1;i<=n;++i)
{
s=s+sum2[i][j];
F[j]=F[j]+sum1[i][j];
}
s%=mod,F[j]%=mod;
ans=(ans+s*F[j+1])%mod;
F[j]=(F[j]+F[j+1])%mod;
}
for(int i=1;i<=n;++i)
{
int s=0;
F[i]=0;
for(int j=n;j>=1;--j)
{
s=s+sum2[i][j];
F[i]=F[i]+sum1[i][j];
}
s%=mod,F[i]%=mod;
ans=(ans+s*F[i-1])%mod;
F[i]=(F[i]+F[i-1])%mod;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
cnt1[i][j]=(cnt1[i-1][j]+cnt1[i][j-1]-cnt1[i-1][j-1]+sum2[i][j]+mod)%mod;
cnt2[i][j]=(cnt2[i-1][j]+cnt2[i][j-1]-cnt2[i-1][j-1]+sum4[i][j]+mod)%mod;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
ans=(ans-sum1[i][j]*calc1(i+1,1,n,j-1)%mod+mod)%mod;
ans=(ans-sum3[i][j]*calc2(i+1,j+1,n,n)%mod+mod)%mod;
}
printf("%d\n",ans);
}
int main()
{
read();
prepare();
work();
return 0;
}


作业
直接用莫队+树状数组爆搞
出题人表示出数据的时候为了卡暴力,左右端点隔的非常远
于是莫队就飞快了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
#define maxm 1000010
#define lowbit(x) (x&(-x))
using namespace std;
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
int limit,n,m,seq[maxn];
int Sum1[maxn],Sum2[maxn];
void Insert1(int p,int v)
{
for(int i=p;i<=n;i+=lowbit(i))
Sum1[i]+=v;
}
void Insert2(int p,int v)
{
for(int i=p;i<=n;i+=lowbit(i))
Sum2[i]+=v;
}
int Query1(int p)
{
int ans=0;
for(int i=p;i;i-=lowbit(i))
ans+=Sum1[i];
return ans;
}
int Query2(int p)
{
int ans=0;
for(int i=p;i;i-=lowbit(i))
ans+=Sum2[i];
return ans;
}
struct Question
{
int l,r,a,b,ans1,ans2,id;
friend bool operator < (const Question &a,const Question &b)
{
return a.l/limit<b.l/limit||(a.l/limit==b.l/limit&&a.r<b.r);
}
}q[maxm];
bool cmp_id(const Question &a,const Question &b)
{
return a.id<b.id;
}
void read()
{
Read(n),Read(m);
limit=sqrt(n);
for(int i=1;i<=n;i++)
Read(seq[i]);
for(int i=1;i<=m;i++)
{
Read(q[i].l),Read(q[i].r),Read(q[i].a),Read(q[i].b);
q[i].id=i;
}
sort(q+1,q+m+1);
}
int sum[maxn];
void Insert(int p)
{
Insert1(p,1);
sum[p]++;
if(sum[p]==1)
Insert2(p,1);
}
void Delete(int p)
{
Insert1(p,-1);
sum[p]--;
if(sum[p]==0)
Insert2(p,-1);
}
void Mo_Algorithm()
{
for(int i=1,l=1,r=0;i<=m;i++)
{
if(r<q[i].r)
{
for(r=r+1;r<=q[i].r;r++)
Insert(seq[r]);
r--;
}
if(r>q[i].r)
for(;r>q[i].r;r--)
Delete(seq[r]);
if(l<q[i].l)
for(;l<q[i].l;l++)
Delete(seq[l]);
if(l>q[i].l)
{
for(l=l-1;l>=q[i].l;l--)
Insert(seq[l]);
l++;
}
q[i].ans1=Query1(q[i].b)-Query1(q[i].a-1);
q[i].ans2=Query2(q[i].b)-Query2(q[i].a-1);
}
}
void print()
{
sort(q+1,q+m+1,cmp_id);
for(int i=1;i<=m;i++)
printf("%d %d\n",q[i].ans1,q[i].ans2);
}
int main()
{
read();
Mo_Algorithm();
print();
return 0;
}


连通图
以前作HNOI的动态最小生成树的时候我是云里雾里的
现在再看还是好理解多了
这题就是动态最小生成树的弱化版
做法如下:
按询问分治
对于区间[l,r],所有没有参与删除的边,我们可以缩点,这样图的点数就变成O(r-l+1)的一个规模了
当然我们也可以删掉新图的重边,所以边数也是O(r-l+1)了
不断递归下去
感觉最大的收获是懂了动态MST
如果无限RE,请回去看题目最下面一行
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define maxn 100010
#define maxm 200010
using namespace std;
struct Edge
{
int u,v;
};
vector<Edge>graph[20];
int n,m,q,father[maxn];
int ask[maxm][6];
bool ans[maxm];
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void read()
{
Read(n),Read(m);
Edge e;
for(int i=1,a,b;i<=m;++i)
{
Read(a),Read(b);
e.u=a,e.v=b,graph[1].push_back(e);
}
Read(q);
for(int i=1;i<=q;++i)
{
Read(ask[i][0]);
for(int j=1;j<=ask[i][0];++j)
Read(ask[i][j]);
}
}
int Find(int p)
{
if(father[p]!=p)
father[p]=Find(father[p]);
return father[p];
}
void solve(int dep,int l,int r,int n,int m)
{
static int pos_edge[maxm],pos_point[maxn];
static bool mark[maxm];
int id_point=0,id_edge=0;
graph[dep+1].clear();
for(int i=1;i<=m;++i)
mark[i]=false;
for(int i=l;i<=r;++i)
for(int j=1;j<=ask[i][0];++j)
mark[ask[i][j]]=true;
for(int i=1;i<=n;++i)
father[i]=i;
for(int i=1;i<=m;++i)
if(mark[i]==false)
{
int x=graph[dep][i-1].u,y=graph[dep][i-1].v;
if(x==y)
continue;
x=Find(x),y=Find(y),father[x]=y;
}
for(int i=1;i<=n;++i)
if(Find(i)==i)
pos_point[i]=++id_point;
if(id_point==1)
{
for(int i=l;i<=r;++i)
ans[i]=true;
return ;
}
if(l==r)
return ;
for(vector<Edge>::iterator e=graph[dep].begin();e!=graph[dep].end();++e)
{
int i=e-graph[dep].begin()+1;
if(mark[i])
{
pos_edge[i]=++id_edge;
Edge tmp=*e;
tmp.u=pos_point[Find(tmp.u)],tmp.v=pos_point[Find(tmp.v)];
graph[dep+1].push_back(tmp);
}
}
for(int i=l;i<=r;++i)
for(int j=1;j<=ask[i][0];++j)
ask[i][j]=pos_edge[ask[i][j]];
int mid=(l+r)>>1;
solve(dep+1,l,mid,id_point,id_edge),solve(dep+1,mid+1,r,id_point,id_edge);
}
void print()
{
for(int i=1;i<=q;++i)
printf("%s\n",ans[i]?"Connected":"Disconnected");
}
int main()
{
read();
solve(1,1,q,n,m);
print();
return 0;
}



差异
当年我们考试的时候考了这道题,那时还什么都不会的我用后缀数组+暴力+特判考场上水掉了这题
所以就直接贴了上来
在这里放个暴力代码吧……随意就会被卡了
至于正解……
http://ydcydcy1.blog.163.com/blog/static/2160890402013102874844570/
用这题的这个模型应该可以秒才对?
没写过不知道……如果可做时间复杂度应该是后缀数组+线段树合并,O(n log n)的
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define Rep(i,l,r) for(int i=l;i<=r;i++)
#define MAXN 500010
using namespace std;
typedef long long LL;
char a[MAXN];
int F[MAXN][20],Sa[MAXN],rank[MAXN],height[MAXN],Log2[MAXN],n;
LL ans;
void sort(int a[],int b[],int c[],int n,int m)
{
static int sum[MAXN];
for(int i=1;i<=m;i++) sum[i]=0;
for(int i=1;i<=n;i++) sum[c[a[i]]]++;
for(int i=1;i<=m;i++) sum[i]+=sum[i-1];
for(int i=n;i>=1;i--) b[sum[c[a[i]]]--]=a[i];
}
void make_Sa()
{
static int x[MAXN],y[MAXN];
n=strlen(a+1);
Rep(i,1,n) y[i]=a[i]-'a',rank[i]=i;
sort(rank,Sa,y,n,256);
rank[Sa[1]]=1;
Rep(i,2,n) rank[Sa[i]]=rank[Sa[i-1]]+(y[Sa[i]]!=y[Sa[i-1]]);
for(int i=1;i<=n;i<<=1)
{
Rep(j,1,n) x[j]=rank[j],y[j]=j+i<=n?rank[j+i]:0,Sa[j]=j;
sort(Sa,rank,y,n,n),sort(rank,Sa,x,n,n);
rank[Sa[1]]=1;
Rep(j,2,n) 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 make_height()
{
int j=0;
Rep(i,1,n)
{
if(j>0) j--;
if(rank[i]!=1)
while(a[i+j]==a[Sa[rank[i]-1]+j])
j++;
height[rank[i]]=j;
}
}
void ST(int digit[],int n)
{
Rep(i,1,n) F[i][0]=digit[i];
Rep(j,1,Log2[n])
Rep(i,1,n-(1<<j)+1)
F[i][j]=min(F[i][j-1],F[i+(1<<(j-1))][j-1]);
}
int Query(int l,int r)
{
if(l>r) swap(l,r);
int h=Log2[r-l+1];
return min(F[l][h],F[r-(1<<h)+1][h]);
}
LL work()
{
LL total=0,sum=0;
static int next[MAXN],jump[MAXN];
Rep(i,1,n) jump[i]=height[i]==height[i-1]+1?jump[i-1]:i-1;
Rep(i,2,n) Log2[i]=Log2[i-1]+((i&(i-1))==0);
ST(height,n);
Rep(i,2,n)
{
if(height[i-1]<height[i]) next[i]=i-2;
else if(Query(2,i)==height[i]) next[i]=0;
else
{
int l=2,r=i-1;
while(l<r)
{
int mid=(l+r)>>1;
if(Query(mid+1,i)<height[i]) l=mid+1;
else r=mid;
}
next[i]=l-1;
}
}
Rep(i,2,n)
{
int j=i,k;
LL p=1<<30;
if(jump[j]!=j-1)
{
int l=jump[j];
LL y=height[j],v;
v=(y-height[l+2]+1)*(height[l+2]+y);
sum=sum+v,p=y;
j=l;
}
while(j)
{
p=j==i?height[j]:height[j+1],k=j==i?next[j]:next[j+1];
sum=sum+p*(j==i?j-k-1:j-k)*2;
j=k;
}
}
Rep(i,1,n)
{
LL len=i;
total=total+len*(n-1);
}
return total-sum;
}
int main()
{
scanf("%s",a+1);
make_Sa();
make_height();
printf("%lld\n",work());
return 0;
}

  评论这张
 
阅读(1123)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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