[Codeforces Round #699 (Div. 2)】A

Codeforces Round #699 (Div. 2)】A"/>

[Codeforces Round #699 (Div. 2)】A

[Codeforces Round #699 (Div. 2)】题解

这一场充分说明了正难则反这种思想的重要性

A.

题意：从（0，0）问是否通过删除序列到达(px,py)

思路：直接看四个方向的范围能否括住就行了

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int t,n;
char s[maxn];
map<char,int>mp;
int main(){ios::sync_with_stdio(false);cin.tie(0); cin>>t;mp['R']=1;mp['U']=1;mp['L']=mp['D']=-1;while(t--){ int px,py;cin>>px>>py;cin>>s;bool f=0;int a=0,b=0,c=0,d=0;for(int i=0;i<strlen(s);++i){if(s[i]=='U')a++;else if(s[i]=='D')b--;else if(s[i]=='L')c--;else d++;}if(px>=c&&px<=d&&py>=b&&py<=a)cout<<"YES\n";else cout<<"NO\n";}return 0;
}

B.

题意：有 n n n个山,每个山有高度 h i hi hi.人站在第一个山头上丢土

• 如果当前的位置是 i i i,那么如果 h i ≥ h i + 1 h_i≥h_{i+1} hi​≥hi+1​那么土会直接飞到下一个山头.
• 反之 h i + = 1 h_i+=1 hi​+=1.
• 飞出去输出负1

思路：煞笔题，最坏的情况就是单增，100*100，直接暴力模拟秒了

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
int t,n,a[105],k;
int main(){ios::sync_with_stdio(false);cin.tie(0); cin>>t;while(t--){ cin>>n>>k;for(int i=1;i<=n;++i)cin>>a[i];int ans=0;a[n+1]=0;for(int i=1;i<=k;++i){ ans=n+1;for(int j=1;j<=n;++j){ if(a[j+1]>a[j]){ ans=j;break;}}a[ans]++;if(ans>n)break;}if(ans>n)ans=-1;cout<<ans<<"\n";}return 0;
}

C.

题意：a,b,c，按顺序让c对a染色，问最后能否使得ab一样

思路：

首先考虑最后一步一定要能染，否则无解，这题正难则反考虑，如果当前可以染，就染，否则就染最后一步的，反正最后的影响也会被消去，所以直接模拟就好了，我是倒过来染的，因为不会有影响

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int t,n,m,a[maxn],b[maxn],c[maxn];
vector<int>G[maxn],ans;
int main(){ios::sync_with_stdio(false);cin.tie(0); cin>>t;while(t--){ int num=0;cin>>n>>m;for(int i=1;i<=n;++i)G[i].clear();ans.clear();for(int i=1;i<=n;++i)cin>>a[i];for(int i=1;i<=n;++i)cin>>b[i];for(int i=1;i<=m;++i)cin>>c[i];int is=0;for(int i=1;i<=n;++i){ if(b[i]==c[m]){ is=i;break;}}if(!is){ cout<<"NO\n";continue;}for(int i=1;i<=n;++i){ if(a[i]!=b[i])G[b[i]].pb(i),num++;}for(int i=m;i;--i){ if(G[c[i]].empty()){ if(i==m)ans.pb(is);else ans.pb(ans[0]);continue;}ans.pb(G[c[i]].back());G[c[i]].pop_back();num--;}if(num){ cout<<"NO\n";continue;}else{ cout<<"YES\n";reverse(ans.begin(),ans.end());for(auto&v:ans){ cout<<v<<" ";}cout<<"\n";}}return 0;
}

D.

题意：给定一个 n n n点的完全有向图,每个边有一个字母 a a a或 b b b.注意:两个点之间的两条边上的字母是不一定相同的。让你构造一个m长的回文路径

思路：

首先存在来回相等的，一定随便解，如果不存在，两点之间都是ab，奇数就随便做了。现在问题在于m是偶数的时候怎么做

容易发现，一个点如果他的两个出边都是一样的字母，一直拓展出去的话只有ababababab…或者babababa…这种构造方式

所以我们要找一个两个出边不一样的点。如果存在这样的点，则可以确定一个必定有解的三元环，首先是abba或者baab一直拓展，可以做m%4=0的，那么还剩下m%4=2的，其实就是在原来%4=0的基础上多了两条边而已，一开始不选择从中间那个点开始，起点选为其中一个出点，终点为另一个即可

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
int t,n,m;
const int maxn=1005;
char s[maxn][maxn];
void solve(){ if(m&1){ cout<<"YES\n";for(int i=1;i<=m+1;++i){ cout<<(i%2+1)<<" ";}cout<<"\n";return;}for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ if(s[i][j]==s[j][i]){ cout<<"YES\n";for(int k=1;k<=m+1;++k){ if(k&1)cout<<j<<" ";else cout<<i<<" ";}cout<<"\n";return;}}}for(int i=1;i<=n;++i){ int pa=0,pb=0;for(int j=1;j<=n;++j){ if(s[i][j]=='a')pa=j;else if(s[i][j]=='b')pb=j;}if(pa&&pb){ if(m%4==0){ cout<<"YES\n";for(int j=1;j<=m/2;++j){ if(j&1){ cout<<i<<" ";}else cout<<pa<<" ";}cout<<i<<" ";for(int j=1;j<=m/2;++j){ if(j&1)cout<<pb<<" ";else cout<<i<<" ";}}else{ cout<<"YES\n";for(int j=1;j<=m/2;++j){ if(j&1)cout<<pa<<" ";else cout<<i<<" "; }cout<<i<<" ";for(int j=1;j<=m/2;++j){ if(j&1)cout<<pb<<" ";else cout<<i<<" ";}}cout<<"\n";return;}}cout<<"NO\n";return;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cin>>t;while(t--){ cin>>n>>m;for(int i=1;i<=n;++i){ cin>>(s[i]+1);}solve();} return 0;
}

E.

题意：有n本书,每本书有自己的颜色.给定一个操作:把一本书移动到所有书的末尾.求最少操作多少次可以让所有相同颜色的书放在一起.

思路：

没见过的dp思路…感觉有点难想，参考了别人的博客会，下面讲解如何推导dp方程

一开始

子问题：dp[i]表示前i个已经合并好的最小代价

但是我们发现，模拟这个移动过程事实上是后面不断排列好的一个过程。

所以改变状态dp[i]后i个已经合并好的最小代价

但是到这里就出现问题了，当前的i是否移动动需要知道后缀的状态，根本无法转移，要么记录更多的维度，要么换状态，但是我们发现根本难以记录，所以换状态。

这就是本题最关键的地方，我们只需要关注最后的答案，而不需要构造方案

反转这个状态:dp[i]表示后i个最多有多少个元素不动

这样的话我们不用当前怎么移动，我们只需要决策当前是否动即可。转移的话分为两种，一种是当前的不保留，dp[i]=dp[i+1],一种是当前保留，而保留的话又分为两种，假如是当前颜色的第一个则可以与后来的合并，否则的话除了当前的都丢掉，足以覆盖所有状态了

这个套路真的很少见，找机会把别人博客里cf 1367F2也给补了

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn=5e5+5;
int t,n,dp[maxn],cnt[maxn],a[maxn],l[maxn],r[maxn];
int main(){ios::sync_with_stdio(false);cin.tie(0); cin>>n;for(int i=1;i<=n;++i){ cin>>a[i];if(!l[a[i]])l[a[i]]=i;r[a[i]]=i;}for(int i=n;i>=1;--i){cnt[a[i]]++;dp[i]=dp[i+1];if(i==l[a[i]])dp[i]=max(dp[i],cnt[a[i]]+dp[r[a[i]]+1]);else dp[i]=max(dp[i],cnt[a[i]]);}cout<<n-dp[1]<<"\n";return 0;
}