Codeforces Round 535 (Div. 3)

Diposting di | Edited on

传送门

前四题水题不讲

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
////A
    int q;
    cin>>q;
    while(q--){
        ll l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        cout<<l1<<" ";
        if(l2!=l1)cout<<l2;
        else cout<<r2;
        cout<<endl;
    }
////B
    int n;
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];mx=max(a[i],mx);num[a[i]]++;
    }
    cout<<mx<<" ";
    for(int i=mx;i>=1;i--){
        if(!(mx%i))num[i]--;
    }
    for(int i=mx;i>=1;i--){
        if(num[i]){cout<<i<<endl;return 0;}
    }
////C
char str[maxn];
char s[8][5]={"RGB","RBG","GRB","GBR","BGR","BRG"};
int id=0;
int num[8];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    cin>>str;
    for(int i=0;i<6;i++){
        for(int j=0;j<n;j++){
            if(str[j]!=s[i][j%3])num[i]++;
        }
    }
    int mx=num[0];
    for(int i=0;i<6;i++)if(num[i]<mx)mx=num[i],id=i;
    cout<<mx<<endl;
    for(int i=0;i<n;i++)cout<<s[id][i%3];
////D
 char str[maxn];
char s[5]="RBG";
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,ans=0;
    cin>>n;
    cin>>str;
    for(int i=1;i<n;i++){
        if(str[i]==str[i-1]){
            for(int j=0;j<3;j++){
                if(s[j]!=str[i-1]&&s[j]!=str[i+1]){
                    str[i]=s[j];break;
                }
            }
            ans++;
        }
    }
    cout<<ans<<endl;
    for(int i=0;i<n;i++)cout<<str[i];

E2.Array and Segments (Hard version) (差分/线段树)

题意

给出N个数,M个区间，每次可以把一个区间-1,问选取哪些区间可以使得这组数据的最大最小值相差最大

题解

枚举区间边界,因为区间边界肯定是敏感点，然后把所有有经过这个敏感点的区间都更新进差分数组，再塞入原数组更新答案；复杂度(n*m)

线段树直接枚举区间（n×m×logn）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int lq[maxn],rq[maxn],a[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    cin>>n>>m;
    int mx=-inf,mi=inf,l,r;
    for(int i=1;i<=n;i++){
        cin>>a[i];mx=max(mx,a[i]);mi=min(mi,a[i]);
    }
    ll res=mx-mi;
    vector<int>Q,now,ans;
    for(int i=1;i<=m;i++){
        cin>>lq[i]>>rq[i];
        Q.push_back(lq[i]);
        Q.push_back(rq[i]);
    }
    int sum[maxn];
    sort(Q.begin(),Q.end());
    Q.erase(unique(Q.begin(),Q.end()),Q.end());
    for(int i=0;i<Q.size();i++){
        now.clear();
        memset(sum,0,sizeof(sum));
        for(int j=1;j<=m;j++){
            if(lq[j]<=Q[i]&&rq[j]>=Q[i]){
                now.push_back(j);
                sum[lq[j]]--;
                sum[rq[j]+1]++;
            }
        }
        mx=-inf,mi=inf;
        for(int i=1;i<=n;i++){
            sum[i]+=sum[i-1];
            mx=max(mx,sum[i]+a[i]);
            mi=min(mi,sum[i]+a[i]);
        }
        if(mx-mi>res){
            res=mx-mi;
            ans=now;
        }
    }
    cout<<res<<endl;
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

F.MST Unification (最小生成树)

题意

给出一个图，可以任意增大一条边的权值，问你需要修改几次可以使这个最小生成树唯一

题解

最小生成树权值已固定，那么需要修改的边肯定是权值相同的边，但是权值相同的边又不能都修改

所以针对堆权值相同的边，哪些边是对答案有影响的

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int fa[maxn],r[maxn],n,m;
struct node{
    int u,v,w;
    bool operator<(const node &x)const {
        return this->w<x.w;
    }
};
vector<node>G;
void init(int n){
    for(int i=0;i<=n;i++)fa[i]=i;
}
int find(int x){
    if(x==fa[x])return fa[x];
    else return fa[x]=find(fa[x]);
}
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(x<y)fa[y]=x;
    else fa[x]=y;
}
bool same(int x,int y){
    return find(x)==find(y);
}
int kruskal(){
    sort(G.begin(),G.end());
    int ans=0;
    for(int i=0;i<G.size();){
        vector<node>now;
        int j;
        for(j=i;j<G.size()&&G[j].w==G[i].w;j++){
            if(!same(G[j].u,G[j].v))now.push_back(G[j]);
        }
        i=j;
        for(j=0;j<now.size();j++){
            if(!same(now[j].u,now[j].v))unite(now[j].u,now[j].v);
            else ans++;
        }
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    init(n);
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        G.push_back(node{x,y,z});
    }
    cout<<kruskal()<<endl;
    return 0;
}