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

牛客周赛 Round 35

时间：2024-03-03 22:01:31浏览次数：28  
标签：return int ll 35 牛客 long using Round dp

牛客周赛 Round 35

小红的字符串切割

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
vector<vector<int>> dp, e, vis;

void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    n /= 2;
    string a = s.substr(0, n);
    string b = s.substr(n);
    cout << a << endl;
    cout << b << 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>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
vector<vector<int>> dp, e, vis;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(2 * n + 1);
    map<int, int> cnt;
    for (int i = 1; i <= 2 * n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }
    for (auto t : cnt)
    {
        if (t.se & 1)
        {
            puts("-1");
            return;
        }
    }
    vector<int> sa, sb;
    for (auto t : cnt)
    {
        int m = t.se / 2;
        for (int i = 1; i <= m; i++)
        {
            sa.push_back(t.fi);
            sb.push_back(t.fi);
        }
    }
    for (auto x : sa)
    {
        cout << x << ' ';
    }
    cout << endl;
    for (auto x : sb)
    {
        cout << x << ' ';
    }
    cout << endl;
}

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

小红关鸡

解题思路:

排序，双指针维护长度小于等于\(k\)的区间，不断更新概率最大值即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
vector<vector<int>> dp, e, vis;

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    int l = 1;
    int r = 1;
    double ans = 0;
    while (l <= r && r <= n)
    {
        while (r + 1 <= n && a[r + 1] - a[l] <= k)
        {
            r++;
        }
        ans = max(ans, (r - l + 1.0) / (1.0 * n));
        l++;
        if (l > r && r + 1 <= n)
        {
            r++;
        }
    }
    printf("%.10lf", ans);
}

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

小红的排列构造

解题思路:

大于\(n\)的数要改，小于等于\(n\)且出现次数大于\(1\)的要改。

改成合法范围内，没出现过的数即可。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;
vector<vector<int>> dp, e, vis;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int ans = 0;
    map<int, int> cnt;
    int cur = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] > n)
        {
            ans++;
        }
        else if (cnt[a[i]] > 0)
        {
            ans++;
        }
        cnt[a[i]]++;
    }
    cout << ans << endl;
    for (int i = 1; i <= n; i++)
    {
        if ((a[i] <= n && cnt[a[i]] > 1) || (a[i] > n))
        {
            while (cnt[cur] > 0)
            {
                cur++;
            }
            cnt[a[i]]--;
            cout << i << ' ' << cur << endl;
            cnt[cur]++;
        }
    }
}

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

小红的无向图构造

解题思路:

点\(1\)为根，先构造有根树。最短路距离就是深度。

若最短路距离之间出现断层，即有深度\(1,3\)但无深度\(2\)，无解。按深度构造有根树，消耗边\(n - 1\)条。

对于剩余的边，我们有两种处理方法：

  • 同深度结点相连。
  • 深度相差为\(1\)的两节点相连。

若如此连接完边还有剩余，那么无解。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
const int N = 6010;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<pii> a(n + 1);
    vector<vector<int>> d(n + 10, vector<int>());
    map<pii, bool> vis;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi;
        a[i].se = i;
        d[a[i].fi].push_back(i);
    }
    if (m < n - 1)
    {
        puts("-1");
        return;
    }
    sort(a.begin() + 1, a.end());
    for (int i = 2; i <= n; i++)
    {
        if (a[i].fi - a[i - 1].fi > 1)
        {
            puts("-1");
            return;
        }
    }
    m -= n - 1;
    ll res = 0;
    for (int i = 1; i <= n; i++)
    {
        ll x = d[i].size();
        if (x > 0)
        {
            res += (x * (x - 1)) / 2;
        }
        ll y = d[i + 1].size();
        if (x > 0 && y > 0)
        {
            res += (x - 1) * y;
        }
    }
    if (m > res)
    {
        puts("-1");
        return;
    }
    vector<pii> ans;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < (int)d[i].size(); j++)
        {
            ans.emplace_back((pii){d[i - 1][0], d[i][j]});
            vis[{d[i - 1][0], d[i][j]}] = true;
        }
    }
    // for (int i = 2; i <= n; i++)
    // {
    //     ans.emplace_back((pii){a[i].se, d[a[i].fi - 1][0]});
    //     vis[{a[i].se, d[a[i].fi - 1][0]}] = true;
    // }
    for (int i = 0; i <= n; i++)
    {
        if (m == 0)
        {
            break;
        }
        for (int j = 0; j <= (int)d[i].size() - 1; j++)
        {
            for (int k = j + 1; k <= (int)d[i].size() - 1; k++)
            {
                if (vis[{d[i][j], d[i][k]}] == false)
                {
                    vis[{d[i][j], d[i][k]}] = true;
                    ans.push_back({d[i][j], d[i][k]});
                    m--;
                    if (m == 0)
                    {
                        break;
                    }
                }
            }
            if (m == 0)
            {
                break;
            }
        }
        if (m == 0)
        {
            break;
        }
    }
    for (int i = 0; i <= n; i++)
    {
        if (m == 0)
        {
            break;
        }
        for (int j = 0; j <= (int)d[i].size() - 1; j++)
        {
            for (int k = 0; k <= (int)d[i + 1].size() - 1; k++)
            {
                if (vis[{d[i][j], d[i + 1][k]}] == false)
                {
                    vis[{d[i][j], d[i + 1][k]}] = true;
                    ans.push_back({d[i][j], d[i + 1][k]});
                    m--;
                    if (m == 0)
                    {
                        break;
                    }
                }
            }
            if (m == 0)
            {
                break;
            }
        }
        if (m == 0)
        {
            break;
        }
    }
    if (m > 0)
    {
        puts("-1");
        return;
    }
    for (auto t : ans)
    {
        cout << t.fi << ' ' << t.se << endl;
    }
    cout << endl;
}

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

