CF-957
赛时A去写全排列……前三题我的写法都挺丑的,后面改进了再更……
Problem - D - Codeforces
虽然是很简单很经典的线性dp,但也是我第一次自己把这种题写出来ヾ(≧▽≦*)o
分析
看题面很容易想到线性递推来更新状态,是一种线性dp。
-
f[i]>=0表示第i个点能被达到,否则不能被达到,因为最多在水中游k米,这一条件会影响是否能达到该点,所以我们用f[i]>=0时的值来表示这一状态,即在第i点最多还能游f[i]米
-
初始条件:f[0]显然为k,而1~m内的点都在第一次跳跃的范围内,其中s[i]为C情况不能达到,设f[i]=-1,其余点就是f[i]=k,由此m+1~n+1的点都可以通过状态转移递推得到
-
状态转移:对于在m+1~n+1范围内的点i,如果s[i]为C,显然无法达到,f[i]=-1,而s[i]为W或者L时,点i的状态可以由[i-m,i-1]的点j更新,s[j]=L或者j为0时意味着可以由点j跳到点i,而s[j]为W的情况则只能在j为i-1时更新,表示从i-1游到i,此时要用f[i-1]-1来更新f[i]
最后若判断f[n+1]>=0与否即可
代码
const int N=2e5+5;
int f[N];
void solve() {
int n,m,k;cin>>n>>m>>k;
string s;cin>>s;
s=' '+s;
rep(i,0,n+1) f[i]=-1;
rep(i,0,m){
if(s[i]!='C'||i==0) f[i]=k;
else f[i]=-1;
}
rep(i,m+1,n+1){
if(s[i]!='C'||i==n+1){
rep(j,i-m,i-1){
if(s[j]=='L'||j==0) f[i]=max(f[i],f[j]);
else if(j==i-1&&s[j]=='W') f[i]=max(f[i],f[j]-1);
}
}
else f[i]=-1;
}
if(f[n+1]>=0) cout<<"YES";
else cout<<"NO";
cout<<endl;
}
Problem - E - Codeforces
暴力枚举
分析
注意到a的范围只有1e4,n为一、二、三位数时,n*a最多1e4、1e5、1e6,也就是说,n为一,二,三位数的情况下,a-b分别<=4,5,6,如此我们可以在考虑n的位数的情况下暴力枚举a、b的值求解
代码
int n,_=1e4;
bool f(int w,int a,int b){
int res=0,cnt=0;
if(w==1){
cnt=a-b;
while(cnt--){
res=res*10+n;
}
}
else if(w==2){
cnt=a*2-b;
int now=1;
while(cnt--){
if(now) res=res*10+n/10;
else res=res*10+n%10;
now^=1;
}
}
else{//因为按数据范围,这种情况只有n=100
cnt=a*3-b;
int now=0;
while(cnt--){
if(!now) res=res*10+1;
else res=res*10;
now=(now+1)%3;
}
}
return res==n*a-b;
}
void solve() {
cin>>n;
vector<pair<int,int>>ans;
if(n<10){
rep(i,1,_){
int s=max(i-4,1ll);
rep(j,s,i-1){
if(f(1,i,j)) ans.push_back({i,j});
}
}
}
else if(n<100){
rep(i,1,_){
int s=max(i*2-5,1ll);
rep(j,s,i*2-1){
if(f(2,i,j)) ans.push_back({i,j});
}
}
}
else{
rep(i,1,_){
int s=max(i*3-6,1ll);
rep(j,s,i*3-1){
if(f(3,i,j)) ans.push_back({i,j});
}
}
}
cout<<ans.size()<<endl;
for(auto [a,b]:ans) cout<<a<<" "<<b<<" "<<endl;
}
标签:10,cnt,int,res,CF,957,else,now
From: https://www.cnblogs.com/mono-4/p/18301379