牛客小白月赛101题解 | A~E（F不会哈哈哈）

好久没有参加过比赛了，交题都是过了样例就交，导致白白吃了不少罚时，反思。

A:tb的区间问题

分析

要求必须从头和尾处总共删 个数，数据只有 可以用 的暴力做法做出。这里写一个 的做法。

前缀和预处理， 表示区间 的区间和。

然后可以从 到 枚举从头部删除的数有多少，由此可知道从尾部删除的数有多少。

通过前缀和数组可以 的得出当前方案的数组和，维护最大值即可。

代码

const int N = 2e5 + 50, mod = 998244353, MOD = 1e9 + 7, base = 13331;
 
int a[N], sum[N];
 
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int mx = 0;
    for (int i = 0; i <= m; i++)
    {
        mx = max(mx, sum[n - (m - i)] - sum[i]);
    }
    cout << mx;
}

B:tb的字符串问题

分析

我们删除了 和 ，后面的字符拼接上来后只有两种情况：

1. 上来的字符能和前一个字符组合成为新的 或 ，此时我们的答案可以增加1
2. 上来的字符不能和前一个字符组合成为目标字符串，对答案没有影响

所以可以看出对于原先字符串中的目标字串我们应该能删就删。

遍历字符串的时候我们可以用栈来模拟删除目标字串和删除后下个字符凑上来的情况，这也是栈的一个经典用法。

代码

void solve()
{
    int n;
    string s, t = " ";
    cin >> n >> s;
    for (auto& i : s)
    {
        if (i == 'b' && t.back() == 't')t.pop_back();
        else if (i == 'c' && t.back() == 'f')t.pop_back();
        else t += i;
    }
    cout << t.size() - 1;
}

C:tb的路径问题

分析

首先看完问题一看范围 最大到了 就可以知道这不是寻常的搜索或递推可以找出来的，这范围连矩阵都存不下来。 那就可以先打个表做个小范围的矩阵来找规律，打印一个 的矩阵可以发现：

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
1 1 3 1 1 3 1 1 3 1 1 3 1 1 3
1 2 1 4 1 2 1 4 1 2 1 4 1 2 1
1 1 1 1 5 1 1 1 1 5 1 1 1 1 5
1 2 3 2 1 6 1 2 3 2 1 6 1 2 3
1 1 1 1 1 1 7 1 1 1 1 1 1 7 1
1 2 1 4 1 2 1 8 1 2 1 4 1 2 1
1 1 3 1 1 3 1 1 9 1 1 3 1 1 3
1 2 1 2 5 2 1 2 1 10 1 2 1 2 5
1 1 1 1 1 1 1 1 1 1 11 1 1 1 1
1 2 3 4 1 6 1 4 3 2 1 12 1 2 3
1 1 1 1 1 1 1 1 1 1 1 1 13 1 1
1 2 1 2 1 2 7 2 1 2 1 2 1 14 1
1 1 3 1 5 3 1 1 3 5 1 3 1 1 15

1. 如果 为偶数，则它向左或向上走两部就可以发现一个 ，那我们只要从 开始用两步走到最近的 ，然后瞬移到离 最近的 ，再走两步就可以到达 ，答案为 .

2. 如果 为奇数，离他最近的数可以有 或 ，其中最近的 到 距离为 ，最近的 到 距离为 ，但是如果我们想从 出发走到 ，最快也要走三步（走到后转移到一个的头上，再走一步到）。可以看出不管是从最近 还是 走到 ，所用的步数都是 .

3. 特别的，如果 时答案为 ； 时答案为 ； 时答案为 . 对输入的 进行特判即可。

代码

void solve()
{
    int n;
    cin >> n;
    if (n == 1)cout << 0 << endl;
    else if (n == 2)cout << 2 << endl;
    else if (n == 3)cout << 4 << endl;
    else if (n % 2 == 0)cout << 4 << endl;
    else cout << 6 << endl;
}

D:tb的平方问题

分析

暴力做法 （过不了） （卧槽能过）

首先 的值都为正整数，那就说明以 为左端点的区间和为 的区间只会有一个。（即不会出现多个左端点相同、区间和也相同的情况） 先用前缀和进行预处理，同时记录下所有 的出现情况。 用一个数组 记录下来每个点被多少个符合要求的区间覆盖。 然后枚举所有的左端点 ，对于每个左端点，再枚举出所有可能的完全平方数，查看是否有符合要求的区间右端点 。 如果有，我们在 中给区间 的所有数都加上1。 对于每次询问，输出 即可。

