[3/12福建四校联考]

来自FallDream的博客。未经允许，请勿转载，谢谢

------------------------------------------------

A.跳马

T组数据，每次给定x和y，要求从(0,0)走马字形(一个坐标变化1，另一个变化2)到(x,y)的最小步数。 T<=1000;x,y<=10^9

先贪心，然后小暴力。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read()
{
    int  x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

const int d[8][2]={{2,-1},{2,1},{1,2},{1,-2},{-1,2},{-1,-2},{-2,1},{-2,-1}};
int dis[105][105];
int x,y,ans;
int qx[20005],qy[20005],top,tail;

inline int abs(int x){return x<0?-x:x;}

void bfs()
{
    memset(dis,0,sizeof(dis));dis[50][50]=1;top=tail=0;qx[++top]=50;qy[top]=50;
    while(top!=tail)
    {
        int xx=qx[++tail],yy=qy[tail];
        for(int i=0;i<8;i++)
        {
            int nx=xx+d[i][0],ny=yy+d[i][1];
            if(nx<0||ny<0||dis[nx][ny]||nx>100||ny>100) continue;
            dis[nx][ny]=dis[xx][yy]+1;qx[++top]=nx;qy[top]=ny;
        }     
    }
}

int main()
{
    freopen("jump.in","r",stdin);
    freopen("jump.out","w",stdout);
    int t=read();
    while(t--)
    {
        x=abs(read());y=abs(read());    bfs();
        if(x<y)swap(x,y);ans=0;
        if(x>50&&x>2*y+3){int t=(x-2*y-50)/4;if(t>0){x-=t*4;ans+=t*2;}}
        if(x<y)swap(x,y);
            if(x>50) {int t=(x-y-100)/2;if(t>0){ans+=t*2;x-=t*4;y-=t*2;}}
            if(x>1000&&y>1000){int t=(x-1000)/3;x-=t*3;y-=t*3;ans+=t*2;}
        while(x+y>=50)
        {
            if(x<y)swap(x,y);
            if(x-4>=2*y)x-=4;else x-=4,y-=2;ans+=2;
        }
        printf("%d
",ans+dis[x+50][y+50]-1);
    }
    return 0;
}

B.绝对值

给定n个实数，每个实数在li,ri中随机选取，求和的绝对值的期望值。abs(li,ri)<=10^6，n<=15

积分？没听说过，贴个题解跑路。

C.序列。

有n个序列对，每个对有a和b两个值。你要把这个序列分成任意段，满足每一段的a的最大值的和不超过m,并且对于任意的i<j且bi<=aj，i和j要分在一段中。在这基础上，你要使得每一段的b的和最大值最小。

求这个最小的最大值。n<=100000,m<=10^12,a,b<=10^9

做法：先缩点。

很容易想到二分一个答案，我们可以用f[i]表示前i个点满足条件时的a的最大值的和的最小值。用这样n^2的dp来check，复杂度n^2logn可以通过20分。

然后我们发现在这个dp中，如果在可以选择的区间里，我们发现每个点，它到现在这个点的转移费用是中间的最大值，所以可以维护一个单调队列，使得其中的ai单调下降(很显然上升的话小的那个点并不可能成为转移费用)。这样对于每个ai，由于f是单调上升的，所以可以把它可以作为转移费用的这段区间的最左端的f值加上它的i值作为一个可能最优的答案扔到线段树里面，这样我们就把转移的复杂度降到了logn，可以通过啦。

复杂度nlog^2n

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 262144
#define INF 20000000000000000LL
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

int n,cnt=0;ll m;
ll l[200005];
ll a[100005],b[100005];
ll f[100005];
ll s[100005],mx[100005];
ll T[N*2+5];
ll q[100005],top,tail;
int d[100005],lt[100005];

void renew(int x,ll ad)
{
    x+=N;T[x]=min(T[x],ad);
    for(x>>=1;x;x>>=1)T[x]=min(T[x<<1],T[x<<1|1]);
}

void change(int x,ll ad)
{
    //cout<<"change"<<x<<" "<<ad<<endl;
    x+=N;T[x]=ad;
    for(x>>=1;x;x>>=1)T[x]=min(T[x<<1],T[x<<1|1]);
}

ll query(int l,int r)
{
    l=max(l,1);ll sum=INF;
    for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1)
    {
        if(~l&1)sum=min(sum,T[l+1]);
        if( r&1)sum=min(sum,T[r-1]);    
    }
    return sum==INF?0:sum;
}

int get(int x,ll lim)
{
    int l=1,r=x,mid,ans=x;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(s[x]-s[mid-1]>lim)l=mid+1;
        else ans=mid,r=mid-1;    
    }
    return ans-1;
}

bool check(ll x)
{
    tail=top=1;q[tail]=1;for(int i=1;i<=N*2+1;i++)T[i]=INF;
    change(1,mx[1]);f[1]=mx[1];//cout<<x<<endl;
    for(int i=2;i<=n;i++)
    {        
        int pos=get(i,x);
        while(pos>=q[tail]&&top>=tail) ++tail;    
        while(mx[i]>=mx[q[top]]&&top>=tail)--top;
        q[++top]=i;change(top,f[(top==tail)?pos:q[top-1]]+mx[i]);
        change(tail,f[pos]+mx[q[tail]]);
        f[i]=query(tail,top);
    }    
//    cout<<x<<" "<<f[n]<<endl;
    return f[n]<=m;
}

int main()
{
    freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        l[i<<1]=a[i]=read();
        l[(i<<1)-1]=b[i]=read();
    }sort(l+1,l+2*n+1);int j=0;
    for(int i=1;i<=n<<1;i++) if(l[i]!=l[i-1])l[++j]=l[i];
    for(int i=1;i<=N*2+1;i++)T[i]=INF;
    for(int i=1;i<=n;i++)
    {
        int x=lower_bound(l+1,l+j+1,a[i])-l;
        int y=lower_bound(l+1,l+j+1,b[i])-l;
        lt[i]=query(1,x);if(!lt[i]) lt[i]=i;
        renew(y,i);
    }
    for(int i=1;i<=N*2+1;i++)T[i]=INF;
    for(int i=1;i<=n;i++)
        renew(i,lt[i]);    
    for(int i=n;i;)
    {
        int x=lt[i],y=query(x,i);
        for(;y<x;x=y,y=query(x,i));
        ++cnt;for(int j=x;j<=i;j++)mx[cnt]=max(mx[cnt],a[j]),s[cnt]+=b[j];
        i=x-1;
    }n=cnt; 
    ll l=1,r=2000000000000000LL,mid,ans;
    for(int i=1;i<=n;i++)swap(s[i],s[n-i+1]),swap(mx[i],mx[n-i+1]);
    for(int i=1;i<=n;i++)l=max(l,s[i]),s[i]+=s[i-1];
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;    
    }
    cout<<ans<<endl;
    return 0;
}