首页 > 其他分享 >2023牛客暑期多校训练营7 CGILM

2023牛客暑期多校训练营7 CGILM

时间:2023-08-13 21:55:57浏览次数:47  
标签:tmp CGILM int ll pos 多校 牛客 vector using

比赛链接

C

题解

知识点:位运算,贪心。

我们用分段的思想考虑大小关系,若在同一段则大小不能确定,一开始为 \([1,n]\) 。

我们按位从高到低考虑,某位如果 \(b_i\) 产生了 \(1\) ,那么会这一位的第 \(i\) 个数产生大小的分段,得到 \([1,i-1]<[i,n]\) ,之后这两段的大小关系就确定了,我们可以对各段分别继续相同的讨论。

同时,若在某一位,某段中产生分段,在这段的分段点之前所有数字的这一位一定是全 \(0\) ,之后一定是全 \(1\) ,否则就会大小关系矛盾无解。因此,分段后 \(0,1\) 的情况就立刻确定了。此时可能会出现,在某一位,之前产生的分段已经限制了当前位的情况,而当前的分段需要的 \(0,1\) 情况和之前确定的不同,此时也无解。

到最后,我们确定了所有能确定的位,剩下的位就是自由的。我们发现只要确定 \(a_1\) 即可确定所有数字,我们用 \(k-1\) 的二进制,从低位到高位填入 \(a_1\) 的自由位,就可以得到字典序第 \(k\) 小的序列。