小红的子序列权值和（easy）

小红的子序列权值和（hard）

解题思路:

一个数的因子个数取决于他质因数分解后，质因子的次数。\(x = p_1^{\alpha_1}p_2^{\alpha_2}\)。那么\(x\)的因子个数为\((\alpha_1 + 1)\times (\alpha_2 + 1)。\)

本题中只有两个质因子\((2,3)\)，所以关键就是维护他们次数之和。

\(dp[i]:考虑前i个数字，他们的序列权值和为dp[i]\)。

$s[2]:考虑前i个数字，他们序列构成的每个子序列，设子序列中元素乘积为x_i,x_i = 2{\alpha_i}3 .s[2] = \sum(\alpha_i + 1) $。

\(s[3] = \sum(\beta_i + 1)\)。

考虑\(dp[i]\)时，首先，相比\(dp[i -1]\)，会多出\(2^{i -1}\)个子序列。这些子序列中有一个是\(a[i]\)，其余\(2^{i-1} - 1\)个子序列为\(dp[i-1]\)中的所有子序列分别乘以\(a[i]\)。

  • \(a[i] = 1\)：那么前面所有的\(\alpha_i 和\beta_i\)都不会发生变化，只是单纯子序列的增加。

    • \(dp[i] = 2 * dp[i-1] + 1\)，其中\(+1\)是因为\(a[i] =1,a[i] 的因子只有一个\)。
    • \(s[2] = 2 * s[2] + 1\)，对应上面解释。\(s[3]\)同理。

  • \(a[1] = 2\)：前面\(2^{i -1}\)个子序列要乘以\(a[i]\)，\(\alpha_i + 1\)。

    • \(dp[i] = 2 * dp[i - 1] + s[3] + 2\)。其中，\(+s[3]\)是因为质因子\(2\)的次数\(+1\)，参照最初给的根据质因子次数求因子个数的公式。\(+1\)是因为\(a[i] = 2, a[i]的因子有2个\)。

    • \(s[2] = 2 *s[2] + 2^{i -1}\),\(s[3] = 2 * s[3] + 1\)。

  • \(a[1] = 3\)：前面\(2^{i -1}\)个子序列要乘以\(a[i]\)，\(\beta_i + 1\)。

    • \(dp[i] = 2 * dp[i - 1] + s[2] + 2\)。其中，\(+s[2]\)是因为质因子\(3\)的次数\(+1\)，参照最初给的根据质因子次数求因子个数的公式。\(+1\)是因为\(a[i] = 3, a[i]的因子有2个\)。

    • \(s[3] = 2 *s[3] + 2^{i -1}\),\(s[2] = 2 * s[2] + 1\)。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
typedef double db;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int mod = 1e9 + 7;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    vector<ll> cnt(4, 0), s(4, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    vector<ll> dp(n + 1);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 1)
        {
            dp[i] = ((dp[i - 1] * 2) + 1) % mod;
            s[3] = (2 * s[3] + 1) % mod;
            s[2] = (2 * s[2] + 1) % mod;
        }
        else if (a[i] == 2)
        {
            dp[i] = (2 * dp[i - 1] + s[3] + 2) % mod;
            dp[i] %= mod;
            s[3] = (2 * s[3] + 1) % mod;
            s[2] = ((2 * s[2] + 1) + (qmi(2, i - 1))) % mod;
            // cnt[2]++;
            // s[2] = s[2] + (qmi(2, i - 1) * s[3]) + 2;
            // s[2] %= mod;
        }
        else
        {
            dp[i] = (2 * dp[i - 1] + s[2] + 2) % mod;
            dp[i] %= mod;
            s[2] = (2 * s[2] + 1) % mod;
            s[3] = ((2 * s[3] + 1) + (qmi(2, i - 1))) % mod;
            // cnt[3]++;
            // s[3] = s[3] + (qmi(2, i - 1) - 1) + 3;
            // s[3] %= mod;
        }
        // cout << i << ' ' << s[2] << ' ' << s[3] << ' ' << dp[i] << endl;
    }
    cout << dp[n] << endl;
}

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

