官方题解
点击跳转：官方题解

A. Print a Pedestal (Codeforces logo?)

思路：分三种情况讨论即可

代码如下：

#include 

using namespace std;

typedef long long LL;
typedef pair 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 %dn", t, t+1, t-1);
    }
    else if( n%3 == 1)
    {
        t = n/3;
        printf("%d %d %dn", t, t+2, t-1);
    }
    else
    {
        t = n/3;
        printf("%d %d %dn", t+1, t+2, t-1);
    }

}

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

    return 0;
}

B. Array Decrements

思路：当 b[i] 不为0是，必须减去 a[i] - b[i] 次；当 b[i] 为 0 时，可以减去 >= a[i] 次，两者所有的情况结合以下即可

代码如下：

#include 

using namespace std;

typedef long long LL;
typedef pair 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

思路：令变量last 存之前的最大结尾时间，与这次开始时间取 max 作为本次的开始时间，用本次结束时间减去，即可

代码如下：

#include 

using namespace std;

typedef long long LL;
typedef pair PII;

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

int T;

void solve()
{
    int n;
    scanf("%d", &n);
    int a[N];
    vector 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

思路：滑动窗口板子题

代码如下：

#include 

using namespace std;

typedef long long LL;
typedef pair 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

思路：多余 k 的对 k 取模，整数部分直接加到答案上，然后对每个数从小到大枚举余数与其匹配的数，若判断成功，则将两个数标记一下

代码如下：

#include 

using namespace std;

typedef long long LL;
typedef pair 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

思路：枚举所有闭合的环，判断令每个环再次相等的最小次数，对所有环的答案取 lcm （最大公倍数）

环解释：比如原题的样例1所示，1->3->5->1，2->4->2，这就时两个环，

1->3->5 ---> 3->5->1 ---> 5->1->3 --> 1->3->5，最多三次变换就能恢复，但可能小于本身长度，所以我们要判断一下

代码如下：

#include 

using namespace std;

typedef long long LL;
typedef pair 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("%lldn", res);

}

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

    return 0;
}

G. Count the Trains

思路：

插入和修改时都判断两个操作，

1，若大于等于前一个数，则本数无效（即，与前面的数合并），删去

2，若后面的数大于本数，则后一个数无效，（即，后面的数与本数合并为一个），删去

代码如下：

#include 

using namespace std;

typedef long long LL;
typedef pair PII;

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

int T;
map 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
    {
        // 看it 后面的数，如果大于c则删去，继续循环下一位，小于c则停止
        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;
}

Codeforces Round #797 (Div. 3)

官方题解
点击跳转：官方题解

C/C++/C#相关栏目本月热门文章

Codeforces Round #797 (Div. 3)

官方题解 点击跳转：官方题解

C/C++/C#相关栏目本月热门文章

官方题解
点击跳转：官方题解