Chladni Figure

RegisterFault · 2023-08-10 16:51:05 · 题解

简述题意

在圆环上均匀分布 n 个点，有 m 条线段，每条线段的端点都在圆上。求该图形是否为旋转对称图形。

题目分析

首先暴力算法就是枚举旋转多少，然后检查旋转后的图形和原图形是否相等即可。这样的时间复杂度显然是 O(n ^ 2) 的，无法通过。

然后可以发现题目有一个性质：设旋转了 x 个单位，则 x 一定是 n 的约数。因为考虑如果旋转 x 之后，则旋转 kx 之后也一定重合。

所以就可以暴力枚举 x 的所有约数，旋转之后暴力 check 即可。

关于本题的时间：我们可以将每条线段用类似字符串哈希的方式转化成整数，然后开一个哈希表存储。这样时间复杂度就是 O(n \times \sigma_0 (n))。

#include <unordered_map>
#include <iostream>
#include <cstring>
#include <cstdio>
#define a first
#define b second

using namespace std;

const unsigned long long P = 998244353;
const int N = 500010;
using PII = pair<int, int>;
using ULL = unsigned long long;
PII p[N]; int n, m;
unordered_map<ULL, bool> Map;
ULL get(PII x) {
    return (1ull * x.first * P + 1ull * x.second);
}
bool check(int x) {
    if (x == n) return false;
    for (int i = 1; i <= m; i ++ ) {
        if (!Map.count(get({(p[i].a + x) % n, (p[i].b + x) % n})))
            return false;
    } return true;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++ ) {
        scanf("%d%d", &p[i].a, &p[i].b);
        p[i].a -- , p[i].b -- ;
        Map[get(p[i])] = true;
        PII tmp = {p[i].b, p[i].a};
        Map[get(tmp)] = true;
    }
    for (int i = 1; i <= n / i; i ++ ) {
        if (n % i == 0) {
            if (check(i)) return puts("Yes"), 0;
            if (check(n / i)) return puts("Yes"), 0;
        }
    } return puts("No"), 0;
}

截止到 2023.08.10 是最优解。