首页 > 其他分享 >牛客小白月赛101

牛客小白月赛101

时间：2024-09-20 22:49:58浏览次数：3  
标签：return constexpr int rhs cin 牛客 小白月赛 101 MInt

比赛链接

https://ac.nowcoder.com/acm/contest/90072

A题 tb的区间问题

思路

实际上是求长度为 n − k n-k n−k的区间的和的最大值。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, k;
int a[N], sum[N];
void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int ans = 0;
    int len = n - k;
    for (int i = 1; i + len - 1 <= n; i++)
    {
        int j = i + len - 1;
        ans = max(ans, sum[j] - sum[i - 1]);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
    }
    return 0;
}

B题 tb的字符串问题

思路

用栈从前往后模拟，类似于括号匹配。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
string s;
void solve()
{
    cin >> n >> s;
    stack<char> st;
    for (int i = 0; i < n; i++)
    {
        if (st.empty())
        {
            st.push(s[i]);
        }
        else
        {
            if ((s[i] == 'c' && st.top() == 'f') || (s[i] == 'b' && st.top() == 't'))
            {
                st.pop();
            }
            else
                st.push(s[i]);
        }
    }
    cout << st.size() << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
    }
    return 0;
}

C题 tb的路径问题

思路

打表观察样例即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
void solve()
{
    cin >> n;
    if (n == 1)
    {
        cout << 0 << endl;
        return;
    }
    if (n == 2)
    {
        cout << n << endl;
        return;
    }
    if (n == 3)
    {
        cout << 4 << endl;
        return;
    }
    if (n % 2 == 0)
    {
        cout << 4 << endl;
    }
    else
        cout << 6 << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
    }
    return 0;
}

D题 tb的平方问题

思路

n n n最大为 1 e 3 1e3 1e3，因此我们可以先用前缀和进行预处理，之后暴力枚举每一个连续子数组，对于和为完全平方数的连续子数组，我们对整个区间的个数加 1 1 1。

因此，本题便转化为了区间加减的问题，可以使用树状数组进行求解。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 5;
int n, q;
int a[N], s[N];
struct BIT
{
    const static int maxnum = 1e3 + 10;
    int tree[maxnum];
    int lowbit(int x)
    {
        return (x) & (-x);
    }
    void add(int idx, int x)
    {
        for (int pos = idx; pos < maxnum; pos += lowbit(pos))
        {
            tree[pos] += x;
        }
    }
    int query(int n)
    {
        int ans = 0;
        for (int pos = n; pos; pos -= lowbit(pos))
        {
            ans += tree[pos];
        }
        return ans;
    }
    int query(int a, int b)
    {
        return query(b) - query(a - 1);
    }
    void init(int n)
    {
        for (int i = 0; i <= n + 2; i++)
            tree[i] = 0;
    }
} tree;
bool check(int x)
{
    int op = sqrt(x);
    if (op * op == x)
        return true;
    return false;
}
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            int sum = s[j] - s[i - 1];
            if (check(sum))
            {
                tree.add(i, 1);
                tree.add(j + 1, -1);
            }
        }
    }
    while (q--)
    {
        int x;
        cin >> x;
        cout << tree.query(x) << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
    }
    return 0;
}

E题 tb的数数问题

思路

找每个没有出现的数，他的倍数都是false的，其余的都是true。

时间复杂度为调和级数。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n;
int a[N];
bool st[N];
void solve()
{
    cin >> n;
    map<int, int> mp;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        mp[a[i]]++;
    }
    int ans = 0, high = *max_element(a + 1, a + 1 + n);
    for (int i = 1; i <= high; i++)
    {
        if (mp.count(i) && !st[i])
        {
            ans++;
        }
        else
        {
            for (int j = i; j <= high; j += i)
            {
                st[j] = true;
            }
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
    }
    return 0;
}

F题 tb的排列问题

思路

对于任意一个 b i b_{i} bi​，当且仅当 p o s [ b i ] > i + w pos[b_{i}] > i + w pos[bi​]>i+w时无解。

