所有题目都在橙到绿之间。梦回小学。
用一个前驱数组和一个后继数组维护一个类似于链表的结构。
然后每次更改根据题意要求,依次递进地更改结点的前驱 / 后继即可。
namespace XSC062 { using namespace fastIO; const int maxn = 35; char t, t1; int n, x, y; int fa[maxn], so[maxn]; inline void moto(int a, int b) { so[fa[a]] = 0; int x = a, y; while (so[x]) { y = x; x = so[x]; so[y] = 0; } while (x != a) { y = x; x = fa[x]; fa[y] = 0; } x = b; while (so[x]) { y = x; x = so[x]; so[y] = 0; } while (x != b) { y = x; x = fa[x]; fa[y] = 0; } fa[a] = b; so[b] = a; return; } inline void moer(int a, int b) { so[fa[a]] = 0; int x = a, y; while (so[x]) { y = x; x = so[x]; so[y] = 0; } while (x != a) { y = x; x = fa[x]; fa[y] = 0; } x = b; while (so[x]) x = so[x]; fa[a] = x; so[x] = a; return; } inline void pito(int a, int b) { so[fa[a]] = 0; int x = b; while (so[x]) { y = x; x = so[x]; so[y] = 0; } while (x != b) { y = x; x = fa[x]; fa[y] = 0; } fa[a] = b; so[b] = a; return; } inline void pier(int a, int b) { so[fa[a]] = 0; int x = b; while (so[x]) x = so[x]; fa[a] = x; so[x] = a; return; } inline bool check(int x, int y) { while (fa[x]) x = fa[x]; while (fa[y]) y = fa[y]; return x != y; } int main() { scanf("%d", &n); do { scanf("%1s%*s", &t); if (t == 'q') break; scanf("%d %*1s%1s%*s %d", &x, &t1, &y); if (!check(++x, ++y)) continue; if (t == 'm') { if (t1 == 'n') moto(x, y); else moer(x, y); } else { if (t1 == 'n') pito(x, y); else pier(x, y); } } while (1); for (int i = 1; i <= n; ++i) { printf("%d:", i - 1); if (!fa[i]) { x = i; do { printf(" %d", x - 1); x = so[x]; } while (x); } putchar('\n'); } return 0; } } // namespace XSC062
发现题目保证最多循环 \(10^3\) 次,考虑暴力模拟 \(10^3\) 次,若中间任意时刻整个数组为 \(0\),则输出 ZERO
,否则输出 LOOP
。
优化:使用 std::map
或 std::set
存储某个序列是否出现过(可以采用 std::vector
实现),若出现过则输出 LOOP
,不过不优化时间上也完全没有问题,故没有优化。
namespace XSC062 { const int maxn = 25; int T, n; int a[maxn], b[maxn]; inline int abs(int x) { return x >= 0 ? x : -x; } int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int _t = 1; _t <= 1000; ++_t) { a[n + 1] = a[1]; bool flag = 1; for (int i = 1; i <= n; ++i) { b[i] = abs(a[i] - a[i + 1]); if (b[i]) flag = 0; } if (flag) goto ZEROOOOO; memcpy(a, b, sizeof(a)); } puts("LOOP"); continue; ZEROOOOO: puts("ZERO"); } return 0; } } // namespace XSC062
题意:有若干个环,求其大小的最小公倍数,结果对 \(10^9+7\) 取模。
一个典型的错解是,使用 \(x \times y \div \gcd(x,y)\) 与逆元 依次 求最小公倍数,因为取模会改变因子,从而使最大公约数的值 unexpected。
一个好的解决方案是模拟人工计算,将每一个 \(x\) 分解质因数并计算每个质因子最多的出现次数,最后相乘即可。
#define int long long namespace XSC062 { using namespace fastIO; const int mod = 1e9 + 7; const int maxn = 1e5 + 5; int T, n, x, cnt, res, tmp; int a[maxn], u[maxn], p[maxn], tot[maxn]; inline int qkp(int x, int y) { int res = 1; while (y) { if (y & 1) (res *= x) %= mod; (x *= x) %= mod; y >>= 1; } return res; } inline int max(int x, int y) { return x > y ? x : y; } int main() { read(T); while (T--) { cnt = 0; res = 1; read(n); for (int i = 1; i <= n; ++i) { read(a[i]); u[i] = p[i] = tot[i] = 0; } for (int i = 1; i <= n; ++i) { if (p[i]) continue; ++cnt; x = i; do { p[x] = cnt; x = a[x]; ++u[cnt]; } while (x != i); } for (int i = 1; i <= cnt; ++i) { for (int j = 2; j <= u[i]; ++j) { if (u[i] % j) continue; tmp = 0; while (!(u[i] % j)) { ++tmp; u[i] /= j; } tot[j] = max(tot[j], tmp); } } for (int i = 1; i <= n; ++i) (res *= qkp(i, tot[i])) %= mod; printf("%lld\n", res); } return 0; } } // namespace XSC062 #undef int
可以预先计算出共有几行几列。设最大长度为 \(m\),则列数 \(l = \lfloor 62 \div m \rfloor\),行数 \(c = \lceil n \div l \rceil\)。
为什么是 \(62\) 呢?因为有一列要少输出 \(2\) 个空格,为了方便,我们加上这 \(2\) 个空格使得其与其他列统一。
然后模拟行、列增加的过程(枚举行列或枚举字符串均可),最后输出即可。
namespace XSC062 { const int maxn = 505; std::string t; std::string s[maxn]; std::string op[maxn][maxn]; int n, mx, l, c, m, tc, tl; inline int max(int x, int y) { return x > y ? x : y; } int main() { while (std::cin >> m) { mx = 0; n = 0; std::getline(std::cin, t); for (int i = 1; i <= m; ++i) { std::getline(std::cin, t); std::stringstream temp(t); while (temp >> s[++n]) mx = max(mx, s[n].length()); --n; } n = m; std::sort(s + 1, s + n + 1); l = 62 / (mx + 2); c = (n + l - 1) / l; tc = tl = 1; for (int i = 1; i <= c; ++i) { for (int j = 1; j <= l; ++j) op[i][j].clear(); } for (int i = 1; i <= n; ++i) { op[tc++][tl] = s[i]; if (tc == c + 1) { ++tl; tc = 1; } } for (int i = 1; i <= 60; ++i) putchar('-'); putchar('\n'); for (int i = 1; i <= c; ++i) { for (int j = 1; j <= l; ++j) { if (op[i][j].size()) std::cout << op[i][j]; for (int k = s[(j - 1) * c + i].size() + 1; k <= mx; ++k) { putchar(' '); } if (!op[i][j + 1].size()) break; putchar(' '); putchar(' '); } putchar('\n'); } } return 0; } } // namespace XSC062
一个简单的对齐输出。简单到我认为没有可讲的。
namespace XSC062 { const int maxn = 1e4 + 5; int n, lin; int mx[maxn]; std::string t, t1; std::vector<std::string> s[maxn]; inline int max(int x, int y) { return x > y ? x : y; } int main() { while (std::getline(std::cin, t)) { ++lin; s[lin].clear(); // s[lin].shrink_to_fit(); std::stringstream temp(t); int cnt = 0; while (temp >> t1) { s[lin].push_back(t1); ++cnt; mx[cnt] = max(mx[cnt], t1.length()); } } for (int i = 1; i <= lin; ++i) { for (int j = 0; j < (int)s[i].size(); ++j) { std::cout << s[i][j]; for (int k = s[i][j].size() + 1; k <= mx[j + 1] + 1; ++k) putchar(' '); } putchar('\n'); } return 0; } } // namespace XSC062
难点在于判断一个数为整数还是浮点数。
令某个存储了一整个数的字符串为 \(s\)。
不难发现,当 \(|s|\le 3\) 时,\(s\) 一定表示一个整数。
否则,若 \(s\) 表示整数,则位数 \(>3\),至少分一段,此时 \(s_{|s|-4}\) 为 .
(从 \(0\) 开始存储)。
其余情况,\(s\) 为浮点数。
namespace XSC062 { using namespace fastIO; bool f; char inp; std::string s, t; int x, y, tx, ty, cnt; int main() { std::getline(std::cin, s); s.push_back('#'); std::stringstream temp(s); while (temp >> inp) { if (inp >= '0' && inp <= '9') { std::string tmp; tx = ty = 0; do tmp.push_back(inp); while (temp >> inp && ((inp >= '0' && inp <= '9') || inp == '.')); if (tmp.size() <= 3) tx = std::stoi(tmp); else if (tmp[tmp.size() - 4] == '.') { for (auto i : tmp) { if (i >= '0' && i <= '9') tx = tx * 10 + i - '0'; } } else { for (int i = 0; i < (int)tmp.size() - 2; ++i) { if (tmp[i] >= '0' && tmp[i] <= '9') tx = tx * 10 + tmp[i] - '0'; } ty = (tmp[tmp.size() - 2] - '0') * 10 + tmp[tmp.size() - 1] - '0'; } x += tx; y += ty; } } x += y / 100; y %= 100; if (!x) t.push_back('0'); while (x) { t.push_back((x % 10) + '0'); x /= 10; } std::reverse(t.begin(), t.end()); cnt = t.length(); for (const auto &i : t) { putchar(i); if (!((--cnt) % 3)) { if (cnt) putchar('.'); } } if (y) { putchar('.'); if (y < 10) putchar('0'); std::cout << y; } return 0; } } // namespace XSC062