Codeforces Round #479 (Div. 3)

题目链接
A  00:01
B  00:08
C  00:22
D  00:41
E  01:00
F  --:--

A. Wrong Subtraction

如果一个数最后一位大于0则减1,否则除10
这部操作执行k次

    int n = read(), k = read();
    while(k --){
        if(n % 10){
            n --;
        }else{
            n /= 10;
        }
    }
    cout << n << endl;

B. Two-gram

找一个长度为2的字串,是这个字符串出现次数最多的字串

    #include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define _ 0
#define eps 1e-9
#define endl '\n'
#define gcd __gcd
#define pi acos(-1)
#define ll long long
#define LL long long
#define IDX(x) (x - 'A')
#define idx(x) (x - 'a')
#define idz(x) (x - '0')
#define ld long double
#define lowebit(x) (x&(-x))
#define rint register int
#define Len(x) (int)(x).size()
#define all(s) (s).begin(), (s).end()
//char buf[1 << 23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
#define int ll
inline int read()
{
    register int x = 0, f = 1, ch = getchar();
    while( !isdigit(ch) ){if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch) ){x = (x << 1) + (x << 3) + ch - 48; ch = getchar();}
    return x * f;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    clock_t c1ockck = clock();
    // ..........................................................
    int n; cin >> n;
    string s; cin >> s;
    int ans = 0;
     string p = "";
    for(int i = 0 ; i + 1 < Len(s) ; i ++){
        int sum = 0;
        for(int j = i ; j + 1 < Len(s) ; j ++){
            if(s[j] == s[i] && s[i + 1] == s[j + 1]){
                sum ++;
            }
        }
        if(ans < sum){
            ans = sum;
            p = s[i];
            p = p + s[i + 1];
        }
    }
    cout << p << endl;
    // ..........................................................
    cerr << endl << "Time:" << clock() - c1ockck << "ms" <<endl;
    return ~~(0^_^0);
}

C. Less or Equal

找出一个x使序列里面恰好有k个数小于等于x
首先直接sort看第k个元素等不等于第k+1个元素,如果等于肯定找不出来
否则输出第k个
但是如果k为0的话那就看第一个元素,如果大于1则输出1~第一个元素-1,否则因为x不能等于零,所以也找不到x

    int n = read(), k = read();
    for(int i = 1 ; i <= n ; i ++) a.push_back(read());
    a.push_back(1e10);
    sort(all(a));
    if(!k && a[0] == 1) cout << -1 << endl;
    else if(!k) cout << a[0] - 1 << endl;
    else if( a[k - 1] == a[k]) cout << -1 << endl;
    else cout << a[k - 1] << endl;

D. Divide by three, multiply by two

个人感觉写了一个假算法,但是能在cf上AC应该就没有问题
枚举第一个元素,就是看看如果他是3的倍数且他除3存在,下一个就是他除3否则下一个就是他乘2

     int n = read();
    for(int i = 1 ; i <= n ; i ++) a.push_back(read());
    for(auto x : a) m[x] ++;
    for(auto x : a){
        map<int, int> tmp = m;
        vector<int> b;
        m[x] --;
        b.push_back(x);
        bool flag = false;
        for(int i = 1 ; i < n ; i ++){
            b.push_back(0);
            if(b[i - 1] % 3 == 0){
                b[i] = b[i - 1] / 3;
                if(m[b[i]]){
                    m[b[i]]--;
                    continue;
                }
            }
            b[i] = b[i - 1] * 2;
            if(m[b[i]]){
                m[b[i]]--;
                continue;
            }
            //puts("x");
            flag = true;
            break;
        }
        if(!flag){
            for(auto y : b) cout << y << " ";
            cout << endl;
            return 0;
        }
        m = tmp;
    }

E. Cyclic Components

给定一个图,找一下这个图里面有多少简单环(只存在一个环的联通图,并且不出现分支)
如果每次都是在找是否存在环,那么这道题其实很难写
因此需要遍历所有联通图,寻找这个联通图的每个点的最大度数和最小度数
如果都等于2那么这个联通图就是简单环
证明省略...........

