2020牛客暑期多校训练营（第五场）

D Drop Voicing（dp）

题意：

有一个 $1~n$ 的排列，有以下两种操作：

1. $Drop-2$：将倒数第二个数放到开头，前面的数向后平移
2. $Invert$：将倒数第二个数放到开头，前面的数向后平移

若干连续的 $Drop-2$ 称为 $Multi-drop$。计算要使该排列排成 $1~n$ 所需的最少的 $Multi-drop$ 的数量。

$invert+drop+invert$ 可以把一个数转移到任意位置。比如对于序列 : $2 ，4， 5 ，1， 3 ，6$。

我想把 $4$ 移动到 $1$ 后面，可以进行下面三个步骤

1. 进行两次 $Invert$ 操作序列变成 $5,1,3,6,2,4$
2. 进行三次 $Drop-2$ 操作序列变成 $3,6,2,5,1,,4$
3. 进行两次 $Invert$ 操作序列变成 $2,5,1,4,6,3$

所以 $drop$ 的最少次数就是找到最长的一个环状 $lis$ 然后把其他元素插进去，这个环状是因为可以通过 $Invert$ 操作改变序列的顺序，然后就是求每个位置往后的 $n$ 长度 的 $lis$ ，找到这些 $lis$ 的最大值用 $n$ 减去就行了。

AC代码：

const int N = 5e5 + 50;
int a[N], dp[N];
int n, m;

int main()
{
	sd(n);
	rep(i, 1, n)
	{
		sd(a[i]);
		a[n + i] = a[i];
	}
	int ans = 0;
	rep(pos, 1, n)
	{
		int sum = 0;
		rep(i, pos, pos + n - 1)
			dp[i] = 1;
		rep(i, pos, pos + n - 1)
		{
			rep(j, pos, i - 1)
			{
				if (a[j] < a[i])
					dp[i] = max(dp[i], dp[j] + 1);
			}
			sum = max(sum, dp[i]);
		}
		ans = max(ans, sum);
	}
	pd(n - ans);
	return 0;
}

E Bogo Sort（大数，求环）

题意：

已知一个长度为 $n$ 的序列 $p$，用序列 $p$ 将排列 $a$ (未知)进行置换，要求找到排列使其被 $p$ 置换若干次之后能够有序，求满足条件的排列有多少种。

置换群，其实就是找环。比如 $p$ 为 $3 2 1$，$a$ 为 $3 2 1$ ，那么 $a$ 被 $p$ 置换一次后为 $1 2 3$ ，再被置换一次为 $3 2 1$ ，又变为了原数组，即 $1 3$ 构成一个环，$2$ 自身构成一个环。
本题实际上就是要求出每个环的长度，然后求所有环的长度的 $LCM$ 。

这道题给出的模数其实是迷惑人的，因为根本到不了怎么大，所以不用考虑，至于如何求多个数的 $LCM$ 。

$n$ 个数的最小公倍数可以用质因子分解法；

例如：求 $10 , 12 , 4$ $的最小公倍数（用质因数表示）

1. $10 = 2 * 5$
2. $12 = 2 * 2 *3$
3. $4 = 2 * 2$

在 $1$ 中有一个 $2$，一个 $5$；在 $2$ 中有两个 $2$ ，一个 $3$；在 $3$ 式中有两个$2$；

所以 $2$ 最多有两个，$3$最多有一个，$5$ 最多有一个；最后 $ans = ( 2 ^ 2 ) * ( 3 ^ 1 ) * ( 5 ^ 1 ) = 60$

所以先把每个环的质因子分解出来，然后取幂次最高的那个，然后把所有质因子按照幂次都乘上即可。

AC代码：

const int N = 4e5 + 50;
int n, m;
int a[N], vis[N];
int cnt[N];
vector<int> v;

namespace bigI
{
typedef vector<ll> VI;
const int bas = 1e4;

void print(VI A)
{
	if (A.size() == 0)
		return;
	printf("%lld", A.back());
	for (int i = A.size() - 2; i >= 0; --i)
		printf("%04lld", A[i]);
	puts("");
}

VI mul(VI A, ll b)
{
	static VI C;
	C.clear();
	ll t = 0;
	for (int i = 0; i < (int)A.size() || t; ++i)
	{
		if (i < (int)A.size())
			t += A[i] * b;
		C.push_back(t % bas);
		t /= bas;
	}
	return C;
}
} // namespace bigI
using namespace bigI;

int dfs(int p)
{
	if (vis[p])
		return 0;
	vis[p] = 1;
	return dfs(a[p]) + 1;
}//找环

int main()
{
	sd(n);
	rep(i, 1, n)
		sd(a[i]);
	rep(i, 1, n)
	{
		if (vis[i])
			continue;
		int x = dfs(i);
		v.pb(x);
	}
	for (auto i : v)
	{
		int now = i;
		int res = 0;
		for (int j = 2; j * j <= now; j++)
		{
			res = 0;
			while (now % j == 0)
				res++, now = now / j;
			cnt[j] = max(cnt[j], res);
		}
		if (now > 1)
			cnt[now] = max(cnt[now], 1);
	}
	VI ans = {1};
	rep(i, 2, n)
	{
		while (cnt[i])
		{
			ans = mul(ans, i);
			cnt[i]--;
		}
	}
	print(ans);
	return 0;
}

F DPS（签到）

题意：

编写一个程序，输出显示对敌人造成伤害的直方图，其中空格的长度为 $s_i=50\frac{d_i}{max_i\ d_i}$ (向上取整)，必须通过将最后一个空格替换为 $‘∗’‘*’‘∗’$ 来标记对敌人造成最大伤害的玩家，如果有多个最大值，则将其全部标记。

这个思路很明显，按照题意模拟就行，注意精度问题。

AC代码：

const int N = 2e5 + 50;
int d[110];
int main()
{
    int n;
    sd(n);
    rep(i, 1, n)
        sd(d[i]);
    int maxn = 0;
    rep(i, 1, n)
        maxn = max(maxn, d[i]);
    rep(i, 1, n)
    {
        int len = ceil(50.0 * d[i] / maxn);
        printf("+");
        rep(j, 1, len)
            printf("-");
        printf("+");
        puts("");
        printf("|");
        rep(j, 1, len - 1)
            printf(" ");
        if (d[i])
            printf("%c", (d[i] == maxn) ? '*' : ' ');
        printf("|%d\n", d[i]);
        printf("+");
        rep(j, 1, len)
            printf("-");
        printf("+");
        puts("");
    }
    return 0;
}

I Hard Math Problem

题意：

给出一个 $n*m$ 的网格，每个格子可放 $H、E、G$ 中的一个，要求 $H$ 的上下左右至少要有一个 $E$ 和一个 $G$ ，问 $n、m$ 都取无穷大时放 $H$ 的个数占总格数的多少。

取一条斜线，在斜线上交错摆 $E$ 和 $G$，这样斜线之上和之下的两条斜线都可以摆放 $H$，则占比为$\frac{2}{3}$ 。

GHGHGH
HEHEHE
GHGHGH
HEHEHE
GHGHGH
HEHEHE

AC代码：

int main()
{
    double ans=2.0/3.0;
    printf("%.6lf\n",ans);
    return 0;
}

本文地址：https://blog.csdn.net/qq_43627087/article/details/107589252