(说实话我真没想到这个方法能过，写题解的时候感觉可以试试没想到就过了。。）

暴力代码

int f[N];

void solve()
{
    int n, m;
    cin >> n >> m;
    unordered_map<int, int>mymap;
    for (int i = 1; i <= n; i++)
    {
        ans[i] = -1;
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        mymap[sum[i]] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 1e4 && sum[i - 1] + j * j <= sum[n]; j++)
        {
            int x = sum[i - 1] + j * j;
            if (mymap.count(x))
            {
                for(int k=i;k<=mymap[x];k++)
                    f[k]++;
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        cout << f[x] << endl;
    }
}

线段树优化（本人赛时做法）

因为想着对于每个合法区间都手动 跑一遍加答案太慢，对于这个区间加的操作用线段树去实现，最后单点查询每个点的答案。

线段树代码

int a[N], sum[N], f[N], lz[N];

void pushdown(int k)
{
    if (lz[k])
    {
        lz[k + k] += lz[k];
        f[k + k] += lz[k];
        lz[k + k + 1] += lz[k];
        f[k + k + 1] += lz[k];
        lz[k]=0;
    }
}

void revise(int k, int l, int r, int x, int y)
{
    if (l == x && r == y)
    {
        lz[k]++;
        f[k]++;
        return;
    }
    pushdown(k);
    int mid = (l + r) / 2;
    if (y <= mid)revise(k + k, l, mid, x, y);
    else if (x > mid)revise(k + k + 1, mid + 1, r, x, y);
    else
    {
        revise(k + k, l, mid, x, mid);
        revise(k + k + 1, mid + 1, r, mid + 1, y);
    }
}

int query(int k, int l, int r, int x)
{
    if (l == r)return f[k];
    pushdown(k);
    int mid = (l + r) / 2;
    if (x <= mid)return query(k + k, l, mid, x);
    else return query(k + k + 1, mid + 1, r, x);
}

int ans[N];

void solve()
{
    int n, m;
    cin >> n >> m;
    unordered_map<int, int>mymap;
    for (int i = 1; i <= n; i++)
    {
        ans[i] = -1;
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        mymap[sum[i]] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 1e4 && sum[i - 1] + j * j <= sum[n]; j++)
        {
            int x = sum[i - 1] + j * j;
            if (mymap.count(x))
            {
                revise(1, 1, n, i, mymap[x]);
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        //q最大有3e5，而n只有1e3，必有重复询问的情况，直接把答案都记下来省的下次再找一遍
        if (ans[x] != -1)cout << ans[x] << endl;
        else
        {
            ans[x] = query(1, 1, n, x);
            cout << ans[x] << endl;
        }
    }
}

E:tb的数数问题

分析

一开始没有啥思路，连暴力都想不出来，因为感觉只要取极限情况 ：集合 中存 ，可以整出很大的好数来。还以为是什么组合数的高深题。

后来手玩几个测试例的时候发现一个数它本身也是自己的约数啊！ （太傻了，太久没写题给脑子整坏了）

那就有这么个结论：

一个数如果是好数就必须在集合 内。

对于第一个结论，很容易想到暴力做法，对集合 中的所有数用试除法求约数，只要有一个约数不在集合 内就不是好数。

复杂度：。

很明显要寄。

正难则反，我们想想不是通过枚举约数一步步向着答案收敛，而是通过已经非法的数向其它答案扩散呢？

就比如如果 不是好数中，那通过 扩散出去，所有以 为约数的数也都是有问题的。

这就是一个类似线性筛的情况了，线性筛质数的时候我们就是通过一个质数不断的去排除其他的非质数。

具体细节看代码注释。

代码

//st[i]表示数字i是不是一个好数
int st[N];

void solve()
{
    int n, x, mx = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        //出现在A集合内的我们都暂且认为它是好数
        st[x] = 1;
        //维护最大值，因为大于mx的数显然不是好数，减少我们筛选的范围
        mx = max(mx, x);
    }
    
	//小小的特判一手
    if (!st[1])
    {
        cout << 0 << endl;
        return;
    }
	//初始为1，因为先把1的答案记在里面
    int cnt = 1;
    //直接从2开始就好
    for (int i = 2; i <= mx; i++)
    {
    	//如果枚举到他了，它仍然是好数，就说明它真的是好数
        if (st[i])cnt++;
        else
        {
        	//不是好数，我们通过它去扩展到其他数上
            for (int j = 1; j * i <= mx; j++)
            {
            	//凡是以i为约数的都不是好数，哪怕它之前是
                st[i * j] = 0;
            }
        }
    }
    cout << cnt << endl;
}