Codeforces Round 916 (Div. 3)

A. Problemsolving Log

签到题，对于给出的字符串，记录每个字母出现的次数，然后遍历一遍，如果对应的字母出现的次数大于它的位次，则说明该题被解出来了，最后输出解题数量即可

点击查看代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
const int N = 2*1e5 + 10;
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int st[27] = { 0 };
    int count = 0;
    for (int i = 0; i < s.size(); i++)
    {
        st[s[i] - 'A' + 1]++;
    }
    for (int i = 1; i < 27; i++)
    {
        if (st[i] >= i) count++;
    }
    cout << count << endl;
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

B. Preparing for the Contest

排序问题，兴奋 $k$ 次，即前 $1-k$ 按照升序排列，剩下的按照降序排序即可

点击查看代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) {            //最大公约数
    while (y ^= x ^= y ^= x %= y);
    return x;
}
ll lcm(ll x, ll y) {           //最小公倍数
    return x * y / gcd(x, y);
}
void solve() {
    int x, k;
    cin >> x >> k;
    int no = 0;
    for (int i = 1; i<=x; i++)
    {
        if (k != 0)
            cout << i << " ";
        else
        {
            no = i;
            break;
        }
        k--;
    }
    for (int i = x; i >= no; i--)
    {
        cout << i << " ";
    }
    cout << endl;
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. Quests

暴力贪心，先用前缀和预处理数组 $a$ ，之后对于数组 $b$ ，用一个数组 $d[i]$ 表示前 $i$ 个中最大的 $b$ ,最后遍历一遍， $ans$ 取最大的 $c[i] + (y-i)\times d[i]$

点击查看代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) {            //最大公约数
    while (y ^= x ^= y ^= x %= y);
    return x;
}
ll lcm(ll x, ll y) {           //最小公倍数
    return x * y / gcd(x, y);
}
void solve() {
    ll x, y;
    cin >> x >> y;
    vector<ll>a(x+1);
    vector<ll>b(x+1);
    vector<ll>c(x + 1);
    vector<ll>d(x + 1);
    d[0] = 0;
    c[0] = 0;
    ll ans = 0;
    for (int i = 1; i <=x; i++)
    {
        cin >> a[i];
        c[i] = a[i] + c[i - 1];//前缀和
       // cout << c[i] <<" ";
    }
    for (int i = 1; i <=x; i++)
    {
        cin >> b[i];
        d[i] = max(d[i - 1], b[i]);//最大
    }
    for (int i = 1; i <=min(x,y); i++)
    {
        ll sum = c[i] + (y - i) * d[i];
        //cout << sum << " ";
        ans = max(ans, sum);
    }
    cout << ans << endl;
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

D. Three Activities

暴力打表，先将每一个活动都排序(找出最多人数的3天)，然后这3天互相排列组合，去除天数相同的，剩下的找最大值即是答案

点击查看代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll gcd(ll x, ll y) {            //最大公约数
    while (y ^= x ^= y ^= x %= y);
    return x;
}
ll lcm(ll x, ll y) {           //最小公倍数
    return x * y / gcd(x, y);
}
struct no {
    ll num;
    ll day;
}a[N],b[N],c[N];
 
bool cmp(no x, no y)
{
    return x.num > y.num;
}
void solve() {
    ll x;
    cin >> x;
    for (int i = 0; i < x; i++)
    {
        cin >> a[i].num;
        a[i].day = i;
    }
    for (int i = 0; i < x; i++)
    {
        cin >> b[i].num;
        b[i].day = i;
    }
    for (int i = 0; i < x; i++)
    {
        cin >> c[i].num;
        c[i].day = i;
    }
    sort(a, a + x, cmp);
    sort(b, b + x, cmp);
    sort(c, c + x, cmp);//由大到小排序
    ll ans = 0;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                if (a[i].day != b[j].day && a[i].day != c[k].day && b[j].day != c[k].day)
                    ans = max(a[i].num + b[j].num + c[k].num, ans);
            }
        }
    }
    cout << ans << endl;
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

E. Game with Marbles

贪心排序问题，这一题 $easy$ 和 $hard$ 差别不大, $easy$ 应该暴力模拟可以过。计算每一组的权值， $Alice$ (简称 $A$ )， $Bob$ (简称 $B$ ) 对于 $A$ 来说，选择的一组所获得的权值是 $a_i+b_i-1$ (消除 $b_i$ 等于加 $b_i$ 与 $B$ 拉开了 $b_i$ 的差距且保留了自己的剩余的 $a_i-1$ ,因此是 $a_i+b_i-1$ );同理，对于 $B$ 来说，也是这样，因此无论是 $A$ 操作时还是 $B$ 操作时，所选择的都是 $a_i+b_i$ 最大值那一组 (每一组的权值都有 -1 因此可以仅比较 $a_i+b_i$) , 使用结构体存储每一组石子的数量和和组号，对石子数量进行排序，之后由大到小进行模拟即可。

