首页 > 其他分享 >P8410 题解

P8410 题解

时间:2022-08-26 02:01:42浏览次数:105  
标签:typedef int 题解 P8410 unsigned seed UI include

前言

题目传送门!

更好的阅读体验?

本次比赛第二题,好像没有人抢题解,那我来一发。

思路还是挺巧妙的。

\(\texttt{10 pts}\) 思路

深搜求解即可。

最坏情况,时间复杂度 \(O(n!)\)。

#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned int UI;
typedef unsigned long long ULL;
inline UI get_next(UI &seed) //直接套用给出的随机数代码即可。
{
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}
UI n, seed;
UI a[105], fa[105];
ULL maxn = 0;
bool vis[105];
void dfs(int x, ULL sum, UI minn)
{
	if (x == n)
	{
		//cout<<"sum="<<sum<<'\n';
		maxn = max(maxn, sum);
		return;
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i] && vis[fa[i]]) //选过 fa[i] 且没选过 i 才可以。
		{
			vis[i] = true;
			dfs(x+1, sum + min(minn, (UI)a[i]), min(minn, (UI)a[i]));
			vis[i] = false; //回溯。
		}
}
int main()
{
	scanf("%u%u", &n, &seed);
	for (int i = 1; i <= n; i++) a[i] = get_next(seed);
	for (int i = 2; i <= n; i++) fa[i] = get_next(seed) % (i-1) + 1;
	vis[1] = true;
	dfs(1, (ULL)(a[1]), a[1]);
	printf("%llu", maxn);
    return 0;
}

\(\texttt{50 pts}\) 思路

前置知识点:拓扑排序。

没学过没关系,可以直接看正解。


观察本题,捕捉关键句,如下。

先完成 \(fa_i\) 才能完成 \(i\)。

求和的最大值。

这不就是拓扑排序吗?

容易看出,用优先队列求解,每次选当前队列里的最大值即可。

所以要重载一下。

时间复杂度是带 \(\log\) 的,可以卡过 \(50\%\) 的数据。

最后按照拓扑序计算和即可。

类似模版,没有什么需要特别理解的地方。

#include <iostream>
#include <cstdio>
#include <queue>
#define N 10000005
using namespace std;
typedef unsigned int UI;
typedef unsigned long long ULL;
inline UI get_next(UI &seed)
{
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}
UI n, seed;
UI a[N], fa[N];
struct Edge
{
	int now, nxt;
}e[N];
int head[N], cur;
void add(int x, int y)
{
	e[++cur].now = y;
	e[cur].nxt = head[x];
	head[x] = cur;
}
struct Node
{
	UI x;
	bool operator <(const Node &t) const
	{
		return a[x] < a[t.x];
	}
};
int in[N], topo[N], Cur;
void topo_sort()
{
	priority_queue <Node> Q;
	Q.push( (Node){1} );
	while (!Q.empty())
	{
		int topi = Q.top().x;
		topo[++Cur] = topi;
		Q.pop();
		for (int i = head[topi]; i; i = e[i].nxt)
		{
			int p = e[i].now;
			in[p]--;
			if (in[p] == 0) Q.push( (Node){p} );
		}
	}
}
int main()
{
	scanf("%u%u", &n, &seed);
	for (int i = 1; i <= n; i++) a[i] = get_next(seed);
	for (int i = 2; i <= n; i++) fa[i] = get_next(seed) % (i-1) + 1;
	for (int i = 2; i <= n; i++) add(fa[i], i), in[i]++;
	topo_sort();
	ULL sum = 0, minn = 1e18;
	for (int i = 1; i <= n; i++) minn = min(minn, (ULL)a[topo[i]]), sum += minn;
	printf("%llu", sum);
    return 0;
}

正解

讲完部分分,终于可以将正解了。

然而正解和部分分几乎没有关系。


正解的突破口在于:\(1 \leq fa_i < i\)。

换句话说,顺着扫一遍数组,必定先扫到 \(fa_i\) 再扫到 \(i\)。

进一步讲,顺着扫,等同于遵守了拓扑序

这下,问题就很简单了,转移方程 \(f_i = min(a_i, f_{fa_i})\)。

