<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1293.夏洛克和他的女朋友
夏洛克有了一个新女友(这太不像他了!)。
情人节到了,他想送给女友一些珠宝当做礼物。
他买了 $n$ 件珠宝,第 $i$ 件的价值是 $i+1$,也就是说,珠宝的价值分别为 $2,3,…,n+1$。
华生挑战夏洛克,让他给这些珠宝染色,使得一件珠宝的价格是另一件珠宝的价格的质因子时,两件珠宝的颜色不同。
并且,华生要求他使用的颜色数尽可能少。
请帮助夏洛克完成这个简单的任务。
输入格式
只有一行一个整数 $n$,表示珠宝件数。
输出格式
第一行一个整数 $k$,表示所使用的颜色数;
第二行 $n$ 个整数,表示第 $1$ 到第 $n$ 件珠宝被染成的颜色。
若有多种答案,输出任意一种。
请用 $1$ 到 $k$ 表示你用到的颜色。
数据范围
$1 \le n \le 10^5$
这题显然是个 构造题,观察样例容易猜出 颜色个数最优为 $2$ (当 $3 \le n$)
证明如下:
具体来说,对于每个 $3 \le n$,我们枚举第 $i$ 枚珠宝
- 如果 $i + 1$ 为 质数,给这个珠宝涂上颜色 $1$
- 如果 $i + 1$ 不是质数,给这个珠宝涂上颜色 $2$
如果这种方案不符合题意,那么一定有两个数 $a, b$ 不满足题意,而两个数一个是质数,一个是合数,所以颜色一定不同,矛盾!
显然,对于每个大于 $3 \le n$,只用一种颜色会使第一件宝物和第三件的宝物颜色相同,不符合题意。
综上,当 $3 \le n$ 时,最优情况就是用两种颜色
当 $n = 2$ 时需要 特判,具体细节见代码
c++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000009;
int n, prime[N];
int cnt;
bool v[N];
void get_prime(int n)
//线性筛函数,n 表示一共要筛几个数
{
v[1] = true;
//1 显然不是质数
for (int i = 2; i <= n; ++ i)
//枚举所有小于等于 n 的数
//因为一个数的最小质因子显然小于等于这个数,所以
//我们从小到大枚举 i
{
if (!v[i]) prime[cnt ++] = i;
//如果数 i 已经没有被更新过了,那么这个数就是
//质数,所以 prime 数组增加这个质数
for (int j = 0; prime[j] <= n / i; ++ j)
//从小到大枚举所有已知质数
{
v[prime[j] * i] = true;
//显然,prime[j] * i 是一个合数
if (i % prime[j] == 0) break;
//如果 i % primes[j] == 0,primes[j] 一定是
//i 的最小质因子 (因为是从小到大遍枚举 j)
//primes[j] 一定是 primes[j] * i 的最小质因子
//如果 i % primes[j] != 0,primes[j] 一定是
//小于 i 的所有质因子,primes[j] 也一定是
//primes[j] * i的最小质因子
}
}
}
int main()
{
cin >> n;
get_prime(n + 1);//线性筛求素数,注意价值的范围,至少筛 n + 1 个
if(n > 2) cout << 2 << endl;//注意特殊情况
else cout << 1 << endl;
for (int i = 2; i <= n + 1; ++ i)//注意价值从 2 开始算
{//详见解析
if (!v[i]) cout << 1 << " ";//如果是质数
else cout << 2 << " ";//如果不是质数
}
return 0;
}
哇,高质量呀!
清晰的,赞~