首页 > 编程语言 >2024牛客寒假算法基础集训营3

2024牛客寒假算法基础集训营3

时间：2024-03-07 20:23:17浏览次数：14  
标签：const int vi long 2024 牛客 vector using 集训营

A-智乃与瞩目狸猫、幸运水母、月宫龙虾

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    string a , b;
    for( int x , y ; n ; n -- ){
        cin >> a >> b;
        x = a[0] , y = b[0];
        if( x >= 'A' and x <= 'Z' ) x = x + 'a' - 'A';
        if( y >= 'A' and y <= 'Z' ) y = y + 'a' - 'A';
        if( x == y ) cout << "Yes\n";
        else cout << "No\n";
    }

}

B-智乃的数字手串

模二后，把序列按照连续相同进行分段，并且如果第一段和最后一段相同则要合并成一段，如果一共分成了cnt段，则整体可进行的操作次数就是n-cnt。但是要注意如果只有一段则可以进行n次操作。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

void solve() {
    int n;
    cin >> n;
    vi a(n);
    for (auto &i: a) cin >> i, i %= 2;
    int cnt = 1 , res ;
    for (int i = 1; i < n; i++)
        if (a[i] != a[i - 1]) cnt++;
    if (cnt > 2 and a.front() == a.back()) cnt--;
    if( cnt == 1 ) res = n;
    else res = n - cnt;
    if( res % 2 ) cout << "qcjj\n";
    else cout << "zn\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
}

C-智乃的前缀、后缀、回文

其实是是一个字符串模板题了算是，所以我用了两个字符串算法来求解。

首先用 Manacher 求出\(S\)串所有的前缀回文串和后缀回文串，然后用字符串哈希判断每一个\(S\)的前缀前缀是否与\(T\)的后缀相同，每一个\(S\)的后缀是否与\(T\)的前缀相同。

处理选择我先处理出后缀最大值，然后计算前缀的时候直接与后缀最大值一起更新答案即可。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using vi = vector<i64>;


namespace Hash {
    // 下标从 1 开始
    using Val = pair<i64, i64>;
    const Val Mod(1e9 + 7, 1e9 + 9);
    const Val base(13331, 23333);
    vector<Val> p;

    Val operator+(Val a, Val b) {
        i64 c1 = a.first + b.first, c2 = a.second + b.second;
        if (c1 >= Mod.first) c1 -= Mod.first;
        if (c2 >= Mod.second) c2 -= Mod.second;
        return pair(c1, c2);
    }

    Val operator-(Val a, Val b) {
        i64 c1 = a.first - b.first, c2 = a.second - b.second;
        if (c1 < 0) c1 += Mod.first;
        if (c2 < 0) c2 += Mod.second;
        return pair(c1, c2);
    }

    Val operator*(Val a, Val b) {
        return pair(a.first * b.first % Mod.first, a.second * b.second % Mod.second);
    }

    void init(int n) {
        p.resize(n + 1), p[0] = pair(1, 1);
        for (int i = 1; i <= n; i++) p[i] = p[i - 1] * base;
        return;
    }

    struct Hash {
        vector<Val> h;

        Hash(const string &s) {
            h.resize(s.size() + 1);
            for (int i = 1; i <= s.size(); i++)
                h[i] = h[i - 1] * base + pair(s[i - 1], s[i - 1]);
            return;
        }

        Val getHash(int l, int r) {
            if (l > r) return pair(0, 0);
            return h[r] - h[l - 1] * p[r - l + 1];
        }

        Val val() {
            return h.back();
        }
    };

}


const int N = 1e5;


string manacherInit(const string &s) {
    string t = "#";
    for (const char &c: s)
        t += c, t += '#';
    return t;
}

vector<int> manacher(const string &s) {
    int n = s.size();
    vector<int> p(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (j + p[j] > i) p[i] = min(p[j * 2 - i], j + p[j] - i);
        while (i >= p[i] and i + p[i] < n and s[i - p[i]] == s[i + p[i]]) p[i]++;
        if (i + p[i] > j + p[j]) j = i;
    }
    return p;
}


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    Hash::init(N);
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    if (n > m) swap(n, m), swap(s, t);
    auto p = manacher(manacherInit(s));

    vi pm, sm;
    for (int i = 1; i < n; i++) {
        if (p[i] > i) pm.push_back(i);
        if (p[n * 2 - i] > i) sm.push_back(i);
    }

    Hash::Hash hs(s), ht(t);

    vi sufVal(n + 1, -1);
    for (auto len: sm) {
        if (ht.getHash(1, len) == hs.getHash(n - len + 1, n))
            sufVal[n - len + 1] = len;
    }
    for (int i = n - 1; i >= 1; i--) sufVal[i] = max(sufVal[i], sufVal[i + 1]);

    i64 res = -1;
    for (auto len: pm) {
        if (sufVal[len + 1] == -1) break;

        if (hs.getHash(1, len) == ht.getHash(m - len + 1, m))
            res = max(res, len + sufVal[len + 1]);
    }
    if (res > 0) cout << res * 2 << "\n";
    else cout << "-1\n";
    return 0;
}

