题解 | #牛客周赛 Round 32#

A-小红的 01 背包

思路：

跳过

以下是代码部分

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

int main()
{
    int v, x, y;
    cin >> v >> x >> y;
    cout << v / x * y << endl;

    return 0;
}

B-小红的 dfs

思路：

总共三种情况
枚举即可

以下是代码部分

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

string s[3];

int min_modify()
{
    string target = "dfs";
    int min_changes = INT_MAX;
    int cnt = 0;
    for(int i = 0; i < 3; i ++)
    {
        if(s[i][0] != target[i])
            cnt ++;
        if(s[0][i] != target[i] && i != 0)
            cnt ++;
    }
    min_changes = min(cnt, min_changes);
    cnt = 0;
    for(int i = 0; i < 3; i ++)
    {
        if(s[i][1] != target[i])
            cnt ++;
        if(s[1][i] != target[i] && i != 1)
            cnt ++;
    }
    min_changes = min(cnt, min_changes);
    cnt = 0;
    for(int i = 0; i < 3; i ++)
    {
        if(s[i][2] != target[i])
            cnt ++;
        if(s[2][i] != target[i] && i != 2)
            cnt ++;
    }
    min_changes = min(cnt, min_changes);
    return min_changes;
}

int main()
{
    for (int i = 0; i < 3; i++) cin >> s[i];

    int result = min_modify();
    cout << result << endl;
    return 0;
}

C-小红的排列生成

思路：

先从小到大排序，累加差值即可
要达到全排列，只需要做到最小值匹配全排列的最小值，第二小值匹配全排列第二小值，以此类推即可

以下是代码部分

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

typedef long long ll;
const int N = 1e5 + 10;
int a[N];

int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    ll ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(a[i] != i)
            ans += abs(a[i] - i);
    }
    cout << ans << '\n';
    
    return 0;
}

D-小红的二进制树

题目大意：

这里翻车了，看了半天不知道啥意思
$i$ 节点的子树，不包括 $i$ 节点本身，所有的奇数组合。

思路：

树形 $dp$

以下是代码部分

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

const int N = 1e5 + 10;
vector<int> mp[N];
int dp[N];
string s;
//dfs深搜
void dfs(int u, int father)
{
  //赋初值
    dp[u] = (s[u] == '1');
    for(int x : mp[u])
    {
        if(x == father) continue;
        dfs(x, u);
      //每次记得相加，传递状态
        dp[u] += dp[x];
    }
}

int main()
{
    int n;
    cin >> n >> s;
  //保持下标一致
    s = '$' + s;
  //建立邻接表
    for(int i = 1, a, b; i < n; i ++)
    {
        cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
  //深搜
    dfs(1, -1);
  //遍历输出
    for(int i = 1; i <= n; i ++)
        cout << (dp[i] - s[i] + '0') << '\n';

    return 0;
}

E-小红的回文数

思路：

通过类似于前缀和的方式，判断该段区间是否合法

以下是代码部分，代码参考来源——官方视频题解

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

typedef long long ll;
string s;
map<vector<int>, int> m;
vector<int> temp(10);

int main()
{
    ios::sync_with_stdio(false);
    cin >> s;
    int len = (int)s.length();
    m[temp] ++;
    ll sum = 0;
    for(int i = 0; i < len; i ++)
    {
        temp[s[i] - '0'] ^= 1;//此数字多出现一次时，偶数变奇数，奇数变偶数
        //若出现的数字次数均为偶数时
        sum += m[temp];// 若此种奇偶情况之前出现过，则必然有合法区段，统计加入
        //若只有一个数字出现的次数为奇数，其他均为偶数时
        for(int j = 0; j < 10; j ++)
        {
            vector<int> tt = temp;
            tt[j] ^= 1;
            sum += m[tt];
        }
        //更新出现次数
        m[temp] ++;
    }
    cout << sum;

    return 0;
}

原理相同

以下是代码部分，代码参考来源——tiger2005

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

typedef long long ll;
string s;
//分奇偶，共有10个数字， 2 ^ 10 = 1024， 因为为0-9，所以肯定足够
vector<int> mp(1024);

int main()
{
    ios::sync_with_stdio(false);
    cin >> s;
    //统计最后答案数
    ll sum = 0;
    int cnt = 0;
    mp[cnt] ++;
    for(auto x : s)
    {
        x -= '0';
        cnt ^= (1 << x);
        sum += mp[cnt];
        mp[cnt] ++;
        for(int i = 0; i < 10; i ++)
            sum += mp[cnt ^ (1 << i)];
    }
    cout << sum << '\n';

    return 0;
}

F-小红的矩阵修改

思路：

状压dp

以下是代码部分，代码参考来源——官方视频题解

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

typedef long long ll;
int dp[1010][100]; //dp[i][j] 代表前i列，第i列的状态值为j的合法方案数。
/*
 * red : 012
 * 000
 */
string s[4];
int n, m;
int p3[5] = {1, 3, 9, 27, 81};
int a[4];

bool check(int x)
{
    for(int i = 0; i < n; i ++)
        a[i] = x % 3, x /= 3;
    for(int i = 1; i < n; i ++)
        if(a[i] == a[i - 1])
            return false;
    return true;
}
bool check(int x, int y)
{
    for(int i = 0; i < n; i ++)
    {
        if(x % 3 == y % 3)
            return false;
        x /= 3, y /= 3;
    }
    return true;
}

map<char, int>mp;

int main()
{
    int res = INT_MAX;
    mp['r'] = 0;
    mp['e'] = 1;
    mp['d'] = 2;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //输入n行， m列
    cin >> n >> m;
    //输入初始地图
    for(int i = 0; i < n; i ++) cin >> s[i];
    //初始化为正无穷
    memset(dp, 0x3f, sizeof dp);
    for(int i = 0; i < m; i ++)
    {
        //在第一列的情况下
        if(!i)
        {
            //每一种情况
            for(int j = 0; j < p3[n]; j ++)
                //检查该种状态下，是否合法
                if(check(j))
                {
                    int cnt = 0;
                    //判断是否修改过，统计修改次数
                    for(int k = 0; k < n; k ++)
                        if(a[k] != mp[s[k][i]])
                            cnt ++;
                    //比较，存储更小的修改次数
                    dp[0][j] = min(dp[0][j], cnt);
                }
        }
        //不是第一列时
        else
        {
            for(int j = 0; j < p3[n]; j ++)
                //判断该种状压下列与列是否合法
                if(check(j))
                {
                    int cnt = 0;
                    //如果进行了修改，则统计
                    for(int k = 0; k < n; k ++)
                        if(a[k] != mp[s[k][i]])
                            cnt ++;
                    //判断j能否由k推出来
                    //这一列能否由上一列推出来
                    for(int k = 0; k < p3[n]; k ++)
                        if(check(j, k))
                            dp[i][j] = min(dp[i][j], dp[i - 1][k] + cnt);
                }
        }
        if(i == m - 1)
            for(int j = 0; j < p3[n]; j ++)
                res = min(res, dp[i][j]);
    }
    cout << res << '\n';

    return 0;
}