Codeforces 1161B（判断旋转对称）

要点

外层暴力枚举转的“角度”，会发现肯定是n的约数
对于m条线段想判定当前的“角度”是否ok，每个线段只要管它自己的下一个即可，不必画个圈遍历一遍
之后将本来的线段集合和当前需要的线段集合比较，如果相同则该图形旋转对称
一个小优化是只需要枚举n的质约数，质约数d含义为把圆划分成d份。这样划分成6份根本不必要枚举，如果6份行的话，2份的时候就跑出去了；如果6份不行的话……所以就不用枚举它呀～

const int maxn = 1e5 + 5;

int n, m;

vector<pii> p;

vector<int> d;

void pre(int n) {

	for (int i = 2; i <= n; i++) {

		if (n % i)	continue;

		d.emplace_back(i);

		while (n % i == 0)	n /= i;

	}

}

int main() {

	read(n), read(m);

	pre(n);

	for (int i = 1, a, b; i <= m; i++) {

		read(a), read(b);

		a--, b--;

		if (a > b)	swap(a, b);

		p.emplace_back(a, b);

	}

	sort(All(p));

	for (int x : d) {

		int k = n / x;

		vector<pii> t;

		rep(i, 0, m - 1) {

			int a = p[i].first, b = p[i].second;

			a = (a + k) % n, b = (b + k) % n;

			if (a > b)	swap(a, b);

			t.emplace_back(a, b);

		}

		sort(All(t));

		if (p == t) {

			puts("Yes"); return 0;

		}

	}

	puts("No");	return 0;

}

巴特西

Codeforces 1161B（判断旋转对称）

要点

最新文章

热门文章