A-小红小紫替换

思路：

  • 简单，跳过

以下是代码部分

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

string s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    cout << (s == "kou" ? "yukari" : s) << endl;

    return 0;
}

B-小红的因子数

思路：

  • 为减少时间复杂度，可用 i <= sqrt(x), 也就是 i * i <= x

以下是代码部分

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

int main()
{
    int ans = 0;
    ll x;
    cin >> x;
  //每次都会筛去某个基本质因子，使得i必须是质数才可成立
    for (ll i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            ans++;
        }
    }
    cout << ans + (x != 1);
    return 0;
}

C- 小红的字符串中值

思路：

  • 问的是以ch为中心的子串有多少
  • 所以只需要知道以ch为中心的子串的最大范围为多少
  • 刚好可以用字符串的下标算出表示

以下是代码部分

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

string s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll sum = 0;
    char chr;
    cin >> n >> chr >> s;
    s = '$' + s;
    for(int i = 1; i <= n; i ++)
        if(s[i] == chr)
          //该字符串里左边近还是右边近，取最小的即可
          //每次得到的ch取值都加起来
            sum += min(i, n - i + 1);
    cout << sum << endl;

    return 0;
}

D-小红数组操作

思路：

  • 双链表问题
  • 用map构造出一个双链表

以下是代码部分，代码参考于——出题人视频讲解

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

map<int, int> l, r;//l[i]代表元素i的左节点 r[i]代表元素i的右节点

int main()
{
    ios::sync_with_stdio(false);
    int q;
    int be = -1e9 - 1, en = 1e9 + 1;
    //初始时
    //头节点的右边是尾节点
    r[be] = en;
    //尾节点的左边是头节点
    l[en] = be;
    cin >> q;
    while(q --)
    {
        int op;
        cin >> op;
        if(op == 1)//插入操作
        {
            int x, y;
            cin >> x >> y;
            int ll, rr;
            //插入到第一个位置
            if(y == 0)
                ll = be, rr = r[be];
            else
                ll = y, rr = r[y];
            //节点ll的右边更改为x
            r[ll] = x;
            //节点x的左边是头及结点
            l[x] = ll;
            //节点x的右边是原本的第一个节点
            r[x] = rr;
            //原本y右边的节点的左边更改为x
            l[rr] = x;
        }
        else//删除操作
        {
            int x;
            cin >> x;
          //ll为节点x左边的节点，rr为节点x右边的节点
            int ll = l[x], rr = r[x];
          //ll右边的节点为r
            r[ll] = rr;
          //rr左边的节点为ll
            l[rr] = ll;
        }
    }
    vector<int>out;
  //遍历存入数组中
    for(int i = r[be]; i != en; i = r[i])
        out.push_back(i);
  //输出
    cout << out.size() << '\n';
    for(auto x : out)
        cout << x << ' ';

    return 0;
}

E-小红的子集取反

思路：

  • o1背包问题的变式
    • , 代表第几个元素
    • 代表前i个元素的和为
    • 值代表取反的元素数

以下是代码部分， 代码参考来源——出题人视频讲解

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

int dp[210][80100];

int main()
{
    ios::sync_with_stdio(false);
    int n, x;
    cin >> n;
  //赋值，作为正无穷
    memset(dp, 0x3f, sizeof dp);
  //因为最大为40000， 最小为-40000
    dp[0][40000] = 0;
    for(int i = 1; i <= n; i ++)
    {
        cin >> x;
        for(int j = 0; j <= 80000; j ++)
        {
          //当不取反，且合法时
            if(j + x >= 0 && j + x <= 80000)
              //状态转移，比较这两种状态哪一种需要的少
                dp[i][j] = min(dp[i][j], dp[i - 1][j + x]);
          //当取反，且合法时
            if(j - x >= 0 && j - x <= 80000)
              //状态转移，比较这两种状态，哪一种需要的少
                dp[i][j] = min(dp[i][j], dp[i - 1][j - x] + 1);
        }
    }
  //如果dp[n][4000]不是有dp[0][40000]状态转移过来的，那么，他的值一定大于n
  //所以当小于n时，合法，否则，不合法
    if(dp[n][40000] < n)
        cout << dp[n][40000] << endl;
    else
        cout << -1 << endl;
    return 0;
}

F-小红的连续段

知识点：

  • 快速幂，乘法逆元，组合数，隔板法

思路:

  • 隔板法
    • 当把y个b插入到x个a中，成为5个连续段，有几种方法
      • 相当于把y个b插入到x-1个间隙中，有 2个位置 C(x-1, 5 / 2 + 5 % 2) * C(y - 1, 5 / 2);
    • 当把y个b插入到x个a中，成为4个连续段，有几种方法
      • 相当于把y个b插入到x-1个间隙中，有 2个位置 C(x-1, 4 / 2 + 5 % 2) * C(y - 1, 4 / 2); 所以需分奇偶讨论。 并且有把b插入打a当中，也有把a插入到b当中，也许考虑

以下时代码部分， 代码参考来源——出题人视频讲解

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

typedef long long ll;

ll fac[2010], invfac[2010];
const int mod = 1e9 + 7;
//快速幂
ll quick(ll base, int pow)
{
    ll res = 1;
    while(pow)
    {
        if(pow & 1)
            res = base * res % mod;
        pow >>= 1;
        base = base * base % mod;
    }
    return res;
}
//费马小定理求逆元
ll inv(ll x)
{
    return quick(x, mod - 2);
}
//求组合数
ll C(int n, int m)
{
    if(m < 0 || n - m < 0) return 0;
    return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
//预处理阶乘和逆元
void init(int n)
{
    fac[0] = 1;
    for(int i = 1; i <= n; i ++)
        fac[i] = fac[i - 1] * i % mod;
    invfac[n] = inv(fac[n]);
    for(int i = n - 1; i >= 0; i --)
        invfac[i] = invfac[i + 1] * (i + 1) % mod;
}

int main()
{
    ios::sync_with_stdio(false);
    int x, y;
    cin >> x >> y;
    init(x + y);
  
    for(int i = 1; i <= x + y; i ++)
    {
      //当要求连续段为奇数的时候    当要求连续段为偶数的时候
        int ji = i / 2 + (i & 1), ou = i / 2;
      //间隙为x-1, 共可以插入ji - 1个空 ……
        cout << (C(x - 1, ji - 1) * C(y - 1, ou - 1) % mod + C(y - 1, ji - 1) * C(x - 1, ou - 1) % mod) % mod << endl;
    }
    
    return 0;
}