CF-957(D-E)

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; }