注意到 \(a_i\) 在后面没有用了,所以可以直接用 \(a_i\) 代替\(f_i\),节约空间。

另外,不存在 \(fa_1\),所以开头稍作改变。

看到代码,你会觉得很简单的。

时间复杂度 \(O(n)\)。

#include <iostream>
#include <cstdio>
#include <queue>
#define N 10000005
using namespace std;
typedef unsigned int UI;
typedef unsigned long long ULL;
inline UI get_next(UI &seed)
{
	seed ^= seed << 13;
	seed ^= seed >> 17;
	seed ^= seed << 5;
	return seed;
}
UI a[N], fa[N];
int main()
{
	int n;
	UI seed;
	scanf("%d%u", &n, &seed);
	for (int i = 1; i <= n; i++) a[i] = get_next(seed);
	for (int i = 2; i <= n; i++) fa[i] = get_next(seed) % (i-1) + 1;
	ULL sum = a[1]; //注意这里需要 long long 来储存。
	for (int i = 2; i <= n; i++) a[i] = min(a[i], a[ fa[i] ]), sum += a[i];
	printf("%llu", sum);
    return 0;
}

希望能帮助到大家,谢谢!

首发:2022-06-25 10:19:04

标签:typedef,int,题解,P8410,unsigned,seed,UI,include
From: https://www.cnblogs.com/liangbowen/p/16622890.html

相关文章

  • CF722B 题解
    前言题目传送门!更好的阅读体验?这是一道简单的字符串练手题。思路每次暴力计数,是否为元音。最后判断是否满足题意即可。重点是字符串读入问题。由于字符串读入部分......
  • AT1330 题解
    前言题目传送门!更好的阅读体验?这一题内部比赛时考到了,个人觉得是一道二分答案好题。本题时间很宽松,导致\(O(n\log^2n)\)的代码可以跑过去。但是,我内部比赛的时限......
  • P2130 题解
    前言题目传送门!更好的阅读体验?本题是练习bfs的好题。思路结合代码进行思路讲解。首先是读入部分,我们可以用bool存下地图,节省空间开销。需要注意,数据比较烂,起始......
  • CF1635B 题解
    题目传送门!更好的阅读体验?这题显然可以使用贪心的思想解决。由于头和尾一定不用更改,所以只需从\(a_2\)枚举到\(a_{n-1}\)。贪心原则下,我们更改的数应该要与相邻的......
  • P8295 题解
    ###前言题目传送门\(\color{red}{see}\space\color{green}{in}\space\color{blue}{my}\space\color{purple}{blog}\)这题并不困难,代码也挺短的,题目理解稍有困难。......
  • 题解 UVA10869 Brownie Points II
    题意平面上有若干点,\(\text{stan}\)通过一个点划了一条直线,\(\text{ollie}\)通过在这条直线上的点作了一条垂线,那么平面被分成\(4\)个象限,\(\text{stan}\)获得的分数......
  • idea导入依赖maven的dependenci列表报红问题解决
    打开一个idea的pom文件时,明明仓库有相关依赖,并且maven的仓库配置没有错误,但是maven的dependencies列表却报红,我们可以让idea每次加载pom文件的依赖不从idea的缓存中读取,而......
  • npm 报错:npm ERR! Maximum call stack size exceeded 超过最大栈问题解决方案
       错误的原因,npm版本问题;解决办法:   1、更新到最新版本:npminstallnpm-g  要记住全局更新2、回退版本:[email protected] ......
  • 蔚来杯2022牛客暑期多校训练营10 题解
    D.MiReDoSiLa?SoFa![NOI2016]优秀的拆分原题。枚举周期\(k\),并将位置为\(k\)的倍数的点设为关键点。枚举相邻两个点\(i,i+k\),并求出\(lcp(S[i...n],S[i+k......
  • 2022“杭电杯”中国大学生算法设计超级联赛(10) 题解
    C.WavyTree发现修改次数和相邻两数的相对大小有关,所以可先求出差分数组。分两种情况考虑:①奇数位置为波峰②偶数位置为波峰。以情况①为例,若奇数位置差分后值小......