思路

不外乎八种情况，0，1，2都大于/小于平均值这两种情况不存在，所以只有六种情况，根据字典序贪心修改一下即可

解决方案

/*
    @description: 
    @author: universal42@163.com
    @solution: 
    @chinese problem:
        给定一个只包含0,1,2的字符串，这样的串称为三元串
        改动最少次数，使0,1,2的数量相等
        输出字典序最小的目标字符串
*/
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
#define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 1e9
const int maxn=2e3+5;
int main() {
    cls;
#ifdef LOCAL
    freopen("in.in","r",stdin);
#endif // LOCAL
    int n;
    string s;
    cin>>n>>s;
    int cnt[3]={0};
    int average=n/3;
    for(int i=0;i<n;i++){
        cnt[s[i]-'0']++;
    }

    if(cnt[0]>=average&&cnt[1]>=average&&cnt[2]<=average){
        int a=cnt[0]-average;
        int b=cnt[1]-average;
        for(int i=n-1;i>=0&&(a||b);i--){
            if(s[i]=='0'&&a){
                s[i]='2';
                a--;
            }
            else if(s[i]=='1'&&b){
                s[i]='2';
                b--;
            }
        }
    }
    else if(cnt[0]>=average&&cnt[1]<=average&&cnt[2]<=average){
        int a=cnt[0]-average;
        int c=average-cnt[2];
        int b=average-cnt[1];
        for(int i=n-1;i>=0&&c;i--){
            if(s[i]=='0'){
                s[i]='2';
                c--;
            }
        }
        for(int i=n-1;i>=0&&b;i--){
            if(s[i]=='0'){
                s[i]='1';
                b--;
            }
        }
    }
    else if(cnt[0]<=average&&cnt[1]>=average&&cnt[2]<=average){
        int a=average-cnt[0];
        int c=average-cnt[2];
        for(int i=0;i<n&&a;i++){
            if(s[i]=='1'){
                s[i]='0';
                a--;
            }
        }
        for(int i=n-1;i>=0&&c;i--){
            if(s[i]=='1'){
                s[i]='2';
                c--;
            }
        }
    }
    else if(cnt[0]<=average&&cnt[1]>=average&&cnt[2]>=average){
        int b=cnt[1]-average;
        int c=cnt[2]-average;
        for(int i=0;i<n&&(b||c);i++){
            if(s[i]=='1'&&b){
                s[i]='0';
                b--;
            }
            else if(s[i]=='2'&&c){
                s[i]='0';
                c--;
            }
        }
    }
    else if(cnt[0]<=average&&cnt[1]<=average&&cnt[2]>=average){
        int a=average-cnt[0];
        int b=average-cnt[1];
        for(int i=0;i<n&&a;i++){
            if(s[i]=='2'){
                s[i]='0';
                a--;
            }
        }
        for(int i=0;i<n&&b;i++){
            if(s[i]=='2'){
                s[i]='1';
                b--;
            }
        }
    }
    else if(cnt[0]>=average&&cnt[1]<=average&&cnt[2]>=average){
        int a=cnt[0]-average;
        int c=cnt[2]-average;
        for(int i=n-1;i>=0&&a;i--){
            if(s[i]=='0'){
                s[i]='1';
                a--;
            }
        }
        for(int i=0;i<n&&c;i++){
            if(s[i]=='2'){
                s[i]='1';
                c--;
            }
        }
    }
    cout<<s<<endl;
    return 0;
}

思路

如果 ai=aj,且bi=bj时，可知b[i]=b[i+1]=…=b[j]，对b来说 [i,j] 这个区间的值是一致的
用l[x],r[x]分别代表，x这个值的边界位置（也就是最左和最右位置） 则[l[x],r[x]]这个区间是一致的
如果两个线段相交，那么相交的两个线段必然都一致
设y是不相交线段的个数，ans是解
那么 ans=2^y%mod

解决方案

