C.Kevin的七彩旗
思路：贪心和dp均可以解决。
贪心：我们可以发现，最终想要获得合法的序列，我们必须是通过把几段连续的序列拼凑起来，但序列之间可能有重合，因此我们就转化为了，记录每一段最大的合法序列，然后使用最小的序列段数去覆盖区间[1,M]，因此就转化为了区间覆盖板子题，但这题有些许不同，因为两个区间不一定要相交，端点差值为1也是合法状态。
#include<bits/stdc++.h>using namespace std;
const int N=1e7+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<int,4> p4;
int mod=998244353;
const int maxv=4e6+5;void solve()
{int n,m;cin>>n>>m;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];vector<pll> se;for(int i=0;i<n;i++){int j=i;while(j<n-1&&a[j+1]==a[j]+1) j++;se.push_back({a[i],a[j]});//处理出每个区间i=j;}sort(se.begin(),se.end());//贪心的按左端点排序int cnt=0;int l=1,r=0;int f=0;for(int i=0;i<se.size();i++){auto [nl,nr]=se[i];if(nl>l){//因为我们的l是由r+1更新而来，所以此时的端点nl若大于l了，则肯定不合法f=1;break;}cnt++;int j=i;while(j<se.size()&&se[j].first<=l){//更新右端点r=max(r,(int)se[j].second);j++;}if(r>=m) break;l=r+1;}if(f||r<m){//如果是不合法的状态cout<<-1<<endl;}else{cout<<cnt<<endl;}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}
dp：我们使用g数组预处理出每个位置的第一个非法状态，即对于连续区间[ai,aj],对于aj的第一个非法端点即为ai-1，然后转移方程为：
举个例子，以区间而言，他们对应的g数组值均为1，因为若是想让整个区间合法，他们只能从端点1的状态转移而来。
#include<bits/stdc++.h>using namespace std;
const int N=1e7+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<int,4> p4;
int mod=998244353;
const int maxv=4e6+5;void solve()
{int n,m;cin>>n>>m;vector<int> a(n);vector<int> g(m+5,m+1),dp(m+5,m+1);for(int i=0;i<n;i++) cin>>a[i];for(int i=0,j=0;i<n;i++){if(i!=0&&a[i]!=a[i-1]+1) j=i;if(a[i]<=m) g[a[i]]=min(g[a[i]],a[j]-1);}dp[0]=0;for(int i=1;i<=m;i++){dp[i]=min(dp[g[i]]+1,dp[i]);}if(dp[m]<=m){cout<<dp[m]<<endl;}else cout<<-1<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}
D.长途的春天
思路：贪心。记录每个数的出现个数，我们贪心的从后往前找，若当前数的出现个数小于等于前一个数的出现个数，即,那么我们可以接着往下选。
#include<bits/stdc++.h>using namespace std;
const int N=1e7+5;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<int,4> p4;
int mod=998244353;
const int maxv=4e6+5;void solve()
{int n;cin>>n;vector<int> a(n);for(int i=0;i<n;i++) cin>>a[i];vector<int> mp(n+5);//记录每个数的出现次数for(int i=0;i<n;i++) mp[a[i]]++;for(int i=n;i>=1;i--){while(mp[i]){int cnt=0;for(int j=i;j>=1;j--){mp[j]--;//因为一共只有2e5个数，每个数只会被删一次，所以不会超时cnt++;if(mp[j]+1>mp[j-1]) break;
//因为当前数已经删去了，我们所说的合法状态为删去前，所以此时需要+1}if(cnt<5){cout<<"NO"<<endl;return ;}}}cout<<"YES"<<endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();}system("pause");return 0;
}
