| 记录编号 |
262369 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOI 2000]算符破译 |
最终得分 |
100 |
| 用户昵称 |
 ppfish |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
5.004 s |
| 提交时间 |
2016-05-20 16:32:19 |
内存使用 |
0.34 MiB |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void Read(T &x)
{
int f = 1;
char t = getchar();
while (t < '0' || t > '9') {
if (t == '-') f = -1;
t = getchar();
}
x = 0;
while (t >= '0' && t <= '9') {
x = x * 10 + t - '0';
t = getchar();
}
x *= f;
}
template<typename T>inline void Write(T x)
{
static int output[20];
int top = 0;
if (x < 0) putchar('-'), x = -x;
do {
output[++top] = x % 10;
x /= 10;
} while (x > 0);
while (top > 0) putchar('0' + output[top --]);
putchar('\n');
}
template<typename T>inline void chkmin(T &x, T y) { if (x > y) x = y; }
template<typename T>inline void chkmax(T &x, T y) { if (x < y) x = y; }
const int maxn = 1005;
const int sigma = 13;
const int maxlen = 14;
const char uti[] = "=+*0123456789";
int n;
int len[maxn];
char str[maxn][maxlen];
bool ban[sigma];
bool fst[sigma];
bool end[sigma];
bool ineql[sigma];
bool okeql[sigma];
bool adj[sigma][sigma];
int st[maxn];
int ed[maxn];
vector<pair<int, int> > neighbor[sigma];
bool used[sigma];
int to[sigma];
bool nosol = true;
int res[sigma][sigma];
void input()
{
Read(n);
for (int i = 1; i <= n; i++) {
scanf("%s", str[i] + 1);
len[i] = strlen(str[i] + 1);
for (int j = 1; j <= len[i]; j++) {
if (str[i][j] - 'a' >= sigma) {
puts("noway");
exit(0);
}
}
}
}
long long calc(char *re, int l, int r)
{
static long long num[maxlen];
static long long qn[maxlen];
static char opr[maxlen];
static char s[maxlen];
int ol = 0;
int nl = 0;
int nt = 0;
long long cnt;
for (int i = l; i <= r; i++) {
if (isalpha(re[i])) {
s[i] = uti[to[re[i] - 'a']];
} else {
s[i] = re[i];
}
}
if (!isdigit(s[l]) || !isdigit(s[r])) return -1;
for (int i = l; i <= r; i++) {
if (!isdigit(s[i])) opr[++ol] = s[i];
else {
cnt = s[i] - '0';
while (i + 1 <= r && isdigit(s[i + 1])) {
cnt = cnt * 10 + s[i + 1] - '0';
i ++;
}
num[++nl] = cnt;
}
}
qn[++nt] = num[1];
for (int i = 1; i <= ol; i++) {
if (opr[i] == '*') {
qn[nt] = qn[nt] * num[i + 1];
} else {
qn[++nt] = num[i + 1];
}
}
long long res = 0;
while (nt > 0) res += qn[nt --];
return res;
}
void prepare()
{
static int appear[sigma];
for (int i = 0; i < sigma; i++) okeql[i] = true;
for (int i = 1; i <= n; i++) {
memset(appear, 0, sizeof(appear));
for (int j = 1; j <= len[i]; j++) {
appear[str[i][j] - 'a'] ++;
ineql[str[i][j] - 'a'] = true;
}
for (int j = 0; j < sigma; j++) {
okeql[j] &= (appear[j] == 1);
okeql[j] &= (str[i][1] - 'a' != j);
okeql[j] &= (str[i][len[i]] - 'a' != j);
}
for (int j = 1; j < len[i]; j++) {
adj[str[i][j] - 'a'][str[i][j + 1] - 'a'] = true;
adj[str[i][j + 1] - 'a'][str[i][j] - 'a'] = true;
}
fst[str[i][1] - 'a'] = true;
end[str[i][len[i]] - 'a'] = true;
}
static set<pair<int, int> > g[sigma];
pair<int, int> foo;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < len[i]; j++) {
g[str[i][j] - 'a'].insert(make_pair(j == 1 ? -1 : str[i][j - 1] - 'a', str[i][j + 1] - 'a'));
}
}
for (int i = 0; i < sigma; i++) {
for (set<pair<int, int> >::iterator it = g[i].begin(); it != g[i].end(); it++) {
neighbor[i].push_back(*it);
}
}
}
vector<int> remain;
void fillmax(char s[maxlen], int l, int r)
{
for (int i = l; i <= r; i++) {
if (to[s[i] - 'a'] == -1) {
s[i] = '9';
}
}
}
void fillmin(char s[maxlen], int l, int r)
{
for (int i = l, last = -1; i <= r + 1; i++) {
if (to[s[i] - 'a'] == -1 && last == -1) last = i;
if ((to[s[i] - 'a'] != -1 || i == r + 1) && last != -1) {
if (i - last == 1) {
s[last] = '0';
} else {
s[last] = '1';
for (int j = last + 1; j < i; j++) s[j] = '0';
}
last = -1;
}
}
}
void split()
{
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= len[i]; j++) {
if (to[str[i][j] - 'a'] == 0) {
ed[i] = j - 1;
st[i] = j + 1;
break;
}
}
}
}
bool checkrange()
{
char tmp[maxlen];
for (int i = 0; i < sigma; i++) {
if (to[i] != -1) {
for (int j = i; j < sigma; j++) {
if (to[j] != -1) {
if (adj[i][j]) {
return false;
}
}
}
}
}
long long lmax, rmax;
long long lmin, rmin;
for (int i = 1; i <= n; i++) {
memcpy(tmp, str[i], sizeof(str[i]));
fillmax(tmp, 1, len[i]);
lmax = calc(tmp, 1, ed[i]);
rmax = calc(tmp, st[i], len[i]);
memcpy(tmp, str[i], sizeof(str[i]));
fillmin(tmp, 1, len[i]);
lmin = calc(tmp, 1, ed[i]);
rmin = calc(tmp, st[i], len[i]);
if (lmax < rmin || lmin > rmax) return false;
}
return true;
}
bool prezero()
{
int pr, nx;
for (int i = 0; i < sigma; i++) {
if (to[i] == 3) {
for (int j = 0; j < (int)neighbor[i].size(); j++) {
pr = neighbor[i][j].first;
nx = neighbor[i][j].second;
if ((pr == -1 || (to[pr] < 3 && to[pr] != -1)) && (to[nx] == -1 || to[nx] >= 3)) {
return true;
}
}
}
}
return false;
}
bool checkall()
{
long long r1, r2;
for (int i = 1; i <= n; i++) {
r1 = calc(str[i], 1, ed[i]);
r2 = calc(str[i], st[i], len[i]);
if (r1 == -1 || r2 == -1 || r1 != r2) return false;
}
return true;
}
void dfs(int cur)
{
if (cur == (int)remain.size()) {
if (checkall()) {
nosol = false;
for (int i = 0; i < sigma; i++) {
if (to[i] != -1) {
res[i][to[i]] ++;
} else {
ban[i] = true;
}
}
}
return;
}
for (int i = 3; i < sigma; i++) {
if (!used[i]) {
used[i] = true;
to[remain[cur]] = i;
if (i != 3 || (i == 3 && !prezero())) dfs(cur + 1);
used[i] = false;
to[remain[cur]] = -1;
}
}
}
void enumopr(int cur)
{
if (cur == 1) split();
if (cur == 3) {
if (checkrange()) {
remain.clear();
for (int i = 0; i < sigma; i++) {
if (to[i] == -1 && ineql[i]) {
remain.push_back(i);
}
}
dfs(0);
}
return;
}
for (int i = 0; i < sigma; i++) {
if (cur == 0 && !okeql[i]) continue;
if (to[i] == -1 && !fst[i] && !end[i]) {
to[i] = cur;
enumopr(cur + 1);
to[i] = -1;
}
}
}
void solve()
{
memset(to, -1, sizeof(to));
enumopr(0);
for (int i = 0; i < sigma; i++) {
if (ban[i]) continue;
int cert = -1;
bool flag = true;
for (int j = 0; j < sigma; j++) {
if (res[i][j] > 0) {
if (cert == -1) cert = j;
else flag = false;
}
}
if (cert != -1 && flag) {
printf("%c%c\n", 'a' + i, uti[cert]);
}
}
if (nosol) puts("noway");
}
int main()
{
//#ifndef ONLINE_JUDGE
freopen("equation.in", "r", stdin);
freopen("equation.out", "w", stdout);
//#endif
input();
prepare();
solve();
//#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
//#endif
return 0;
}