Educational Codeforces Round 96 (Rated for Div. 2) 题解

Educational Codeforces Round 96 (Rated for Div. 2)

目录

• Educational Codeforces Round 96 (Rated for Div. 2)
  • A-Number of Apartments
  • B-Barrels
  • C-Numbers on Whiteboard
  • D-String Deletion

A-Number of Apartments

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

int t,n;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        int a,b,c;
        a=b=c=0;
        int rec=n%3;
        if(rec==0){
            cout<<n/3<<" "<<0<<" "<<0<<"
";
            continue;
        }
        if(rec==2){
            a=n/3-1;
            if(a<0){
                cout<<-1<<"
";
                continue;
            }
            cout<<a<<" "<<b+1<<" "<<c<<"
";
            continue;
        }
        if(rec==1){
            a=n/3-2;
            if(a<0){
                cout<<-1<<"
";
                continue;
            }
            cout<<a<<" "<<b<<" "<<c+1<<"
";
            continue;
        }
    }
    return 0;
}

B-Barrels

• 没开long long wa一发

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

int t,n,k;
const int N=2e5+10;
long long a[N],sum[N];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;++i) cin>>a[i];
        sort(a+1,a+n+1);
        if(k==0){
            cout<<a[n]-a[1]<<"
";
            continue;
        }
        memset(sum,0,sizeof(int)*(n+1));
        for(int i=1;i<=n;++i){
            sum[i]=sum[i-1]+a[i];
        }
        //for(int i=1;i<=n;++i) cout<<sum[i]<<"
";
        cout<<sum[n]-sum[n-k-1]-0ll<<"
";
    }
    return 0;
}

C-Numbers on Whiteboard

• 反正这个也睿智了wa一发

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

int t, n;
const int N = 2e5 + 10;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        queue<pair<int,int> >p;
        priority_queue <int, vector<int>, less<int> > q;
        if(n==2){
            cout<<2<<"
";
            cout<<1<<" "<<2<<"
";
            continue;
        }
        for (int i = 1; i <= n; ++i) q.push(i);
        int tmp = 0;
        while (q.size() != 1) {
            // int r[3];
            // int s = q.size();
            // for (int i = 0; i < 3; ++i) {
            //     if (s <= 2 && i == 2) break;
            //     r[i] = q.top(), q.pop();
            // }
            // if ((r[0] + r[1]) % 2 == 0) {
            //     tmp = (r[0] + r[1]) / 2;
            //     q.push(tmp);
            //     if(s != 2)q.push(r[2]);
            //     //cout << r[0] << " " << r[1] << "
";
            //     p.push(make_pair(r[0],r[1]));
            // }
            // else {
            //     tmp = (r[0] + r[2]) / 2;
            //     q.push(tmp);
            //     if (s != 2)q.push(r[1]);
            //     //cout << r[0] << " " << r[2] << "
";
            //     p.push(make_pair(r[0],r[2]));
            // }
            queue<int>tmp;
            int a=q.top();q.pop();
            while((a+q.top())%2!=0){
                tmp.push(q.top());
                q.pop();
            }
            int b=q.top();q.pop();
            p.push(make_pair(a,b));
            q.push((a+b)/2);
            while(!tmp.empty()){
                q.push(tmp.front());
                tmp.pop();
            }
        }
        cout<<q.top()<<"
";
            while(!p.empty()){
                cout<<p.front().first<<" "<<p.front().second<<"
";
                p.pop();
            }
    }
    return 0;
}

D-String Deletion

• 就把长度大于1的连续的子串的第一位的位置和长度保存一下，从前面起，如果有长度大于1的连续子串，就在这个子串里删一个，然后把开头的删了，直到当前子串删到长度为1，然后换下一个子串

#include<bits/stdc++.h>
using namespace std;

int t, n;
string s;
queue<pair<int, int> >q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> s;
        for (int i = 0, j; i < n; i = j) {
            char a = s[i];
            for (j = i; s[j] == a; ++j);
            if (j - i > 1)
                q.push(make_pair(i, j - i));
        }
        int ans = 0;
        if (q.empty()) {
            cout << (n + 1) / 2 << "
";
            continue;
        }
        pair<int, int>tmp;
        int denum = 0;
        while (!q.empty()) {
            tmp = q.front();
            tmp.first -= denum;
            int tnum = 0;
            for (;;) {
                if (tmp.second == 1) {
                    q.pop();
                    break;
                }
                else {
                    if (tmp.first == 0) {
                        ans++;
                        s.erase(0, tmp.second);
                        tnum += tmp.second;
                        q.pop();
                        break;
                    }
                    else {
                        s.erase(0, 1);
                        tmp.first--;
                        s.erase(tmp.first , tmp.first + 1 );
                        tnum++;
                        tmp.second--;
                        ans++;
                    }
                }
            }
            denum += tnum;
        }
        if (s.length()) {
            ans += ((s.length() + 1) / 2);
        }
        cout << ans << "
";
    }
    return 0;
}

• E待补