2017–2018, NEERC, Northern Subregional Contest

题目连接：https://codeforces.com/gym/101612

E. Equal Numbers

题目 ：

给你一个序列，一次操作是选一个数，使其变为自己的任意倍数，问0~n

次操作后，这个序列数的最小种类为多少。每次操作不用在前面操作后的状态操作。

题解：

很容易想到，按数的个数排序，个数少的在前面，每个数都变为全部数的lcm(最小公倍数)，次数好像是最小。但有一种情况，比如 3，6。此时3变为18需要一次操作，操作后种类还是2。而如果3变为6，则种类为1。也就是说，如果对于一个数，它的倍数存在，那在一开始，变为他的倍数，操作次数可以少一次。暂时称这类数为V1。

如果说，一开始已经有数字变为lcm了，那V1变为lcm还是变它的倍数，实际是一样的。也就是说，V1影响的是一开始的操作，所以在求出所有的数都转为lcm后，再用V1在操作次数为0开始，变为他的倍数的策略去更新答案。

AC代码:

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <string>
#include <cmath>
#include <ctime>
#include <queue>
#include<stack>
#include <map>
#include <set>
#include<fstream>
#define lowbit(x) x&(-x)
using namespace std;
typedef  long long ll;
const int N = 1e6 + 5;
const int INF =0x3f3f3f3f;
int num[N],dp[N];//dp记录操作i次的最少种类
vector<int>V[2];
int main()
{
   freopen("equal.in", "r", stdin);
   freopen("equal.out", "w", stdout);
   int n,x,sum,time;
   sum = 0;
   scanf("%d",&n);
   for (int i = 0; i < n; i++) {
   	scanf("%d",&x);
   	if (!num[x])
   		sum++;//记录一开始种类
   	num[x]++;
   }
   fill(dp, dp + n+1, sum);
   for (int i = 1; i < N; i++) {
   	if (num[i]) {
   		V[0].push_back(num[i]);//存全部数
   		for (int j = i * 2; j < N; j += i) {
   			if (num[j]) {
   				V[1].push_back(num[i]);//题解的V1
   				break;
   			}
   		}
   	}
   }
   //按个数排序
   sort(V[0].begin(), V[0].end());
   sort(V[1].begin(),V[1].end());
   time = 0;
   for (int i = 0; i < V[0].size(); i++) {//变为lcm，注意i是从0开始，不用再加一
   	time +=V[0][i];
   	dp[time] = min(dp[time],sum-i);
   }
   time = 0;//从零开始
   for (int i = 0; i < V[1].size(); i++) {//变为倍数的策略，操作 i 块的次数就减少 i 块。
   	time += V[1][i];
   	dp[time] = min(dp[time], sum - i-1);
   }
   printf("%d ",sum);
   for (int i = 1; i <= n; i++) {
   	dp[i] = min(dp[i], dp[i - 1]);
   	printf("%d%c",dp[i],i==n?'\n':' ');
   }
   return 0;
}
           

L. Little Difference

题目：

把一个数n，拆成某些数相加，这些拆成的数相差小于等于1.输出所有方案。

题解：

很容易想到单独用 i 或者用 i 和 i+1 去分解n，但看了下数据范围1e18，意味着时间复杂度为1e9，超时。

这道题很有意思，你会发现，分解成两个数只有一种情况，就是 sqrt(n) 和 n/sqrt(n) （向下取整）这两个数。分解成三个数就是开三次方了，也就是在三个数的时候，直接算复杂度也就1e6*logn，可以接受。

还有个地方要注意的，比如 9 ，在 i=2时，用 i 和 i+1 去分解得到 3，3 。那么在算 i=3时就重复了，所以要在算之前，判定n%i==0。

AC代码：

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <string>
#include <cmath>
#include <ctime>
#include <queue>
#include<stack>
#include <map>
#include <set>
#include<fstream>
#define lowbit(x) x&(-x)
using namespace std;
typedef  long long ll;
typedef  long long LL;
const int N = 5e4 + 5;
const ll INF =1e17;
const int mod = 1000000007;
int main()
{
	freopen("little.in", "r", stdin);
	freopen("little.out", "w", stdout);
	ll n,sq,cnt;
	scanf("%lld",&n);
	if (n == (n & (-n))) {
		printf("-1\n");
		exit(0);
	}
	vector<ll>V[100];
	cnt = 0;
	sq = floor(sqrt(n));
	V[cnt++].push_back(n);
	if (n%sq == 0&&sq!=1) {//两个的情况
		V[cnt].push_back(sq);
		V[cnt++].push_back(n/sq);
	}
	for (int i = 2; i <= 1000005&&i<sq; i++) {
		ll num = n;
		if (n%i == 0) {//这里的判定体会一下，防止重复。
			while (num%i == 0)
				V[cnt].push_back(i), num /= i;
			while (num % (i + 1) == 0)
				V[cnt].push_back(i + 1), num /= i + 1;
		}
		if (num == 1)
			cnt++;
		else
			V[cnt].clear();
	}
	printf("%d\n",cnt);
	for (int i = 0; i < cnt; i++) {
		printf("%d ",V[i].size());
		for (int j = 0; j < V[i].size(); j++) {
			printf("%lld%c",V[i][j],j==V[i].size()-1?'\n':' ');
		}
	}
	return 0;
}