Codeforce 1016C Vasya And The Mushrooms

题目链接 Vasya And The Mushrooms

题意：

每个格子都有蘑菇，且具有生长速度，没走一个格子就可以获得当前蘑菇的价值。把所有格子走一遍(每个格子只走一次)，求得到的最大值

思路：

仔细发现，终点只有一下几种情况

对于终点在第一行，也就是偶数列，我们可以这样走

对于终点在第二行，也就是奇数列，我们可以这样走

这是有规律的，所以对于一个终点来说，他能得到的最大值分别是左边得到的最大值加上右边的得到的最大值。左边的最大值不难求，我们只需使用前缀和就可以的到。右边的怎么求呢？ 不一样的时间经过的点不一样，也就是价值不一样。虽然说到达每个点的时间不一样，但是可以发现一但我们把当前的点当作终点时，每个点到达的时间的差是一样的，也就是偏移量一样，我们假设开始都是从最左边开始走，到达终点时的所获得价值为$x$,我们再计算到达这个终点的当前时间，拿这个当前时间减去我们刚开始认为它到达终点的时间，这个就是时间偏移量$t$，当前价值$x+t*(\text{所经过的蘑菇生长的速度和})$既是这个终点右边所得到的值。
这个蘑菇生长的速度和可以用后缀和表示，因为右边是往右跑，因此是后缀和。

注意：我们认为终点所在列的左边是左边得到的价值，这个终点所在列不包括在左边价值里，而是包括在右边价值里

代码：

#include <iostream>
#include <algorithm>
#define MAXN 300010
using namespace std;

typedef long long ll;

int n;

ll a[MAXN], b[MAXN];		// 原矩阵的两行
ll sum[MAXN];			// sum[i] 存储了第i列到第n列所有a[i],b[i]的和,也即是所说的后缀和
ll sum_s[2 * MAXN];			// 顺时针跑。sum_s[i] 当i在1~n的时候，存储的是a[1]~a[i]的和
//			当i在n+1 ~ 2*n的时候，存储的是a[1]~a[n]的和再加上b[n]~b[2*n - i - 1]的和
ll sum_n[2 * MAXN];			// 逆时针跑。sum_n[i] 当i在1~n的时候，存储的是b[1]~b[i]的和
//			当i在n+1 ~ 2*n的时候，存储的是b[1]~b[n]的和再加上a[n]~a[2*n - i - 1]的和
ll sumr[MAXN];				// 终点列右部最大值
ll suml[MAXN];				// 终点列左部最大值

void table() {
	for (int i = n; i >= 1; i--)
		sum[i] = sum[i + 1] + a[i] + b[i];
	for (int i = 1; i <= n; i++)
	{
		sum_s[i] = sum_s[i - 1] + a[i] * (i - 1);
		sum_n[i] = sum_n[i - 1] + b[i] * (i - 1);//初始假定都是从0时间开始走
	}
	/*
	这里要说一下sum_n[1]，这里可以是0，可以是b[1]，如果设为b[1]，后面的时间偏移量就减一即可
	*/
	for (int i = n; i >= 1; i--)
	{
		sum_s[2 * n - i + 1] = sum_s[2 * n - i] + b[i] * (2 * n - i);
		sum_n[2 * n - i + 1] = sum_n[2 * n - i] + a[i] * (2 * n - i);
	}
	for (int i = 1; i <= n; i++)
	{
		if (i & 1)
		{
			sumr[i] = sum_s[2 * n - i + 1] - sum_s[i - 1] + sum[i] * (i-1);//这个(i-1)就是时间偏移量
			suml[i] = suml[i - 1] + a[i-1] * (2 * i - 3) + b[i-1] * (2 * i - 4);//左边价值前缀和递推即可，注意经过每个点时间
		}
		else
		{
			sumr[i] = sum_n[2 * n - i + 1] - sum_n[i - 1] + sum[i] * (i - 1);
			suml[i] = suml[i - 1] + a[i-1] * (2 * i - 4) + b[i-1] * (2 * i - 3);
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
	}

	table();
	
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, sumr[i] + suml[i]);
	}

	cout << ans << endl;

	return 0;
}

