首页 > 其他分享 >欢乐结训赛题解

欢乐结训赛题解

时间：2023-05-29 20:55:22浏览次数：63  
标签：maxx const int 题解 flag 欢乐 vec 结训 solve

欢乐结训赛题解

A 题目链接

  • 题目大意
给你一个字符串，让你求字符串中最大的字母在字母表中排第几 例如 codeforces 中 s 的是最大的 s在字母表中排 19位

  • 代码

    #include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
void solve()
{
    string s;
    int n;
    cin >> n;
    cin >> s;
    int maxx = 0;
    for (int i = 0; i < s.length(); i++)
    {
        maxx = max((int)s[i], maxx);
    }
    cout << maxx - 'a' + 1 << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        solve();
    }
    return 0;
}

B 题目链接

  • 题目大意

    给你一个数组a,对于每个a[i],在a数组中找出除了a[i]自己，最大的数，然后输出该数与a[i]的差值

  • 思路

    求出数组中最大的数(maxx_1)和第二大的数(maxx_2)，遍历数组，如果a[i]不是最大的数 就输出a[i]-maxx_1,否则输出a[i]-maxx_2

  • 代码

    #include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
void solve()
{
    int n;
    cin >> n;
    vector<int> vec(n);
    int maxx = 0;
    int sec = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> vec[i];
        if (vec[i] > maxx)
        {
            sec = maxx;
            maxx = max(vec[i], maxx);
        }
        else if (vec[i] > sec)
        {
            sec = vec[i];
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (vec[i] != maxx)
        {
            cout << vec[i] - maxx << ' ';
        }
        else
        {
            cout << maxx - sec << ' ';
        }
    }
    cout << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        solve();
    }
    return 0;
}

C题目链接

  • 题目大意

    给定一串数组，问这个数组a[ l .....r ]是否满足如下性质
0 <= l <= r <= n - 1
a l = a l + 1 = a l + 2...... = ar
l = 0 or a l - 1 > a l
r = n - 1 or a r < a r + 1
若满足这些性质，输出YES 否则输出 NO

  • 思路

    形成一个山谷我们需要先下降然后上升
我们定义一个flag 
flag=0 代表 现在是无状态
flag=1 代表 下降状态,如果接下来有一个上升的话就会形成一个山谷
需要注意 初始时 flag为1，结束时还需要判断一下flag是否为1 如果为1，山谷数+1 原因见原题目
具体实现见代码

  • 代码

    #include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
void solve()
{
    int n;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++)
        cin >> vec[i];
    int flag = 1;
    int cnt = 0;
    for (int i = 1; i < n; i++)
    {
        if (vec[i] > vec[i - 1])  //假如现在是上升 并且flag状态为1 ，山谷数+1
        {
            if (flag == 1)
            {
                flag = 0;
                cnt++;
            }
        }
        else if (vec[i] < vec[i - 1]) //如果现在是下降 那么将flag赋值为1
        {
            flag = 1;
        }
    }
    if (flag == 1)
        cnt++;
    if (cnt == 1)
        cout << "YES\n";
    else
        cout << "NO\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        solve();
    }
    return 0;
}

D 题目链接

  • 题目大意

    给定一串二进制数组，把其中一个 1 变成 0 或者 0 变成 1 使得数组逆序对数量最大，问这个最大数量是几

  • 思路

    先求出不变的情况下 逆序对的个数 ans
case1：我们把一个0 变成1 那么这次改变对答案的贡献为 后面所有的0 - 前面所有的1 
case2：我们把一个1 变成0 那么这次改变对答案的贡献为 前面所有的1 - 后面所有的0
然后把所有的情况都算出来 得到一个最大值 加到ans上 详情见代码 时间复杂度(O(n))

  • 代码

    #include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int sum[N];  //sum[i] 代表前i个数有多少个1