/*
    @description: 
    @author: universal42@163.com
    @solution: 
        后一项等于当前项，或者比当前项大于1
        b序列使一个单调递增的序列
*/
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
#define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 1e9
const int maxn=2e5+5;
int a[maxn];
int n;
map<int,int> r;//记录数字x最右边位置
ll pow_mod(ll a,ll b){//a^b%mod
    ll res=1;
    while(b){
        if(b&1) res=(res*a)%Mod;
        b>>=1;
        a=a*a%Mod;
    }
    return res;
}
ll getSegNum(){//获取不相交线段个数
    /*
        初始化线段个数为n，如果两个线段相交，那么用n减去  相交线段的最右边的线段的右端点减去第一个线段的左端点再加一 ，就是不相交线段的个数 
    */
    int ans=n;
    int last=-1;
    int start=0;
    for(int i=0;i<n;i++){
        if(r[a[i]]!=i){//右边端点不是自身，也就是说这个值不是单点
            last=r[a[i]];
            start=i;
            for(int j=start+1;j<=last;j++){
                if(r[a[j]]>r[a[start]]){//该区间相交
                    start=j;
                    last=r[a[j]];
                }
            }
            ans=ans-last+i;
            i=last;
        }
    }
    return ans;
}
int main() {
    //cls;
#ifdef LOCAL
    freopen("in.in","r",stdin);
#endif // LOCAL
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        r[a[i]]=i;
    }
    ll cnt=getSegNum();
    ll ans=pow_mod(2,cnt-1);
    printf("%lld\n",ans);
    return 0;
}

思路

从1开始对元素染色，如果某个元素当前颜色已经染过了，那么寻找一个没有染过的颜色即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/*
    @description: cf-1102-B
    @author: universal42@163.com
    @solution: greedy
*/
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
#define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 1e9
const int maxn=5000+5;
string yes="YES\n";
string no="NO\n";
int a[maxn];
bool v[maxn][maxn];//元素a[i],颜色j是否出现过
int num[maxn];
int ans[maxn];
int main() {
    cls;
#ifdef LOCAL
    freopen("in.in","r",stdin);
#endif // LOCAL
    int n,k;
    cin>>n>>k;
    bool flag=0;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        num[a[i]]++;
        if(num[a[i]]>k) flag=true;
    }
    if(flag){
        cout<<no;
        return 0;
    }
    int color=1;
    for(int i=0;i<n;i++){
        int j=0;
        while(v[a[i]][color]&&j<k) {
            color=color%k+1;
            j++;
        }
        v[a[i]][color]=true;
        ans[i]=color;
        color=color%k+1;
        j=0;
    }
    cout<<yes;
    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<ans[i];
    }
    cout<<endl;
    return 0;
}

先贴代码，后面证明

/*
    @description: cf-1107-D
    @author: universal42@163.com
    @solution: 暴力
*/
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
#define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 1e9
const int maxn=5200+5;
int a[maxn][maxn];
int n;
void debug(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cout<<a[i][j]<<" ";
        cout<<endl;
    }
}
bool check(int x){//判断x*x的子矩阵内所有元素是否相等,x是子矩阵长
    for(int i=1;i<=n;i+=x){
        for(int j=1;j<=n;j+=x){
            int t=a[i][j];
            for(int k=0;k<x;k++){
                for(int l=0;l<x;l++) if(a[i+k][j+l]!=t) return 0;
            }
        }
    }
    return 1;
}
int main() {
    cls;
#ifdef LOCAL
    freopen("in.in","r",stdin);
#endif // LOCAL
    cin>>n;
    string s;
    for(int i=1;i<=n;i++){
        //16进制转换为二进制
        cin>>s;
        int t;
        for(int j=n;j>=1;j-=4){
            t=(isdigit(s[(j-1)/4])?s[(j-1)/4]-'0':s[(j-1)/4]-'A'+10);
            for(int l=0;l<4;l++){
                a[i][j-l]=(t>>l)&1;
            }
        }
    }
    //debug();
    //暴力解法
    for(int i=n;i>1;i--){
        if(n%i==0){//是其因子
            if(check(i)){//x==i
                cout<<i<<endl;
                return 0;
            }
        }
    }
    cout<<1<<endl;
    return 0;
}

贴出代码，先鸽了，学会了A*再来更

尝试思路

首先考虑到有很多’@‘点，所以很容易想到的是 bfs 每个’@‘点，从中取出最小值即可。但是假设图中有很多’@'点，那么必定超时(200^4);

正确思路

从’Y’、‘M’开始 bfs，得到与每个’@‘的距离，再遍历每个’@'得出最小值即可.

题目描述

给定两个长为len的字符串s、t和长为2*len的串g，问是否存在按制定规则组合s、t得到g，如果s，t不能组成g，则将g的前后半部分分别赋予s、t，重复以上过程。如果可以得到，这输出变换步长，如果不能，则输出-1.

思路

暴力就完事了，注意判重

代码

#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
#define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 1e9
const int maxn=105;
int len=0;
string s,t,g;

