AT2142 [ARC062E] AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

博主： tony102
发布时间：2020 年 11 月 26 日
1098 次浏览
暂无评论
638字数
分类：题解

[Link](https://www.luogu.com.cn/problem/AT2142)

## Sol

事实上确定一个立方体只需要确定上下两个面就可以了(这样子每个角的颜色就唯一确定了)

讨论一下不同情况的瓷砖

一块瓷砖有可能四个角颜色都相同,那么它随意旋转都可以对答案贡献$1$, 所以这种瓷砖的贡献是$4$

一块形似$aabb$的瓷砖,也就是每次旋转$180\circ$ 颜色相同, 那么它对答案的贡献是 $2$

如果都不相同对答案的贡献就是 $1$

考虑统计答案的方式,我们每次枚举上下两个面,那么随之其他面也被确定

可以用一个哈希表,把一种瓷砖本身\旋转和全部倒过来的都存进哈希表,每次取出两个面的时候乘法原理算一下答案即可

## Code

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

#define int long long

const int SIZE = 5e2 + 5;
const int key = 2002;
const int mod = 998244853;

int n, ans;
int hsh[SIZE], p[5], q[5];

std::unordered_map < int, pair < int, int > > s;

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

inline int getHash(int a, int b, int c, int d) {
	return a * key * key * key + b * key * key + c * key + d;
}

namespace tony102 {
	inline int swap(int x) { 
		return x % (key * key) * key * key + x / key / key;
	}

inline int reverse(int x) {
		return x % key * key * key * key + x / key;
	}

inline int min(int x) {
		int t = swap(x);
		return std::min(std::min(t, x), std::min(reverse(t), reverse(x)));
	}
}

inline int getVal(int x, int opt) {
	return x / q[opt] % key;
}

inline void solve(int x, int y, int tim) {
	p[1] = tony102::min(getHash(getVal(x, 1), getVal(y, 2), getVal(y, 1), getVal(x, 2)));
	if (!s[p[1]].second) return;
	p[2] = tony102::min(getHash(getVal(x, 2), getVal(y, 1), getVal(y, 4), getVal(x, 3)));
	if (!s[p[2]].second) return;
	p[3] = tony102::min(getHash(getVal(x, 3), getVal(y, 4), getVal(y, 3), getVal(x, 4)));
	if (!s[p[3]].second) return;
	p[4] = tony102::min(getHash(getVal(x, 4), getVal(y, 3), getVal(y, 2), getVal(x, 1)));
	if (!s[p[4]].second) return;
	int cnt = 1;
	for (int i = 1; i <= 4; ++ i) {
		cnt = (s[p[i]].first * s[p[i]].second) * cnt;
		-- s[p[i]].second;
	}
	for (int i = 1; i <= 4; ++ i) ++ s[p[i]].second;
	cnt = cnt * tim;
	ans = (ans + cnt);
}

signed main() {
	// freopen("intermezzo.in", "r", stdin);
	// freopen("intermezzo.out", "w", stdout);
	n = read(), q[4] = 1;
	for (int i = 3; i; -- i) q[i] = q[i + 1] * key;
	for (int i = 1, c0, c1, c2, c3; i <= n; ++ i) {
		c0 = read(), c1 = read(), c2 = read(), c3 = read();
		int h = getHash(c0, c1, c2, c3);
		h = tony102::min(h);
		if (h == tony102::reverse(h)) s[h].first = 4;
		else {
			if (h == tony102::swap(h)) s[h].first = 2;
			else s[h].first = 1;
		}
		++ s[h].second, hsh[i] = h;
	}
	for (int i = 1; i < n - 2; ++ i) {
		-- s[hsh[i]].second;
		for (int j = i + 1; j <= n; ++ j) {
			-- s[hsh[j]].second;
			if (s[hsh[i]].first == 1) {
				solve(hsh[i], hsh[j], 1);
				solve(hsh[i], tony102::reverse(hsh[j]), 1);
				solve(hsh[i], tony102::swap(hsh[j]), 1);
				solve(hsh[i], tony102::reverse(tony102::swap(hsh[j])), 1);
			}
			else if (s[hsh[i]].first == 2) {
				solve(hsh[i], hsh[j], 2);
				solve(hsh[i], tony102::reverse(hsh[j]), 2);
			}
			else if (s[hsh[i]].first == 4) solve(hsh[i], hsh[j], 4);
			++ s[hsh[j]].second;
		}
	}
	printf("%lld\n", ans);
	return 0;
}
```

最后修改：2021 年 09 月 04 日