点击查看代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll gcd(ll x, ll y)
{            //最大公约数
    while (y ^= x ^= y ^= x %= y);
    return x;
}
ll lcm(ll x, ll y) {           //最小公倍数
    return x * y / gcd(x, y);
}
struct non {
    ll num;
    ll step;
}v[10];
bool cmp(non x, non y) {
    return x.num < y.num;
}
 
void solve() {
    ll x;
    cin >> x;
    vector<ll>a(x + 1);
    vector<ll>b(x + 1);
   // vector<ll>v(x + 1);
    for (int i = 0; i < x; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < x; i++)
    {
        cin >> b[i];
    }
    for (int i = 0; i < x; i++)
    {
        v[i].num = a[i] + b[i] - 1;
        v[i].step = i;
    }
    sort(v, v + x,cmp);
    //for (int i = 0; i < x; i++)
    //{
    //    cout << v[i].num << " ";
    //}
    ll sum = 0;
    int j = 1;
    if (x % 2 == 0)
    {
        for (int i = x-1; i>=0; i--)
        {
            //cout << v[i] << " ";
            if (j == 1)
            {
                sum += a[v[i].step] - 1;
            }
            else
                sum -= b[v[i].step] - 1;
            j *= -1;
        }
    }
    else
    {
        for (int i = x - 1; i >= 0; i--)
        {
            if (i ==0)
            {
                sum += a[v[i].step] - 1;
                break;
            }
            else
            {
                if (j == 1)
                {
                    sum += a[v[i].step] - 1;
                }
                else
                    sum -= b[v[i].step] - 1;
            }
            j *= -1;
        }
    }
    cout << sum << endl;
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

F. Programming Competition

这是一个树型结构 + $dfs$ 的题目。一种贪心方法：

首先，叶子节点之间，不会存在上下级的关系，所以叶子节点都可以互相两两配对，所以我们只需要找叶子节点两两配对就行了。但是没这么简单，因为这并不是最优的。例如：

如果是这种情况，只考虑叶子节点配对，那么会出现 (4,3) 只能配对一次的情况，但是实际上可以 (4,5),(2,3) 配对；

所以需要这次贪心一下，每次配对的叶子节点都是深度最深的叶子节点，这样一来才有可能解放更多的深度较低的节点成为叶子节点，从而来使得它们与其他的叶子节点组成一组。

点击查看代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 2 * 1e5 + 10;
ll n, p[N], d[N], c[N];
vector<ll>e[N];
ll gcd(ll x, ll y) {            //最大公约数
    while (y ^= x ^= y ^= x %= y);
    return x;
}
ll lcm(ll x, ll y) {           //最小公倍数
    return x * y / gcd(x, y);
}
void dfs(ll u, ll v)//深度
{
    d[u] = d[v] + 1;
    for (auto i = e[u].begin(); i != e[u].end(); i++)//遍历
    {
        //cout << *i << endl;
        dfs(*i, u);
    }
}
void solve() {
    cin >> n;
    d[0] = 0;
    for (int i = 2; i <=n; i++)
    {
        cin >> p[i];
        e[p[i]].push_back(i);
        c[p[i]]++;//子节点个数
    }
    dfs(1, 0);
    priority_queue<pair<ll, ll>>q;//优先队列，先将根深的进行组合
    for (int i = 2; i <= n; i++)
    {
        if (c[i] == 0)//叶子节点
            q.push(make_pair(d[i], i));
    }
    //while (!q.empty())
    //{
    //    cout << q.top().second;
    //    q.pop();
    //}
    ll ans = 0;
    while (q.size() >= 2)//单个
    {
        ll xx = q.top().second;//配队的第一个
        q.pop();
        ll yy = q.top().second;
        q.pop();
        ans++;//成功配队一对
       // cout << p[xx] << " " << p[yy] << endl;
        c[p[xx]]--;
        c[p[yy]]--;
        if (c[p[xx]] == 0)
            q.push(make_pair(d[p[xx]], p[xx]));
        if (c[p[yy]] == 0&&p[xx]!=p[yy])
            q.push(make_pair(d[p[yy]], p[yy]));
    }
    cout << ans << endl;//输出答案
    for (int i = 0; i <= n; i++)
    {
        c[i] = 0;
        p[i] = 0;
        d[i] = 0;
        e[i].clear();
    }
}
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}