bool check(string &x){//由x y能否组成g


    for(int i=0;i<(len<<1);i++){
        if(x[i]!=g[i]) return false;
    }
    return true;
}
int work(){
    int ans=1;
    string x,y;
    string ss;
    map <string ,int >m;
    cin>>len;
    cin>>s>>t>>g;
    x.resize(len);
    y.resize(len);
    ss.resize(2*len);
    for(int i=0;i<len;i++) x[i]=s[i];
    for(int i=0;i<len;i++) y[i]=t[i];
    for(int i=0;i<len;i++){
        ss[i<<1]=y[i];
        ss[i<<1|1]=x[i];
    }
    m[ss]=1;
    while(!check(ss)){
        ans++;
        for(int i=0;i<len;i++){//各取前后半部分
            x[i]=ss[i];
            y[i]=ss[len+i];
        }
        for(int i=0;i<len;i++){//如果没有出现过，则组成新的串
            ss[i<<1]=y[i];
            ss[i<<1|1]=x[i];
        }
        if(m[ss]) return -1;
        else m[ss]=1;
    }
    return ans;
}
int main() {
    cls;
#ifdef LOCAL
    freopen("in.in","r",stdin);
#endif // LOCAL
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        cout<<i<<" "<<work()<<endl;
    }
    return 0;
}

问题描述：略

思路： 简单的bfs，从初始位置开始，按位暴力从当前状态出发的所有素数状态，注意去重。这里因为数字不大于9999，所以我使用了vis[10000]来判断重复。

贴出代码

#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
#define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 1e9
const int maxn=2e3+5;
int n,m;
char err[]="Impossible";
int vis[10005];
struct node{
    int x;
    int step;
};
bool isPrime(int x){
    int len=sqrt(x*1.0);
    for(int i=2;i<=len;i++){
        if(x%i==0) 
            return false;
    }
    return true;
}
int getInt(char *s){
    int x=0;
    for(int i=3;i>=0;i--){
        x=x*10+s[i]-'0';
    }
    return x;
}
int bfs(){
    mset(vis,0);
    queue<node> q;
    node st;
    st.x=n;
    st.step=0;
    q.push(st);
    node f;
    char tmp[10];
    char mp[10];
    vis[n]=1;
    while(!q.empty()){
        f=q.front();
        q.pop();
        if(f.x==m) return f.step;
        int x=f.x;
        for(int i=0;i<4;i++){
            mp[i]=x%10+'0';//取最后一位
            x/=10;
        }
        node ps;
        strcpy(tmp,mp);
        for(int i=0;i<10;i++){//个位变换 0~9
            tmp[0]='0'+i;
            int tp=getInt(tmp);
            if(isPrime(tp)&&!vis[tp]){
                vis[tp]=1;
                ps.x=tp;
                ps.step=f.step+1;
                q.push(ps);
            }
        }
        strcpy(tmp,mp);
        for(int i=0;i<10;i++){//十位变换 0~9
            tmp[1]='0'+i;
            int tp=getInt(tmp);
            if(isPrime(tp)&&!vis[tp]){
                vis[tp]=1;
                ps.x=tp;
                ps.step=f.step+1;
                q.push(ps);
            }
        }
        strcpy(tmp,mp);
        for(int i=0;i<10;i++){//百位变换 0~9
            tmp[2]='0'+i;
            int tp=getInt(tmp);
            if(isPrime(tp)&&!vis[tp]){
                vis[tp]=1;
                ps.x=tp;
                ps.step=f.step+1;
                q.push(ps);
            }
        }
        strcpy(tmp,mp);
        for(int i=1;i<10;i++){//千位变换 1~9
            tmp[3]='0'+i;
            int tp=getInt(tmp);
            if(isPrime(tp)&&!vis[tp]){
                vis[tp]=1;
                ps.x=tp;
                ps.step=f.step+1;
                q.push(ps);
            }
        }
    }
    return -1;
}
int main() {
    cls;
#ifdef LOCAL
    freopen("in.in","r",stdin);
#endif // LOCAL
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        int ans=bfs();
        if(ans==-1) cout<<err<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

睡前最后一题，可以开心的睡觉去了

介绍

康拓展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩，康拓展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

定义

X=a_n(n-1)!+a_{n-1}(n-2)!+a_{n-2}(n-3)!+···+a_2(1)!+a_1(0!)

其中 a[i]为整数，并且0<=a[i]<i,代表元素arr[i]在还未出现的数字中排第几，简而言之，就是后面与多少个数小于arr[i]

康拓展开是可逆的，若求排列中第x个数的排列，则先将x-1，之后按照公式依次除以(n-i)!

斯特灵   Stirling 公式

公式介绍

斯特灵公式是一条用来取n阶乘近似值的数学公式

证明：略

    ln(n!)=ln 1+ln 2+···+ln n

          ≈n ln(n)-n+1

len=((0.5*log(2*pi*x)+x*log(x) - x)/log(10))