首页 > 其他分享 >牛客周赛 Round 34

牛客周赛 Round 34

时间：2024-02-25 23:56:17浏览次数：18  
标签：int back 34 牛客 solve pair using Round dp

牛客周赛 Round 34

小红的字符串生成

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    string a, b;
    cin >> a >> b;
    if (a == b)
    {
        cout << 2 << endl;
        cout << b << endl;
        cout << a + b << endl;
    }
    else
    {
        cout << 4 << endl;
        cout << a << endl;
        cout << b << endl;
        cout << a + b << endl;
        cout << b + a << endl;
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

小红的非排列构造

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int cnt = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] != i)
        {
            cnt = 0;
        }
    }
    cout << cnt << endl;
    if (cnt)
    {
        cout << 1 << ' ' << n << endl;
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

小红的数字拆解

解题思路:

从前往后拆，遇到偶数就分，最后记得排序。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

bool cmp(string a, string b)
{
    if (a.size() != b.size())
    {
        return a.size() < b.size();
    }
    return a < b;
}

void solve()
{
    string s;
    cin >> s;
    string cur;
    vector<string> t;
    for (auto c : s)
    {
        cur += c;
        int x = c - '0';
        if (!(x & 1))
        {
            if (cur.size())
            {
                t.emplace_back(cur);
            }
            cur.clear();
        }
    }
    sort(t.begin(), t.end(), cmp);
    for (auto c : t)
    {
        cout << c << endl;
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

小红的陡峭值

解题思路:

设出现了\(x\)个大于零的数。

  • \(x = 0\)：构造序列\((2, 1, 1, ..., 1)\)。

  • \(x = 1\)：如果序列首尾都不为零，那么无解。否则首尾取一个作为出现数字加一。

  • \(x =2\)：若两数之差大于\(1\)，无解。

    否则，设最左边出现的非零数为\(a\),设最右边出现的非零数为\(b\)。从左开始向右赋值\(a\)，直到遇到非零且非\(a\)的数停止，右侧同理。最后按题意判断序列陡峭值是否为\(1\)。

  • \(x > 2\)：无解。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    set<int> s;
    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] > 0)
        {
            s.insert(a[i]);
        }
    }
    if (s.size() > 2)
    {
        puts("-1");
        return;
    }
    if (s.size() == 0)
    {
        for (int i = 1; i <= n; i++)
        {
            if (i == 1)
            {
                cout << 2 << ' ';
                continue;
            }
            cout << 1 << ' ';
        }
    }
    else if (s.size() == 1)
    {
        int x = *s.begin();
        if (a[1] == 0)
        {
            a[1] = x + 1;
            for (int i = 1; i <= n; i++)
            {
                if (i != 1)
                {
                    cout << x << ' ';
                    continue;
                }
                cout << a[i] << ' ';
            }
        }
        else if (a[n] == 0)
        {
            a[n] = x + 1;
            for (int i = 1; i <= n; i++)
            {
                if (i != n)
                {
                    cout << x << ' ';
                    continue;
                }
                cout << a[i] << ' ';
            }
        }
        else
        {
            puts("-1");
        }
    }
    else
    {
        int x = *s.begin();
        int y = *s.rbegin();
        if (abs(x - y) > 1)
        {
            cout << -1 << endl;
            return;
        }
        vector<int> v(13);
        for (int i = 1; i <= n; i++)
        {
            if (a[i] != 0)
            {
                v[1] = a[i];
                break;
            }
        }
        for (int i = n; i; i--)
        {
            if (a[i] != 0)
            {
                v[2] = a[i];
                break;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            if (a[i] != 0 && a[i] != v[1])
            {
                break;
            }
            a[i] = v[1];
        }
        for (int i = n; i; i--)
        {
            if (a[i] != 0 && a[i] != v[2])
            {
                break;
            }
            a[i] = v[2];
        }
        ll t = 0;
        for (int i = 2; i <= n; i++)
        {
            t += abs(a[i] - a[i - 1]);
        }
        if (t == 1)
        {
            for (int i = 1; i <= n; i++)
            {
                cout << a[i] << ' ';
            }
        }
        else
        {
            puts("-1");
        }
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

小红的树形 dp

解题思路:

\(dp[i][0/1]:对于节点i，我们选节点i字符为(d/p)是否有解。\)

如果有解，那么顺着构造即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 1e5 + 10;
const int inf = 1 << 30;
vector<int> e[N];
int n;
string s;
int ans[N];
bool dp[N][2];

void dfs(int u, int fa)
{
    if (s[u] == 'd')
    {
        dp[u][0] = 1;
        dp[u][1] = 0;
    }
    else if (s[u] == 'p')
    {
        dp[u][1] = 1;
        dp[u][0] = 0;
    }
    else
    {
        dp[u][0] = dp[u][1] = 1;
    }
    for (auto v : e[u])
    {
        if (v == fa)
        {
            continue;
        }
        dfs(v, u);
        dp[u][0] = dp[u][0] & dp[v][1];
        dp[u][1] = dp[u][1] & dp[v][0];
    }
}

void dfs_solve(int u, int fa, int par)
{
    ans[u] = par ^ 1;
    for (auto v : e[u])
    {
        if (v == fa)
        {
            continue;
        }
        dfs_solve(v, u, par ^ 1);
    }
}

void solve()
{
    cin >> n;
    cin >> s;
    s = ' ' + s;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    dfs(1, -1);
    if (!(dp[1][0] | dp[1][1]))
    {
        puts("-1");
    }
    else
    {
        if (dp[1][0])
        {
            dfs_solve(1, -1, 1);
        }
        else
        {
            dfs_solve(1, -1, 0);
        }
        for (int i = 1; i <= n; i++)
        {
            char c = ans[i] == 1 ? 'p' : 'd';
            cout << c;
        }
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

小红的矩阵构造

解题思路：

注意：\(x\)为偶数。尝试构造，最终每行每列的异或和都是\(0\)。

  • \(x \% 4 = 0\)：将\(x / 4\)填入左上方四个格子。
  • \(x \% 4 =2\)：
    • \(x = 2\)：无解。
    • \(x = 6\)：我们发现，可以将\(6\)个\(1\)填入右下角，使得最终每行每列的异或和都是\(0\)。
    • \(x > 6\)：只要不是\(n = m = 4\)，都有解。结合上述方法先减去\(6\)，在填入左上角。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    int n, m, x;
    cin >> n >> m >> x;
    vector<vector<int>> g(n + 1, vector<int>(m + 1));
    if (x % 4 == 0)
    {
        x /= 4;
        g[1][1] = g[1][2] = g[2][1] = g[2][2] = x;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                cout << g[i][j] << ' ';
            }
            cout << endl;
        }
    }
    else
    {
        if (x == 2 || (n == m && n == 4 && x > 6))
        {
            puts("-1");
        }
        else if (x == 6)
        {
            x -= 6;
            g[n][m] = g[n - 1][m - 1] = g[n - 2][m - 2] = g[n - 2][m - 1] = g[n - 1][m] = g[n][m - 2] = 1;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    cout << g[i][j] << ' ';
                }
                cout << endl;
            }
        }
        else
        {
            x -= 6;
            g[n][m] = g[n - 1][m - 1] = g[n - 2][m - 2] = g[n - 2][m - 1] = g[n - 1][m] = g[n][m - 2] = 1;
            x /= 4;
            g[1][1] = g[1][2] = g[2][1] = g[2][2] = x;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    cout << g[i][j] << ' ';
                }
                cout << endl;
            }
        }
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