当然了，判断回文串也可以逆序哈希求解。

D-chino's bubble sort and maximum subarray sum(easy version)

直接枚举交换的位置即可。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vi a(n);
    for (auto &i: a) cin >> i;

    auto calc = [&a]() {
        int ans = -inf;
        for (int i = 0, cnt = 0; i < a.size(); i++) {
            cnt += a[i];
            ans = max(ans, cnt);
            if (cnt < 0) cnt = 0;
        }
        return ans;
    };
    if (k == 0)
        cout << calc() << "\n";
    else {
        int res = -inf;
        for (int i = 1; i < n; i++) {
            swap(a[i - 1], a[i]);
            res = max(res, calc());
            swap(a[i - 1], a[i]);
        }
        cout << res << "\n";
    }
}

G-智乃的比较函数(easy version)

可以直接枚举三个数赋值

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

void solve() {
    int n;
    cin >> n;
    vector<array<i32, 3>> b(n);
    for (auto &it: b)
        for (auto &i: it) cin >> i;
    vector<int> a(4);
    auto check = [&a, &b]() {
        for (const auto &[x, y, z]: b)
            if ((a[x] < a[y]) != z) return false;
        return true;
    };
    for (a[1] = 0; a[1] <= 2; a[1]++)
        for (a[2] = 0; a[2] <= 2; a[2]++)
            for (a[3] = 0; a[3] <= 2; a[3]++)
                if (check()) {
                    cout << "Yes\n";
                    return;
                }

    cout << "No\n";
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

H-智乃的比较函数(normal version)

同 G

J-智乃的相亲活动

其实可以分开算每个女生不选某个男生的概率，分别累乘就可以计算出一个男生不被所有女生选中期望，然后就可以算出被选男生的数量的期望。女生同理。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vi> manToFemale(n), femaleToMan(m);
    for (int x, y; k; k--) {
        cin >> x >> y, --x, --y;
        manToFemale[x].push_back(y);
        femaleToMan[y].push_back(x);
    }
    vector<ldb> notMan(n, 1.0), notFemale(m, 1.0);
    for (const auto &it: manToFemale)
        for (const auto &i: it)
            notFemale[i] *= (ldb) (it.size() - 1) / (it.size());
    for (const auto &it: femaleToMan)
        for (const auto i: it)
            notMan[i] *= (ldb) (it.size() - 1) / (it.size());
    ldb eMan = 0, eFemale = 0;
    for (const auto &i: notMan)
        eMan += 1.0 - i;
    for (const auto &i: notFemale)
        eFemale += 1.0 - i;
    cout << "float\n" << fixed << setprecision(10) << eMan << " " << eFemale << "\n";
    return 0;
}

k-智乃的“黑红树”

构造起来还算简单，简单思路就是用两个队列分别进行 bfs。如果最后点凑不够就是无解。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

void solve() {
    int a, b, n;// black red
    cin >> a >> b, n = a + b;
    if( a == 0 ) {
        cout << "No\n";
        return;
    }
    vector<vi> tree(n + 1, vi(2, -1));
    queue<int> redLeaf, blackLeaf;
    blackLeaf.push(1), a--;
    for (int f = 0, t = 1, x; a + b > 0; f = 0) {
        while (not blackLeaf.empty() and b >= 2 and t + 2 <= n) {
            f |= 1, x = blackLeaf.front(), b -= 2, blackLeaf.pop();
            tree[x][0] = ++t, redLeaf.push(t);
            tree[x][1] = ++t, redLeaf.push(t);
        }
        while (not redLeaf.empty() and a >= 2 and t + 2 <= n) {
            f |= 1, x = redLeaf.front(), a -= 2, redLeaf.pop();
            tree[x][0] = ++t, blackLeaf.push(t);
            tree[x][1] = ++t, blackLeaf.push(t);
        }
        if (f == 0) break;
    }
    if (a + b > 0) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    for (int i = 1; i <= n; i++) {
        for (auto j: tree[i])
            cout << j << " ";
        cout << "\n";
    }
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

L-智乃的36倍数(easy version)

直接暴力枚举就好

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    for( auto & i : a ) cin >> i;
    int res = 0;
    for( int i = 0 ; i < n ; i ++ )
        for( int j = 0 ; j < n ; j ++ ){
            if( i == j ) continue;
            if (a[j] < 10) {
                if ((a[i] * 10 + a[j]) % 36 == 0) res++;
            } else {
                if ((a[i] * 100 + a[j]) % 36 == 0) res++;
            }
        }
    cout << res << "\n";
    return 0;

}

M-智乃的36倍数(normal version)

因为数字位数有限，可以计算每个数字在某个位置下模 36 的值，然后枚举低位的值和低位占的位数，然后既可以计算出高位的值，这样就可以统计方案数。

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
using ldb = long double;

#define int i64

using vi = vector<int>;

using pii = pair<int, int>;
using vii = vector<pii>;

