Numb 题解

前言

五一网课的例题，但是网上没有题解，所以来写一篇，就当攒 RP 了。题目可以在这里提交。原题是 Baekjoon - 19083，但是交不了？

题目简述

给你一个偶数 \(n\)，求一个二进制数 \(x=\overline {a_1 a_2 \dots a_n}\)，满足：

1. \(x \equiv 0 \pmod{n}\)；
2. \(\forall i \in [1, n]\)，\(\overline {a_1 a_2 \dots a_i} \bmod n\) 互不相同；
3. 不含有前导 \(0\)。

题目分析

代码

#include <cstdio>
#include <cstring>
#pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
typedef unsigned int uint;

uint t, n, m, top;

bool vis[3000001][2];
bool ans[6000001];

inline uint add(uint a, uint b){
	a += b;
	return a >= m ? a - m : a;
}

inline void dfs(uint now){
	if (!vis[now][1]){
		vis[now][1] = true;
		dfs(add(now, now + 1));
		ans[++top] = 1;
	}
	if (!vis[now][0]){
		vis[now][0] = true;
		dfs(add(now, now));
		ans[++top] = 0;
	}
}

inline void solve(){
	scanf("%ud", &n), m = n >> 1, memset(vis, 0, sizeof (bool) * (n)), top = 0, dfs(0);
	for (register int i = top; i; --i) putchar(ans[i] | 48);
	putchar('\n');
}

signed main(){
	for (scanf("%ud", &t); t--; solve());
	return 0;
}

checker.cpp

#include "testlib.h"
#include <vector>

signed main(int argc, char* argv[]) {
	registerTestlibCmd(argc, argv);

	int t = inf.readInt();

	while (t--) {
		int n = inf.readInt();
		std::vector<bool> vis(n, false);
		std::string str = ouf.readLine();
		
		if (int(str.length()) != n) quitf(_wa, "You're too long or too short!");

		for (int i = 1, now = 0; i <= n; ++i) {
			char ch = str[i - 1];
			
			if (ch != '0' && ch != '1') quitf(_wa, "Read '%c' not 0 or 1!", ch);
			
			if (i == 1 && ch == '0') quitf(_wa, "There mustn't be any leading zeros!");
			
			now = (now << 1 | (ch ^ 48)) % n;

			if (vis[now]) quitf(_wa, "Found %d again!", now);
			vis[now] = true;

			if (i == n && now != 0) quitf(_wa, "The number is not divisible by n!");
		}
	}

	ouf.readEof();

	quitf(_ok, "I love yzh!");

	return 0;
}