小红的元素交换

解题思路:

排列交换到升序，构造置换环。

环有三种，纯红，纯白，红白。

纯的本身都无法移动元素；红白和正常置换环一样，元素数减一次操作即可完成置换。

将一个纯红和一个纯白合并成红白需要一步，纯加红白变为红白也只需要一步，但明显先合并纯色更优。

注意：元素数量为一的环，也就是自环，看情况使用。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), ne(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    string s;
    cin >> s;
    s = ' ' + s;
    bool us = true;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] != i)
        {
            us = false;
        }
    }
    if (us)
    {
        puts("0");
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        ne[i] = a[i];
    }
    vector<bool> vis(n + 1);
    vector<int> vr, vw, vh;
    for (int i = 1; i <= n; i++)
    {
        int u = i;
        if (vis[a[u]])
        {
            continue;
        }
        vector<int> cnt(2, 0);
        while (!vis[a[u]])
        {
            vis[a[u]] = true;
            if (s[a[u]] == 'R')
            {
                cnt[0]++;
            }
            else
            {
                cnt[1]++;
            }
            u = ne[u];
        }
        if (cnt[0] && cnt[1])
        {
            vh.emplace_back(cnt[0] + cnt[1]);
        }
        else if (cnt[0])
        {
            vr.emplace_back(cnt[0]);
        }
        else
        {
            vw.emplace_back(cnt[1]);
        }
    }
    ll ans = 0;
    if (vh.empty() && (vr.empty() || vw.empty()))
    {
        puts("-1");
        return;
    }
    sort(vr.begin(), vr.end());
    sort(vw.begin(), vw.end());
    while (vr.size() > 0 && vw.size() > 0)
    {
        int x = vr.back();
        int y = vw.back();
        int h = vr.back() + vw.back();
        if ((x == 1 || y == 1) && vh.size() > 0)
        {
            break;
        }
        vr.pop_back();
        vw.pop_back();
        vh.push_back(h);
        ans++;
    }
    while (vr.size() > 0)
    {
        int x = vr.back();
        int t = vh.back() + vr.back();
        if (x == 1)
        {
            break;
        }
        vh.pop_back();
        vr.pop_back();
        vh.emplace_back(t);
        ans++;
    }
    while (vw.size() > 0)
    {
        int y = vw.back();
        int t = vh.back() + vw.back();
        if (y == 1)
        {
            break;
        }
        vh.pop_back();
        vw.pop_back();
        vh.emplace_back(t);
        ans++;
    }
    for (auto x : vh)
    {
        ans += x - 1;
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

标签：int,back,34,牛客,solve,pair,using,Round,dp
From： https://www.cnblogs.com/value0/p/18033368

相关文章

  • Educational Codeforces Round 162 (Rated for Div. 2)
    目录写在前面ABCDE写在最后写在前面比赛地址：https://codeforces.com/contest/1923。为唐氏儿的寒假带来了一个构式的结局，飞舞一个。天使骚骚不太行啊妈的，推了三条线了感觉剧情太白开水了，咖啡馆也是这个熊样子、、、A签到。显然最优的策略是不断地选择最右侧的1进行操作，每......
  • Codeforces Round 791 (Div. 2)
     C-RooksDefenders线段树模板，维护：1）v：个数，2）sum：v的个数是否大于0.//#include"bits/stdc++.h"#include"iostream"usingnamespacestd;constintN=2e5;structNode{intl,r,v,sum;}tr1[N*4],tr2[N*4];intn,q;voidbuild(Nodetr[],i......
  • 牛客寒假4到6补题
    牛客寒假4：F：来点每日一题题意：给定一个长度为n的数组，任意选6个数，6个数得分为 ((a-b)*c-d)*e-f，问最大能得到多少分解：n*n的dp，暴力枚举每一个数字v[i]，f[i]表示以第i个位置结尾的得分最大是多少 voidsolve(){intn;cin>>n;vector<int>v(n+10......
  • HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）
    HUAWEIProgrammingContest2024（AtCoderBeginnerContest342）A-Yay!代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128_t;usingpiii=p......
  • Codeforces Round 926 (Div. 2)
    A.升序排列再求和#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn;cin>>n;vector<int>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];sort(a.b......
  • 2024牛客寒假算法基础集训营6
    A.欧拉筛处理出素数直接3重暴力循环找#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fboolis_prime[N];//是否是质数，0为是，1为不是intprime[N];//质数数组inttop=1;//质数的下标intmin_p[N];//最小......
  • 2024牛客寒假算法基础集训营6 H 纷乱的红线 题解
    Question2024牛客寒假算法基础集训营6H纷乱的红线小红拿到了一个圆，以及平面上有\(n\)个点（保证没有三点共线）。现在小红将随机取\(3\)个点画一个三角形，她想知道这个三角形和圆的交点数量的期望是多少？Solution考虑到\(n\le1000\)可以枚举每一条线，计算这一条线和圆的交......
  • 2024牛客寒假算法基础集训营6 G 人生的起落 题解
    Question2024牛客寒假算法基础集训营6G人生的起落定义一个三元组\((x,y,z)\)是“v-三元组”当且仅当该三元组满足以下条件：\(x=z\)\(x>y\)现在需要你构造一个\(n\)个正整数组成的数组，所有元素之和恰好等于\(S\)，且恰好有\(k\)个长度威\(3\)的连续子数组......
  • Atcoder Beginner Contest 342 全题解
    A-Yay!题意给定字符串\(s\)已知该字符串中只有一个字符与其他字符不同求这个字符思想开一个数组\(cnt_i\)来记录\(s\)中每个字符出现的次数，一个数组\(first_i\)来记录\(s\)中每个字符第一次出现的下标。选择\(cnt_i=1\)的\(i\)输出\(first_i\)......
  • 牛客六
    1.B爱恨的纠葛（先将ab排序，再二分查找ab元素间差值最小的一对，再从a和c中找出对应下标（因为第二个数组不能动），再交换a的两个下标位置的值）1#include<bits/stdc++.h>2usingnamespacestd;3inta[1000005];4intb[1000005];5intc[1000005];6voidsolve(intn)7{......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99