Codeforces Round #595 (Div. 3) 题解

前言

大家都在洛谷上去找原题吧，洛谷还是不错的qwq

A

因为没有重复的数，我们只要将数据排序，比较两两之间有没有\(a_j - a_i == 1 (j > i)\) 的，有则输出 \(2\) , 无则输出 \(1\)

普及T1难度

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 107
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<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int q,n,ans;
int a[N];
void work() {
    memset(a, 0, sizeof(a));
    n = read();
    for(int i=1;i<=n;++i)
        a[i] = read();
    sort(a+1, a+1+n);
    bool flag = 1;
    for(int i=1;i<=n-1;++i) {
        if(a[i+1]-a[i] == 1) flag = 0;
    }
    if(flag) puts("1");
    else puts("2");
}
int main()
{
    q = read();
    while(q--) {
        work();
    }
    return 0;
}

B

通过模拟样例我们可以发现序列上有一些环 (这个很好理解吧？拿出纸笔画画qwq)

先预处理一下每个环的长度，和每个点所在环

然后直接输出即可

普及T2？

Code

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
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<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 2e5+7;
int n,q,tot;
int p[N],color[N],cnt[N];
void work() {
    memset(color, 0, sizeof(color));
    tot = 0;
    n = read();
    for(int i=1;i<=n;++i)
        p[i] = read();
    for(int i=1,j,sum;i<=n;++i) {
        if(!color[i]) {
            color[i] = ++tot;
            j = p[i], sum = 1;
            while(j != i) j = p[j], ++sum, color[j] = tot;
            cnt[tot] = sum;
        }
    }
    for(int i=1;i<=n;++i)
        printf("%d ",cnt[color[i]]);
    putchar('\n');
}
int main()
{
    q = read();
    while(q--) work();
    return 0;
}

C

先把十进制转换为三进制

如 \(17\) -> \(1\) \(2\) \(2\)

从左往右数发现第二位有一个 "\(2\)"，

再找 "2" 的前面出现的第一个 "\(0\)" ，把它改为 "\(1\)"，如果前面没有 "\(0\)" 了，我们就加一位 (->\(1\) \(1\) \(2\) \(2\)) (第四位是改动的位置)

再从改动的位置向下把它下面的每一位改为 "\(0\)" (->\(1\) \(0\) \(0\) \(0\)) ，这个数我们就找到了

想一想，这样做为什么是对的？

∵ 我们要消除 "\(2\)" ∴ 最高位上的 "\(2\)" 是一定要消去的

∴ 找到比这个 "\(2\)" 高的最近的一位 "0" ，把它改为 "\(1\)" ，相当于进了一位，故把后面所有的数改为 "\(0\)"

提高 Day1T1 难度？

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#define int long long
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<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int n,q;
void work() {
    vector<int> num;
    n = read(); int t = n;
    while(n) num.push_back(n%3), n/=3;
    int x = -1LL;
    for(int i=num.size()-1;i>=0;--i)
        if(num[i] == 2) {
            x = i; break;
        }
    if(x == -1LL) printf("%lld\n",t);
    else {
        num.push_back(0);
        for(int i=x+1;i<num.size();++i)
            if(!num[i]) {
                num[i] = 1; 
                for(int j=i-1;j>=0;--j) num[j] = 0LL;
                break;
            }
        x = 0LL;
        for(int i=num.size()-1;i>=0;--i) x = (x*3) + num[i];
        printf("%lld\n",x);
    }
}
signed main()
{
    q = read();
    while(q--) work();
    return 0;
}

D

USACO原题 如果考场上快点看了这题就好了

如果用贪心+线段树思路是比较简单的。

线段树做两个事情：1.查询区间最大值(当前区间被线段覆盖得最多的这个点，判断是否还能继续加，不能就说明这条边要删去，计入答案)。2.区间加上一个值(如果这个区间加入一条线段，区间的每个点加一)

这个还是比较好理解的吧

纯贪心有点神仙，我不会qwq

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
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<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 2e5+7;
int n,k,ans;
vector<int> v;
struct Node {
    int l,r,id;
}a[N];
struct Segment_Tree {
    int mx[N<<2],lazy[N<<2];
    inline int ls(int p) { return p<<1; }
    inline int rs(int p) { return p<<1|1; }
    inline void push_up(int p) { mx[p] = max(mx[ls(p)], mx[rs(p)]); }
    inline void fl(int p,int x) { lazy[p] += x; mx[p] += x; }
    inline void push_down(int p) {
        fl(ls(p),lazy[p]); fl(rs(p),lazy[p]); lazy[p] = 0;
    }
    void update(int nl,int nr,int p,int l,int r,int x) {
        if(nl<=l && r<=nr) {
            fl(p,x); return ;
        }
        int mid = (l+r)>>1;
        if(nl<=mid) update(nl,nr,ls(p),l,mid,x);
        if(nr>mid) update(nl,nr,rs(p),mid+1,r,x);
        push_up(p);
    }
    int Query(int ql,int qr,int p,int l,int r) {
        if(ql<=l && r<=qr) return mx[p];
        int mid = (l+r)>>1, res = 0;
        push_down(p);
        if(ql<=mid) res = max(res, Query(ql,qr,ls(p),l,mid));
        if(qr>mid) res = max(res, Query(ql,qr,rs(p),mid+1,r));
        return res;
    }
}T;
bool cmp(Node x,Node y) {
    return x.r < y.r;
}
int main()
{
    n = read(), k = read(); int m = 0;
    for(int i=1;i<=n;++i)
        a[i].l = read(), a[i].r = read(), m = max(m,a[i].r), a[i].id = i;
    sort(a+1, a+1+n, cmp);
    for(int i=1;i<=n;++i) {
        int l = a[i].l, r = a[i].r;
        int maxx = T.Query(l,r,1,1,m);
        if(k-maxx>=1) {
            T.update(l,r,1,1,m,1);
        } else {
            v.push_back(a[i].id);
        }
    }
    printf("%d\n",(int)v.size());
    for(int i=0;i<v.size();++i)
        printf("%d ",v[i]);
    return 0;
}

E

F