pair<int, int> dfs(int u){
    int mi, ma = mi = Len(a[u]);
    if(vis[u]) return make_pair(mi,ma);
    vis[u] = 1;
    for(auto x : a[u]){
        auto y = dfs(x);
        mi = min(y.first, mi);
        ma = max(y.second, ma);
    }
    return make_pair(mi, ma);
}
    int n = read(), m = read();
    for(int i = 1 ; i<= m ; i ++){
        int u = read(), v = read();
        a[u].push_back(v);
        a[v].push_back(u);
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++){
        if(vis[i]) continue;
        auto x = dfs(i);
        if(x.first == 2 && x.second == 2) ans ++;
    }
    cout << ans << endl;

F. Consecutive Subsequence

这道题别看写了一个小时wa了19次都没有出来,只是算错复杂度了,导致一直没有正确的debug
我第一次写的代码评价复杂度确实是nlogn的,但是在最坏情况下比如只有两个数每个数出现次数都是\frac{n}{2},这样的话复杂度就是\frac{nlogn}{4}
思路一
枚举每一个没有访问过的元素,并且这个元素的下标也是没有访问过的
然后去查找需要出现的下一个元素是否存在,
存在的话就继续上一步

    int n = read();
    for(int i = 1 ; i <= n ; i ++) a.push_back(read());
    for(auto x : a){
        b.push_back(x);
        b.push_back(x + 1);
    }
    sort(all(b));
    b.erase(unique(all(b)), b.end());
    for(auto& x: a){
        x = lower_bound(all(b), x) - b.begin() + 1;
    }
    for(int i = 0 ; i < n ; i ++) c[a[i]].push_back(i + 1);

    int l = 0, r = n - 1;
    vector<int> ans;
    for(int i = 0 ; i < n ; i ++){
        if(vis[i] || v[a[i]]) continue;
        vector<int> tmp;
        int nex = a[i] + 1, up = i + 1;
        tmp.push_back(i + 1);
        v[a[i]] = 1;
        while(Len(c[nex])){
            if(!Len(c[nex])) break;
            int x = lower_bound(all(c[nex]), up) - c[nex].begin();
            if(x + c[nex].begin() != c[nex].end()){
                vis[c[nex][x]-1] = 1;
                tmp.push_back(c[nex][x]);
                up = c[nex][x];
                nex ++;
                continue;
            }
            break;
        }
        if(Len(tmp) > Len(ans)) ans = tmp;
    }
    cout << Len(ans) << endl;
    for(auto x : ans) cout << x << " " ;

思路二
对于每一个元素我直接二分它的下一个元素,并且让下一个元素的长度看看需不需要加上当前元素的长度,如果需要就记录前驱,并更新下一个元素的长度
记录最长的长度和最长的长度出现的最后一个元素
倒叙输出所有元素

void print(int u){
    if(up[u] != -1) dfs(up[u]);
    cout << u + 1 << " ";
}
     memset(up, -1, sizeof up);
    int n = read();
    for(int i = 1 ; i <= n ; i ++) a.push_back(read());
    for(auto x : a){
        b.push_back(x);
        b.push_back(x + 1);
    }
    sort(all(b));b.erase(unique(all(b)), b.end());
    for(auto& x: a) x = lower_bound(all(b), x) - b.begin() + 1;
    for(int i = 0 ; i < n ; i ++) c[a[i]].push_back(i), vis[i] = 1;

    int len = 1, nex = 0;
    for(int i = 0 ; i < n ; i ++){
        int x = lower_bound(all(c[a[i] + 1]), i) - c[a[i] + 1].begin();
        if(x == Len(c[a[i] + 1])) continue;
        if(vis[c[a[i] + 1][x]] < vis[i] + 1){
            vis[c[a[i] + 1][x]] = vis[i] + 1;
            up[c[a[i] + 1][x]] = i;
        }
        if(vis[c[a[i] + 1][x]] > len){
            len = vis[c[a[i] + 1][x]];
            nex = c[a[i] + 1][x];
        }
    }
    cout << len << endl;
    print(nex);
点赞

发表评论

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