当前位置： 移动技术网 > IT编程>开发语言>Java > 2020牛客暑期多校训练营（第五场）

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

2020年07月28日  | 移动技术网IT编程  | 我要评论

D Drop Voicing（dp）

题意：

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

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

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

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

我想把 44 移动到 11 后面，可以进行下面三个步骤

  1. 进行两次 InvertInvert 操作序列变成 5,1,3,6,2,45,1,3,6,2,4
  2. 进行三次 Drop−2Drop-2 操作序列变成 3,6,2,5,1,,43,6,2,5,1,,4
  3. 进行两次 InvertInvert 操作序列变成 2,5,1,4,6,32,5,1,4,6,3

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

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（大数，求环）

题意：

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

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

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

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

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

  1. 10=2∗510 = 2 * 5
  2. 12=2∗2∗312 = 2 * 2 *3
  3. 4=2∗24 = 2 * 2

在 11 中有一个 22，一个 55；在 22 中有两个 22 ，一个 33；在 33 式中有两个22；

所以 22 最多有两个，33最多有一个，55 最多有一个；最后 ans=(22)∗(31)∗(51)=60ans = ( 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（签到）

题意：

编写一个程序，输出显示对敌人造成伤害的直方图，其中空格的长度为 si=50dimaxi dis_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∗mn*m 的网格，每个格子可放 H、E、GH、E、G 中的一个，要求 HH 的上下左右至少要有一个 EE 和一个 GG ，问 n、mn、m 都取无穷大时放 HH 的个数占总格数的多少。

取一条斜线，在斜线上交错摆 EE 和 GG，这样斜线之上和之下的两条斜线都可以摆放 HH，则占比为23\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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网