https://ac.nowcoder.com/acm/contest/75174#question

$E-小红的回文数$

$题目要求是统计所有连续区间,计算构成“好数”的方案总数$

$由于区间长度为10^5,暴力枚举必然超时,需要寻找特殊的性质来解题$

一个整数是“好数”，当且仅当该整数通过重排之后可以形成回文数。（可以包含前导零）

$注意到好数的性质,出现次数为奇数的数字最多只有一个,$

$因此可以分开计算出现次数为偶数的和奇数的情况$

$因为数字种类最多只有10个,每个奇偶性用1、0表示,最多只有1024种情况$

$枚举区间右端点r,表示[1,r]的区间,通过前缀记录与其状态相同的区间[1,l]个数$

$相减必为好数区间-数字出现次数全为偶数的$

$再计算当前状态恰有一位不同的区间-即相减为出现一个奇数的区间$

$时间复杂度O(10·n)-n为整数长度$

状压写法

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
int cnt[1024];
long long ans;
int main() {
    string s;
    cin>>s;
    cnt[0] ++;
    int sum = 0;
    for(int i = 0; i < s.size(); i ++ )
    {
        sum^=1<<(s[i]-'0');
        ans+=cnt[sum];
        for(int j = 0; j < 10; j ++ )
        {
            int res = sum^(1<<j);
            ans+=cnt[res];
        }
        cnt[sum]++;
    }
    cout<<ans;
    return 0;
}

map+数组写法

$时间复杂度O(10·n·log)$

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
map<vector<int>,int>h;
int main() {
    string s;
    cin>>s;
    vector<int>temp;
    for(int i = 0; i < 10; i ++ ) temp.push_back(0);
    h[temp]++;
    long long sum = 0;
    for(int i = 0; i < s.size(); i ++ )
    {
        temp[s[i]-'0']^=1;
        sum+=h[temp];
        for(int j = 0; j < 10; j ++ )
        {
            vector<int> tt = temp;
            tt[j]^=1;
            sum+=h[tt];
        }
        h[temp]++;
    }
    cout<<sum;
    return 0;
}

$F-小红的矩阵修改$

$经典的状压dp,注意到n<=4,m<=1000,’r’,’e’,’d’可以分别看成012,代表三进制串$

$通过三进制整数表示每一列的状态,利用check函数保证当前列本身和上一列的合法性,dp即可$

$时间复杂度O(3^{2·n}·m)$

#include <bits/stdc++.h>
using namespace std;
int dp[1010][100];
int n,m;
char g[4][1010];
int r[5] = {1,3,9,27,81};
int b[4] = {};
int ans;
map<char,int>mp;
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;
}
bool check(int x) // 判断一列状态是否有两个相邻的字母
{
    for(int i = 0; i < n; i ++ )
        b[i] = x%3,x/=3;
    for(int i = 1; i < n; i ++ )
        if(b[i]==b[i-1]) return false;
    return true;
}
int main()
{
    cin>>n>>m;
    for(int i = 0; i < n; i ++ ) scanf("%s",g[i]);
    mp['r'] = 0;
    mp['e'] = 1;
    mp['d'] = 2;
    memset(dp,0x3f,sizeof dp);
    ans = 2e9;
    for(int i = 0; i < m; i ++ )
    {    
        if(i == 0) // 首列没有转移
        {    
            for(int j = 0; j < r[n]; j ++)
            {
                int cnt = 0;
                if(check(j)){
                    for(int k = 0; k < n; k ++ )
                        cnt+=(b[k]!=mp[g[k][i]]);
                    dp[0][j] = min (dp[0][j],cnt);
                }
            }
        }else // j由k转移,如果k不合法，不会转移
        {
            for(int j = 0; j < r[n]; j ++)
            {       
                int cnt = 0;
                if(check(j))
                {    
                    for(int k = 0; k < n; k ++ )
                       cnt+=(b[k]!=mp[g[k][i]]);
                    for(int k = 0; k < r[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 < r[n]; j ++ ) ans = min(dp[i][j],ans);
    }
    cout<<ans;
    return 0;
}