Codeforce 932C Permutation Cycle

题目链接 Permutation Cycle

题意：balabala

思路：

$g[i]$的值要么是$a$，要么是$b$。也就是至少一个数要转换$a$次或$b$次。如果有一个长度为$a$的环，环上一点从当前位置走$a$次，必定回到原位。这样想的话，这题答案就出来了。按照题意，并且这个位置的前一个位置的$p$值一定是自己。这样的话，我们构造出若干个长度为$a$的环和长度为$b$的环即可。开始要判断 $ax+by=n$ 是否有整数解，这个直接枚举判断即可。

#include <iostream>
#include <algorithm>
const int N = 2e5 + 10;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n, a, b;
int main()
{
	cin >> n >> a >> b;
	int cnta = 0, cntb = 0;
	for (int i = 0; i*a <= n; i++)
	{
		int val = n - i*a;
		if (val%b == 0){
			cnta = i;
			cntb = val / b;
			break;
		}
	}
	if (cnta*a + cntb*b != n) {
		puts("-1");
		return 0;
	}
	int lst = 1, cur = 1;
	for (int i = 0; i < cnta; i++)
	{
		for (int j = 1; j < a; j++)
		{
			printf("%d ", ++cur);
		}
		printf("%d ", lst);
		lst = ++cur;
	}
	for (int i = 0; i < cntb; i++)
	{
		for (int j = 1; j < b; j++)
		{
			printf("%d ", ++cur);
		}
		printf("%d ", lst);
		lst = ++cur;
	}
	return 0;
}

Codeforce 1059C Sequence Transformation

题目链接 Sequence Transformation

题意：

数组有$n$个数，$1\dots n$ 每次将数组中的$gcd$添加到序列末尾，然后从数组中任意删除一个数，最后使得得到的序列字典序最大

思路：

由于相邻两项$gcd$为$1$，所以就要去除相邻的数。因此最优的是开始先把所有奇数删去。删除所有的奇数以后剩下 ： 2 4 6 8 10 12 14 16.
$GCD(2，4，6，8，10，12，14...)=2* GCD(1，2，3，4，5，6，7....)$，这就和刚开始一样了，同时$gcd$变为$2$.

于是每次把数组长度减半，然后删去奇数位上的值，$gcd=gcd \times 2$.

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 6;

int n;

int main(){
	cin >> n;
	int mul = 1;
	while (n)
	{
		if (n == 1){
			printf("%d\n", mul);
			break;
		}
		else if (n == 2){
			printf("%d %d\n", mul, mul * 2);
			break;
		}
		else if (n == 3){
			printf("%d %d %d\n", mul, mul, mul * 3);
			break;
		}
		for (int i = 1; i <= (n + 1) / 2; i++)
		{
			printf("%d ", mul);
		}
		n /= 2;
		mul *= 2;
	}
	return 0;
}

Codeforce 1047C Enlarge GCD

题目链接 Enlarge GCD

题意：

删除尽量少的数使$gcd$变大

思路：

先把每个数除于它们的$gcd$,留下来的数的共同质因数一定是最多的，我们可以枚举每个数的质因数，然后取出现最多的那个质因数的个数,这个个数就代表留下来最多的个数，删除的数一定是不具有这个出现最多质因数的。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 15000000 +5;
int prime[N], st[N], cnt,num[N];
int n, a[N];
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}
void seive(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!prime[i])
		{
			prime[i] = i;
			st[cnt++] = i;
		}
		for (int j = 0; j < cnt&&i*st[j] <= n; j++)
		{
			prime[i*st[j]] = st[j];
			if (i%st[j] == 0) break;
		}
	}
}
int main()
{
	seive(15000000);
	scanf("%d", &n);
	int g = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		g = gcd(a[i], g);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		a[i] /= g;
		for (int j = a[i]; j > 1;)
		{
			int t = prime[j];
			num[t]++;
			ans = max(ans, num[t]);
			while (j > 1 && j%t == 0)
			{
				j /= t;
			}
		}
	}
	ans = ans ? n-ans : -1;
	cout << ans << endl;
	return 0;
}

做了cf的题，发现自己的思维还是很差，多刷题训练。