牛客多校第六场 A 题题解

A Array

题意：给定长度为 $nn$ 的序列 $\{a_n\}\backslash \{a\_n\backslash \}$。现构造一个序列 $\{b_m\}\backslash \{b\_m\backslash \}$，令 $\{c\}\backslash \{c\backslash \}$ 为 $\{b_m\}\backslash \{b\_m\backslash \}$ 序列的无穷拼接，要求 $\{c\}\backslash \{c\backslash \}$ 中每连续 $a_{i}a\_i$ 个数字就得出现一次 $ii$。要求 $\{b_m\}\backslash \{b\_m\backslash \}$ 序列长度 $m\le 1\times 10^{6}m\backslash leq\; 1\backslash times\; 10^6$。

解法：设最终长度为 $MM$。首先注意到，对于每个数字，最少填放次数为 $\lceil {\displaystyle \frac{M}{a_i}}\rceil \backslash left\; \backslash lceil\; \backslash dfrac\{M\}\{a\_i\}\backslash right\; \backslash rceil$，因而理论上满足 ${\displaystyle \sum _{i=1}^n\lceil \frac{M}{a_i}\rceil \le M}\backslash displaystyle\; \backslash sum\_\{i=1\}^n\; \backslash left\; \backslash lceil\; \backslash dfrac\{M\}\{a\_i\}\backslash right\; \backslash rceil\; \backslash leq\; M$ 即可保证有解，可推出即 ${\displaystyle \sum _{i=1}^n\frac{1}{a_i}\le 1}\backslash displaystyle\; \backslash sum\_\{i=1\}^n\; \backslash dfrac\{1\}\{a\_i\}\backslash leq\; 1$。此题条件更为苛刻：${\displaystyle \sum _{i=1}^n\frac{1}{a_i}\le \frac{1}{2}}\backslash displaystyle\; \backslash sum\_\{i=1\}^n\; \backslash dfrac\{1\}\{a\_i\}\backslash leq\; \backslash dfrac\{1\}\{2\}$，暗示可能需要对 $a_{i}a\_i$ 进行适当的缩小，至多可以缩小到原来的一半。

因而可以考虑这样的构造：令 $M=2^{k}M=2^k$，$\mathrm{\forall }i\in [1,n]\backslash forall\; i\; \backslash in\; [1,n]$，$a_i^{\mathrm{\prime }}\leftarrow 2^{j}a\_i\text{'}\; \backslash leftarrow\; 2^j$，其中 $2^{j}2^j$ 为小于等于 $a_{i}a\_i$ 的最大值。这样 ${\displaystyle \sum _{i=1}^n\frac{1}{a_i^{\mathrm{\prime }}}\le 1}\backslash displaystyle\; \backslash sum\_\{i=1\}^n\; \backslash dfrac\{1\}\{a\_i\text{'}\}\backslash leq\; 1$。同时，由于 $a_i^{\mathrm{\prime }}\mathrm{\mid }Ma\_i\text{'}|M$，因而不会出现多个数字都要填在同一处导致某些数字需要出现的更多以满足条件，从小到大的对 $a_i^{\mathrm{\prime }}a\_i\text{'}$ 进行填放。即可。实际操作中可取 $M=2^{19}M=2^\{19\}$。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000, M = 1 << 19;
pair<int, int> a[N + 5];
int ans[M + 5];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n;i++)
	{
		scanf("%d", &a[i].first);
		a[i].second = i;
		for (int j = 20; j >= 0;j--)
			if (a[i].first >> j & 1)
			{
				a[i].first = 1 << j;
				break;
			}
	}
	sort(a + 1, a + n + 1);
	int now = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = now; j <= M; j += a[i].first)
			ans[j] = a[i].second;
		while (ans[now])
			now++;
	}
	printf("%d\n", M);
	for (int i = 1; i <= M;i++)
		printf("%d ", !ans[i] ? 1 : ans[i]);
	return 0;
}