Codeforces Round #625 (Div. 1)

A. Journey Planning
给你n个点和他们的权值,你可以从任意点开始跳,但是接下来跳的点有限制,要求\(j>i\)并且\(a_i-i=a_j-j\),然后可以获得\(a_j\)的权值,问最多能获得多少。
解 把每一位的值减掉pos,然后相同的合到一起即可。
复杂度 \(O(n\log n)\)

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
map<ll,ll>m;
ll a[400005];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        m[a[i]-i]+=a[i];
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,m[a[i]-i]);
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

B.Navigation System
给n个点,m条单向边,给一条长度为k的路径从起点到终点,每到一个点时,系统会推荐一条最短路径(有相同的则随机),如果沿着系统给的路径走则最短路径不变,问最短路线最少和最多改变几次。
解 将边反向然后倒着跑bfs 记录每个点到终点的距离,同时将每个点最短距离所可以走的边存起来,然后按照路径走,如果走的不是最短中的一个,那么2个都++,如果走的是最短,并且是唯一的一条,则不变,如果不是唯一的一条,那么最多++。
复杂度 \(O(n\logn)\)

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
vector<int>v[200005];
int q[200005];
int vis[200005];
set<int>s[200005];
void bfs(int x)
{
    pair<int,int>now;
    now.fr=x;
    now.sc=0;
    queue<pair<int,int> >q;
    q.push(now);
    while(!q.empty()){
        now=q.front();
        q.pop();
        for(int i=0;i<v[now.fr].size();i++){
            pair<int,int>nxt;
            nxt.fr=v[now.fr][i];
            nxt.sc=now.sc+1;
            if(vis[nxt.fr]==0&&nxt.fr!=x){
                vis[nxt.fr]=nxt.sc;
                s[nxt.fr].insert(now.fr);
                //printf("%d %d\n",now.fr,nxt.fr);
                q.push(nxt);
            }else{
                if(vis[nxt.fr]==nxt.sc){
                    s[nxt.fr].insert(now.fr);
                   // printf("%d %d\n",now.fr,nxt.fr);
                }
            }
            
        }
    }
}
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[y].push_back(x);
    }
    int k;
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        scanf("%d",&q[i]);
    }
    bfs(q[k]);
    int minn=0;
    int maxx=0;
    for(int i=2;i<=k;i++){
        if(s[q[i-1]].find(q[i])!=s[q[i-1]].end()){
            if(s[q[i-1]].size()!=1){
                maxx++;
            }
        }else{
            minn++;
            maxx++;
        }
    }
    printf("%d %d\n",minn,maxx);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

C. World of Darkraft: Battle for Azathoth
有n把剑,分别有\(x_i\)的攻击力和\(v_i\)的价格,有m个盾,分别有\(x_i\)的防御力和\(v_i\)的价格,你必须选一把剑和一个盾,有q个怪物,分别有 \(x_i\)的防御力,\(y_i\)的攻击力和\(v_i\)的价值,只有你的攻击力大于怪物的防御力并且你的防御力大于怪物的攻击力才能杀死怪物获得怪物的价值,问最大收益。
解 将剑以攻击力排序,将盾离散化后插入线段树,然后将怪物以防御力排序。枚举剑,然后将防御力小于剑的攻击力的怪物插入到线段树盾的防御力大于怪物攻击力的地方,然后求全局最大值即可。
复杂度 \O(n\logn)\)
调试代码比较多。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
struct node
{
    int x;
    int v;
    int id;
}a[200005],b[200005];
struct node1
{
    int x,y,v;
}c[200005];
bool cmp(node a,node b)
{
    if(a.x!=b.x)return a.x<b.x;
    else return a.v<b.v;
}
bool cmp1(node1 a,node1 b)
{
    if(a.y!=b.y)return a.y<b.y;
    else return a.x<b.x;
}
int d[200005];
ll maxx[200005<<2];
ll lazy[200005<<2];
void pushup(int rt)
{
    maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
}
void pushdown(int rt)
{
    if(lazy[rt]){
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        maxx[rt<<1]+=lazy[rt];
        maxx[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    if(l==r){
        maxx[rt]=-b[l].v;
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int x)
{
    if(L<=l&&R>=r){
        maxx[rt]+=x;
        lazy[rt]+=x;
        return;
    }
    pushdown(rt);
    int m=(l+r)>>1;
    if(L<=m)update(l,m,rt<<1,L,R,x);
    if(R>m)update(m+1,r,rt<<1|1,L,R,x);
    pushup(rt);
}
// void query(int l,int r,int rt,int x)
// {
//     if(l==r&&l==x){
//         printf("%d %d\n",l,maxx[rt]);
//         return;
//     }
//     pushdown(rt);
//     int m=(l+r)>>1;
//     if(x<=m)query(l,m,rt<<1,x);
//     else query(m+1,r,rt<<1|1,x);
// }
void work()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].v);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&b[i].x,&b[i].v);
        b[i].id=i;
        d[i]=b[i].x;
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&c[i].y,&c[i].x,&c[i].v);
    }
    ll ans=-2e9;
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+m+1,cmp);
    sort(d+1,d+m+1);
    sort(c+1,c+q+1,cmp1);
    build(1,m,1);
    int now=1;
    for(int i=1;i<=n;i++){
        //printf("%d\n",i);
        while(c[now].y<a[i].x&&now<=q){
            //printf("%d\n",now);
            int l=1;
            int r=m;
            while(l<=r){
                //printf("%d %d\n",l,r);
                int mid=(l+r)>>1;
                if(c[now].x<b[mid].x)r=mid-1;
                else l=mid+1;
            }
            //printf("%d %d\n",l,r);
            if(l<=m){
                update(1,m,1,l,m,c[now].v);
                //printf("%d %d %d\n",c[now].x,b[l].x,l);
            }
            now++;
        }
        //printf("i=%d\n",i);
        // for(int j=1;j<=m;j++){
        //     query(1,m,1,j);
        // }
        //printf("%lld\n",maxx[1]-a[i].v);
        ans=max(ans,maxx[1]-a[i].v);
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注