const int inf = INT_MAX, INF = 1e18;
const int mod = 998244353;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
using edge = array<int, 3>;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, res = 0;
    cin >> n;
    vector cntA(20, vi(36)), cntB(20, vi(36));

    for (int x, y; n; n--) {
        cin >> x, y = log10(x) + 1;

        cntA[y][x % 36]++;
        for (i128 i = 1, j = 10; i <= 19; i++, j *= 10)
            cntB[i][(i128(x) * j) % 36]++;

        i128 z = x;
        for (int i = 1; i <= y; i++) z = z * 10;
        z += x;
        if (z % 36 == 0) res--;
    }
    for (int i = 1; i <= 19; i++)
        for (int j = 0; j < 36; j++)
            res += cntA[i][j] * cntB[i][(36 - j) % 36];
    cout << res << "\n";
    return 0;
}

标签：const,int,vi,long,2024,牛客,vector,using,集训营
From： https://www.cnblogs.com/PHarr/p/18059672

相关文章

  • 2024-03-07
    2024-03-07做题埃及分数迭代加深搜索两层迭代：单位分数的个数\(depth\)和最大的分母\(mxs\)推枚举的当前分母\(p\)的上下界：\(\frac{1}{p}\le\frac{a}{b}\)即\(p\ge\frac{b}{a}\)每一个单位分母不相同，所以\(p\gelast\)要在后面\(depth-k+1\)个分数凑出当......
  • 2024 联合省选游记
    摘要：考前别做去年的题，因为你会觉得去年的自己是个若智。day1登顶了大家回来膜你，你的压力会很大导致day2寄掉。考后别去补题，因为你会觉得场上的自己是个若智。day0因为去年省选day2生病的阴影一直存在，所以拒绝了一切面基（试机，没有selfeval，差评。选了三台电脑测了一......
  • 20240307正则表达式对常见字段的校验
    验证固话号码//表示以0开头，后跟2到3位数字，然后是-，最后是7到8位数字。publicstaticbooleancheckPhoneNumber(StringphoneNumber){if(StringUtils.isEmpty(phoneNumber)){returnfalse;}Patternpattern=Pattern.co......
  • 2024 年春节集训 _ 第二课 - 莫比乌斯反演
    练习\(5\)\(\color{orange}{\texttt{E->link}}\)求\[\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)\]\(n,m\leq10^7,\T\leq10^4\)贴个照片。及其丑陋的照片（我的草稿）如上化简最后可以得到\[\sum_{d=1}^nd\sum_{k=1}^{\left[\dfrac{n}{d}\right]}\mu(k)k^2\......
  • [游记] ZJOI2024 游记
    Day0最紧张的一天。一切都很如梦初醒，甚至很难接受“也许是最后一场比赛”了呢。一反往常地开始写模板，开始看之前看过的题，开始阅读很多考前Reminder。一切的一切似乎都带上了很多沉重感……身边的每个人对自己说的话都渲染着一种风暴之前低气压的氛围。早早理好了第二天的......
  • Though Our Paths May Diverge（JSOI 2024 游记）
    Isn’titsupposedtobesunnynow?且当是JSOI2024的游记吧。省选前的精神状态处于一种微妙的平衡。确实也不断在给自己心理暗示，自己有省队水平，但是其实无论是哪边的模拟打得都属于比较稀烂的水平，有的时候真的是一题不会签不上到。跟不上zhy和黄色蜜蜂的节奏啊，大概就......
  • HNOI 2024游记
    HNOI2024游记总的来说，感觉两天基本上发挥出了自己的水平，虽然挂了分，但是挂的分不多，所以勉强在省队线上。得分：\(100+20+32+100+30+0=282\)day0这一天之前的培训基本上就是在打模拟赛和该题，然后也做了一些好题，模拟赛的时候感觉每一天都有很多同学比我的分高很多，感觉大家都非常......
  • 2024年“ENVI/SARscape遥感应用培训班（7城市）”启动计划
    传递遥感技术助力遥感应用2024年“ENVI/SARscape遥感应用培训班（7城市）”启动计划 每一站会提前通知，详细信息及报名方式请关注：微信公众号：ENVI技术殿堂（右侧二维码）博客：https://envi.geoscene.cn/blog邮箱：[email protected]热线：400-819-2281转4......
  • Salesforce 2024财年爆发式增长！第一次现金分红
    对于Salesforce来说，这是非凡的转型之年，所有的关键指标都表现强劲，现金流和利润增长创下了纪录。截至第四季度末，Salesforce的剩余履约价值（RPO）总额为569亿美元，同比增长17%。MarcBenioffSalesforce启动了有史以来第一次分红，并将股票回购计划增加100亿美元。凭借统一Einstein1平......
  • 【国际会议】首届智能教育技术与应用国际会议 （ITEA 2024）
    首届智能教育技术与应用国际会议将于2024年7月20-22日在马来西亚吉隆坡及线上同步举办。ITEA旨在为研究人员、学者和行业专业人士提供交流平台，共同讨论智能教育相关技术领域的最新进展。 会议诚邀国内外高校、科研机构专家、学者，企业界人士及其他相关人员参会交流、展示最新研......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99