自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 23:07:18，当前版本为作者最后更新于2025-07-14 20:40:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

已知 $m$ 的值，由字符串容易得到 $n$ 的值，结合题目名称以及提示，推测出题人可能想让我们对 $n$ 分解质因数然后想办法 check。但我不会 check，于是就有了本题解中与因数分解毫无关系的暴力解法。

将小朋友互相认识的关系建图，设得到的图为 $\mathcal{G}=\{\mathcal{V}(\mathcal{G}),\mathcal{E}(\mathcal{G})\}$。则题目转化为：

有一个 $a_1\times a_2\times\cdots\times a_k$ 的 $k$ 维超立方体，这些参数均未知。将其分割为棱长为 $1$ 的若干单位超正方体。当且仅当两个单位超正方体有公共面时，在它们之间连边。现给出这个图的结构，求出所有参数。

第一步自然是求出 $k$ 的值。考察不同位置的单位超正方体，发现位于角上的单位超正方体的度数恰好为 $k$，其余的单位超正方体的度数均大于 $k$。因此，只需要统计出每个点的度数，取其中的最小值即可得到 $k$，还可以顺便知道一个位于角上的单位超正方体的编号（记为 $s$）。

我们规定 $s$ 的坐标为 $(1,1,\cdots,1)$。考虑从它开始 BFS，依次确定所有单位超正方体的坐标。设 $\operatorname{dis}(u)$ 为 $s$ 与 $u$ 之间的曼哈顿距离（也就是 BFS 的距离），设 $\operatorname{from}(u)=\{v\in\mathcal{V}(\mathcal{G})\mid\operatorname{dis}(u)=\operatorname{dis}(v)+1\land(u,v)\in\mathcal{E}(\mathcal{G})\}$，两者均可在 BFS 时求得。

每个单位超正方体的坐标可以通过以下方式求得：

• 若 $\operatorname{card}(\operatorname{from}(u))=0$，说明 $u=s$，规定它的坐标为 $(1,1,\cdots,1)$。
• 若 $\operatorname{card}(\operatorname{from}(u))=1$，说明 $u$ 在棱上。设 $\operatorname{from}(u)=\{v\}$，进一步地：
  • 若 $v=s$，则 $u$ 的坐标为 $(1,1,\cdots,2,\cdots,1)$。显然，恰有 $k$ 个这样的 $u$，令它们不为 $1$ 的维度互不相同即可。
  • 否则，$v$ 必定恰有一个不为 $1$ 的维度，将该维度增加 $1$ 并保持其他维度不变即可得到 $u$ 的坐标。
• 若 $\operatorname{card}(\operatorname{from}(u))\ge 2$，则 $u$ 的每一维度均取 $\operatorname{from}(u)$ 中所有元素该维度的最大值。

最后统计所有维度的最大值，排序后输出即可。

一个使得写代码更简单的优化：

• 注意到 $\operatorname{card}(\operatorname{from}(u))\ge 2$ 的所有 $u$ 并不会使得某一维度坐标增加，我们不需要维护出这些单位超正方体的坐标，只需要维护所有 $\operatorname{card}(\operatorname{from}(u))=1$ 的单位超正方体的不为 $1$ 的维度坐标即可。

由于最多有 $(126-32+1)^3=857375$ 个小朋友，把名字与编号对应时，如果用 map 或者 unordered_map 会导致 TLE，直接用数组存就好了。

还有一个坑点，就是 ASCII 为 $32$ 的字符是空格，因此不能用 cin 直接读字符串，需要使用 getline 系列函数。

时间复杂度 $O(n+m)$。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 1e6 + 5, D = 21, A = 126 - 32 + 1;

int m, n, idx[A * A * A], deg[N], dim, coord_key[N], coord_val[N], dis[N], from[N], a[D];
string s;
vector<int> e[N];

inline int getId(string s) {
    return (s[0] - 32) * A * A + (s[1] - 32) * A + (s[2] - 32);
}

void bfs(int s) {
    memset(dis, 0x3f, sizeof(dis));
    int ptr = 1;
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        if(from[u] != -1 && from[u] != 0) {
            int v = from[u];
            if(v == s) {
                coord_key[u] = ptr++;
                coord_val[u] = 2;
            }
            else {
                coord_key[u] = coord_key[v];
                coord_val[u] = coord_val[v] + 1;
            }
            chkmax(a[coord_key[u]], coord_val[u]);
        }
        for(int v: e[u]) {
            if(dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                from[v] = u;
                q.push(v);
            }
            else if(dis[v] == dis[u] + 1) from[v] = -1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> m; cin.ignore();
    getline(cin, s);
    for(int i = 0, j = 3; j < s.size(); i += 6, j += 6) {
        string u_raw = s.substr(i, 3), v_raw = s.substr(j, 3);
        int u_id = getId(u_raw), v_id = getId(v_raw);
        int u = idx[u_id] ? idx[u_id] : idx[u_id] = ++n;
        int v = idx[v_id] ? idx[v_id] : idx[v_id] = ++n;
        // cout << u_raw << "(" << u << ") " << v_raw << "(" << v << ")" << endl;
        e[u].push_back(v);
        e[v].push_back(u);
        ++deg[u];
        ++deg[v];
    }
    // rep(i, 1, n) cout << deg[i] << " \n"[i == n];
    dim = *min_element(deg + 1, deg + 1 + n);
    cout << dim << endl;
    int corner = min_element(deg + 1, deg + 1 + n) - deg;
    bfs(corner);
    sort(a + 1, a + 1 + dim);
    rep(d, 1, dim) cout << a[d] << endl;
    return 0;
}