题解 P3417 【[POI2005]BANK-Cash Dispenser】
小黑AWM
2019-02-11 21:35:28
##### 看到提交记录中很多人的代码和zyl的长得一模一样，~~屎名警告哦~~qwq
***
在z老师课上一开始茫然半天才弄明白题意，也没太看懂周老师的标程，不过还是十分感谢POI搬运组。
题意oscar巨巨已经简述过了，在此不再赘述，本题解主要提供一种不太一样的写法以及思考过程并且说一下坑点。做法直接跳转到第9段。
***
不难想到我们要枚举0000 - 9999的所有密码输入序列依次检验，不过检验过程中如果强行代入t个动作序列，那么检验的复杂度便是$O(\sum t)$。这必然是不可取的。
那么不妨做一遍LCS再对LCS进行枚举？做一遍$n = 1e3,\space t= 1e4$的LCS的复杂度怕是要凉。
根据题目性质我们可以增加一些思考，我们手头有的只是四个数字的序列，
我们只要在所有的$t$个序列中找到_有这四个数字的子序列就行了_。
因此我们不需要这个数字的下一个是什么，我们只要知道我们密码数字的后一位在哪儿，寻找过去就是了。
考虑用一个NXT[i][j][k]的数组表示在第i行，第j列，之后（由于我们可以在一个数字上按很多次所以包括其本身）最近的数字k（$k\in[0,9],\space k\in N$）的位置
这个东西只要倒过来维护就可以了。
```cpp
#include <cstdio>
#include <iostream>
#define Int int
using namespace std;
const int maxn = 1e3 + 10;
const int maxt = 1e4 + 10;
int n, t, nxt[maxn][maxt][10], cnt;
char input[maxt];
bool check(int xx, int row){
int x[5];
x[1] = xx/1000;
x[2] = (xx/100)%10;
x[3] = (xx/10)%10;
x[4] = xx%10;
int at = 1;
for(int i = 1; i <= 4; i++){
if(nxt[row][at][x[i]] == 0)
return false;
at = nxt[row][at][x[i]];
}
return true;
}
bool check(int xx){
for(int i = 1; i <= n; i++)
if(!check(xx, i))
return false;
return true;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> t;
cin >> input;
for(int j = t; j >= 1; j--){
for(int k = 0; k < 10; k++){
if(k == input[j-1] - '0')
nxt[i][j][k] = j;
else
nxt[i][j][k] = nxt[i][j+1][k];
}
}
}
for(int i = 0; i < 10000; i++)
cnt += check(i);
cout << cnt << endl;
return 0;
}
//60分
```
嗯，提交，MLE。这如果是在NOIP是要爆零的！
我们计算一下空间复杂度，光nxt就有1e8*4bit。[束手无措.jpg]╮(￣▽￣"")╭
脑子钝了好久愣是没想出来怎么优化空间。考虑提取公因式，发现在检验和预处理中在第几行都出现过了，那么我们能不能在每一行就检验一下呢，这样nxt就可以省下n这一维。
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#define Int int
using namespace std;
const int maxn = 1e3 + 10;
const int maxt = 1e4 + 10;
int n, t, nxt[maxt][10], cnt;
char input[maxt];
bool great[10000];
bool check(int xx){
int x[5];
x[1] = xx/1000, x[2] = (xx/100)%10, x[3] = (xx/10)%10, x[4] = xx%10;
int at = 1;
for(int i = 1; i <= 4; i++){
if(nxt[at][x[i]] == 0)
return false;
at = nxt[at][x[i]];
}
return true;
}
int main(){
memset(great, 1, sizeof(great));
cin >> n;
for(int i = 1; i <= n; i++){
memset(nxt, 0, sizeof(nxt));
cin >> t;
cin >> input;
for(int j = t; j >= 1; j--){
for(int k = 0; k < 10; k++){
if(k == input[j-1] - '0')
nxt[j][k] = j;
else
nxt[j][k] = nxt[j+1][k];
}
}
for(int j = 0; j < 10000; j++)
great[j] &= check(j);
}
for(int i = 0; i < 10000; i++)
cnt += great[i];
cout << cnt << endl;
return 0;
}
//AC
```
# 大功告成！