欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020牛客暑期多校训练营(第五场)

程序员文章站 2022-06-19 09:14:36
DDrop Voicing(dp)题意:有一个 1n1~n1n 的排列,有以下两种操作:Drop−2Drop-2Drop−2:将倒数第二个数放到开头,前面的数向后平移InvertInvertInvert:将倒数第二个数放到开头,前面的数向后平移若干连续的 Drop−2Drop-2Drop−2 称为 Multi−dropMulti-dropMulti−drop。计算要使该排列排成 1n1~n1n 所需的最少的 Multi−dropMulti-dr...

D Drop Voicing(dp)

题意:

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

  1. Drop2Drop-2:将倒数第二个数放到开头,前面的数向后平移
  2. InvertInvert:将倒数第二个数放到开头,前面的数向后平移

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

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

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

  1. 进行两次 InvertInvert 操作序列变成 5,1,3,6,2,45,1,3,6,2,4
  2. 进行三次 Drop2Drop-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 置换若干次之后能够有序,求满足条件的排列有多少种。

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

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

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

例如:求 10,12,410 , 12 , 4 $的最小公倍数(用质因数表示)

  1. 10=2510 = 2 * 5
  2. 12=22312 = 2 * 2 *3
  3. 4=224 = 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

题意:

给出一个 nmn*m 的网格,每个格子可放 HEGH、E、G 中的一个,要求 HH 的上下左右至少要有一个 EE 和一个 GG ,问 nmn、m 都取无穷大时放 HH 的个数占总格数的多少。

取一条斜线,在斜线上交错摆 EEGG,这样斜线之上和之下的两条斜线都可以摆放 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

相关标签: 牛客