当前位置：网站首页>Codeforces Round ＃798 (Div. 2)

Codeforces Round ＃798 (Div. 2)

2022-06-10 21:14:00 【AC automatic mail】

Catalog

Official explanation

A. Print a Pedestal (Codeforces logo?)

B. Array Decrements

C. Restoring the Duration of Tasks

D. Black and White Stripe

E. Price Maximization

F. Shifting String

G. Count the Trains

Official explanation

Click the jump ： Official explanation

A. Print a Pedestal (Codeforces logo?)

Ideas ： It can be discussed in three cases

The code is as follows ：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n;
    scanf("%d", &n);
    int t;
    if( n%3 == 0)
    {
        t = n/3;
        printf("%d %d %d\n", t, t+1, t-1);
    }
    else if( n%3 == 1)
    {
        t = n/3;
        printf("%d %d %d\n", t, t+2, t-1);
    }
    else
    {
        t = n/3;
        printf("%d %d %d\n", t+1, t+2, t-1);
    }

}

int main()
{
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

B. Array Decrements

Ideas ： When b[i] Not for 0 yes , Must subtract a[i] - b[i] Time ; When b[i] by 0 when , Can be subtracted >= a[i] Time , The combination of all the two situations is as follows

The code is as follows ：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n;
    scanf("%d", &n);
    int t;
    int a[N], b[N];
    int mx1 = -2e9, mx0 = 0;
    for(int i = 0; i < n; i ++ )
        scanf("%d", &a[i]);
    for(int i = 0; i < n; i ++ )
        scanf("%d", &b[i]);

    for(int i = 0; i < n; i ++ )
    {
        if(a[i] < b[i])
        {
            puts("NO");
            return;
        }

        if(b[i] != 0)
        {
            if(mx1 != -2e9 && mx1 != a[i] - b[i])
            {
                puts("NO");
                return;
            }
            mx1 = a[i] - b[i];
        }
        else mx0 = max(mx0, a[i]);
    }

    if( mx1 < mx0 && mx1 != -2e9)
    {
        puts("NO");
        return;
    }
    puts("YES");

}

int main()
{
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

C. Restoring the Duration of Tasks

Ideas ： Make Variable last Maximum end time before saving , And the starting time of this time is max As the starting time of this time , Subtract... From this end time , that will do

The code is as follows ：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n;
    scanf("%d", &n);
    int a[N];
    vector<PII> segs;
    for(int i = 0; i < n; i ++ )
        scanf("%d", &a[i]);
    int x;
    for(int i = 0; i < n; i ++ )
    {
        scanf("%d", &x);
        segs.push_back({a[i], x});
    }

    int last = 0;
    for(int i = 0; i < segs.size(); i ++ )
    {
        printf("%d ", segs[i].second - max(last, segs[i].first));
        last  = max(last, segs[i].second);
    }
    puts("");

}

int main()
{
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

D. Black and White Stripe

Ideas ： Sliding window board sub problem

The code is as follows ：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, k;
    scanf("%d %d", &n, &k);
    char ch[N];
    cin >> ch+1;
    int s[N];
    int mi = 0x3f3f3f3f;
    for(int i = 1; i <= n; i ++ )
    {
        if(ch[i] == 'W') s[i] = s[i-1] + 1;
        else s[i] = s[i-1];

        if(i >= k) mi = min(mi, s[i] - s[i-k]);
    }

    cout << mi << endl;

}

int main()
{
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

E. Price Maximization

Ideas ： redundant k Right k modulus , The integer part is added directly to the answer , Then enumerate the remainder and its matching number from small to large for each number , If the judgment is successful , Mark the two numbers

The code is as follows ：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

void solve()
{
    int n, k;
    scanf("%d %d", &n, &k);
    int a[N];
    int st[N] = {0};
    LL res = 0;
    for(int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        if(a[i] >= k)
        {
            res += a[i]/k;
            a[i] %= k;
        }
        st[a[i]] ++;
    }

    for(int i = 0; i < n; i ++ )
    {
        if(st[a[i]] == 0) continue;
        st[a[i]] --;

        for(int j = 0; j < k; j ++ )
        {
            if( st[k - a[i] + j] )
            {
                res ++;
                st[k-a[i]+j] -- ;
                break;
            }
        }
    }

    cout << res << endl;

}

int main()
{
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

F. Shifting String

Ideas ： Enumerate all closed rings , Determine the minimum number of times to make each ring equal again , The answer to all rings is lcm （ The greatest common multiple ）

Ring interpretation ： For example, the sample of the original question 1 Shown ,1->3->5->1,2->4->2, These are the two rings ,

1->3->5 ---> 3->5->1 ---> 5->1->3 --> 1->3->5, Up to three transformations can restore , But it may be less than its own length , So we have to judge

The code is as follows ：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b): a;
}

LL lcm(LL a, LL b)
{
    return a*b/gcd(a, b);
}

LL shift(string s)
{
    string t = s;
    LL res = 1;

    if(t.size() > 1)
        t = t.substr(1) + t[0];
    else return 1;

    while(t != s)
        t = t.substr(1) + t[0], res ++;
    return res;
}

void solve()
{
    int n, k;
    scanf("%d", &n);
    int p[N];
    bool st[N] = {0};
    string s;
    cin >> s;
    for(int i = 0; i < n; i ++ )
    {
        scanf("%d", &p[i]);
        p[i] --;
    }

    LL res = 1;
    for(int i = 0; i < n; i ++ )
    {
        string ss = "";
        int j = i;

        if(st[j]) continue;

        while(!st[j])
        {
            ss += s[j];
            st[j] = true;
            j = p[j];
        }
        LL t = shift(ss);
        res = lcm(res, t);
    }

    printf("%lld\n", res);

}

int main()
{
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

G. Count the Trains

Ideas ：

Both insert and modify operations are judged ,

1, If greater than or equal to the previous number , Then this number is invalid （ namely , Merge with the previous number ）, delete

2, If the following number is greater than this number , Then the latter number is invalid ,（ namely , The following numbers and this number are merged into one ）, delete

The code is as follows ：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int T;
map<int, int> mp;

void add(int x, int c)
{
    mp[x] = c;
    auto it = mp.find(x);

    if( it != mp.begin() && c >= prev(it)->second )
        mp.erase(it);
    else
    {
        //  see it  The number behind , If it is greater than c Delete , Continue to cycle to the next , Less than c Then stop 
        while(next(it) != mp.end() && c <= next(it)->second)
            mp.erase(next(it));
    }
}

void solve()
{
    mp.clear();
    int n, m;
    scanf("%d %d", &n, &m);
    int a[N];
    for(int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        add(i, a[i]);
    }

    while(m -- )
    {
        int x, c;
        scanf("%d%d", &x, &c);
        a[x] -= c;
        add(x, a[x]);
        cout << mp.size() << " ";
    }
    cout << endl;

}

int main()
{
    scanf("%d", &T);
    while(T -- )
        solve();

    return 0;
}

原网站

版权声明
本文为[AC automatic mail]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/161/202206101953520654.html