BZOJ1704: [Usaco2007 Mar]Face The Right Way 自动转身机
Aug 18, 2015 07:53:41 PM
题解:
首先枚举$k$,那我们需要知道给定$k$,最少进行多少次操作.
显然应该从小到大进行扫描,考虑当前位置$i$,若颜色不对,则反转$[i,i+k-1]$.
然后再判定剩下的位置颜色对不对.
这个过程可以利用单调队列轻松实现,详情见代码.
代码:
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 5010
bool a[N];
int q[N],fr,ta;
int main(){
int n;
scanf("%d",&n);
int i,j;
char s[10];
for(i=1;i<=n;++i){
scanf("%s",s);
a[i]=(s[0]=='F');
}
int ans=0x3f3f3f3f,temp,k;
for(i=1;i<=n;++i){
fr=ta=0;
for(temp=0,j=1;j+i-1<=n;++j){
while(fr!=ta&&q[fr]+i-1<j)
++fr;
if((((ta-fr)&1)^a[j])==0){
q[ta++]=j;
++temp;
}
}
bool ok=1;
for(j=n+2-i;j<=n;++j){
while(fr!=ta&&q[fr]+i-1<j)
++fr;
if((((ta-fr)&1)^a[j])==0)
ok=0;
}
if(ok){
if(temp<ans){
ans=temp;
k=i;
}
}
}
cout<<k<<" "<<ans<<endl;
return 0;
}
BZOJ2221:[Jsoi2009]面试的考验 单调性+随机数据
Mar 05, 2015 09:32:32 AM
思路:
宋文杰的题解很详细.
一开始每个点30s,结果在OJ上一共30s...
也就是说原来莫队是能过的,结果我无悬念TLE.
莫队怎么做我就不说了.(貌似官方正解就是莫队...)
莫队很暴力,因为没有利用一个题目中的性质:就是数据随机生成!
询问随不随机意义是不大的.
但是如果询问很特殊,我们就可以用科学的方法去处理:
(1)任意两个区间不互相包含.这种情况我们将区间随便排个序就能发现总移动次数是\(O(n)\)的.
(2)任意两个区间要么互相包含,要么不相交.这样就会形成一棵树.我们利用启发式合并,插入次数就为\(O(nlogn)\).
但是随机数据显然没有这种性质.
那么唯一可能有比较优秀的性质的就是随机数列了.
考虑一种朴素算法:
将所有询问离线按照右端点从小到大排序.
从前向后依次加入右端点,令\(f_i\)表示当前以\(i\)为起点的后缀的答案,那么朴素来看,如果当前加入的是\(n\),那么\(f_1-f_{n-1}\)都需要更新.
但是有很多冗余的更新.
例如我们考虑所有大于\(a_n\)的数,不妨令\(a_i,a_j>a_n,a_i>a_j,i<j\),那么如果我们能够维护一个后缀的答案,我们就只需更新\(f_j\)就可以了.
于是我们发现了某些单调性.
我们利用数据结构维护后缀的答案,那么只需更新一些点就行了.
那么我们的任务就是找到,对于\(n\)之前的数,一个均\(>a_n\)的递减序列,一个均\(<a_n\)的递增序列.然后我们就拿序列中的东西暴力更新答案.
然而由于是随机数据,序列中的元素个数是\(O(logn)\)级别的.
这样总时间复杂度就是\(O(qlogn+nlog^2n)\).
具体去看宋文杰的题解.
(另外此题要求结果\(>0\) 23333)
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
#define Q 100010
int n,q,a[N];
struct Interval{
int l,r,lab;
bool operator<(const Interval&B)const{return r<B.r;}
}S[N];
int re[Q];
inline void mini(int&x,int y){if(x>y)x=y;}
struct SegmentTree{
int A[262144],M;
inline void Init(int _siz){
for(M=1;M<(_siz+2);M<<=1);
memset(A,0x3f,sizeof A);
}
inline void modify(int x,int d){
for(x+=M;x;x>>=1)mini(A[x],d);
}
inline int query(int tl,int tr){
int re=~0U>>1;
for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
if(~tl&1)mini(re,A[tl^1]);
if(tr&1)mini(re,A[tr^1]);
}
return re;
}
}Seg;
int preless[N],premore[N],small[N][30],big[N][30],stk[N],top;
int main(){
//freopen("tt.in","r",stdin);
scanf("%d%d",&n,&q);
register int i,j,k;
for(i=1;i<=n;++i)scanf("%d",&a[i]);
for(i=1;i<=q;++i)
scanf("%d%d",&S[i].l,&S[i].r),S[i].lab=i;
sort(S+1,S+q+1);
Seg.Init(n);
for(i=1;i<=n;++i){
while(top&&a[stk[top]]>=a[i])--top;
preless[i]=stk[top];
stk[++top]=i;
}
top=0;
for(i=1;i<=n;++i){
while(top&&a[stk[top]]<=a[i])--top;
premore[i]=stk[top];
stk[++top]=i;
}
for(i=1;i<=n;++i){
if(premore[i]){
big[i][++big[i][0]]=premore[i];
j=big[i][1];
while(1){
bool find=0;
for(k=1;k<=small[j][0];++k)if(a[small[j][k]]>a[i]){find=1;break;}
if(find)big[i][++big[i][0]]=(j=small[j][k]);else break;
}
}
if(preless[i]){
small[i][++small[i][0]]=preless[i];
j=small[i][1];
while(1){
bool find=0;
for(k=1;k<=big[j][0];++k)if(a[big[j][k]]<a[i]){find=1;break;}
if(find)small[i][++small[i][0]]=(j=big[j][k]);else break;
}
}
}
j=1;
for(i=1;i<=n;++i){
for(k=1;k<=small[i][0];++k)Seg.modify(small[i][k],a[i]-a[small[i][k]]);
for(k=1;k<=big[i][0];++k)Seg.modify(big[i][k],a[big[i][k]]-a[i]);
for(;j<=q&&S[j].r==i;++j)re[S[j].lab]=Seg.query(S[j].l,S[j].r);
}
for(i=1;i<=q;++i)printf("%d\n",re[i]);
return 0;
}
APIO2010信号覆盖 单调性+计算几何+容斥原理
Feb 13, 2015 11:47:02 PM
思路:
一开始只是YY出了一个\(O(n^3logn)\)的算法.
我们枚举每两个点,同时再枚举另外一个点,就能得到这三个点的圆心前在两个点垂直平分线的位置.
那么现在我们再枚举每个点出现在这种圆中有多少种情况:这个点已经给定时,我们可以考虑圆心在垂直平分线上的可行位置,通过解不等式发现仅仅满足一个限制就是可行的圆心.于是就可以用数据结构维护快速得到有多少个可行的圆心.
然而正解的思路非常巧妙:
考虑每四个点,要么形成一个凸多边形,要么形成一个凹多边形.
由于没有任意四个点在一个圆上,那么对于一个凸多边形对于答案的贡献是2,一个凹多边形对于答案的贡献是1.
考虑如何计算凹多边形的数目.(然后我们也可以知道凸多边形的数目)
我们枚举中间的凹点,那么发现形成凹多边形的另外三个点必然不在凹点的同侧.因此我们就转化为计算总数减去在凹点同侧的三元组数目,这个利用极角序排序以及单调性可以\(O(nlogn)\)得到.
因此就在\(O(n^2logn)\)的时间内做出来了.
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef double f2;
#define N 1510
int x[N],y[N];
struct Point{
int x,y;
f2 Ang;
inline void read(){scanf("%d%d",&x,&y);}
Point(){}
Point(int _x,int _y):x(_x),y(_y){}
Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
bool operator<(const Point&B)const{return Ang<B.Ang;}
inline void print(){printf("%d %d\n",x,y);}
}P[N],seq[N<<1];int cnt;
inline LL Cross(const Point&a,const Point&b){return(LL)a.x*b.y-(LL)a.y*b.x;}
int main(){
//freopen("tt.in","r",stdin);
int n;scanf("%d",&n);int i,j,k;
for(i=1;i<=n;++i)P[i].read();
LL res=0;
for(i=1;i<=n;++i){
for(cnt=0,j=1;j<=n;++j)if(i^j)seq[++cnt]=P[j],seq[cnt].Ang=atan2(P[j].y-P[i].y,P[j].x-P[i].x);
sort(seq+1,seq+cnt+1);
for(j=cnt+1;j<=2*cnt;++j)seq[j]=seq[j-cnt];
res+=(LL)(n-1)*(n-2)*(n-3)/6;
int get;k=1;
for(j=1;j<=cnt;++j){
while(k+1!=j+cnt&&Cross(seq[j]-P[i],P[i]-seq[k+1])<=0)++k;
//printf("j=%d ",j);seq[j].print();printf("k=%d ",k),seq[k].print();puts("");
get=k-j;
res-=(LL)get*(get-1)/2;
}
}
LL all=(LL)n*(n-1)*(n-2)*(n-3)/24;
LL ret=res+(all-res)*2;
printf("%.3lf",3.0+(f2)ret*6/n/(n-1)/(n-2));
return 0;
}
BZOJ2276:[Poi2011]Temperature 单调性+线段树
Jan 30, 2015 12:51:43 PM
思路:
貌似存在\(O(n)\)的算法,不过由于我太弱只想到了\(O(nlogn)\).
现在很困就发代码了...有问题回复找我吧.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 1000010
struct SegmentTree{
int a[2100000],M;
inline void Init(int _siz){
for(M=1;M<(_siz+2);M<<=1);
memset(a,0xc0,sizeof a);
}
inline void upd(int x,int to){
for(a[x+=M]=to,x>>=1;x;x>>=1)a[x]=max(a[x<<1],a[x<<1^1]);
}
inline int ask(int tl,int tr){
int res=-1<<30;
for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
if(~tl&1)res=max(res,a[tl^1]);
if(tr&1)res=max(res,a[tr^1]);
}return res;
}
}Seg;
int up[N];
namespace Fio{
inline int getc(){
#ifndef ONLINE_JUDGE
static const int L=1<<1;
#else
static const int L=1<<15;
#endif
static char buf[L],*S=buf,*T=buf;
if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}return*S++;
}
inline bool digit(char c){return c>='0'&&c<='9';}
template<typename T>inline void Get(T&x){
int c=0;while(!digit(c=getc())&&c!='-');bool sign=c=='-';x=sign?0:c-'0';
while(digit(c=getc()))x=(x<<1)+(x<<3)+c-'0';if(sign)x=-x;
}
}
int main(){
int n;Fio::Get(n);register int i,j;
Seg.Init(n);
int x;for(i=1;i<=n;++i)Fio::Get(x),Fio::Get(up[i]),Seg.upd(i,x);
int nowmax=Seg.ask(1,1);
int lans,ans;
for(lans=2;lans<=n;++lans){
if(nowmax>up[lans])break;
nowmax=max(nowmax,Seg.ask(lans,lans));
}ans=--lans;
for(i=2;i<=n;++i){
nowmax=Seg.ask(i,lans);
for(++lans;lans<=n;++lans){
if(nowmax>up[lans])break;
nowmax=max(nowmax,Seg.ask(lans,lans));
}--lans;
ans=max(ans,lans-i+1);
}
printf("%d",ans);
return 0;
}
POJ3415 Common Substrings 后缀数组+单调栈
Jan 11, 2015 04:45:10 PM
思路:
最近好像是被<囚人的旋律>里的主人公的心情所影响,所以效率很低.
例如,这样一道傻逼题我居然傻逼了3个小时!
我整个人都单调栈了.
就是求个height,然后在连续块内,我们对于每个属于串A的后缀分别计算出在他前面的属于串B的后缀的影响,在计算出在他之后的属于B的后缀的影响.
然后我们从前到后,再从后到前扫描一边,利用一个单调栈维护一下属于串B的后缀即可.
说起来简单...不过写起来...一定是我太鶸了.
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define N 200010
char s1[N],s2[N],s[N];int v[N],tv[N],q[N],c[N],sa[N];
inline bool cmp(int x,int y,int hl,int n){
return v[x]==v[y]&&((x+hl>=n&&y+hl>=n)||(x+hl<n&&y+hl<n&&v[x+hl]==v[y+hl]));
}
inline void calcsa(char*s,int n,int m,int*sa){
register int i,j,k;int id,hl;
for(i=0;i<m;++i)c[i]=0;
for(i=0;i<n;++i)++c[v[i]=s[i]];
for(i=1;i<m;++i)c[i]+=c[i-1];
for(i=n-1;i>=0;--i)sa[--c[v[i]]]=i;
for(int d=1;;++d){
for(hl=1<<(d-1),id=0,i=n-hl;i<n;++i)q[id++]=i;
for(i=0;i<n;++i)if(sa[i]>=hl)q[id++]=sa[i]-hl;
for(i=0;i<m;++i)c[i]=0;
for(i=0;i<n;++i)++c[v[q[i]]];
for(i=1;i<m;++i)c[i]+=c[i-1];
for(i=n-1;i>=0;--i)sa[--c[v[q[i]]]]=q[i];
for(i=m=0;i<n;i=j+1,++m){
for(j=i;j<n-1&&cmp(sa[j],sa[j+1],hl,n);++j);
for(k=i;k<=j;++k)tv[sa[k]]=m;
}for(i=0;i<n;++i)v[i]=tv[i];
if(m==n)break;
}
}
int rk[N],h[N];
inline void calch(char*s,int n,int*sa,int*rk,int*h){
register int i,j;
for(i=0;i<n;++i)rk[sa[i]]=i;
for(i=0;i<n;++i)if(rk[i]){
j=max(0,h[rk[i-1]]-1);while(i+j<n&&sa[rk[i]-1]+j<n&&s[i+j]==s[sa[rk[i]-1]+j])++j;h[rk[i]]=j;
}
}
int lim;
struct Case{
int v,c;
Case(){}
Case(int _v,int _c):v(_v),c(_c){}
}stk[N];
int top,nowcnt;long long sum[N];int cnt[N];
int belong[N];
int main(){
int i,j,k;
while(scanf("%d",&lim)&&lim){
scanf("%s%s",s1,s2);int len1=strlen(s1),len2=strlen(s2);
memset(s,0,sizeof s);int len=0;for(i=0;i<len1;++i)belong[len]=1,s[len++]=s1[i];s[len++]='$';for(i=0;i<len2;++i)belong[len]=2,s[len++]=s2[i];
calcsa(s,len,256,sa),calch(s,len,sa,rk,h);
LL ans=0;int tmp;
for(i=1;i<len;){
if(h[i]>=lim){
for(j=i;j<len&&h[j]>=lim;++j);
for(top=0,h[i-1]=h[i],tmp=h[j],h[j]=h[j-1],k=i-1;k<j;++k){
nowcnt=0;
while(top&&stk[top].v>=h[k])nowcnt+=stk[top--].c;
if(nowcnt)stk[++top]=Case(h[k],nowcnt),sum[top]=sum[top-1]+(LL)stk[top].c*stk[top].v,cnt[top]=cnt[top-1]+stk[top].c;
if(belong[sa[k]]==2)ans+=sum[top]-(LL)cnt[top]*(lim-1);
else{
nowcnt=1;while(top&&stk[top].v>=h[k+1])nowcnt+=stk[top--].c;
stk[++top]=Case(h[k+1],nowcnt),sum[top]=sum[top-1]+(LL)stk[top].c*stk[top].v,cnt[top]=cnt[top-1]+stk[top].c;
}
}
for(top=0,k=j-1;k>=i-1;--k){
nowcnt=0;
while(top&&stk[top].v>=h[k+1])nowcnt+=stk[top--].c;
if(nowcnt)stk[++top]=Case(h[k+1],nowcnt),sum[top]=sum[top-1]+(LL)stk[top].c*stk[top].v,cnt[top]=cnt[top-1]+stk[top].c;
if(belong[sa[k]]==2)ans+=sum[top]-(LL)cnt[top]*(lim-1);
else{
nowcnt=1;while(top&&stk[top].v>=h[k])nowcnt+=stk[top--].c;
stk[++top]=Case(h[k],nowcnt),sum[top]=sum[top-1]+(LL)stk[top].c*stk[top].v,cnt[top]=cnt[top-1]+stk[top].c;
}
}h[j]=tmp;
i=j;
}else++i;
}
cout<<ans<<endl;
}
return 0;
}