题解 | #2023周赛Round26#

A-小红的整数操作

这题似乎测试数据没有题目看起来的大

对取模的简单考察：

每个数在取模K后的余数相同，那么通过n次加K后，必定可以相同。

通过X = k * n1 + b-----------Y = k * n2 + b容易得出;

#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10, M = 2e1 + 8;
const int mod = 10;

int a[N];

int main()
{
    int n, k, maxn = 0, ans = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        a[i] %= k;//取模操作
    }
    sort(a, a + n);
  //统计相同的模的元素数最大值
    for(int i = 0;  i < n - 1; i ++)
    {
        if(a[i] == a[i + 1]) ans ++;
        else ans = 0;
        maxn = max(maxn, ans);
    }
    cout << maxn + 1<< endl;

    return 0;
}

B-小红的01串

在遇到相邻两个不是同一个字符的区段。
可以看作2个‘0’与‘1’交换，相当于冒泡排序，先把‘0’和‘1’放到一起。
之后发现在‘0’或者‘1’只要有一个是偶数时
就可以把是偶数个数的‘1’串转化成全是‘0’串或者把是偶数的‘1’串全部转化成‘0’串

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

string s;

int main()
{
    int q, a[2];
    cin >> q;
    while(q --)
    {
        a[0] = a[1] = 0;//用于统计‘0’ or '1'的个数
        cin >> s;
        for(int i = 0; i < s.length(); i ++)
            a[s[i] - '0'] ++;//计数
        if(a[0] % 2 == 0 || a[1] % 2 == 0)
            cout << "Yes" << endl;
        else
          cout << "No" << endl;    
    }

    return 0;
}

C-小红闯沼泽地

题目注意:

小红只能向左，向下，向右走。进入不同的地形花费时间为 2。

做题思路：动态规划

除边界外方格可有三种状态得来向左的状态转移过来，向下的状态转移过来，向右的状态转移过来

我就是没有考虑到向左走

alt

#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 2e3 + 10, M = 2e1 + 8;
const int mod = 10;
// setw(n) setfill('0') ## Add leading '0'
//===================================================
int n,m;
bool mp[N][N];//储存平地，沼泽地图
int dp[N][N];//动态规划所用
//===================================================

//===================================================
int main()
{
    ios;
    cin >> n >> m;
    for(int i = 1; i <= n ; i ++)
        for(int j = 1; j <= m; j++)
            cin >> mp[i][j];//输入
  //两者均可预处理数组
    fill(dp[0], dp[0] + N*N, 1e5);
    // memset(f, 0x7f, sizeof(f));
    dp[1][1] = 0;
    for(int i = 1; i <= n; i ++)
    {
      //向下，向右的状态转移
        for(int j = 1; j <= m; j ++)
        {
          //向下的状态转移
            if(mp[i][j] == mp[i - 1][j])//地形相同
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
            else//地形不同
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 2);
          //向右的状态转移
            if(mp[i][j] == mp[i][j - 1])//地形相同
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
            else//地形不同
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 2);
        }
        for(int j = m; j >= 1; j --)
        {
          //向左的状态转移
            if(mp[i][j] == mp[i][j + 1])//地形相同
                dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
            else//地形不同
                dp[i][j] = min(dp[i][j], dp[i][j + 1] + 2);
        }
    }
    cout << dp[n][m] << endl;//输出

    return 0;
}

参考代码----牛客：Xhesica_Frost，逍遥人。

D-小红的漂亮串（二）

思路

根据正难则反的原则，反向考虑。漂亮串的总数 = 总的方案数-没有red的方案数-只有一个red的方案数。

依旧dp(动态规划)

1. 没有red的方案数

dp[i][1]：长度为i，以“r”结尾的方案数
dp[i][2]：长度为i，以“e”结尾的方案数
dp[i][0]：长度为i，以“d”结尾的方案数
dp[i][0]：长度为i，以其他字母结尾的方案数
没有red的方案数为 = dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3]

可以得到状态转移公式 alt

2. 只有一个red的方案

可以由没有red的方案数得出
确定red的位置，前后的方案数相乘，再枚举出red可能的每一个位置，将得出的乘积相加

3.总的方案数

总的方案数 = $2^n$

具体请看代码部分

#include <bits/stdc++.h>
using namespace std;
#define LF(x) fixed<<setprecision(x)
#define ios ios::sync_with_stdio(false)
#define endl '\n'
typedef long long ll;
const int N = 1e6 + 10, M = 2e1 + 8;
const int mod = 1e9 + 7;
// setw(n) setfill('0') ## Add leading '0'
//===================================================
ll dp[N][4];
//===================================================
void init(int n)
{
    dp[1][0] = 23;
    dp[1][1] = dp[1][2] = dp[1][3] = 1;
    dp[2][1] = 26;
    for(int i = 2; i <= n; i ++)
    {
        ll temp = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod;
        dp[i][0] = 23 * temp % mod;
        dp[i][1] = temp;
        dp[i][2] = temp;
        dp[i][3] = ((temp - dp[i - 2][1]) % mod + mod) % mod;
    }
}
//快速幂,这题也可直接循环求出26^n,不会TLE
ll quick_pow(ll base, ll power)
{
    ll result = 1;
    while(power > 0)
    {
        if (power & 1)
            result = result * base % mod;
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}
//===================================================
int main()
{
    int n;
    ll ans, left, right;
    ios;
    cin >> n;
    ans = quick_pow(26, n);//通过快速幂求得总方案数
    init(n);//状态转移，预处理
    //先减去没有red的情况
    ans = (ans - (dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3]) % mod + mod) % mod;
    //枚举只有一个res时的每个位置的方案数，并减去
    for(int i = 1; i <= n - 2; i ++)
    {
        left = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod;
        //防止前面的方案数为0的情况导致乘积为0
        left = max(left, 1ll);
        right = dp[n - i - 2][0] + dp[n - i - 2][1] + dp[n - i - 2][2] + dp[n - i - 2][3];
        //防止后面的方案数为0的情况导致乘积为0
        right = max(right, 1ll);
        //防止成为负号
        ans = (ans - left * right % mod + mod) % mod;
    }

    cout << ans << endl;

    return 0;
}

牛客周赛题解便于查看文章被收录于专栏

方便本人自己查看复习知识点。