首页 > 代码库 > Wow! Such String!
Wow! Such String!
题目链接
- 题意:
给一个n,输出一个长度为n的字符串,使得串中任意相连四个字符组成的串不重复N (1 ≤ N ≤ 500000) - 分析:
const int MAXV = 18278; const int MAXE = 475228; struct Edge { int from, to; }; struct Direct_Euler { int n, m; int out[MAXV]; bool vis[MAXE]; vector<int> G[MAXV]; vector<Edge> edges; stack<int> sk; vector<int> ans; void init(int n) { this->n = n; edges.clear(); REP(i, n) { out[i] = 0; G[i].clear(); } } void addEdge(int a, int b) { edges.push_back((Edge) { a, b }); m = edges.size(); G[a].push_back(m - 1); out[a]++; out[b]--; } void dfs(int u, int ind) { REP(i, G[u].size()) { int x = G[u][i]; Edge& e = edges[x]; if (!vis[x]) { vis[x] = true; dfs(e.to, x); } } if (ind >= 0) sk.push(ind); } //返回1:欧拉回路 返回2:欧拉路经 int solve(int s) { int cnt = 0; ans.clear(); REP(i, n) { if (out[i] == 1) { if (++cnt > 1) { return 0; } s = i; } else if (out[i] > 1 || out[i] < -1) return 0; } while (!sk.empty()) sk.pop(); REP(i, m) vis[i] = false; dfs(s, -1); REP(i, m) if (!vis[i]) return 0; while (!sk.empty()) { ans.push_back(sk.top()); sk.pop(); } return cnt != 0 ? 1 : 2; } } graph; char x[456979], tot = 0; int main() { int size = 29 << 20; // 29MB char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p)); graph.init(18278); REP(i, 26) REP(j, 26) REP(k, 26) REP(l, 26) graph.addEdge(i * 676 + j * 26 + k, j * 676 + k * 26 + l); graph.solve(0); vector<int>& ans = graph.ans; int tot = 0; int to = graph.edges[ans[0]].from; x[tot++] = to / 676 + 'a'; to %= 676; x[tot++] = to / 26 + 'a'; to %= 26; x[tot++] = to + 'a'; REP(i, ans.size()) x[tot++] = graph.edges[ans[i]].to % 26 + 'a'; int n; while (~RI(n)) { if (n > tot) puts("Impossible"); else { REP(i, n) printf("%c", x[i]); puts(""); } } return 0; }
其实,如果没有想到是欧拉回路问题,暴力也是可以试试的,懊悔当时没写出来,祭奠一下。。
const int MAXN = 1000000; bool vis[26][26][26][26]; int x[MAXN]; int tot; int main() { tot = 0; REP(i, 26) { x[tot + 3] = x[tot + 2] = x[tot + 1] = x[tot] = i; tot += 4; } FF(i, 3, tot) vis[x[i]][x[i - 1]][x[i - 2]][x[i - 3]] = 1; bool flag = true; while (flag) { flag = false; REP(i, 26) { if (!vis[i][x[tot - 1]][x[tot - 2]][x[tot - 3]]) { vis[i][x[tot - 1]][x[tot - 2]][x[tot - 3]] = 1; x[tot++] = i; flag = true; } } } int n; while (~RI(n)) { if (n > tot) puts("Impossible"); else { REP(i, n) printf("%c", x[i] + 'a'); puts(""); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。