Codeforces 635(Div.2)

A题

题意：给你$a,b,c,d$四个数，然后规定$a<=b<=c<=d$。然后给你$x,y,z$，规定，$a<=x<=b$,$b<=y<=c$,$c<=z<=d$,$x,y,z$可以构成面积为正的三角形，问你$x,y,z$。

思路：这道题的话，根据题意，我们直接输出$b,c,c$即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t,a,b,c,d;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>c>>d;
        cout<<b<<" "<<c<<" "<<c<<endl;
    }
    return 0;
}

B题

题意：kana现在在玩一个游戏，她想猎杀一条龙，龙的初始生命值是x，当$x<=0$的时候，说明猎杀成功。kana有两个技能，第一个技能可以使$x=x/2+10$，第二个技能可以使$x=x-10$。然后第一个技能可以使用n次，第二个技能可以使用m次，问你能不能成功猎杀龙。

思路：这道题的话，通过读题我们可以发现当$x<20$之后，用第一次技能会使x变大，所以我们就先将x通过第一个技能尽可能的降至大于20且最小的血量，再用第二个技能判断其是否会小于等于0。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int x, n, m;
        cin >> x >> n >> m;
        while (n && x>20)
        {
            n--;
            x = x / 2 + 10;
        }
        if (x <= m * 10)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

C题

题意：给你一颗树，这棵树有两种顶点，一个是旅游节点，一个是工业节点，你如何设置工业节点让每一个工业节点到根节点路上得旅游节点的总和最大。

思路：这道题的话，我们可以求出每一个节点的深度，这个就是每一个节点能够得到的最大的权值，然后就是计算每一个节点下面有多少个工业节点，因为如果这个作为工业节点的话，那么后面的工业得节点的权值都会减1，所以我们就可以得到每一个节点的计算公式$val=deep−ans$，然后进行排序取k个最大的相加，得到的和就是答案了。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
using namespace std;
vector<ll> G[maxn];
vector<ll> sum;
int n, k;
bool cmp(int a, int b)
{
    return a > b;
}
int dfs(int u, int pre, int deep)
{
    int ans = 1;
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if (v == pre)
            continue;
        ans += dfs(v, u, deep + 1);
    }
    sum.push_back(deep - ans);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0, 1);
    sort(sum.begin(), sum.end(), cmp);
    ll cnt = 0;
    for (int i = 0; i < k; i++)
        cnt += 1ll * sum[i];
    cout << cnt << endl;
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