实现时,我们对 \(b\) 数组前缀异或和,此时得到的是每一个数字和 \(a_1\) 异或的值,用刚才的思路稍作修改,即可直接完成对 \(a_1\) 每一位情况的确定。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int a[1000007];
int a1[30];
bool solve() {
    int n, k;
    cin >> n >> k;
    a[1] = 0;
    for (int i = 2;i <= n;i++) cin >> a[i], a[i] ^= a[i - 1];

    vector<pair<int, int>> seg = { {1,n} };
    for (int i = 29;i >= 0;i--) {
        vector<pair<int, int>> tmp;
        a1[i] = -1;
        for (auto [l, r] : seg) {
            int pos = l;
            while (pos <= r) {
                if ((a[l] >> i & 1) != (a[pos] >> i & 1)) break;
                pos++;
            }
            tmp.push_back({ l,pos - 1 });
            if (pos > r) continue;
            tmp.push_back({ pos,r });
            for (int j = pos;j <= r;j++) {
                if ((a[pos] >> i & 1) == (a[j] >> i & 1)) continue;
                return false;
            }
            int x = a[l] >> i & 1;
            if (a1[i] != -1 && a1[i] != x) return false;
            a1[i] = x;
        }
        seg = tmp;
    }

    k--;
    for (int i = 0;i <= 29;i++) {
        if (a1[i] != -1) a[1] |= a1[i] << i;
        else {
            a[1] |= (k & 1) << i;
            k >>= 1;
        }
    }
    if (k) return false;
    for (int i = 1;i <= n;i++) cout << (i == 1 ? a[1] : a[1] ^ a[i]) << " \n"[i == n];
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

G

题解

知识点:模拟,数学。

注意到,我们可以把能互相修改的环单独拿出来考虑,考虑每个环是否可以清零即可。

对于一个环 \(a_1,a_2,\cdots,a_m\),我们随意选择一个数字作为起点,假设将其和下一个环上相邻的数字 \(a_2\) 减去 \(x\) ,再将后续数字清零并回到 \(a_1\) 将 \(a_1\) 清零,呈现操作次数为 \(x,a_2 - x,a_3-a_2 + x, \cdots\) 。最后一步,得到的是将 \(a_1\) 清零的操作次数,它应该等于 \(x\) 。

在这个过程中,我们利用操作次数必须是非负的,来收紧 \(x\) 的上下界 \([l,r]\) ,若上下界是空集,则无解。

我们发现操作次数是个一次函数,若 \(m\) 是奇数则得到 \(-x+b\) ,否则为 \(x + b\) 。对于前者情况,若 \(b\) 是偶数则 \(x = b/2\) ,否则无解;对于后者情况,若 \(b \neq 0\) 则 \(x\) 在 \([l,r]\) 范围任意有解,否则无解。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int a[1000007];
bool vis[1000007];

bool check(const vector<int> &cyc) {
    int sz = cyc.size();
    ll val = 0;
    ll l = 0, r = cyc[0];
    for (int i = 1;i <= sz;i++) {
        val = cyc[i % sz] - val;
        if (i & 1) r = min(r, val);
        else l = max(l, -val);
    }
    if (r < l) return false;
    if (sz & 1) {
        if (val & 1) return false;
        ll x = val / 2;
        if (x < l || x > r) return false;
        return true;
    }
    else return val == 0;
}

bool solve() {
    int n, k;
    cin >> n >> k;
    bool ok = 1;
    for (int i = 0;i < n;i++) cin >> a[i], vis[i] = 0, ok &= !a[i];
    if (ok) {
        cout << "YES" << '\n';
        return true;
    }
    else if (k > n / 2) {
        cout << "NO" << '\n';
        return true;
    }
    for (int i = 0;i < n;i++) {
        if (vis[i]) continue;
        vector<int> cyc;
        int pos = i;
        while (!vis[pos]) {
            cyc.push_back(a[pos]);
            vis[pos] = 1;
            (pos += k) %= n;
        }
        if (!check(cyc)) {
            cout << "NO" << '\n';
            return true;
        }
    }
    cout << "YES" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

I

题解

知识点:根号分治,容斥原理,枚举。

先将字符串按长度分类。

对于同一个长度的字符串,考虑按长度和个数分治,若长度大于个数则用字符串本身容斥,否则直接暴力搜索每个可能的串并检查是否能匹配。

后者情况很好处理,前者的容斥每次需要选择一个字符串的子集,计算子集中字符串的共同贡献。因此,对于一个子集里的字符串,每一位都必须是不矛盾的,否则这个子集的贡献是 \(0\) ,最后统计有多少位置是自由的,即可计算贡献。

时间复杂度 \(O(2^{\sqrt{n}} \sum |s_i|)\)

空间复杂度 \(O(\sum |s_i|)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int P = 998244353;

vector<string> s[407];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        string t;
        cin >> t;
        s[t.size()].push_back(t);
    }

    int ans = 0;
    for (int i = 1;i <= 400;i++) {
        if (!s[i].size()) continue;
        if (s[i].size() > i) {
            for (int j = 0;j < (1 << i);j++) {
                for (auto str : s[i]) {
                    bool ok = 1;
                    for (int k = 0;k < i;k++) ok &= str[k] == '?' || (j >> (i - k - 1) & 1) == str[k] - '0';
                    if (ok) {
                        (ans += 1) %= P;
                        break;
                    }
                }
            }
        }
        else {
            int sz = s[i].size();
            for (int j = 1;j < (1 << sz);j++) {
                bool f = 0;
                string tmp(i, '?');
                for (int k = 0;k < sz;k++) {
                    if (!(j >> k & 1)) continue;
                    f ^= 1;
                    for (int l = 0;l < i;l++) {
                        if (s[i][k][l] == '?') continue;
                        if (tmp[l] == '?') tmp[l] = s[i][k][l];
                        if (tmp[l] != s[i][k][l]) tmp[l] = '#';
                    }
                }

                int mul = 1;
                bool ok = 1;
                for (int k = 0;k < i;k++) {
                    mul = (tmp[k] == '?' ? 2LL : 1LL) * mul % P;
                    ok &= tmp[k] != '#';
                }
                if (ok) (ans += (f ? 1 : -1) * mul) %= P;
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

L

题解

知识点:KMP。

对于 \(|s| > |t|\) 时,显然答案是 \(0\) ,否则暴力跑一次KMP即可,时间复杂度是 \(|t|\) 的总和。

时间复杂度 \(O(\sum |t|)\)

空间复杂度 \(O(|s| + |t|)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<class T>
class KMP {
    int m;
    T p;

public:
    vector<int> nxt;

    KMP() {}
    KMP(const T &_p) { init(_p); }

    void init(const T &_p) {
        m = _p.size() - 1;
        p = _p;
        nxt.assign(m + 1, 0);
        for (int i = 2;i <= m;i++) {
            nxt[i] = nxt[i - 1];
            while (nxt[i] && p[i] != p[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];
            nxt[i] += p[i] == p[nxt[i] + 1];
        }
    }

    vector<int> find(const T &s) {
        int n = s.size() - 1;
        vector<int> pos;
        for (int i = 1, j = 0;i <= n;i++) {
            while (j && s[i] != p[j + 1]) j = nxt[j];
            j += s[i] == p[j + 1];
            if (j == m) {
                pos.push_back(i - j + 1);
                j = nxt[j];
            }
        }
        return pos;
    }

    vector<int> get_cycle_time() {
        vector<int> res;
        int pos = m;
        while (pos) {
            pos = nxt[pos];
            res.push_back(m - pos);
        }
        return res;
    }

    vector<int> get_cycle_loop() {
        vector<int> res;
        for (auto val : get_cycle_time())
            if (!(m % val)) res.push_back(val);
        return res;
    }
    int min_cycle_loop() { return get_cycle_loop()[0]; }

    void debug() {
        for (int i = 1;i <= m;i++)
            cout << nxt[i] << " \n"[i == m];
    }
};
/// KMP,前缀函数O(|P|)、查找O(|S|+|P|)、循环相关O(|P|),维护字符串前缀函数

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q, b, p;
    cin >> n >> q >> b >> p;

    vector<int> s(n + 1);
    for (int i = 1;i <= n;i++) cin >> s[i];

    ll z = 0;
    int mul = 1, ans = 0;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            ll x, c;
            cin >> x >> c;
            x = (x ^ z) % n + 1;
            c ^= z;
            s[x] = c;
        }
        else {
            int m;
            cin >> m;
            vector<int> t(m + 1);
            for (int i = 1;i <= m;i++) {
                ll val;
                cin >> val;
                t[i] = val ^ z;
            }
            mul = 1LL * mul * b % p;
            if (m < n) z = 0;
            else {
                KMP<vector<int>> kmp(s);
                z = 1LL * kmp.nxt[n] * kmp.find(t).size();
            }
            ans = (ans + z % p * mul % p) % p;
        }
    }
    cout << ans << '\n';
    return 0;
}

M

题解

知识点:数学。

枚举数字个数的范围即可。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve() {
    int n;
    cin >> n;
    ll base = 10, cnt = 1;
    ll ans = 0;
    while (base - 1 <= n) {
        ans += (base - base / 10) * cnt;
        base *= 10;
        cnt++;
    }
    base /= 10;
    ans += (n - base + 1) * cnt;
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

标签:tmp,CGILM,int,ll,pos,多校,牛客,vector,using
From: https://www.cnblogs.com/BlankYang/p/17627348.html

相关文章

  • 2023年多校联训NOIP层测试7+【LGR-149-Div.3】洛谷基础赛 #2 & qw Round -1
    2023年多校联训NOIP层测试7,集训欢乐赛,绝对欢乐,童叟无欺赛时在回家的路上+睡觉,所以没打。\(T1\)近似ybtOJ2049:【例5.19】字符串判等本题少了对空格的判断,水题。PS:题面和题解中都写了文件输入输出,测评时没有文件输入输出是几个意思,艹。#include<bits/stdc++.h>usingname......
  • 暑假牛客多校第八场 2023-8-11(H、K)
    H.Insert1,Insert2,Insert3,...算法:栈做法:   我们分析题目发现每个区间的左端点一定是\(1\),而且每个新加入的数\(x\)一定是匹配最靠近它的且未经匹配的\(x-1\)。举个例子,在[1,1,2,2,3]中我们加入一个数\(3\)时由于从左到右的第二个\(2\)是已经和第一个......
  • 牛客sql-计算用户的平均次日留存率
    参考大佬题解做一下记录:https://blog.nowcoder.net/n/fe24f96a26f1437da19e91ab1d035b03?f=commenthttps://blog.nowcoder.net/n/dd3d75ce08e3485c95bafe3c23668fc2?f=comment https://www.runoob.com/sql/sql-dates.htmlDATE_ADD(date,intervalexprtype) date参数是合......
  • 2023.08.08杭电多校第七场
    solved:3/13rank:B.RandomNimGame题意:两个人玩Nim游戏取石子,但是每次选择石子都是随机的,问最后先手获胜的概率;瞎写了几组样例算出来都是1/2,遂大胆猜想:除了每堆石子都只有一个时按石子堆数的奇偶判断先手获胜的概率是1还是0,其余情况先手获胜概率都是1/2;根据题解所说,可以用归纳......
  • 2023.08.10杭电多校第八场
    solved:3rank:C.Congruences题意:对于每组数据给定M个pi和qi,pi为两两不同的质数,N为所有pi的积,问是否存在最小的正整数x使得xpi在模N的意义下与qi同余可以推出xpi在模pi的意义下与qi同余在模N的意义下与qi同余,如果存在输出x,否则输出-1;显然xpi在模N的意义下与qi同余可以......
  • 2023牛客周赛 Round 6
    https://ac.nowcoder.com/acm/contest/62622/Cc题从x!作为切入点,阶乘增长的非常快,我们可以枚举x,从而达到固定x,只剩y一个变量,问题转变为一次函数绝对值求最小值的数学问题,显然可以o(1)。\[13!=6227020800=6.2270208×10^9\]\[12!=479001600=4.790016×10^8\]对于13的阶......
  • HDU 多校 Round #6 题解
    HDU多校Round#6题解\(\text{ByDaiRuiChen007}\)A.CountProblemLink题目大意求有多少个长度为\(n\),字符集大小为\(m\)的字符串有长度为\(n-k\)的周期。数据范围:\(n,m,k\le10^{18}\)。思路分析\(k=n\)时答案为\(m^n\),否则转为有长度为\(k\)的Border,答案......
  • 2023杭电多校(8)
    有点事结果鸽了两场牛客多校,杭电7懒得写题解了(1005不难发现无非分三种情况一种两边都是$1$,一种两边都是$0$,一种一$1$一$0$于是直接贪心,把所有连续段压成一份,对于最后一种情况很好解决,只有一个方向能走,直接走就好。对于前两种情况,显然如果先手两个1,取完还能构造一个两个1的情......
  • 2023牛客暑期多校训练营6 ABCEG
    比赛链接A题解方法一知识点:并查集,树形dp,背包dp。因为需要路径中的最大值,因此考虑按边权从小到大加入图中,保证通过这条边产生贡献的点对已经全部出现。在加边的同时进行树上背包,答案存在集合根节点里即可。树上背包需要用到上下界限制的转移优化,能将复杂度从\(O(n^3)\)降......
  • 2018牛客多校第五场 F take[树状数组]
    理解题目画了一个二叉树,然后思维定势让我想构建一个有n层的二叉树,然后统计叶子节点。。有点恐怖。但是正解是考虑每一个箱子对答案的贡献。图片来自take_baymax520的博客对于每个箱子,它要发生交换也就是为答案贡献的条件是它当前宝石大小小于它的大小。对于比它小的宝石之前取......