Codeforces Round #791 (Div. 2)[已补BCD，待补EF]Codeforces Round #791 (Div. 2)

133 阅读 0 评论 88 点赞

我是靠谱客的博主无语睫毛膏，这篇文章主要介绍Codeforces Round #791 (Div. 2)[已补BCD，待补EF]Codeforces Round #791 (Div. 2)，现在分享给大家，希望可以做个参考。

Codeforces Round #791 (Div. 2)

Problem - B - Codeforces

思路

不用线段树模板的话

记录下区间修改的时间T、v记录区间修改的值，以及用t[i]记录下第i个点修改的时间
若t[i]<T则a[i]的值不是原值而是v
否则a[i]为原值

可以直接模拟，也可以用map来维护

代码

AC2

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    ll a[n+1],all=0,v=0;
    int time[n+1]={0},T=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        all+=a[i];
    }
    for(int k=1;k<=q;k++){
        int op;
        cin>>op;
        if(op==1){
            int i;
            ll x;
            cin>>i>>x;
            if(time[i]<T)all+=-v+x;
            else all+=-a[i]+x;
            cout<<all<<endl;
            a[i]=x;
            time[i]=k;
        }
        if(op==2){
            ll x;
            cin>>x;
            cout<<n*x<<endl;
            all=n*x;
            T=k;
            v=x;
        }
    }
}

说明：

时间k要从1开始，不能从0开始。不然第一次为区间修改在单点的话t[i]<T会不成立

AC2

map维护

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    ll all=0,v=0;
    map<int,ll>a;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        a[i]=x;
        all+=x;
    }
    while(q--){
        int op;cin>>op;
        if(op==2){
            ll x;cin>>x;
            cout<<n*x<<endl;
            all=n*x;
            a.clear();
            v=x;
        }
        if(op==1){
            int i,x;
            cin>>i>>x;
            if(a.count(i))all+=-a[i]+x;
            else all+=-v+x;
            cout<<all<<endl;
            a[i]=x;
        }
    }
}

说明

用c.clear()来消除区修改前的区间（相当与上面的记录T）
用c.count()判断单点修改前是否区间修改（相当于时间t[i]），若c.count(i)==0则上一次经历过区间修改

Problem - C - Codeforces

思路

建两颗线段树node r[],c[]，r代表行，c代表列，线段树维护区间最小值
若t==1，把点x加1，点y加1
若t==2，把点x减1，点y减1
若t==3，查找区间（x1，x2）与区间（y1，y2），有一个区间最小值不为0，则yes否则no

代码

复制代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int n,q;
struct node{
   int l,r,x;
   node(){l=r=x=0;}
}r[4*maxn],c[4*maxn];

void update(int k,node*a){
   a[k].x=min(a[k*2].x,a[k*2+1].x);
}

void build(int k,int l,int r,node *a){
   a[k].l=l,a[k].r=r;
   if(l==r){
       a[k].x=0;
       return;
   }
   int mid=(l+r)>>1;
   build(2*k,l,mid,a);
   build(2*k+1,mid+1,r,a);
   update(k,a);
}

void change(int k,int index,node*a,int m){
   if(a[k].l==a[k].r){
       a[k].x+=m;
       return;
   }
   int mid=(a[k].l+a[k].r)>>1;
   if(index<=mid)change(2*k,index,a,m);
   if(index>mid)change(2*k+1,index,a,m);
   update(k,a);
}

int search(int k,int l,int r,node*a){
   if(a[k].l==l&&a[k].r==r){
       return a[k].x;
   }    
   int mid=(a[k].l+a[k].r)>>1;
   if(r<=mid) return search(2*k,l,r,a);
   else if(l>mid) return search(2*k+1,l,r,a);
   else return min(search(2*k,l,mid,a),search(2*k+1,mid+1,r,a));
}

void solve(){
   int t;cin>>t;
   if(t==1){
       int x,y;
       cin>>x>>y;
       change(1,x,r,1);
       change(1,y,c,1);
   }
   if(t==2){
       int x,y;
       cin>>x>>y;
       change(1,x,r,-1);
       change(1,y,c,-1);
   }
   if(t==3){
       int x1,y1,x2,y2;
       cin>>x1>>y1>>x2>>y2;
       if(search(1,x1,x2,r)||search(1,y1,y2,c))cout<<"YES"<<endl;
       else cout<<"NO"<<endl;

}
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);cout.tie(0);
   cin>>n>>q;
   build(1,1,n,r);
   build(1,1,n,c);
   while(q--){
       solve();
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int n,q;
struct node{
   int l,r,x;
   node(){l=r=x=0;}
}r[4*maxn],c[4*maxn];

void update(int k,node*a){
   a[k].x=min(a[k*2].x,a[k*2+1].x);
}

void build(int k,int l,int r,node *a){
   a[k].l=l,a[k].r=r;
   if(l==r){
       a[k].x=0;
       return;
   }
   int mid=(l+r)>>1;
   build(2*k,l,mid,a);
   build(2*k+1,mid+1,r,a);
   update(k,a);
}

void change(int k,int index,node*a,int m){
   if(a[k].l==a[k].r){
       a[k].x+=m;
       return;
   }
   int mid=(a[k].l+a[k].r)>>1;
   if(index<=mid)change(2*k,index,a,m);
   if(index>mid)change(2*k+1,index,a,m);
   update(k,a);
}

int search(int k,int l,int r,node*a){
   if(a[k].l==l&&a[k].r==r){
       return a[k].x;
   }    
   int mid=(a[k].l+a[k].r)>>1;
   if(r<=mid) return search(2*k,l,r,a);
   else if(l>mid) return search(2*k+1,l,r,a);
   else return min(search(2*k,l,mid,a),search(2*k+1,mid+1,r,a));
}

void solve(){
   int t;cin>>t;
   if(t==1){
       int x,y;
       cin>>x>>y;
       change(1,x,r,1);
       change(1,y,c,1);
   }
   if(t==2){
       int x,y;
       cin>>x>>y;
       change(1,x,r,-1);
       change(1,y,c,-1);
   }
   if(t==3){
       int x1,y1,x2,y2;
       cin>>x1>>y1>>x2>>y2;
       if(search(1,x1,x2,r)||search(1,y1,y2,c))cout<<"YES"<<endl;
       else cout<<"NO"<<endl;

   }
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);cout.tie(0);
   cin>>n>>q;
   build(1,1,n,r);
   build(1,1,n,c);
   while(q--){
       solve();
   }
}