标签：return,int,ll,35,牛客,long,using,Round,dp
From： https://www.cnblogs.com/value0/p/18050841

相关文章

  • 牛客大厂真题刷题记录
    1、问题：统计在有用户互动的最近一个月（按包含当天在内的近30天算，比如10月31日的近30天为10.2~10.31之间的数据）中，每类视频的转发量和转发率（保留3位小数）。注：转发率＝转发量÷播放量。结果按转发率降序排序。selecttag,sum(if_retweet)retweet_cut,round(sum(if_retweet)/coun......
  • 牛客练习赛122
    牛客练习赛122黑白配代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;typedefdoubledb;#definefifirst#definesesecondusingi128=__int128_t;usingpiii=pair<ll,pair<ll,ll>>;cons......
  • 16 Educational Codeforces Round 142 (Rated for Div. 2)C. Min Max Sort（递归、思维
    C.MinMaxSort很不错的一道题目，不过脑电波和出题人每对上，\(qwq。\)正难则反。我们考虑最后一步是怎么操作的。最后一步一定是对\(1\)和\(n\)进行操作那么上一步呢？上一步应该是对\(2\)和\(n-1\)以此类推第一步应该是对\(\frac{n}{2}\)和\(\frac{n}{2}+1\)我们的答案应该......
  • Educational Codeforces Round 143 (Rated for Div. 2)C. Tea Tasting(前缀和+二分、
    C.TeaTasting思路这里枚举有三种思路然后经过考虑3是最可行的，然后接着考虑如何计算贡献这里在实现的时候用了一个差分数组，因为我们需要记录第i个茶师它喝了多少个\(b_i\)以及不满\(b_i\)的用\(c_i\)记录，最后计算一下答案即可。#include<bits/stdc++.h>#defineintlon......
  • 牛客练习赛122
    目录写在前面ABCDE写在最后写在前面比赛地址：https://ac.nowcoder.com/acm/contest/75768。因为suzt大神在打所以也来凑一凑热闹。A签到。///*By:Luckyblock*/#include<bits/stdc++.h>#defineLLlonglong//=====================================================......
  • Codeforces Round 930 (Div. 2)
    目录写在前面ABCDEF写在最后写在前面比赛地址：https://codeforces.com/contest/1937。被交互杀死的一集。赛时卡C明天有早八就直接睡大觉了，第二天看看D一眼秒了，最困的一集。A签到发现1会被先后交换到2，4，8，16……输出\(2^{\left\lfloor\logn\right\rfloor}\)即可。......
  • 牛客练习赛122题解A-D
    牛客练习赛122A.黑白配代码：#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+7;constintINF=0x3f3f3f3f;typedeflonglongll;#defineendl"\n"voidsolve(){ intt,n;cin>>t>>n;inta[n+1];while(t--)......
  • 牛客练习赛122 F 括号匹配 费用流
    CF打多了很多题目中的性质都挖掘出来了，也想到了费用流。很难\(dp\)因为一组中三个括号留下来一个很难作为状态进行dp。由于对括号匹配还不熟悉以为是\(n^2\)的图就没写了，事实上应该是线性的建图。所以对于\(n=2000\)这个数据范围网络流是可以过的。设置源点\(S\)和汇点\(T\)。......
  • Codeforces Round 931 (Div. 2) A-D2
    A.TooMinTooMax贪心、排序。对数组排序后，显然当下标\(i\)、\(j\)、\(k\)、\(l\)分别选择\(1\)、\(n\)、\(2\)、\(n-1\)时求得最大值。时间复杂度：\(O(nlogn)\)。#include<bits/stdc++.h>usingnamespacestd;#definecctieios::sync_with_stdio(0);cin.tie(0)......
  • 周赛Round26总结1
    预计得分500，实际得分400，挂了20+50+30分。T1移动move题目描述：\(n\)个二维向量\((X_{i},Y_{i})\)，随便选择\(k\)个，其中\(0<=k<=n\)，起点是\((0,0)\)，每次移动后的位置是\((s+x_{i},t+y_{i})\)，求终点\(|s|+|t|\)的最大值。分析：分类讨论。\((X_{i},Y_{i})\)可以分到四个......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99