820test

Kurumi995 · 2019-08-22 21:37:13 · 个人记录

CDQ分治真是个神奇的东西

【agent】

Description

IMF(不可能任务小组)有N个Agent，每个Agent的能力值互不相同，现在部长先生想要派出A,B两队Agent去参加特别任务。但是参加大战的两个队伍要满足两个要求：

1. A队中能力最大的Agent的能力值要小于B队能力最弱的Agent的能力值。

2. A,B两队都要有人参加。

并不是所有的Agent都要去参加的，心急的部长先生想知道有多少种安排Agent的方案。由于答案可能很大，所以只需要你求出答案模10^9+7的值就可以了。

Input

输入仅一行，为一个整数N。

Output

输出答案模10^9+7的值。

Sample Input 1

3

Sample Output 1

5

Sample Input 2

6

Sample Output 2

129

数据范围

对于20%的数据 N≤10

对于40%的数据 N≤1000

对于60%的数据 N≤10^5

对于100%的数据 N≤10^9

解析

因为A队中能力最大的agent能力值小于B对能力最小的agent的能力值，所以A中任意agent能力值一定小于B中任意agent的能力值。我们可以假设能力值是有序的，依次枚举A队中能力值最大的agent。

设i为A队中能力值最大的agent，定义该种情况下的方案数为：

f[i]=(c(i-1,0)+c(i-1,1)+c(i-1,2)+...+c(i-1,i-1))*(2^{n-i}-1)

=2^{i-1}*(2^{n-i}-1)

=2^{n-1}-2^{i-1}

即前i-1个数中可以任选入A队，后n-i个数至少选一个进入B队。

所以答案就显而易见了（只需几步繁琐复杂的化简而已）：

ans=\sum_{i=1}^{n}f[i]

=\sum_{i=1}^{n}n*(2^{n-1}-2^{i-1})

=n*2^{n-1}-\sum_{i=1}^{n}2^{i-1}

=n*2^{n-1}-(2^{n}-1)

=n*2^{n-1}-2^{n}+1

一个快速幂就搞定啦。

Code

#include<bits/stdc++.h>
using namespace std;
long long n,mod=1000000007,ans;
long long qkpow(long long x,long long b){
    long long res=1;
    while(b){
        if(b&1){
            res*=x;
            res%=mod;
        }
        x*=x; 
        x%=mod;
        b>>=1;
    }
    return res%mod;
}
int main(){
    freopen("agent.in","r",stdin);
    freopen("agent.out","w",stdout);
    scanf("%lld",&n);
    ans=n;
    ans*=qkpow(2,n-1);
    ans%=mod;
    ans-=qkpow(2,n)%mod;
    ans++;
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}

【小奇回地球】

Description

开学了，小奇在回地球的路上，遇到了一个棘手的问题。

简单来说，它要从标号为1的星球到标号为n的星球，某一些星球之间有航线。由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球a到b耗费的时间和星球b到a耗费的时间不一定相同。

宇宙法规定：“禁止在出发时间前到达目的地。”

每艘飞船上都有速度调节装置，可以调节飞行的时间。其功能可以使得整次航程中所有两星球间的飞行时间增加或减少相同的整数值。你的任务是帮助它调整速度调节器，使从1~n的最短路径符合宇宙法规定。

Input

输入文件包含多组数据，第1个数为T，表示数据组数。对于每组数据，输入第1行为两个正整数n，m，为星球的个数和星球间的路线数。接下来m行，每行三个整数i，j和t，表示由星球i到星球j飞行的时间为t。由i到j最多只会有一条飞行线路。

Output

输出文件共T行，每组数据输出一行。如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星球1到星球n的最短时间。（注意最短时间要大于或者等于0）。如果不能由星球1到达星球n，则输出-1。

Sample Input

1
4 5
1 2 1
1 3 1
2 3 -3
3 1 1
3 4 1

Sample Output

2

数据范围

1，2号测试点，保证所有星球出度不超过1

3，4号测试点，n<=10

5，6号测试点，-100<=t<=100

对于100%的数据T<=10，n<=100，m<=n*(n-1)，-100000<=t<=100000

数据随机和构造结合生成

解析

根据宇宙法规定，可知从1~n的最短路径必须是非负数，否则就是”在出发点之前达到目的地“。由于答案与要求之间具有单调性，可以考虑二分答案，如果当前所加的时间不能使1~n的最短路径满足宇宙法规定，说明还需加更多时间；反之则考虑加更少时间（或减少时间）。check的部分跑SPFA就可以了。

需要注意的是，跑SPFA判断出有负环不一定就代表不合法，因为有可能这个负环对1~n的最短路径没有影响，换句话说，就是这个负环上的点无法到达n。所以最开始要删去无法到达n的点，可以用建反向边来实现。

Code

