刚学OI 1分钟的萌新求 hack
查看原帖
刚学OI 1分钟的萌新求 hack
275273
EuphoricStar楼主2021/2/3 10:15

如题,实在找不出问题了,但是还是 WA

uDebug 上面的数据都试过了,没有问题,求大佬们 hack

#include <bits/stdc++.h>
using namespace std;

string line;
int n, ansb, pos[128];
char a[10], ans[10];
vector<char> edges[128];

int main() {
    ios::sync_with_stdio(0);
    while (cin >> line && line[0] != '#') {
        memset(pos, 0, sizeof(pos));
        for (int i = 0; i < 128; ++i) {
            edges[i].clear();
        }
        n = 0;
        ansb = 10;
        if (line[line.size() - 1] != ';') {
            line.push_back(';');
        }
        stringstream ss(line);
        string g, nodes;
        set<char> snodes;
        while (getline(ss, g, ':')) {
            getline(ss, nodes, ';');
            snodes.insert(g[0]);
            for (int i = 0; i < nodes.size(); ++i) {
                char v = nodes[i];
                edges[g[0]].push_back(v);
                edges[v].push_back(g[0]);
                snodes.insert(v);
            }
        }
        n = snodes.size();
        for (int i = 0; i < n; ++i) {
            a[i] = 'A' + i;
            ans[i] = 0;
        }
        do {
            memset(pos, 0, sizeof(pos));
            int maxb = 0;
            for (int i = 0; i < n; ++i) {
                pos[a[i]] = i;
            }
            for (int i = 0; i < n; ++i) {
                char u = 'A' + i;
                for (int j = 0; j < edges[u].size(); ++j) {
                    char v = edges[u][j];
                    maxb = max(maxb, abs(pos[u] - pos[v]));
                }
            }
            if (maxb < ansb) {
                ansb = maxb;
                for (int i = 0; i < n; ++i) {
                    ans[i] = a[i];
                }
            }
        } while (next_permutation(a, a + n));
        for (int i = 0; i < n; ++i) {
            cout << ans[i] << ' ';
        }
        cout << "-> " << ansb << endl;
    }
    return 0;
}
2021/2/3 10:15
加载中...