Problem - D - Codeforces

思路

若所选的点权值越大，越容易符合k条边（有k次操作），反之，越难符合k条边
所以满足单调性，并且要最小化最大值可以用二分来搜索最大点权值，并最小化它
而对于我们最大点权值mid，需要check(mid)是否满足题目条件
把num[i]>mid的点去掉，因为我们已经确定点权最大为mid
在进行拓扑排序，找出最长边，若边长>=k则符合条件
并且，若完成while循环后还有点有入度，则有环，也是符合条件的
二分部分用左闭有闭，循环条件l<=r，用ans来记录答案，若mid满足条件，r=mid-1否则l=mid+1寻找有无更小的mid

代码

复制代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

typedef pair<int,int>P;
const int maxn=2e5+5,inf=0x3f3f3f3f;
int n,m;
ll k;
int num[maxn],vis[maxn],in[maxn];
vector<int>g[maxn];
vector<P>e;

bool check(int x){
    for(int i=1;i<=n;i++)vis[i]=0,in[i]=0;
    for(int i=1;i<=n;i++)if(num[i]<=x)vis[i]=1;
    for(int i=0;i<m;i++){
        if(vis[e[i].first]&&vis[e[i].second])in[e[i].second]++;
    }
    queue<int>que;
    int count=0;
    for(int i=1;i<=n;i++)if(vis[i]&&in[i]==0)que.push(i),que.push(count+1);
    while(!que.empty()){
        int st=que.front();
        que.pop();
        int c=que.front();
        que.pop();
        if(c>=k)return 1;
        for(int i=0;i<g[st].size();i++){
            int t=g[st][i];
            if(!vis[t])continue;
            in[t]--;
            if(in[t]==0)que.push(t),que.push(c+1);
        }
    }
    for(int i=1;i<=n;i++)if(vis[i]&&in[i]>0)return 1;
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>num[i];
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        e.push_back(P(u,v));
    }
    int l=1,r=1e9;
    int ans=inf;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=min(ans,mid);
            r=mid-1;
        }
        else l=mid+1;
    }
    if(ans==inf)cout<<-1<<endl;
    else cout<<ans<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#define ll long long
using namespace std;

typedef pair<int,int>P;
const int maxn=2e5+5,inf=0x3f3f3f3f;
int n,m;
ll k;
int num[maxn],vis[maxn],in[maxn];
vector<int>g[maxn];
vector<P>e;

bool check(int x){
    for(int i=1;i<=n;i++)vis[i]=0,in[i]=0;
    for(int i=1;i<=n;i++)if(num[i]<=x)vis[i]=1;
    for(int i=0;i<m;i++){
        if(vis[e[i].first]&&vis[e[i].second])in[e[i].second]++;
    }
    queue<int>que;
    int count=0;
    for(int i=1;i<=n;i++)if(vis[i]&&in[i]==0)que.push(i),que.push(count+1);
    while(!que.empty()){
        int st=que.front();
        que.pop();
        int c=que.front();
        que.pop();
        if(c>=k)return 1;
        for(int i=0;i<g[st].size();i++){
            int t=g[st][i];
            if(!vis[t])continue;
            in[t]--;
            if(in[t]==0)que.push(t),que.push(c+1);
        }
    }
    for(int i=1;i<=n;i++)if(vis[i]&&in[i]>0)return 1;
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>num[i];
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        e.push_back(P(u,v));
    }
    int l=1,r=1e9;
    int ans=inf;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=min(ans,mid);
            r=mid-1;
        }
        else l=mid+1;
    }
    if(ans==inf)cout<<-1<<endl;
    else cout<<ans<<endl;
}

最后

以上就是无语睫毛膏最近收集整理的关于Codeforces Round #791 (Div. 2)[已补BCD，待补EF]Codeforces Round #791 (Div. 2)的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Codeforces
浏览次数：133 次浏览
发布日期：2023-10-01 00:55:30
本文链接：https://www.kaopuke.com/article/k-p-k_14_uzogfx_12__23_c2.html

Codeforces Round #791 (Div. 2)[已补BCD，待补EF]Codeforces Round #791 (Div. 2)

Codeforces Round #791 (Div. 2)

Problem - B - Codeforces

tags

思路

代码

AC2

说明：

AC2

说明

Problem - C - Codeforces

tags

思路

代码

Problem - D - Codeforces

tags

思路

代码

最后

评论列表共有 0 条评论

发表评论取消回复

Codeforces Round #791 (Div. 2)[已补BCD，待补EF]Codeforces Round #791 (Div. 2)

Codeforces Round #791 (Div. 2)

Problem - B - Codeforces

tags

思路

代码

AC2

说明：

AC2

说明

Problem - C - Codeforces

tags

思路

代码

Problem - D - Codeforces

tags

思路

代码

最后

微信扫一扫：分享

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复