UVa 1509 - Leet
题意
给一串字符串，和一个对应的Leet，问能否存在一个转化使其相等。
其中，一个字符只能对应一种Leet，而一种Leet可以对应多个字符。
也就是说，这样是可以的
abc
sss
思路
因为l <= 15, k <= 3，考虑暴力枚举。
对原字符串逐个位置进行枚举对应的Leet和DFS，并用map存储。
如果该字符之前出现过，判断存储的Leet是否和接下来的Leet相等，相等，继续。不相等返回。
第一次用string写，2400+ms，吓cry。
优化了一下，1600+ms。
用char写，600+ms
代码
string版
#include <cstdio>
#include <algorithm>
#include <functional>
#include <stack>
#include <set>
#include <cctype>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <map>
#include <cmath>
#define LL long long
#define lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(arr, num) memset(arr, num, sizeof(arr))
#define PB push_back
#define ROP freopen("input.txt", "r", stdin);
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
using namespace std;
const int MAXN = (1 << 16) + 5;
typedef pair<int, int> pii;
typedef vector<int>::iterator viti;
typedef vector<pii>::iterator vitii;
map<char, string> mp;
string str, dic;
int k;
bool DFS(int curPos, int start)
{
if (curPos == str.length())
{
if (dic.size() == start) return true; //必须同时到达最后，否则不相等。
else return false;
}
if (start >= dic.size()) return false; //枚举多了
if (mp.count(str[curPos])) //如果之前已经存在
{
string ans = mp[str[curPos]];
if (dic.substr(start, ans.size()) != ans) return false;
if (DFS(curPos + 1, start + ans.size())) return true;
}
else
{
for (int i = 1; i <= k && start + i <= dic.size(); i++)
{
string tmp = dic.substr(start, i); //枚举对应的leet
mp[str[curPos]] = tmp;
if (DFS(curPos + 1, start + i)) return true;
mp.erase(str[curPos]); //一定要消除。不然等到回去的时候本来不应该存在的就存在了
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
//ROP;
int T, i, j, n;
cin >> T;
while (T--)
{
cin >> k;
cin >> str >> dic;
if (str.size() * 3 < dic.size())
{
cout << "0" << endl;
continue;
}
bool flag = false;
mp.clear();
if (!DFS(0, 0)) cout << "0" << endl;
else cout << "1" << endl;
}
return 0;
}
char版
#include <cstdio>
#include <algorithm>
#include <functional>
#include <stack>
#include <set>
#include <cctype>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <map>
#include <cmath>
#define LL long long
#define lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(arr, num) memset(arr, num, sizeof(arr))
#define PB push_back
#define ROP freopen("input.txt", "r", stdin);
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
using namespace std;
const int MAXN = 30 + 5;
typedef pair<int, int> pii;
typedef vector<int>::iterator viti;
typedef vector<pii>::iterator vitii;
map<char, char *> mp;
char str[MAXN], dir[MAXN];
int k;
bool DFS(int curPos, int start)
{
if (curPos == strlen(str))
{
if (strlen(dir) == start) return true;
else return false;
}
if (start >= strlen(dir)) return false;
if (mp[str[curPos]])
{
char *tmp = mp[str[curPos]];
int len = strlen(tmp);
int tmpPos = start;
for (int i = 0; i < len; i++)
{
if (tmp[i] != dir[tmpPos]) return false;
tmpPos++;
}
if (DFS(curPos + 1, tmpPos)) return true;
}
else
{
char tmp[MAXN];
for (int i = 1; i <= k; i++)
{
MS(tmp, 0);
int pos = 0;
for (int j = start; j < start + i; j++)
tmp[pos++] = dir[j];
mp[str[curPos]] = tmp;
if (DFS(curPos + 1, start + i)) return true;
mp[str[curPos]] = 0;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
//ROP;
int T, i, j, n;
cin >> T;
while (T--)
{
cin >> k;
cin >> str >> dir;
if (strlen(str) * 3 < strlen(dir))
{
cout << "0" << endl;
continue;
}
mp.clear();
if (!DFS(0, 0)) cout << "0" << endl;
else cout << "1" << endl;
}
return 0;
}