题解 CF296B 【Yaroslav and Two Strings】
2024-10-09 10:10:42
题目
题目大意
如果两个只包含数字且长度为 \(n\) 的字符串 \(s\) 和 \(w\) 存在两个数字 \(1≤i,j≤n\)，使得 \(s_i<w_i,s_j>w_j\) ,则称 \(s\) 和 \(w\) 是不可比的。现在给定两个包含数字和问号且长度为 \(n\) 的字符串，问有多少种方案使得将所有问号替换成 \(0\) 到 \(9\) 的数字后两个字符串是不可比的？
思路
分析
DP 题， 我们注意到，只要有一对这样的数就可以满足条件，而等于是不属于判断情况的，因此我们要单独记一个状态。
状态
f[i][k]: 当在第 $i$ 位时，第 $k$ 种情况的方案数。
以下： j < i
k = 0 : 前面只出现了 s[j] < w[j] 的情况，并没有 s[j] > w[j] ，即 s[j] <= w[j]
k = 1 : 前面 s[j] < w[j] , s[j] > w[j]
k = 2 : 前面只出现了 s[j] > w[j] 的情况，并没有 s[j] < w[j] ,即 s[j] >= w[j]
k = 3 : 前面只有 s[j] == w[j] 情况
转移
我们要对每一位考虑该位上填每个数字的情况。
对于已经确定数字的位，我们要只要对该数字讨论。
如果有'?',我们要枚举 1~9 进行转移。
感觉有点像数位DP？
初始状态
f[0][3] = 1
代码
按照各种状态进行转移即可，代码量有点大。
当然，也有一种代码量小的解法，可以预先算出每种情况转移，就不必枚举。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#define ll long long
using namespace std;
const int MAXN = 1e5+10;
const ll mod = 1e9+7;
int n;
ll f[MAXN][4];
char s[MAXN],w[MAXN];
int main (){
scanf("%d",&n);
scanf("%s",s+1);
scanf("%s",w+1);
f[0][0] = f[0][1] =f[0][2] = 0;
f[0][3] = 1;
for(int i = 1;i <= n;i++){
if(s[i] != '?' &&w[i] != '?'){
if(s[i] > w[i]) {
f[i][0] = 0;
f[i][1] = f[i-1][0] + f[i-1][1];
f[i][2] = f[i-1][2] + f[i-1][3];
f[i][3] = 0;
} else if(s[i] == w[i]){
f[i][0] = f[i-1][0];
f[i][1] = f[i-1][1];
f[i][2] = f[i-1][2];
f[i][3] = f[i-1][3];
} else{
f[i][0] = f[i-1][0] + f[i-1][3];
f[i][1] = f[i-1][2] + f[i-1][1];
f[i][2] = 0;
f[i][3] = 0;
}
} else if(s[i] == '?' && w[i] != '?'){
for(int j = '0';j < w[i] ;j++){
f[i][0] += f[i-1][0] + f[i-1][3];
f[i][1] += f[i-1][1] + f[i-1][2];
f[i][2] += 0;
}
f[i][0] += f[i-1][0];
f[i][1] += f[i-1][1];
f[i][2] += f[i-1][2];
f[i][3] += f[i-1][3];
for(int j = w[i] + 1;j <= '9';j++){
f[i][1] += f[i-1][0] + f[i-1][1];
f[i][2] += f[i-1][2] + f[i-1][3];
}
} else if(s[i] != '?' && w[i] == '?'){
for(int j = '0' ;j < s[i] ;j++){
f[i][1] += f[i-1][0] + f[i-1][1];
f[i][2] += f[i-1][2] + f[i-1][3];
}
f[i][0] += f[i-1][0];
f[i][1] += f[i-1][1];
f[i][2] += f[i-1][2];
f[i][3] += f[i-1][3];
for(int j = s[i] +1;j <= '9' ;j++){
f[i][0] += f[i-1][0] + f[i-1][3];
f[i][1] += f[i-1][1] + f[i-1][2];
}
} else{
for(int j = 0;j < 10;j++){
for(int k = 0;k < 10;k++){
if(j<k){
f[i][0] += (f[i-1][0] + f[i-1][3])%mod;
f[i][1] += (f[i-1][1] + f[i-1][2])%mod;
} else if(j == k){
f[i][0] += f[i-1][0];
f[i][1] += f[i-1][1];
f[i][2] += f[i-1][2];
f[i][3] += f[i-1][3];
} else{
f[i][1] += (f[i-1][0] + f[i-1][1])%mod;
f[i][2] += (f[i-1][2] + f[i-1][3])%mod;
}
f[i][0] %= mod;
f[i][1] %= mod;
f[i][2] %= mod;
}
}
}
f[i][0] %= mod;
f[i][1] %= mod;
f[i][2] %= mod;
}
printf("%d",f[n][1] % mod);
return 0;
}
最新文章
- Selenium-java-Log4j环境搭建和
- 安装GIT,集成到Powershell中
- LeetCode Plus One Linked List
- BAE hibernate c3p0数据库连接池
- IE6，IE7文档模式下 按钮type=submit在页面打开时会有一条黑线边框的处理方法。(转)
- Python 文件读写，条件循环（三次登录锁定账号实例）
- 编译boost
- JAVA 聊天窗口
- Java（Android）编程思想笔记02：组合与继承、final、策略设计模式与适配器模式、内部类、序列化控制（注意事项）
- Jquery OR Js 实现图片预览
- leetcode[149]Max Points on a Line
- 一个简单的MVC框架的实现
- JVM之Java虚拟机详解
- 一种非常巧妙的读取串口数据的方法--C#
- 最短路：spfa算法
- Java并发编程：volatile关键字解析-转
- netty的decoder encoder
- Jmeter实现接口自动化测试
- [Unity优化]UI优化(一)：RaycastTarget
- awk的常用操作场景以及工作中涉及到的一些场景实例