牛客小白月赛101 A~E

A-tb的区间问题

题意：tb 给了 fc 一个长度为 n 的数组 A, fc 对 A 进行 k 次如下操作：

删除数组第一个元素或者删除数组最后一个元素。

求最后得到的数组和的最大值。

思路：最后删除的是某一组前后缀，一一去枚举可行的区间即可。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

ll a[N],s[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,k; cin>>n>>k;
    for(int i = 1;i <= n; i++)
        cin>>a[i];
    for(int i = 1;i <= n; i++)
        s[i] = s[i-1] + a[i];
    int len = n-k;
    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        if(i-len+1 >= 1){
            ans = max(ans,s[i]-s[i-len]);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

B-tb的字符串问题

题意：tb 给了 fc 一个字符串。

fc 对字符串可以进行若干次 （可能是0） 次如下操作：

选择子串 ''fc'' 或者子串 ''tb'' ，将其从字符串中删去。

求最后剩下字符串的最短长度。

子串：原字符串中下标连续的一段字符串。

思路：能删我们肯定删呀，而且"fc"和"tb"也没有共同字母也没有干扰。我们可以用栈去维护，类似括号匹配那种。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    string s; cin>>s;
    s = "?" + s;
    stack<char>st;
    for(int i = 1;i <= n; i++)
    {
        
        if(st.size() > 0){
            char x = st.top();
            char now = s[i];

            if((x=='f'&&now=='c')||(x=='t'&&now=='b'))
                st.pop();
            else st.push(now);
        }else st.push(s[i]);      
    }

    cout<<st.size()<<"\n";



    return 0;
}

/*
12
tfffffcccccb
*/

C-tb的路径问题

题意：tb 给了 fc 一张有 \(n \times n\)个格点的图。 图上每个格点都写着一个数。第 \(i\) 行第\(j\)列的格点上写着的数字为 \(i\) 和 \(j\)的最大公约数。 现在 fc 需要从第 1行第 1 列出发，去往第 n 行第 n 列处的格点，fc 可以消耗一点能量移向相邻的格点。 在任何时，设 fc 所位于的格点上所写的数字为 x ，如果 x 不为 1 ，他可以使用传送阵传送到任何数字为 x 的格点，此操作不消耗能量。求 fc 到达第 n行第 n列所消耗的最少能量。

相邻：如果用 (x,y) 表示第 x行第 y 列的位置，(x,y) 与 (x+1,y),(x,y+1),(x−1,y),(x,y−1)(x+1,y) 相邻。

思路：我们发现对角线的数字都是每个数字第一次出现的位置，就算要瞬移也要先到这里。那么我们考虑枚举先到哪个数字，然后瞬移到距离(n,n)最近的地方，再一步步走即可。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    ll ans = (n-1)*2;
    for(int i = 2;i <= n; i++)
    {
        int x = i,y = i;
        x = n/i*i;
        y = (x-1)/i*i;

        ll t = (i-1)*2;
        if(y > 0)
            t += (n-x)+(n-y);
        else t += (n-i)*2;

        ans = min(ans,t);

        // cout<<"x = "<<x<<" y = "<<y<<" t = "<<t<<"\n";
    }

    cout<<ans<<"\n";


    return 0;
}

D-tb的平方问题

题意：tb 给了 fc 一个数组 A 。
随后， tb 对 fc 进行了 q 次询问，每次询问 tb 给 fc 一个 x，需要 fc 给出包含了 x 位置且区间和为完全平方数的连续子数组个数。
完全平方数：存在正整数 t ，满足\(t \times t = x\) ，则称 x 为完全平方数
连续子数组：原数组中某段下标连续的元素按原顺序构成的数组。

思路：可以先求个前缀和，然后枚举区间，如果是完全平方数那么这段区间的贡献加1。对于区间加很容易想到差分。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3100;

int s[N],d[N],a[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int n,q; 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 l = i,r = j;
            int t = s[r]-s[l-1];
            int tt = sqrt(t);
            if(tt*tt == t)
                d[l]+=1,d[r+1]-=1;
        }
    }

    for(int i = 1;i <= n;i++)
        d[i]+=d[i-1];
    while(q--)
    {
        int x; cin>>x;
        cout<<d[x]<<"\n";
    }

    return 0;
}

E-tb的数数问题（调和级数）

题意：tb 给了 fc 一个包含若干个数字的可重集合 A ，如果我们说一个数字 x 是好的当且仅当 \(\forall \ d | x\) ，有 \(d \in A\)。

现在，fc 想知道有多少个不同的正整数是好的，请你告诉他吧。

d∣x : 表示 d 为 x 的约数。

\(\forall \ d | x\) ，有 \(d \in A\) ： x 的任何约数都至少在 A 中出现一次。

思路：最后的好数一定是A里面的数(因为至少包含数本身)。g[x]=1表示x存在。我们正常的求f[x]的约数有几个，h[x]是在A里面的x的约数个数。如果f[x]==h[x]则说明都在了。这里是调和级数的复杂度\(O(n\log{n})\)（类似于 Eratosthenes 筛的思路）。

int d[1000001] = {0}; // 储存因数倍数，初始全为 0
for (int i = 1; i <= n; i++) // 枚举 [1, n] 的数
{
    for (int j = i; j <= n; j += i) // 枚举 i 的倍数
    {
        d[j]++;
    }
}

代码：

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;

ll a[N],f[N],g[N],h[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    int n; cin>>n;
    ll mx = 0;
    for(int i = 1;i <= n; i++)
    {
        cin>>a[i];
        mx = max(mx,a[i]);
        g[a[i]] = 1;
    }


    for(int i = 1;i <= mx; i++)
    {
        for(int j = i;j <= mx; j += i){
            f[j]++;
            h[j] += g[i];
        }
    }
    ll ans = 0;
    for(int i = 1;i <= mx; i++)
        ans += (f[i] == h[i]);

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