#include<bits/stdc++.h>
#define maxn 10000
#define INF 0x3f3f3f3f
using namespace std;
int t,n,m,flag[maxn+5];
int head[105],head0[105],hd[maxn+5],newp=0,p,np=0,cnt[105],v[105];
long long dist[105],ans=INF;
queue<int> q;
struct node{
    int u,v,w;
    int nex;
}e[maxn+5],e0[maxn+5],op[maxn+5];
void add(int a,int b,int c){
    p++;
    e[p].u=a;
    e[p].v=b;
    e[p].w=c;
    e[p].nex=head[a];
    head[a]=p;
}
void add0(int a,int b,int c){
    newp++;
    e0[newp].u=a;
    e0[newp].v=b;
    e0[newp].w=c;
    e0[newp].nex=head0[a];
    head0[a]=newp;
}
void opadd(int a,int b,int c){
    np++;
    op[np].u=a;
    op[np].v=b;
    op[np].w=c;
    op[np].nex=hd[a];
    hd[a]=np;
}
void dfs(int x){
    flag[x]=1;
    for(int i=hd[x];i;i=op[i].nex){
        int y=op[i].v;
        if(flag[y])continue;
        dfs(y);
    }
}
bool spfa(int s,int k){
    memset(cnt,0,sizeof(cnt));
    memset(v,0,sizeof(v));
    for(int i=1;i<=n;i++)dist[i]=INF;
    while(!q.empty())q.pop();
    q.push(s);
    dist[s]=0;
    v[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        v[x]=0;
        cnt[x]++;
        if(cnt[x]>=n){
            return false;
        }
        for(int i=head[x];i;i=e[i].nex){
            int y=e[i].v;
            if(dist[y]>dist[x]+e[i].w+k){
                dist[y]=dist[x]+e[i].w+k;
                if(!v[y]){
                    q.push(y);
                    v[y]=1;
                }
            }
        }
    }
    return true;
} 
int main(){
    freopen("earth.in","r",stdin);
    freopen("earth.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        newp=0;
        np=0;
        p=0;
        memset(head0,0,sizeof(head0));
        memset(hd,0,sizeof(hd));
        memset(head,0,sizeof(head));
        int x,y,z;
        scanf("%d%d",&n,&m);
        if(n==1){
            printf("0\n");
            continue;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&z);
            add0(x,y,z);
            opadd(y,x,z);
        }
        dfs(n);
        for(int i=1;i<=newp;i++){
            if(!flag[e0[i].u] || !flag[e0[i].v])continue;
            add(e0[i].u,e0[i].v,e0[i].w);
        }
        ans=INF;
        int l=-100000,r=100000;
        while(l<=r){
            int mid=(l+r)/2;
            if(spfa(1,mid) && dist[n]>=0){
                ans=dist[n];
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        if(ans!=INF)printf("%lld\n",ans);
        else printf("-1\n");
    }
    return 0;
} 

【极光】

Description

天空中出现了许多的北极光，这些北极光组成了一个长度为n的正整数数列a[i],远古之魔书上记载到：2个位置的graze值为两者位置差与数值差的和：

graze(x,y)=|x-y|+|a[x]-a[y]|。

要想破解天罚，就必须支持2种操作（k都是正整数）：

Modify x k：将第x个数的值修改为k。

Query x k：询问有几个i满足graze(x,i)<=k。

由于从前的天罚被圣王lmc破解了，所以rhl改进了她的法术，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为同样的数值，按多次统计）。

Input

第1行两个整数n,q。分别表示数列长度和操作数。

第2行n个正整数，代表初始数列。

第3~q+2行每行一个操作。

Output

对于每次询问操作，输出一个非负整数表示答案。

Sample Input

3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

Sample Output

2
3
3

数据范围

N<=40000, 修改操作数<=60000, 询问操作数<=10000, Max{a[i]}(含修改)<=80000

解析

先来看看做这道题的必备技能——

1. 曼哈顿距离：

对于平面内两点 A(x1,y1) , B(x2,y2)，记它们的曼哈顿距离为|x1-x2|+|y1-y2|，即两点横纵坐标差之和。

如图所示，图中A,B两点的曼哈顿距离为AC+BC=4+3=7

如果把与原点的曼哈顿距离为1的所有点连起来，会形成一个边长为\sqrt{2}的正方形：

2. 切比雪夫距离：

对于平面内两点 A(x1,y1) , B(x2,y2)，记它们的切比雪夫距离为max(|x1-x2|,|y1-y2|)，即两点横纵坐标差的最大值。

如图所示，图中A,B两点的切比雪夫距离为max(AC,BC)=4

如果把与原点的切比雪夫距离为1的所有点连起来，会形成一个边长为2的正方形：

与曼哈顿正方形（乱取的名字）对比，会发现两个距离是可以相互转化的：

记点 A(x,y) 为原坐标系中与原点曼哈顿距离为x+y的点，将其坐标变为新坐标系中的点 B(x+y,x-y) 后,会发现A与原点的曼哈顿距离=B与原点的切比雪夫距离。

记点 A(x,y) 为原坐标系中与原点切比雪夫距离为max(x,y)的点，将其坐标变为新坐标系中的点 B(\frac{x+y}{2},\frac{x-y}{2}) 后,会发现A与原点的曼哈顿距离=B与原点的切比雪夫距离。

有木有觉得很神奇呢？？？

那么问题来了，这道题和曼哈顿和切比雪夫有神魔关系？？？

如果把数列中的每个位置i与其对应的值a[i]记作一个点 (i,a[i])，那么很显然，两个位置的graze值就等于两点之间的曼哈顿距离。所以对于每个询问Query(x,k)，问题就转化成求有几个i满足点x到点i的曼哈顿距离小于等于k，根据上面的图，可知只需要在以点x为中心的正方形区域内找点的个数即可。然鹅，这个曼哈顿正方形（说了是随便取的名字）的边与横纵坐标轴不平行或垂直，所以不好求。说到这里是不是想到点什么了？？

没错，我们可以将这个曼哈顿正方形转成切比雪夫正方形~~~

那么这道题的突破口已经找到了，剩下的就交给离线算法——CDQ分治（点我吧）来解决。

Code

#include<bits/stdc++.h>
#define maxn 16000000
#define offset 8000000
using namespace std;
int n,m;
int t=0,cnt=0,num=0;
int lowbit[maxn+5],c[maxn+5],ans[maxn+5];
struct aurora{
    int dfn,type,pos;
    int x,y;
}s[maxn+5],tmp[maxn+5];
struct record{
    int x,y;
}f[maxn+5];
bool cmp(aurora a,aurora b){
    if(a.dfn==b.dfn){
        if(a.x==b.x){
            if(a.y==b.y){
                return a.type<b.type;
            }
            return a.y<b.y;
        }
        return a.x<b.x;
    }
    return a.dfn<b.dfn;
}
void init(){
    for(int i=1;i<=maxn;i++)lowbit[i]=i&(-i);
}
void add(int pos,int dx){
    while(pos<=maxn){
        c[pos]+=dx;
        pos+=lowbit[pos];
    }
}
int query(int pos){
    int res=0;
    while(pos>=1){
        res+=c[pos];
        pos-=lowbit[pos];
    }
    return res;
}
void CDQ(int l,int r){
    if(l==r)return ;
    int mid=(l+r)>>1;
    CDQ(l,mid);
    CDQ(mid+1,r);
    int p=l,q=mid+1;
    int d=0,pp=0;
    while(p<=mid && q<=r){
        if(s[p].x<=s[q].x){
            if(s[p].type==1){
                add(s[p].y,1);
                pp=p;
            }
            d++;
            tmp[d]=s[p];
            p++;
        }
        else{
            if(s[q].type==2)ans[s[q].pos]+=query(s[q].y);
            else if(s[q].type==3)ans[s[q].pos]-=query(s[q].y);
            d++;
            tmp[d]=s[q];
            q++;
        }
    }
    while(p<=mid){
        d++;
        tmp[d]=s[p];
        p++;
    }
    while(q<=r){
        if(s[q].type==2)ans[s[q].pos]+=query(s[q].y);
        else if(s[q].type==3)ans[s[q].pos]-=query(s[q].y);
        d++;
        tmp[d]=s[q];
        q++;
    }
    for(int i=l;i<=pp;i++)if(s[i].type==1)add(s[i].y,-1);
    for(int i=0;i<d;i++)s[l+i]=tmp[i+1];
}
int main(){
    freopen("aurora.in","r",stdin);
    freopen("aurora.out","w",stdout);
    init(); 
    scanf("%d%d",&n,&m);
    cnt=1;
    int a,b;
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        t++;
        s[t].dfn=cnt;
        s[t].x=i+a+offset;
        s[t].y=i-a+offset;
        s[t].type=1;
        f[i].x=s[t].x;
        f[i].y=s[t].y;
    }
    char tmp[15];
    for(int i=1;i<=m;i++){
        cin>>tmp>>a>>b;
        if(tmp[0]=='M'){
            cnt++;
            t++;
            s[t].dfn=cnt;
            s[t].x=a+b+offset;
            s[t].y=a-b+offset;
            s[t].type=1;
            f[a].x=s[t].x;
            f[a].y=s[t].y;
        }
        else{
            int nx=f[a].x;
            int ny=f[a].y;
            int px=nx-b,py=ny-b;
            int qx=nx+b,qy=ny+b;
            num++;
            t++;
            s[t].pos=num;
            s[t].dfn=cnt;
            s[t].x=px-1;
            s[t].y=py-1;
            s[t].type=2;
            t++;
            s[t].pos=num;
            s[t].dfn=cnt;
            s[t].x=qx;
            s[t].y=qy;
            s[t].type=2;
            t++;
            s[t].pos=num;
            s[t].dfn=cnt;
            s[t].x=px-1;
            s[t].y=qy;
            s[t].type=3;
            t++;
            s[t].pos=num;
            s[t].dfn=cnt;
            s[t].x=qx;
            s[t].y=py-1;
            s[t].type=3;
        }
    }
    sort(s+1,s+1+t,cmp);
    CDQ(1,t);
    for(int i=1;i<=num;i++)printf("%d\n",ans[i]);
    return 0;
}