网站seo快速排名优化的软件,织梦 网站栏目管理,wordpress外链跳转样式,龙岩网络图书馆C.Kevin的七彩旗 思路#xff1a;贪心和dp均可以解决。
贪心#xff1a;我们可以发现#xff0c;最终想要获得合法的序列#xff0c;我们必须是通过把几段连续的序列拼凑起来#xff0c;但序列之间可能有重合#xff0c;因此我们就转化为了#xff0c;记录每一段最大的…C.Kevin的七彩旗 思路贪心和dp均可以解决。
贪心我们可以发现最终想要获得合法的序列我们必须是通过把几段连续的序列拼凑起来但序列之间可能有重合因此我们就转化为了记录每一段最大的合法序列然后使用最小的序列段数去覆盖区间[1,M]因此就转化为了区间覆盖板子题但这题有些许不同因为两个区间不一定要相交端点差值为1也是合法状态。
#includebits/stdc.husing namespace std;
const int N1e75;
typedef long long ll;
typedef pairll,ll pll;
typedef arrayint,4 p4;
int mod998244353;
const int maxv4e65;void solve()
{int n,m;cinnm;vectorint a(n);for(int i0;in;i) cina[i];vectorpll se;for(int i0;in;i){int ji;while(jn-1a[j1]a[j]1) j;se.push_back({a[i],a[j]});//处理出每个区间ij;}sort(se.begin(),se.end());//贪心的按左端点排序int cnt0;int l1,r0;int f0;for(int i0;ise.size();i){auto [nl,nr]se[i];if(nll){//因为我们的l是由r1更新而来所以此时的端点nl若大于l了则肯定不合法f1;break;}cnt;int ji;while(jse.size()se[j].firstl){//更新右端点rmax(r,(int)se[j].second);j;}if(rm) break;lr1;}if(f||rm){//如果是不合法的状态cout-1endl;}else{coutcntendl;}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t1;cint;while(t--){solve();}system(pause);return 0;
}dp我们使用g数组预处理出每个位置的第一个非法状态即对于连续区间[ai,aj],对于aj的第一个非法端点即为ai-1然后转移方程为
举个例子以区间而言他们对应的g数组值均为1因为若是想让整个区间合法他们只能从端点1的状态转移而来。
#includebits/stdc.husing namespace std;
const int N1e75;
typedef long long ll;
typedef pairll,ll pll;
typedef arrayint,4 p4;
int mod998244353;
const int maxv4e65;void solve()
{int n,m;cinnm;vectorint a(n);vectorint g(m5,m1),dp(m5,m1);for(int i0;in;i) cina[i];for(int i0,j0;in;i){if(i!0a[i]!a[i-1]1) ji;if(a[i]m) g[a[i]]min(g[a[i]],a[j]-1);}dp[0]0;for(int i1;im;i){dp[i]min(dp[g[i]]1,dp[i]);}if(dp[m]m){coutdp[m]endl;}else cout-1endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t1;cint;while(t--){solve();}system(pause);return 0;
}D.长途的春天 思路贪心。记录每个数的出现个数我们贪心的从后往前找若当前数的出现个数小于等于前一个数的出现个数即,那么我们可以接着往下选。
#includebits/stdc.husing namespace std;
const int N1e75;
typedef long long ll;
typedef pairll,ll pll;
typedef arrayint,4 p4;
int mod998244353;
const int maxv4e65;void solve()
{int n;cinn;vectorint a(n);for(int i0;in;i) cina[i];vectorint mp(n5);//记录每个数的出现次数for(int i0;in;i) mp[a[i]];for(int in;i1;i--){while(mp[i]){int cnt0;for(int ji;j1;j--){mp[j]--;//因为一共只有2e5个数每个数只会被删一次所以不会超时cnt;if(mp[j]1mp[j-1]) break;
//因为当前数已经删去了我们所说的合法状态为删去前所以此时需要1}if(cnt5){coutNOendl;return ;}}}coutYESendl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t1;cint;while(t--){solve();}system(pause);return 0;
}
