BZOJ3876:[Ahoi2014]支线剧情 有上下界网络流

思路:

首先建立有上下界的网络流模型:

\[S->1~cap=[0,INF]~cost=0\]

\[i->T~cap=[0,INF]~cost=0(1\leq{i}\leq{n})\]

\[x->y~cap=[1,INF]~cost=w_{x->y}(ForEach x->y)\]

显然是有源汇的上下界网络流模型,我们对下界不为0的边拆边变成只有上界的网络流模型:

设立附加源\(SS\),附加汇\(\ST),则对于:

\[a->b~cap=[l,r]~cost=w_{a->b}\]

我们这样转化:

(1)\[SS->b~Maxcap=l~cost=w_{a->b}\]

(2)\[a->ST~Maxcap=l~cost=0\]

(3)\[a->b~Maxcap=r-l~cost=w_{a->b}\]

注意:(1)(2)中只有一种边的费用为原来费用,另一种边的费用为0.(至于为什么这样连先挖坑)

我们还需要连:

\[T->S~Maxcap=INF~cost=0\]

然后就可以用最小费用最大流水过了.(有时间试试单纯形)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x3f3f3f3f
 
int cnt;
queue<int>q;
struct Solver{
    int head[5100],next[50010],end[50010],flow[50010],cost[50010],ind;
    int d[5100],used[5100],slack[5100],id;bool inq[5100];
    inline void reset(){ind=0,id=1,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q++]=c;}
    inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);}
    inline void spfa(int S,int T){
        memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S);
        while(!q.empty()){
            int i=q.front();q.pop(),inq[i]=0;
            for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                d[end[j]]=d[i]+cost[j];
                if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }for(int i=0;i<=cnt;++i)d[i]=d[T]-d[i];
    }
    inline bool Newlabel(){
        int Min=INF;for(int i=0;i<=cnt;++i)if(used[i]!=id&&slack[i]<Min)Min=slack[i];
        if(Min==INF)return 0;
        for(int i=0;i<=cnt;++i)if(used[i]==id)used[i]=-1,d[i]+=Min;return 1;
    }
    int Getflow(int p,int T,int maxflow){
        if(p==T)return maxflow;
        used[p]=id;
        for(int j=head[p];j!=-1;j=next[j]){
            if(flow[j]&&used[end[j]]!=id&&d[end[j]]+cost[j]==d[p]){
                int to=Getflow(end[j],T,maxflow<flow[j]?maxflow:flow[j]);if(to){flow[j]-=to,flow[j^1]+=to;return to;}
            }else if(flow[j])slack[end[j]]=min(slack[end[j]],d[end[j]]+cost[j]-d[p]);
        }return 0;
    }
    int Mincost(int S,int T){
        int res(0),get;spfa(S,T);
        do{
            memset(slack,0x3f,sizeof slack);
            while((get=Getflow(S,T,INF)))res+=d[S]*get,++id;
        }
        while(Newlabel());
        return res;
    }
}SteinsGate;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    int n;scanf("%d",&n);
    cnt=n;int SS=0,ST=++cnt,S=++cnt,T=++cnt;
    SteinsGate.reset();
 
    int t,a,c;register int i,j;
    SteinsGate.make(S,1,INF,0);
    for(i=1;i<=n;++i){
        SteinsGate.make(i,T,INF,0);
        scanf("%d",&t);
        while(t--)scanf("%d%d",&a,&c),SteinsGate.make(SS,a,1,c),SteinsGate.make(i,ST,1,0),SteinsGate.make(i,a,INF,c);
    }
    SteinsGate.make(T,S,INF,0);
 
    printf("%d",SteinsGate.Mincost(SS,ST));
 
    return 0;
}

BZOJ2119:股市的预测 分治+后缀数组

思路:

一种分治的神做法.建议去看原论文[2011年集训队作业]

#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
#define N 50010
 
int n,lim;
 
int len[N];
inline void pre(int n){
    for(int i=2;i<=n;++i)len[i]=len[i>>1]+1;
}
 
