1. 假期安排

思路：
用动态规划，设dp[i][0/1/2]表示第i天做不同活动时的最小休息天数（0休息，1比赛，2锻炼）。根据当天可用活动转移，若两天活动相同则跳过。取最小值。n≤100，直接O(n)转移即可。

code

#include<bits/stdc++.h>
using namespace std;
int n;
int a[105];
int dp[105][3];//dp[i][j]:第i天做j活动的最少休息天数
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    // 初始化
    for(int i=0;i<=n;i++){
        for(int j=0;j<3;j++){ 
            dp[i][j]=1e9;
        }
    }
    dp[0][0]=dp[0][1]=dp[0][2]=0;
    for(int i=1;i<=n;i++) {
        //今天休息
        dp[i][0]=min(dp[i-1][0],min(dp[i-1][1], dp[i-1][2]))+1;
        //今天比赛
        if(a[i]==1||a[i]==3){
            dp[i][1]=min(dp[i-1][0], dp[i-1][2]);
        }
        //今天锻炼
        if(a[i]==2||a[i]==3){
            dp[i][2]=min(dp[i-1][0], dp[i-1][1]);
        }
    }
    cout<<min(dp[n][0],min(dp[n][1], dp[n][2]))<<endl;
    return 0;
}

2. 最大最小数

思路：
若s=0且m>1则无解；若s>9m也无解。构造最小数：从高位到低位尽量放小，但首位不能为0，且要保证剩余位能凑够s。构造最大数：从高位到低位尽量放大，每位最多9。贪心构造输出。

错因：

忘记特判

code

#include<bits/stdc++.h>
using namespace std;
string maxnum;
string minnum;
int m,s;
int main(){
	cin>>m>>s;
	if(s>m*9){
		cout<<"-1 -1";
		return 0;
	}
    if(s==0){
        if(m==1) cout<<"0 0\n";
        else cout<<"-1 -1\n";
        return 0;
    }
	int a=s;
	for(int i=0;i<m;i++){
		int bigwei=min(9,a);
		maxnum+=char('0'+bigwei);
		a-=bigwei;
	}
	a=s;
	for(int i=0;i<m;i++){
		int smallwei;
		if(i==0){
			smallwei=max(1,a-9*(m-i-1));
		}else{
			smallwei=max(0,a-9*(m-i-1));
		}
		minnum+=char('0'+smallwei);
		a-=smallwei;
	}
	cout<<minnum<<" "<<maxnum;
	return 0;
}

3. 美丽序列

思路：
用动态规划，dp[i]表示前i个元素变为美丽序列需要删除的最少次数。转移时从当前位置j往后跳a[j]+1步（j+1到j+a[j]为块内容），若j+a[j]≤n则dp[j+a[j]]=min(dp[j+a[j]],dp[j-1])，同时每个位置也可选择删除当前元素。最终答案为n-dp[n]中保留的最多元素数。

错因：

dfs暴搜TLE

code

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t; cin>>t;
    while(t--){
        int n; cin>>n;
        vector<int> a(n+1);
        for(int i=1;i<=n;i++) cin>>a[i];
        vector<int> dp(n+1,-1e9);
        dp[0]=0;
        for(int i=1;i<=n;i++){
            dp[i]=max(dp[i],dp[i-1]);
            if(i+a[i]<=n) dp[i+a[i]]=max(dp[i+a[i]], dp[i-1]+a[i]+1);
        }
        cout<<n-dp[n]<<'\n';
    }
    return 0;
}

4. 字符串拆分

思路：
n≤1000，用DP。对每个位置i，预处理从i出发能延伸的最远合法右端点（子串内每个字母出现次数≤对应a[ch]）。dp1[i]表示前i个字符的拆分方案数，dp2[i]表示最小分段数，同时记录分段中最大子串长度。O(n²)转移即可。

code

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int n;
char s[1005];
int a[26];
long long dp1[1005];
int dp2[1005],dp3[1005];
int main(){
    cin>>n;
    cin>>(s+1);
    for(int i=0;i<26;i++) cin>>a[i];
    memset(dp1,0,sizeof(dp1));
    for(int i=0;i<=n;i++) dp2[i]=0,dp3[i]=INF;
    dp1[0]=1;
    dp3[0]=0;
    for(int i=1;i<=n;i++){
        int mn=1005;
        for(int j=i-1;j>=0;j--){
            int c=s[j+1]-'a';
            mn=min(mn,a[c]);
            int len=i-j;
            if(len>mn) break;
            // [j+1,i] 合法
            dp1[i]=(dp1[i]+dp1[j])%MOD;
            dp2[i]=max(dp2[i],max(dp2[j],len));
            dp3[i]=min(dp3[i],dp3[j]+1);
        }
    }
    cout<<dp1[n]<<endl;
    cout<<dp2[n]<<endl;
    cout<<dp3[n]<<endl;
    return 0;
}

5. 棋盘游戏

思路：
按数字从小到大处理。对每个位置i，枚举所有倍数距离d，检查i±d是否合法且a[j]>a[i]。若存在一个后继位置j，其状态为必败，则当前位置为必胜；否则为必败。从大到小处理，O(n log n)枚举倍数。

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,a[MAXN],pos[MAXN],sg[MAXN];
char ans[MAXN];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]]=i;
    }
    for(int v=n;v>=1;v--){
        int i=pos[v];
        bool win=0;
        int k=v;
        for(int j=i+k;j<=n;j+=k){
            if(a[j]>v){
                if(sg[j]==0){
                    win=1;
                    break;
                }
            }
        }
        if(!win){
            for(int j=i-k;j>=1;j-=k){
                if(a[j]>v){
                    if(sg[j]==0){
                        win=1;
                        break;
                    }
                }
            }
        }
        sg[i]=win;
        ans[i]=win?'A':'B';
    }
    for(int i=1;i<=n;i++) cout<<ans[i];
    cout<<endl;
    return 0;
}

6. 高雅数

思路：
数位DP。状态记录已用的非零数字个数（0~3），以及当前是否已开始填数。枚举每位0~9，若数字非零则计数+1，超过3则剪枝。对每个区间计算f(r)-f(l-1)。t≤1e4，但数位长度仅19位，DP可复用。

code

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
long long dp[20][5];
long long dfs(int p,int cnt,int t){
    if(cnt>3) return 0;
    if(p<0) return 1;
    if(!t&&dp[p][cnt]!=-1)
        return dp[p][cnt];
    int up=t?a[p]:9;
    long long res=0;
    for(int d=0;d<=up;d++){
        int nt=t&&(d==a[p]);
        res+=dfs(p-1,cnt+(d!=0),nt);
    }
    if(!t) dp[p][cnt]=res;
    return res;
}
long long count(long long x){
    if(x<0) return 0;
    a.clear();
    if(x==0) a.push_back(0);
    while(x>0){
        a.push_back(x%10);
        x/=10;
    }
    return dfs(a.size()-1,0,1);
}
int main(){
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t--){
        long long l,r;
        cin>>l>>r;
        cout<<count(r)-count(l-1)<<endl;
    }
    return 0;
}