如果 b i b_{i} bi​没有在数组 a a a中出现过，那么 b i b_{i} bi​可以出现在 ≤ i + w \le i + w ≤i+w的任何地方。因此我们可以使用类似于前缀和的方式， c n t [ i ] cnt[i] cnt[i]表示有多少个数字可以放到 i i i上，又因为前面已经假设放了 p r e pre pre个数字，那么当前位置就有 p r e pre pre个数字不能放了，所以答案与 c n t [ i ] − p r e cnt[i]-pre cnt[i]−pre相乘。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long i64;
const int N = 2e5 + 5;
template <int P>
struct MInt
{
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}

    static int Mod;
    constexpr static int getMod()
    {
        if (P > 0)
        {
            return P;
        }
        else
        {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_)
    {
        Mod = Mod_;
    }
    constexpr int norm(int x) const
    {
        if (x < 0)
        {
            x += getMod();
        }
        if (x >= getMod())
        {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const
    {
        return x;
    }
    explicit constexpr operator int() const
    {
        return x;
    }
    constexpr MInt operator-() const
    {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const
    {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) &
    {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) &
    {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) &
    {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) &
    {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a)
    {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a)
    {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs)
    {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs)
    {
        return lhs.val() != rhs.val();
    }
};

template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;
int n, w;
int a[N], b[N];
void solve()
{
    cin >> n >> w;
    vector<int> pos(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] != -1)
        {
            pos[a[i]] = i;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    vector<int> cnt(n + 1);
    for (int i = n; i >= 1; i--)
    {
        int high = min(n, i + w);
        if (pos[b[i]] && pos[b[i]] > high)
        {
            cout << 0 << endl;
            return;
        }
        if (!pos[b[i]])
            cnt[high]++;
    }

    Z ans = 1;
    int pre = 0;
    for (int i = n; i >= 1; i--)
    {
        cnt[i - 1] += cnt[i];
        if (a[i] != -1)
            continue;
        ans *= (cnt[i] - pre);
        pre++;
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
    }
    return 0;
}

标签：return,constexpr,int,rhs,cin,牛客,小白月赛,101,MInt
From： https://blog.csdn.net/weixin_74754298/article/details/142406939

相关文章

  • 牛客小白月赛101
    总结:无A.tb的区间问题题意:对一个数组进行k次删除操作,对于操作删除只能删除最左元素或者最右元素,求出k次操作后数组和的最大值思路:由于删除最左元素和最右元素那么必然最后得到的数组和是一个连续的区间,那么删除k也就是剩余n-k的空间,通过前缀和预处理得到每一......
  • 2024牛客多校 4 （概率，带权并查集，构造）
    2024牛客多校4（概率，带权并查集，构造）J-Zero题面：给出整数\(n\)和\(k\)，一个01?字符串\(s\)。?有概率是0或是1，且概率相等，一段区间\([l,r]\)的贡献这样计算：这一段区间不包含0贡献为长度的\(k\)次方求这个字符串\(s\)的期望贡献是多少？solution：首......
  • 互连产品，10151114-001RLF PCIe MXM 3.0 连接器，10157096-01221LF 针座连接器（参数）
    10151114-001RLF——PCIeMXM3.0连接器，存储和服务器连接器，直角，表面贴装，P=0.5mm，堆叠高度=5.0mm，30μin镀金概述：MXM连接器是一种高密度PCIe®解决方案，支持新一代服务器系统架构。这是一个非专有的行业标准插座产品系列。可用于升级设备中的图形处理器，而无需更改整个系统或依赖专......
  • 牛客周赛60
    A困难数学题一个数异或其本身就是0，直接输出0就好B构造序列正负数要相邻，那最长的序列肯定是数量最多的数放第一个，例3a2b,ababa,ba为一组，最后结果为少的数的两倍+最开始的那个数，特判两数相等情况点击查看代码lla,b;cin>>a>>b;if(a<b){......
  • 洛谷P1016
    题目传送门：传送门p1016题目描述一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 D1D1​、汽车油箱的容量 CC（以升为单位）、每升汽油能行驶的距离 D2D2​、出发点每升汽油价格PP和沿途油站数 NN（NN 可以为零），油站 ii......
  • 【PAT_Python解】1014 福尔摩斯的约会
    原题链接：PTA|程序设计类实验辅助教学平台Tips：以下Python代码仅个人理解，非最优算法，仅供参考！ls=[]#装输入数据，你也可以S1,S2,S3,S4=input(),···D,H,M='','',''dict={'A':'MON','B':'TUE','C':'WED','D�......
  • PMP--一模--解题--101-110
    文章目录11.风险管理--过程--识别风险→实施定性风险分析→实施定量风险分析→规划风险应对→实施风险应对→监督风险101、[单选]在项目即将进入收尾阶段时，项目经理发现了一项原来没有考虑到的新风险。该风险一旦发生，可能给最终的可交付成果带来重要影响，甚至可能使其不......
  • 视野修炼-技术周刊第101期 | 垂直居中
    欢迎来到第101期的【视野修炼-技术周刊】，下面是本期的精选内容简介......
  • 牛客多校2024-8
    K-HaitangandAva怎么还有人签到题wa啊/kk定义以下的字符串是合法的：空字符串若\(S\)是合法的，那么\(S\)+ava和ava+\(S\)都是合法的若\(S\)是合法的，那么\(S\)+avava和avava+\(S\)都是合法的给定一个字符串，判断是否合法。以v为分隔计数a，容易发现计数数组中除了开头和末......
  • 每日OJ_牛客_点击消除（栈）
    目录牛客_点击消除（栈）解析代码牛客_点击消除（栈）点击消除_牛客题霸_牛客网描述：牛牛拿到了一个字符串。他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。但相同而不相邻、不相同的相邻字母都是不可以被消除的。牛牛想把字符串变......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99