int Read[N],s[N],ss[N],v[N],nv[N],q[N],c[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]));
}
struct SuffixArray{
    int rk[N],h[N],sa[N],rmqh[N][16];
    inline void Init(int s[],int n,int m){
        int i,j,k,hl,id;
        for(i=1;i<=m;++i)c[i]=0;
        for(i=1;i<=n;++i)++c[v[i]=s[i]];
        for(i=2;i<=m;++i)c[i]+=c[i-1];
        for(i=n;i>=1;--i)sa[c[v[i]]--]=i;
        for(int d=1;;++d){
            for(hl=1<<(d-1),id=0,i=n-hl+1;i<=n;++i)q[++id]=i;
            for(i=1;i<=n;++i)if(sa[i]>hl)q[++id]=sa[i]-hl;
            for(i=1;i<=m;++i)c[i]=0;
            for(i=1;i<=n;++i)++c[v[q[i]]];
            for(i=2;i<=m;++i)c[i]+=c[i-1];
            for(i=n;i>=1;--i)sa[c[v[q[i]]]--]=q[i];
            for(i=m=1;i<=n;++m,i=j+1){
                for(j=i;j!=n&&cmp(sa[j],sa[j+1],hl,n);++j);
                for(k=i;k<=j;++k)nv[sa[k]]=m;
            }
            if(--m==n)break;
            for(i=1;i<=n;++i)v[i]=nv[i];
        }
         
        for(i=1;i<=n;++i)rk[sa[i]]=i;
        for(i=1;i<=n;++i){
            if(rk[i]==1)continue;
            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;
        }
        for(i=1;i<=n;++i)rmqh[i][0]=h[i];
        for(j=1;j<=15;++j)for(i=1;i+(1<<j)-1<=n;++i)rmqh[i][j]=min(rmqh[i][j-1],rmqh[i+(1<<(j-1))][j-1]);
    }
    inline int askrmq(int l,int r){
        return min(rmqh[l][len[r-l+1]],rmqh[r-(1<<len[r-l+1])+1][len[r-l+1]]);
    }
    inline int getlcp(int x,int y){
        int lins=min(rk[x],rk[y]),rins=max(rk[x],rk[y]);
        if(lins==rins)return n-x+1;
        else return askrmq(lins+1,rins);
    }
}Steins,revSteins;
 
inline int lcp(int x,int y){
    return Steins.getlcp(x,y);
}
inline int lcs(int x,int y){
    return revSteins.getlcp(n-x+1,n-y+1);
}
inline bool same(int l1,int l2,int len){
    return lcp(l1,l2)>=len;
}
 
map<int,int>M;int sav[N];
 
long long res;
inline void SteinsGate(int l,int r){
    if(r-l+1<lim+2)return;
    int mid=(l+r)>>1;
    SteinsGate(l,mid),SteinsGate(mid+1,r);
    int prelen,suflen,insl,insr,nowlen;
    for(prelen=0;prelen<lim;++prelen){
        suflen=lim-1-prelen;
        insl=mid-prelen,insr=mid+suflen;
        if(insl>=l&&insr<=r)
            for(nowlen=1;insl-nowlen>=l&&insr+nowlen<=r;++nowlen)if(same(insl-nowlen,insr+1,nowlen))++res;
    }
    int lins,rins,anotherins,Lcp,Lcs,up,down;
    for(anotherins=l;anotherins<=r;++anotherins){
        if((anotherins>mid&&anotherins-mid-1>=lim)||(mid>anotherins&&mid-anotherins-1>=lim)){
            lins=min(mid,anotherins),rins=max(mid,anotherins);
            Lcp=lcp(lins,rins),Lcs=lcs(lins,rins);
            down=-INF,up=INF;
            down=max(down,rins-Lcs-lim+1);//rins-(x+m-1)<=lcs
            up=min(up,lins+Lcp);//x-lins<=lcp
            down=max(down,l-lim+rins-lins);//lins-(rins-(x+m-1))+1>=l
            up=min(up,r+1+lins-rins);//rins+(x-lins)-1<=r
            down=max(down,lins+1),up=min(up,rins-1);//lins<=x<=rins
            down=max(down,lins+2-lim),up=min(up,rins-lim);//lins<=x+m-1<=rins
            if(down<=up){
                res+=up-down+1;
                if(anotherins<mid&&down==anotherins+1)--res;
            }
        }
    }
}
 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    scanf("%d%d",&n,&lim);register int i;
    for(i=0;i<n;++i)scanf("%d",&Read[i]);
    for(--n,i=1;i<=n;++i)s[i]=Read[i]-Read[i-1];
     
    for(i=1;i<=n;++i)sav[i]=s[i];sort(sav+1,sav+n+1);
    int id=0;for(sav[0]=-INF,i=1;i<=n;++i)if(sav[i]!=sav[i-1])M[sav[i]]=++id;
    for(i=1;i<=n;++i)s[i]=M[s[i]];
    for(i=n;i>=1;--i)ss[i]=s[n+1-i];
     
    pre(n),Steins.Init(s,n,id),revSteins.Init(ss,n,id);
     
    SteinsGate(1,n);
     
    cout<<res<<endl;
     
    return 0;
}