void solve()
{
    int n;
    cin >> n;
    vector<int> vec(n + 1);
    for (int i = 1; i <= n; i++)
    {
        sum[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> vec[i];
        sum[i] = sum[i - 1] + vec[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)  //先计算 不变的情况下的答案
    {
        if (vec[i] == 1)
        {
            ans += ((n - i) - (sum[n] - sum[i]));
        }
    }
    int maxx = 0;
    for (int i = 1; i <= n; i++)
    {
        if (vec[i] == 0)
        {
            maxx = max(maxx, ((n - i) - (sum[n] - sum[i])) - sum[i]); //逻辑 见思路
        }
        else if (vec[i] == 1)
        {
            maxx = max(maxx, sum[i - 1] - ((n - i) - (sum[n] - sum[i]))); //逻辑 见思路 
        }
    }
    cout << maxx + ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        solve();
    }
    return 0;
}

E 题目链接

  • 题目大意

    有n个任务。如果你完成第i个任务，你将获得ai币。你每天最多只能完成一个任务。然而，一旦你完成了一个任务，在K天内你不能再做同样的任务。(例如，如果k=2，你在第1天做了任务1，那么你在第2天或第3天不能做，但你可以在第4天再做）。
给你两个整数c和d。找出k的最大值，使你在d天内至少能获得c个硬币。如果不存在这样的k，则输出Impossible。如果k可以是任意大的，则输出Infinity。

  • 思路

    二分答案
得到数组后先排序 
如果最大的a[i]*d < c的话 那么无解 输出 Impossible
如果排序后数组的 前d 个数的和 > c 输出 Infinity

然后进行二分答案 具体的check函数 见代码 
需要注意的是 代码中min函数对数组访问越界的控制

  • 代码

    #include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int vec[N];
int c, d;
int n;
bool check(int k)
{
    k += 1;
    int sy = d - (d / k) * k;  //进行k轮后剩余的天数 等效于 sy = d % k 也可以
    int js = 0;
    for (int i = 1; i <= min(k, n); i++)
    {
        js += vec[i];
    }
    js *= (d / k);
    for (int i = 1; i <= min(sy, n); i++)
    {
        js += vec[i];
    }
    return js >= c;
}
void solve()
{
    cin >> n >> c >> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> vec[i];
    }
    sort(vec + 1, vec + n + 1, greater<int>());
    if (vec[1] * d < c)
    {
        cout << "Impossible" << '\n';
        return;
    }
    else
    {
        int ans = 0;
        for (int i = 1; i <= min(n, d); i++)  //不能直接 i<=d 因为d可能比n大 导致访问越界 其他地方的min函数作用亦然
        {
            ans += vec[i];
        }
        if (ans >= c)
        {
            cout << "Infinity" << '\n';
            return;
        }
        else
        {
            int anss = 0;
            int l = 0, r = 1e9 + 10;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (check(mid))
                {
                    anss = mid;
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }
            cout << anss << '\n';
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        solve();
    }
    return 0;
}

F题目链接

  • 题目大意

     给你一棵树和两个点α，b,边有边权。你可以在任意时刻从当前所在的点跳到任意除了b以外的点。求有没有方案使得从a出发，到达b时边权X0r和为0。

  • 思路

    首先我们确定一个共识 就是一条边不会被走两次 因为重走一条边没有任何意义 x^x=0 并且这是一棵树 是不会出现环的
我们考虑先从b出发做一遍 bfs 在bfs的过程中 我们可以得到很多的 {x,y} x代表当前走到的点 y代表走到这个点的val
我们定义一个 map<int> mp 对于每一个{x,y} 我们让 mp[y]=1;

我们再考虑从a点出发 做一遍bfs 我们会获得很多的 {x1,y1} x1代表当前走到的点 y1代表走到这个点的val。如果mp[y1]=1的话,我们就可以直接飞到一个点 使得最后走到b的异或和为0；

  • 代码

    #include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
vector<pair<int, int>> vec[N];
int vis[N];
void solve()
{
    map<int, int> mp;
    int n;
    int a, b;
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)
    {
        vis[i] = 0;
        vec[i].clear();
    }
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v, val;
        cin >> u >> v >> val;
        vec[u].push_back({v, val});
        vec[v].push_back({u, val});
    }
    queue<pair<int, int>> que;
    que.push({b, 0});
    vis[b] = 1;
    while (que.size())
    {
        auto u = que.front();
        que.pop();
        if (u.first != b)
            mp[u.second] = 1;
        for (int i = 0; i < vec[u.first].size(); i++)
        {
            if (!vis[vec[u.first][i].first])
            {
                vis[vec[u.first][i].first] = 1;
                que.push({vec[u.first][i].first,
                          vec[u.first][i].second ^ u.second});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    que.push({a, 0});
    vis[a] = 1;
    vis[b] = 1;
    int flag = 0;
    while (que.size())
    {
        auto u = que.front();
        if (mp[u.second])
        {
            flag = 1;
            break;
        }
        que.pop();
        for (int i = 0; i < vec[u.first].size(); i++)
        {
            if (!vis[vec[u.first][i].first])
            {
                vis[vec[u.first][i].first] = 1;
                que.push({vec[u.first][i].first,
                          vec[u.first][i].second ^ u.second});
            }
        }
    };
    if (flag == 1)
        cout << "YES\n";
    else
        cout << "NO\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int __ = 1;
    cin >> __;
    while (__--)
    {
        solve();
    }
    return 0;
}

G题纯签到就不讲了。题解写的有错误还请指正。

标签：maxx,const,int,题解,flag,欢乐,vec,结训,solve
From： https://www.cnblogs.com/x1uc/p/17441640.html

相关文章

  • 第十二届蓝桥杯c++b组国赛题解（还在持续更新中...）
    试题A：带宽解题思路：由于小蓝家的网络带宽是200Mbps，即200Mb/s，所以一秒钟可以下载200Mb的内容，根据1B=8b的换算规则，所以200Mb=200/8MB=25MB。所以小蓝家的网络理论上每秒钟最多可以从网上下载25MB的内容。代码实现：#include<iostream>#include<algorithm>usingnamespacestd......
  • yarn安装报错网络问题解决方案
    yarn安装报错网络问题解决方案报错为infoThereappearstobetroublewithyournetworkconnection.Retrying...解决方案：更换安装依赖的镜像,使用淘宝镜像安装安装好后更换淘宝镜像yarnconfigsetregistryhttps://registry.npm.taobao.org移除原代理yarn......
  • Java中Collection与Collections有什么区别？Java常见面试题解析
    本文将为大家详细讲解Java中Collection与Collections的区别点，这是我们进行开发时经常用到的知识点，也是大家在学习Java中很重要的一个知识点，更是我们在面试时有可能会问到的问题！文章较长，干货满满，建议大家收藏慢慢学习。文末有本文重点总结，主页有全系列文章分享。技术类问题，欢迎大......
  • [PKUCPC2023] J. Hat Puzzle 题解
    题目链接：http://poj.openjudge.cn/campus2023/J/很荣幸参与了命题。题解的ppt版本在这儿：https://disk.pku.edu.cn:443/link/E4B484E7F3C58A45E9E4FB19C731BF4E.贴一下md版题解，要比ppt版本的简略一些：每个人能够推断出自己帽子颜色的信息，仅有两类：前面的人的帽子情况，以及其......
  • AtCoder Beginner Contest 303 题解 A - E
    A-SimilarString题目大意忽略0和o的差别以及1和l的差别比较两个字符串。解题思路可以硬求，直接写个超长的if判断一下。可以对两个字符串进行修改，0都换成o，1都换成l，然后直接比较两个字符串。ACCode硬求#include<iostream>#include<algorithm>#include<cstring>#i......
  • P9356 「SiR-1」Bracket 题解
    P9356「SiR-1」Bracket题解首先我们来先考虑一下如何计算一个给定的\(f(s[1,n])\)。一般括号序列的题目都是比较套路的将\(\texttt{(}\)赋值为\(1\)，将\(\texttt{)}\)赋值为\(-1\)，然后求一下前缀和记为\(sum_i\)，那么一个括号序列是合法的当且仅当\(\foralli\in[1,n],......
  • comp2123 问题解答
    comp2123Assignment5s12023Problem1.Wewanttodesignadivideandconqueralgorithmforcomputingtheunionofacollectionofrectangles.Theinputrectanglesarealignedwiththeaxesandtheyareallstabbedbythey-axis.Eachrectangleisrepresen......
  • LeetCode-Java题解 977. Squares of a Sorted Array
    题目地址：977.SquaresofaSortedArray解题思路：    又是一道双指针的题目，看见秒想到双指针（平方直接调用sort方法也行，但是这么写这题就没意思了）。但是，我一直在想，不增加空间消耗的情况下，如何进行排列，想了半天把自己绕进去了。开辟一个新数组，倒序放置就非常简单了。一定要利......
  • phpcms常见问题解答
    phpcms常见问题解答1.为什么phpcms首页幻灯片怎么显示不出来?答：需要设置文章的标题图片如果设置标题图片，则可以在首页以及栏目页以图片方式链接到文章。2.自定义phpcms的标签只能是全HTML?答：在自定义标签内容中可以插入html代码，也可以插入多个函数标签或者变量标签。插入函......
  • Gym102978C Count Min Ratio 题解
    赛时无人场切。震撼，震撼。学到许多。全程贺zak。首先我们套路推下式子。枚举左边的红蓝球个数，答案即为\[\begin{aligned}&\sum_{b=0}^B\sum_{r=0}^R\binom{b+r}b\binom{B-b+R-r}{B-b}\min(\fracrb,\frac{R-r}{B-b})\\=&\sum_{x=1}^{\fracRB}\sum_{b=0}^B\sum_{r=0}^R\binom......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99