A.假期

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF698A?lang=zh 动态规划 题意：在每一天，Vasya 可以选择休息，或者参加比赛（如果这一天有比赛），或者锻炼（如果这一天健身房开放），输出一行，包含一个整数，表示 Vasya 至少需要休息多少天，限制：不能连续两天都锻炼，不能连续两天都参加比赛。 思路：dp[i][j]表示第i天做活动j时，前i天最多能活动多少天，状态转移公式：如果休息（dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])），如果健身（dp[i][2] = max(dp[i-1][0],dp[i-1][1])+1），如果比赛（dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + 1）； #include<bits/stdc.h> using namespace std; int n,a[105],dp[105][3]; int main(){ cin>>n; for(int i=1;i<=n;i)cin>>a[i]; memset(dp,0x3f,sizeof(dp)); dp[0][0]=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])); }

B.数字之和

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF489C?lang=zh 题意：你的任务是找出长度为m，各位数字之和为，s的最小和最大数，若不存在满足条件的数，输出“-1 -1”。 思路：贪心，先特判-1 -1，策略最大数：高位尽可能大，最小数：最高位为1，然后从低位到高位尽可能大。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int m,s,x;
	cin>>m>>s;
	x=s;
	if(s>9*m){
		cout<<"-1 -1";
		return 0;
	}
	if(s==0&&m>1){
		cout<<"-1 -1";
		return 0;
	}
	if(s==0&&m==1){
		cout<<"0 0";
		return 0;
	}
	string a="";
	for(int i=1;i<=9;i++){
		if(i<=x&&x-i<=(m-1)*9){
			a+=char('0'+i);
			x-=i;
			break;
		}
	}
	for(int i=2;i<=m;i++){
		for(int j=0;j<=9;j++){
			if(j<=x&&x-j<=(m-i)*9){
				a+=char('0'+j);
				x-=j;
				break;
			}
		}
	}
	x=s;
	string b="";
	for(int i=1;i<=m;i++){
		for(int j=9;j>=0;j--){
			if(i==1&&j==0&&m>1)continue;
			if(j<=x&&x-j<=(m-i)*9){
				b+=char('0'+j);
				x-=j;
				break;
			}
		}
	}
	cout<<a<<" "<<b;
}

C.美丽序列

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF1881E?lang=zh 题意：每次操作，你可以删除序列中的任意一个元素。请问最少需要多少次操作才能使给定序列变为美丽序列（定义：如果一个序列可以被分成若干个区块，每个区块的第一个元素表示该区块的长度，接下来是该区块的元素，则称该序列为美丽序列） 思路：我们需要找到最长的美丽子序列，答案=n-最长美丽子序列的长度，dp[i] 表示以位置i作为区块起点时，从i到n能形成的最大美丽序列长度转移：如果选择x作为区块长度，那么这个区块的长度为 x+1，下一个位置从i+x+1开始，公式：如果i+a[i]<=n,dp[i]=a[i]+1+ dp[i+a[i]+1否则：dp[i]=0（无法形成完整区块）要点：倒着用dp cpp #include<bits/stdc++.h> using namespace std; int n,a[200005],dp[200005]; int main(){ int t; cin>>t; while(t--){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=0;i<=n+1;i++)dp[i]=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; }

D.小高的生日卡

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF766C
题意：一条长度为n的信息s，分成若干个非空的子串，不允许英文字母中第i个字母在长度超过ai的字符串中出现，有多少种方法可以将字符串拆分成若干个子串，使得每个子串都满足魔法纸的条件，子串长度之和为n,且互不重叠？请计算方案数对1e9+7取模,在所有合法拆分中，可能出现的最长子串的最大长度是多少？在所有合法拆分方式中，最少需要分成多少个子串？
思路：dp1[i]：前i个字符的分割方案数，状态转移公式：x[i]=sum(dp1[j-1])，初始化x[0]=1，(j到i是合法子串),y[i]：前i个字符最少需要多少个子串,状态转移公式：y[i]=min(y[j-1]+1)，(j到i是合法子串)，初始化：y[0]=0,最大值：搜索合法子串时找max(···)。
```cpp

#include<bits/stdc.h> using namespace std; int n,a[30],x[1005],y[1005]; string s; int main(){ cin>>n>>s; for(int i=0;i<26;i)cin>>a[i]; int ans=0; for(int i=0;i<=n;i)y[i]=1e9; x[0]=1; y[0]=0; for(int i=0;i<n;i){ int len=1e9; for(int j=i;j<n;j++){ len=min(len,a[s[j]-'a']); if(j-i+1>len)break; x[j+1]=(x[j+1]+x[i])%1000000007; ans=max(ans,j-i+1); y[j+1]=min(y[j+1],y[i]+1); } } cout<<x[n]<<"\n"<<ans<<"\n"<<y[n]<<"\n"; } ```

E.棋盘游戏

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a55f50a47f4ff4971a0c4a3/problem/CF1033C
题意：游戏棋盘由n个格子组成，排成一行，编号从1到n，每个格子内包含一个1到n之间的数字ai。此外，任意两个格子内的数字都不相同。一个棋子被放在某个格子上。他们轮流移动棋子，Alice 先手。当前玩家可以将棋子从第i个格子移动到第j个格子，要求：aj>ai，|i−j∣mod ai=0，无法进行移动的一方判负，对于每一个可能的初始位置，若双方都采取最优策略，判断谁能获胜，输出一个长度为n的字符串s，其中第i个字符表示若棋子初始放在第i个格子时的游戏结果。如果Alice能获胜，则si等于"A"；否则，si等于"B"。
思路：