BZOJ2795:[Poi2012]A Horrible Poem 暴力+hash(&&BZOJ2890)

思路:

一开始的暴力非常容易:对于每一组询问直接暴力枚举答案即可.易知答案仅可能是字串长度的约数,再利用hash\(O(1)\)判断.因此单组询问的复杂度\(O(\sqrt{n})\).这种方法比较卡常数.

其实,存在一种更加科学的方法.

我们将长度分解质因数,考虑每个质因子的幂次.这样即可在\(O(logn)\)的时间内出解.十分科学.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;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++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[20000000],*o=buf;
    template<typename T>inline void Print(T x){
        static int stk[100];
        if(x<0)x=-x,*o++='-';
        if(!x)*o++=48;else{int top=0;for(;x;x/=10)stk[++top]=x%10;for(int i=top;i;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void Final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 500010
 
typedef long long LL;
static const int seed=131;
static const int mod=(1e9)+9;
 
int n,f[N],mi[N];char s[N];
 
inline int get(int l,int r){
    return (f[l]-(LL)f[r+1]*mi[r-l+1]%mod+mod)%mod;
}
inline bool same(int l1,int r1,int l2,int r2){
    return get(l1,r1)==get(l2,r2);
}
 
int p[N],minp[N],cnt;bool np[N];
inline void pre(int n){
    register int i,j;
    for(i=2;i<=n;++i){
        if(!np[i])p[++cnt]=minp[i]=i;
        for(j=1;j<=cnt&&p[j]*i<=n;++j){
            np[i*p[j]]=1,minp[i*p[j]]=min(minp[i],p[j]);
            if(i%p[j]==0)break;
        }
    }
}
 
inline int Solve(int l,int r){
    int len=r-l+1;if(len==1)return 1;
    int tmp=len,res=len;
    while(tmp!=1){
        int nowp=minp[tmp],ans=1,calclen=len,t=1;
        while(1){
            if(calclen==len||same(l,l+(len-calclen)-1,r-(len-calclen)+1,r))ans=max(ans,t);
            if(calclen%nowp!=0)break;
            t*=nowp,calclen/=nowp;
        }
        for(res/=ans;tmp%nowp==0;tmp/=nowp);
    }
    return res;
}
int main(){
    using namespace Fio;
    scanf("%d",&n);scanf("%s",s+1);
    register int i;
    for(i=n;i>=1;--i)f[i]=((LL)seed*f[i+1]+s[i]-'a')%mod;
    for(mi[0]=1,i=1;i<=n;++i)mi[i]=(LL)mi[i-1]*seed%mod;
    pre(n);
     
    int m;Get(m);int l,r;
    while(m--){
        Get(l),Get(r);
        Print(Solve(l,r));
    }
    Final();
    return 0;
}

BZOJ3174:[Tjoi2013]拯救小矮人 贪心+dp

思路:

假设在能逃出相同多数目的小矮人的情况下,我们更愿意让逃生能力更强的小矮人留到最后.

逃生能力就是指\(a_i+b_i\),也即在下面垫的总高度确定时更容易达到更高的高度.

这样我们就有了一个贪心选择顺序,我们设\(f[i]\)表示逃生了\(i\)个小矮人时下面垫的总高度的最大值,并依据这个判定能否再逃出一人即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 2010
struct Case{int a,b;bool operator<(const Case&B)const{return a+b<B.a+B.b;}}S[N];
 
int f[N];
int main(){
    int n,m;scanf("%d",&n);register int i,j;for(i=1;i<=n;++i)scanf("%d%d",&S[i].a,&S[i].b);
    sort(S+1,S+n+1);
    scanf("%d",&m);
    memset(f,-1,sizeof f);for(f[0]=0,i=1;i<=n;++i)f[0]+=S[i].a;
    int ans=0;
    for(i=1;i<=n;++i){
        for(j=ans;j>=0;--j){
            if(f[j]+S[i].b>=m)f[j+1]=max(f[j+1],f[j]-S[i].a);
             
        }if(f[ans+1]>=0)++ans;
    }
    printf("%d\n",ans);
    return 0;
}

BZOJ2799:[Poi2012]Salaries 贪心

思路:

我们维护以每一个节点为根的子树内部有多少个没有确定权值的点,另外,我们利用一个数组维护每个权值已经给了哪个节点.

我们从小到大遍历每个权值,若这个权值当前并没有确定给哪个节点,则将其压入栈中;否则我们在对应节点的子树中进行一系列确定操作:

我们维护栈中有多少个权值,以及有多少个自由权值.(这个是什么一会再说)

若未确定的节点数正好等于当前的自由权值数与栈中的权值总数,显而易见这些权值都应该分配给这棵子树.但是只有只有一个儿子的情况才能确定这个权值.所以我们不断在链上去找即可.这个过程可能确定了一些权值,随后我们将栈清空,并令自由权值的数目为0.因为他们只能被拘束在这颗子树内,而不能去别的地方.

若不然,我们将自由权值及栈中的权值分配给这棵子树所需要的数目,剩下的全部变成自由权值.

我们发现栈中的权值和自由权值很像,但是为什么不都搞成自由权值,而是非要维护一个栈呢?

这个问题显而易见:自由权值都是可以互相交换的(等价的),而栈中的元素显然不是!

于是\(O(n)\)水.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;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++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
 
#define N 1000010
vector<int>v[N];
int pa[N],w[N];
int q[N],fr,ta,ins[N],size[N],stk[N],top,tot,sum;
int main(){
    int n;Fio::Get(n);
    register int i,j;
    for(i=1;i<=n;++i){
        Fio::Get(pa[i]),Fio::Get(w[i]);if(i==pa[i])w[i]=n;
        if(w[i])q[ta++]=i,ins[w[i]]=i;else v[pa[i]].push_back(i);
    }
    int u;
    while(fr<ta){
        u=q[fr++];
        for(j=0;j<v[u].size();++j)q[ta++]=v[u][j];
    }
    for(i=n-1;i>=0;--i){
        u=q[i];
        size[u]=1;
        for(j=0;j<v[u].size();++j)size[u]+=size[v[u][j]];
    }
    int tot=0;
    for(i=1;i<=n;++i){
        if(!(u=ins[i])){stk[++top]=i;continue;}
        int sum=0,ac=0,pretop=top;
        for(j=0;j<v[u].size();++j)sum+=size[v[u][j]];
        if(sum==tot+top){
            for(;v[u].size()==1&&top;u=v[u][0])
                ins[w[v[u][0]]=stk[top--]]=v[u][0],++ac,--sum;
            if(sum)tot=top=0;
        }
        else{
            if(sum)tot=tot+top-sum,top=0;
        }
    }
    for(i=1;i<=n;++i)printf("%d\n",w[i]);
    return 0;
}

 

BZOJ3028:食物 生成函数

思路:

对于一个数列\(f_0,f_1,f_2,...\),我们可以对应的构造一个多项式函数\(f_0+f_1{x}+f_2{x^2}+...\),也即若我们可以知道函数的\(x^n\)项系数,就能知道\(f_n\).

一眼看起来并没有什么用处,实际上有的多项式函数可以化为十分简洁的形式.

例如\(f_0=f_1=f_2=...=1\),其对应的多项式函数为\(1+x+x^2+x^3+...\).

由于我们只在意式子的"型",因此可以利用方便的等比数列来表示:

\[\frac{1-x^{\infty}}{1-x}\]

若\(|x|<1\),则可以化为:

\[\frac{1}{1-x}\]

事实上我们不必在意\(x\)的范围,仅仅是看重形式便可以了.

对于这道题目的计数问题,我们仅需搞出所有限制的多项式,然后将它们相乘.

最终经过一些化简得到:

\[\frac{x}{(1-x)^4}\]

接下来有一种处理方法就是暴力泰勒展开(就是无限求导),感觉不可能找到规律(至少我是不会).

然后又一种方法就是再进行变形:

\[x(1+x+x^2+...)^4\]

求上式的\(x^n\)次项的系数.于是变成简单的组合数问题.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

char s[510];
int main(){
	scanf("%s",s);int len=strlen(s);register int i,j;
	int t=0;for(i=0;i<len;++i)t=(t*10+s[i]-'0')%10007;
	int res=t;res=res*(t+1)%10007,res=res*(t+2)%10007;
	res=res*1668%10007;
	printf("%d",res);
	return 0;
}

BZOJ1195:[HNOI2006]最短母串 AC自动机+状压dp

思路:

首先我的思路十分傻叉,是\(f[i][j][k]\)表示长度为\(i\),在自动机上的节点为\(j\),包含子串的状态为\(k\)可不可能.但这样复杂度直接爆炸.

但是我们可以令\(f[i][j]\)表示在自动机上的节点为\(i\),包含子串的状态为\(j\)时的最短长度.

这样我们就转化成了边权均为1的单源最短路,BFS就行了.

若按照字母字典序从小到大的顺序进行BFS,得出的就是字典序最小的答案了.

(有点卡内存)

(话说我一开始AC自动机都写错,没治了)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 12
#define L 610
 
short ch[L][26],end[L],pre[L],cnt;
 
char s[L];
 
int q[L],fr,ta;
short lastchar[L*(1<<N)];
int laststate[L*(1<<N)];
short state[L*(1<<N)];
short ins[L*(1<<N)];
bool vis[L][1<<N];
 
char ans[L];int id;
 
int main(){
    int n;scanf("%d",&n);register int i,j;
    int p,y;
    for(i=1;i<=n;++i){
        scanf("%s",s);int len=strlen(s);
        for(p=j=0;j<len;++j){
            if(!ch[p][y=s[j]-'A'])ch[p][y]=++cnt;p=ch[p][y];
        }end[p]|=1<<(i-1);
    }
    for(j=0;j<26;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<26;++j)if(ch[u][j]){
            for(q[ta++]=v=ch[u][j],r=pre[u];r&&!ch[r][j];r=pre[r]);end[v]|=end[pre[v]=ch[r][j]];
        }
        else ch[u][j]=ch[pre[u]][j];
    }
    int mask;
    for(fr=ta=0,state[0]=ins[0]=0,++ta;fr^ta;){
        u=ins[fr],mask=state[fr];
        if(mask==(1<<n)-1){
            for(;fr;fr=laststate[fr])ans[++id]=lastchar[fr];
            for(i=id;i>=1;--i)putchar('A'+ans[i]);
            return 0;
        }
        for(j=0;j<26;++j)if(!vis[ch[u][j]][mask|end[ch[u][j]]]){
            lastchar[ta]=j,laststate[ta]=fr,ins[ta]=ch[u][j],state[ta]=mask|end[ch[u][j]];
            vis[ins[ta]][state[ta]]=1;
            ta++;
        }++fr;
    }
    return 0;
}

BZOJ1043:[HAOI2008]下落的圆盘 计算几何+离线处理

思路:

嗯,我诅咒你,出题人,持续一辈子的呦~~

我们考虑每个圆对于最终答案的贡献,显然就是将所有在之后的圆覆盖在这个圆上的部分去掉,剩下的若干段弧长.

那么接下来就是找出对于一个圆,他有哪些部分是被覆盖的.

我们对于每一个后面的圆,找出他覆盖在这个圆上面的极角序区间,最后我们再求一次区间的并就可以了.

找出这段区间成为了这道题目的难点.

首先我们找出两个圆的交点.什么你不会?

看下面的图片:(假设是圆\(O_2\)覆盖圆\(O_1\))

(看不清楚图片请点击一下放大来看)求出\(a,b\)之后,就很容易利用向量求出两个交点坐标了.(具体怎么求就不要问我了吧QoQ)

然后我们确定这两个点关于点\(O_1\)的极角序,但是究竟是由哪一个指向哪一个呢?

我们只要再确定点\(O_2\)关于圆心\(O_1\)的极角序,并保证上述的区间经过这个位置即可.

具体的细节就只能自己体会了.可以参照我的代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
inline f2 sqr(const f2&x){
    return x*x; 
}
static const f2 PI=acos(-1.0);
 
#define N 1010
struct Point{
    f2 x,y;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
};
f2 dist(const Point&A,const Point&B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
 
typedef Point vector;
inline vector Getvertical(vector _v){return vector(-_v.y,_v.x);}
inline f2 Getlength(vector _v){return sqrt(sqr(_v.x)+sqr(_v.y));}
inline vector Getunitvector(vector _v){
    f2 length=Getlength(_v);
    return vector(_v.x/length,_v.y/length);
}
 
struct Circle{
    Point o;f2 r;
    Circle(){}
    Circle(Point _o,f2 _r):o(_o),r(_r){}
    f2 get(const Point&B)const{return atan2(B.y-o.y,B.x-o.x);}
}C[N];
inline bool IsIntersect(const Circle&A,const Circle&B){
    return A.r+B.r>dist(A.o,B.o);
}
inline bool IsCover(const Circle&A,const Circle&B){
    return A.r>=B.r&&dist(A.o,B.o)<=A.r-B.r;
}
 
struct Interval{
    f2 l,r;
    Interval(){}
    Interval(f2 _l,f2 _r):l(_l),r(_r){}
    bool operator<(const Interval&B)const{return l<B.l;}
}S[N<<1];int id;
inline bool find(f2 l,f2 r,f2 x){
	if(l<=r)return x>=l&&x<=r;else return x>=l||x<=r;
}
inline void add(f2 l,f2 r){
    if(l<=r)S[++id]=Interval(l,r);else S[++id]=Interval(l,PI),S[++id]=Interval(-PI,r);
}
 
int main(){
    int n;scanf("%d",&n);
    register int i,j,k;
    for(i=1;i<=n;++i){
        scanf("%lf%lf%lf",&C[i].r,&C[i].o.x,&C[i].o.y);
    }
    f2 totans=0,a,b,d,ang1,ang2,ango;Point p1,p2; 
    vector v,_v;
    for(i=n;i>=1;--i){
        bool cover=0;id=0;
        for(j=i+1;j<=n&&!cover;++j)if(IsCover(C[j],C[i]))cover=1;
        if(!cover){
            for(j=i+1;j<=n;++j)if(IsIntersect(C[i],C[j])&&!IsCover(C[i],C[j])){
                d=dist(C[i].o,C[j].o);
                b=(sqr(C[i].r)-sqr(C[j].r)+sqr(d))/(2*d);
                a=sqrt(sqr(C[i].r)-sqr(b));
                v=C[i].o-C[j].o,_v=Getunitvector(Getvertical(v));
                p1=C[i].o+v*(b/d)+_v*a,p2=C[i].o+v*(b/d)+_v*(-a);
                ang1=C[i].get(p1),ang2=C[i].get(p2),ango=C[i].get(C[j].o);
                if(find(ang1,ang2,ango))add(ang1,ang2);else add(ang2,ang1);
            }
            totans+=2*PI*C[i].r;
            if(id){
                sort(S+1,S+id+1);
                f2 Maxr;
                for(j=1;j<=id;){
                    for(Maxr=S[j].r,k=j+1;k<=id;++k){
                        if(S[k].l>Maxr)break;
                        if(S[k].r>Maxr)Maxr=S[k].r;
                    }
                    totans-=C[i].r*(Maxr-S[j].l);
                    j=k;
                }
            }
        }
    }
    printf("%.3lf",totans);
    return 0;
}

BZOJ3357:[Usaco2004]等差数列 dp

思路:

我们令\(f[i][j]\)表示等差数列最后两项的下标分别为\(i,j\)时的最长长度.

显然我们有:

\[f[i][j]=max_{k=1}^{i-1}\{f[k][i]+1\}(2a[i]=a[j]+a[k])\]

重要的就是如何快速找出\(k\)的位置.

我们呢就可以将权值离散化,记录一下每个权值在序列中出现的位置.

于是我们要找的\(k\),显然就是权值相同时标号小于\(i\)且最大的一个.

因此我们维护一个vector然后二分就好了.

(注意\(n=1\)233)

 

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
 
#define N 2010
vector<int>v[N];
 
int a[N],b[N],id;
map<int,int>M;
 
int f[N][N];
 
int main(){
    int n;scanf("%d",&n);if(n==1){puts("1");return 0;}register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);for(b[0]=-1<<30,i=1;i<=n;++i)if(b[i]!=b[i-1])M[b[i]]=++id;
    for(i=1;i<=n;++i)v[M[a[i]]].push_back(i);
    int nowv,ins,siz;
    for(j=2;j<=n;++j){
        for(i=1;i<j;++i){
            f[i][j]=2;
            nowv=M[2*a[i]-a[j]];
            if(nowv){
                siz=v[nowv].size();
                if(v[nowv][0]<i){
                    int L=0,R=siz-1,mid;
                    while(L<R){
                        mid=(L+R+1)>>1;
                        if(v[nowv][mid]<i)L=mid;else R=mid-1;
                    }f[i][j]=max(f[i][j],f[v[nowv][L]][i]+1);
                }
            }
        }
    }
    int res=0;for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)res=max(res,f[i][j]);
    printf("%d",res);
    return 0;
}

BZOJ1345:[Baltic2007]序列问题Sequence 乱搞

思路:

首先我们考虑序列中最大的元素,如果它是当前区间的头或者尾,当然是只合并一次最优了,否则当然是至少要合并两次了.

将这个元素的影响去掉,然后将区间分裂开,递归处理就行了.容易发现总处理区间数是\(O(n)\)的.

那么现在我们的问题是,给出\(O(n)\)个询问,每次询问一段区间的最大值的标号.

那么我们有两种策略:

[1]RMQ ST算法 \(O(nlogn)-O(1) 空间O(nlogn)\)

[2]直接线段树 \(O(n)-O(logn) 空间O(n)\)

事实上[2]的常数很小,而[1]会TLE!再兼具空间,可以说,在这种询问次数下,[2]完爆[1]!

所以这样就水过去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;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++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
 
#define N 1000010
int a[N];
 
struct SegmentTree{
    int ins[262144*8],M;
    inline void Init(int _siz){
        for(M=1;M<(_siz+2);M<<=1);
        for(int i=1;i<=_siz;++i)ins[M+i]=i;
        a[0]=-INF;for(int i=M-1;i>=1;--i)ins[i]=a[ins[i<<1]]>a[ins[i<<1^1]]?ins[i<<1]:ins[i<<1^1];
    }
    inline int ask(int tl,int tr){
        int res=0;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if((~tl&1)&&(a[res]<a[ins[tl^1]]))res=ins[tl^1];
            if((tr&1)&&(a[res]<a[ins[tr^1]]))res=ins[tr^1];
        }return res;
    }
}Seg;
 
struct Intv{
    int l,r;Intv(){}Intv(int _l,int _r):l(_l),r(_r){}
}q[N];int fr,ta;
 
int main(){
    int n;Fio::Get(n);register int i,j;for(i=1;i<=n;++i)Fio::Get(a[i]);Seg.Init(n);
    long long ans=0;
    q[ta++]=Intv(1,n);Intv tmp;int ins;
    while(fr^ta){
        tmp=q[fr++];if(tmp.l==tmp.r)continue;ins=Seg.ask(tmp.l,tmp.r);
        if(ins==tmp.l)ans+=a[ins],q[ta++]=Intv(tmp.l+1,tmp.r);else if(ins==tmp.r)ans+=a[ins],q[ta++]=Intv(tmp.l,tmp.r-1);
        else ans+=2LL*a[ins],q[ta++]=Intv(tmp.l,ins-1),q[ta++]=Intv(ins+1,tmp.r);
    }
    printf("%lld\n",ans);
    return 0;
}