2021牛客寒假算法基础集训营2

2021牛客寒假算法基础集训营2的补题记录

F.牛牛与交换排序

链接：https://ac.nowcoder.com/acm/contest/9982/F
来源：牛客网

题目描述

牛牛有一个数组，数组元素是 1 到 n 的排列，即数组的值在 1 ∼ n 范围内，且每个数字仅出现 1 次。
牛牛想要将该数组变为升序排列的，他可以进行如下的操作。

首先他要确定一个长度 k ，k 的范围在 1 ∼ n 之间。
接下来他将会进行若干次操作。在每轮操作中他都可以选择一段长度为k的子数组，然后进行区间的翻转操作。

他可以做任意次数的操作，但是要求他每次选择的子数组区间满足 li <= li+1，并且区间长度等于一开始选定的 k ，也就是说一旦某一次操作选择了数组的某个位置进行区间翻转操作，下一次做区间翻转的位置将会比上一次更靠右。

牛牛发现，并不总是存在一个 k 可以使得数组排序变为有序，请你告诉牛牛是否存在一个 k 能够在满足规则的情况下完成排序。

输入描述:

第一行输入一个正整数 n ( 1 ≤ n ≤ 10^5 ) 表示数组的大小。
接下来输出一行 n 个正整数表示一个排列，即每个数的大小范围在 1 到 n 且每个正整数仅出现一次。

输出描述:

如果存在至少一个 k 能够使牛牛完成排序，请先在一行中输出一个 “yes”，然后另起一行输出一个可以满足排序的k，要求k的范围在 [ 1 , n ] 之间，如果有多解，你可以输出任意一个。

反之如果不存在任何一个k可以完成排序，请直接在一行输出一个”no”

示例1

输入

5
5 2 1 4 3
1
2

输出

yes
3
1
2

示例2

输入

5
1 2 3 4 5
1
2

输出

yes
1
1
2

示例3

输入

5
5 4 3 2 1
1
2

输出

yes
5

思路：

首先，我们应该如何找到k。由于我们最后要得到的是一个排序好的数列，所以如果这个数列可以成功排序的话，对于1位置上的数来说一定是1，那么第一次交换一定得让1回到1这个位置上去，所以k的大小就是数字1的下标距离1的差值。如果，1就在1这个位置上的话，那么我们判断2，或者更大的数字来确定k的值。

之后我们如何判断这个k是否可以完成排序呢。我们只需要遵守题目中的规则然后去模拟就可以了。如果模拟到底发现可以排序成功那么就可以，反之则不行。

但是我们可以想到的是，单纯模拟的话时间复杂度起码是n^2以上的，所以我们有什么好一点的方法优化这个时间吗？答案当然是有的，我们可以通过反转标记和双端队列的方式来优化这个模拟的过程。

这个过程就是，维护一个长度为k的双端队列，表示如果下一次进行翻转，会受到影响的那些数字，然后从头开始进行模拟，如果i和队列头或者尾的数字相同，那么让他出队然后在反方向上将新的数字入队，维持这一操作直到全部数字出队或者出现无法复位的数字时停止即可。

代码：

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 8;
int n, k , flag = 0;
int a[N], pos[N];
deque<int> q;

int main() {
	cin >> n;
	for (int i=1;i<=n;++i) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	for (int i=1;i<=n;++i) {
		if (pos[i] != i) {
			k = pos[i] - i + 1;
			break;
		}
	}
	if (!k)  {
		cout << "yes\n" << 1;
		return 0;
	}
	for (int i=1;i<=k;++i)	q.push_back(a[i]);
	for (int i=1+k;i<=n+k;++i) {
		if (!(flag % 2)) {
			if (i - k == q.front())	q.pop_front();
			else if(i - k == q.back())	flag ^= 1, q.pop_back();
			else {
				cout << "no";
				return 0;
			}
		}
		else if (flag % 2){
			if (i - k == q.back())	q.pop_back();
			else if (i - k == q.front())	flag ^= 1, q.pop_front();
			else {
				cout << "no";
				return 0;
			}
		}
		if (i <= n) {
			if (flag % 2)	q.push_front(a[i]);
			else	q.push_back(a[i]);
		}
	}
	cout << "yes\n" << k;
	return 0;
}

I: 牛牛的“质因数”

链接：https://ac.nowcoder.com/acm/contest/9982/I
来源：牛客网

题目描述

算数基本定理，又称唯一分解定理，算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。
朴素的质因子分解算法就是利用了算数基本定理，依次枚举p判断N是否包含素因子p。

牛牛最近对于质因数分解产生了浓厚的兴趣。

牛牛定义了一个函数F(x)，它表示将x做质因数分解后得到的数字从小到大升序排列，然后将其“拼接”成一个大整数。
例如1500=22355*5,F(1500)=223555。
牛牛现在想要知道∑(n, 2)F(i)的值。

由于这个结果非常大，所以你只用告诉牛牛最终答案对10^9 + 7取余数的结果即可。

输入描述:

仅一行一个正整数n(2 ≤ n ≤ 4×10^6)

输出描述:

仅一行，表示答案对10^9+7取余数的结果。

示例1

输入

3

输出

5

说明

示例2

输入

10

输出

342

说明

F(2)=2
F(3)=3
F(4)=22
F(5)=5
F(6)=23
F(7)=7
F(8)=222
F(9)=33
F(10)=25
2+3+22+5+23+7+222+33+25=342

思路

这道题的思路其实就是题中所说的进行模拟即可，素数筛法选择快一点的筛子，用线性筛O（n）的时间复杂度，然后维护一个 f[i] 数组即可。可以叫做：筛法DP。其中有一个细节需要注意的是写了两次都被卡到的一个点。对一个数进行数的长度处理的时候还进行了取模运算，这个时候之前的数字的长度其实是不准的。需要用一个数组将这些数据记录下来。

注意：并不是在模运算下不出现除法得到的结果就一定是正确的了，还要考虑一个数取模之后长度的变化问题。

代码：

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int maxn = 4e6 + 10;
const int mod = 1e9 + 7;
ll n, ans;
ll prime[maxn], size = 0;
ll f[maxn];
ll P[maxn];
bool vis[maxn]; 
ll F(ll x) {
	int c = 0;
	while(x) x /= 10, c++;
	return c;
}
ll power(ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = ll(res * a % mod);
		a = ll(a * a % mod); 
	}
	return res;
}
void init() {
    memset(vis, true, sizeof(vis));
    memset(prime, 0, sizeof(vis));
    vis[1] = false;
    for (ll i=2;i<=n;++i) {
        if (vis[i]) {
			prime[++size] = i;
			f[i] = i;
			P[i] = F(i);
		}
        for (ll j=1;j<=size&&i*prime[j]<=n;++j) {
          	vis[i * prime[j]] = false;
          	int p = P[i];
            f[i * prime[j]] = ((prime[j] * power(10, p) % mod) % mod + f[i]) % mod;
        	P[i * prime[j]] = F(prime[j]) + P[i];
            if (i % prime[j] == 0)	break;
        }
    }
}

int main() {
	cin >> n;
	init();
	for (int i=2;i<=n;++i)	ans = (ans + f[i]) % mod;
	cout << ans;
	return 0;
}