首页 > 其他分享 >士兵训练 题解

士兵训练 题解

时间:2024-10-08 14:24:49浏览次数:8  
标签:__ 训练 int 题解 ans lmax 士兵 max bmax

题意

link.

题解

正解会 RE 几个点,是官方的栈空间太小了。

再者网上几篇题解都被我 hack 了,好不容易找到一组 hack 却不是我错了,而是 STD 错了……

所以我来写篇题解造福社会。


观察到 \(\max \{b_i \bmod b_j\}\),则得到的结果一定比最大值小,则最大能取到次大。

那就维护一个子树内的最大、次大记为 \(bmax\)、\(b\_max\)。

但是我们需要在外面加一个 \(l\)。

似乎再维护一个子树外最大 \(l\) 就行了。

但是不对。

如果是只维护一个最大 \(lmax\)。

\[ \left\{ \begin{array} llmax + b\_max > bmax, ~bmax\\ lmax + b\_max < bmax, ~lmax + b\_max\\ lmax + b\_max = bmax, ? \end{array} \right. \]

此时问号情况就无法维护。

所以还要维护一个次大 \(l\_max\)
(并且严格、不为零,否则就白维护了);

\[ \left\{ \begin{array} llmax + b\_max > bmax, ~bmax\\ lmax + b\_max < bmax, ~lmax + b\_max\\ lmax + b\_max = bmax, ~b\_max + l\_max \end{array} \right. \]

但此时还是不对,因为第三种情况还需要考虑到次次大,因此还需要维护一个严格的次次大 \(b\_\_max\)。

\[ \left\{ \begin{array} llmax + b\_max > bmax, ~bmax\\ lmax + b\_max < bmax, ~lmax + b\_max\\ lmax + b\_max = bmax, ~\min(b\_max + l\_max, b\_\_max + lmax) \end{array} \right. \]

但,还没完。

如果有 \(b\_max = bmax\) 的情况……虽然有,但显然不够优,就不用考虑啦。

完结撒花。

只不过维护 \(lmax\)、\(l\_max\) 的同时还要再维护一个 \(lmax\_\)、\(lmax\_\_\),表示子树内的最大值然后转移得到 \(lmax\)。

非常恶心,真的要看吗。


namespace zqh {
	const int N = 200005;
	
	int n, q, fa[N];
	vector<int> g[N];
	
	struct node {
		int bmax;
		int b_max;
		int b__max;
		int lmax, l_max, l__max, lmax_;
		int fht, tch;
		node() {
			bmax = b__max = b_max = -1;
			fht = tch = lmax = l_max = l__max = lmax_ = 0;
		}
	} b[N];
	
	void dfs(int u) {
		if (!u) return;
		if (g[u].empty()) {
			b[u].bmax = b[u].fht;
			b[u].lmax = b[u].tch;
			return;
		}
		vector<int> q, p;
//		cout << "hmz AK IOI\n";
		q.push_back(b[u].fht);
		for (int x : g[u]) {
			dfs(x);
			q.push_back(b[x].bmax);
			q.push_back(b[x].b_max);
			q.push_back(b[x].b__max);
			p.push_back(b[x].lmax);
			p.push_back(b[x].lmax_);
		}
		p.push_back(b[u].tch);
		sort(p.begin(), p.end(), greater<int>());
		sort(q.begin(), q.end(), greater<int>());
		b[u].bmax = q[0];
		b[u].b_max = q[1];
		for (int i = 2; i < q.size(); i++)
			if (q[i] != q[1]) {
				b[u].b__max = q[i];
				break;
			}
		b[u].lmax = p[0];
				b[u].lmax_ = p[1];
		for (int i = 1; i < p.size(); i++){
			if (p[i] != b[u].lmax){
				b[u].lmax_ = p[i];
				break;
			}
		}
	}
	
	int get_l_max(int u) {
		if (b[u].l_max) return b[u].l_max;
		if (u == 1) {
			return b[u].l_max = 0;
		}
		int t = fa[u];
		int ans = b[t].tch;
		for (int x : g[t]) {
			if (x == u) continue;
			ans = max(ans, b[x].lmax);
			ans = max(ans, b[x].lmax_);
		}
		b[u].l_max = max(ans, get_l_max(t));
		return b[u].l_max;
	}
	
	int get_l__max(int u) {
		if (b[u].l__max) return b[u].l__max;
		if (u == 1) {
			return b[u].l__max = 0;
		}
		int t = fa[u];
		vector<int> q;
		q.push_back(b[t].tch);
		for (int x : g[t]) {
			if (x == u) continue;
			q.push_back(b[x].lmax);
			q.push_back(b[x].lmax_);
//			ans = max(ans, b[x].lmax);
		}
		q.push_back(b[t].l_max);
		q.push_back(get_l__max(t));
		sort(q.begin(), q.end(), greater<int>());
		for (int i = 0; i < q.size(); i++) {
			if (q[i] != b[u].l_max) {
				b[u].l__max = q[i];
				break;
			}
		}
//		b[u].l__max = q[1];
		return b[u].l__max;
	}
	
	void calc_l_max() {
		rep (i, 1, n) {
			if (g[i].empty())
				get_l_max(i);
		}
	}
	
	void calc_l__max() {
		rep (i, 1, n) {
			if (g[i].empty())
				get_l__max(i);
		}
	}
	
	int dfs3(int u, int max_) {
		int ans = 0;
		if (b[u].fht != max_) {
			ans = b[u].fht;
		}
		for (int x : g[u]) {
			ans = max(ans, dfs3(x, max_));
		}
		return ans;
	}
	
	void init() {
		cin >> n >> q;
		rep (i, 2, n) {
			cin >> fa[i];
			g[fa[i]].push_back(i);
		}
		rep (i, 1, n) {
			cin >> b[i].fht >> b[i].tch;
		}
	}
	
	void solve() {
		dfs(1);
		calc_l_max();
		calc_l__max();
		rep (i, 1, n) {
			if (b[i].l__max > b[i].l_max) swap(b[i].l__max, b[i].l_max);
			if (b[i].lmax_ > b[i].lmax) swap(b[i].lmax_, b[i].lmax);
		}
		// rep (i, 460, 460) {
			// cout << b[i].bmax << " " << b[i].b_max << " " << b[i].b__max << " " << b[i].l_max << " " << b[i].l__max << endl;
		// }
		//4053 3053 2016 
		//1000 990
		// q = 0;
		while (q--) {
			int s;
			cin >> s;
//			cout << "[" << b[s].bmax << " " << b[s].b_max << " " << b[s].b__max << "]\n";
			int l = b[s].l_max;
//			cout << l << endl;
			if (b[s].b_max == -1) {
				cout << "0\n";
				continue;
			}
// if (l == 0 && b[s].bmax == b[s].b_max) {
// cout << dfs3(s, b[s].bmax) << endl;
// continue;
// }
			if (l + b[s].b_max > b[s].bmax) {
				cout << b[s].bmax << endl;
				continue;
			}
			if (l + b[s].b_max < b[s].bmax) {
				cout << l + b[s].b_max << endl;
				continue;
			}
// if (b[s].b__max == -1) {
// cout << max(b[s].b_max + b[s].l__max, 0LL) << endl;
// continue;
// }
//			cout << b[s].l__max << endl;
			if (b[s].b__max != b[s].b_max) {
				int ans = 0;
				if (b[s].l_max + b[s].b__max < b[s].bmax && b[s].b__max != -1)
					ans = max(ans, b[s].l_max + b[s].b__max);
				if (b[s].l__max + b[s].b_max < b[s].bmax && b[s].b_max != -1)
					ans = max(ans, b[s].l__max + b[s].b_max);
				cout << ans << endl;
			}
//				while(1);
//				cout << min(b[s].bmax, b[s].b_max + b[s].l__max) << endl;
//			}
		}
	}
	
	void main() {
		init();
		solve();
	}
}  // namespace zqh

赛时 80,后面死活 95 分,心态崩了。

后面才终于调对了。

最后的最后,提供几组 hack,还要可以私信。

10 10
1 1 1 1 3 3 6 4 1 7 1
7 0
1 7
3 5
7 5
1 2
5 5
2 7
7 3
6 0
1
2
3
4
5
6
7
8
9
10
5
0
5
7
0
2
0
0
0
0

5
1 2 2 1
7 6
9 6
0 1
0 8
8 2
1
2
3
4
5
8
9
0
0
0

标签:__,训练,int,题解,ans,lmax,士兵,max,bmax
From: https://www.cnblogs.com/zphh/p/18451550

相关文章

  • YOLOv8-seg训练与推理
    1.YOLOv8-seg简介 YOLOv8-seg是YOLO系列模型的其中一个版本。YOLOv8-seg在继承YOLO系列模型高效性和准确性的基础上,增加了实例分割的能力。 2.数据集使用的数据集较简单,主要以下目录:images:存放原始图片(1500张),大小为128x128。部分如下: images_json:......
  • 【问题解决】remote: parse error: Invalid numeric literal at line 1, column 20,解
    问题现象某同事出现过同样的推送到git仓库报错的问题,报错信息详情如下:Deltacompresionusingupto20threadsCompressingobjects:100%(4/4),done.Writingobjects:100%(5/5),521bytes|521.00KiB/s,done.Total5(delta3),reused0(delta0),pack-reused0r......
  • 代码随想录算法训练营第七天|第454题.四数相加II,383. 赎金信,第15题. 三数之和
    第454题.四数相加II文章链接:https://programmercarl.com/0454.四数相加II.html视频讲解:https://www.bilibili.com/video/BV1Md4y1Q7Yh/题目链接:https://leetcode.cn/problems/4sum-ii/description/题目思路:首先定义一个unordered_map,key放a和b两数之和,value放a和b两数之......
  • 系统开发基础错题解析一【软考】
    目录前言1.开发模型1.1快速原型模型优点1.2敏捷统一模型1.3增量模型的优缺点1.4极限编程1.5螺旋模型2.软件开发方法3.数据流图与数据字典3.1判定表3.2数据流图绘制3.3决策树4.概要设计和详细设计5.内聚性6.耦合性前言本文专门用来记录本人在做软考中有关系统开发基......
  • 代码随想录算法训练营第八天| 151.翻转字符串里的单词
    151.翻转字符串里的单词文章链接:https://programmercarl.com/0151.翻转字符串里的单词.html#思路视频链接:https://www.bilibili.com/video/BV1uT41177fX/?vd_source=6cb513d59bf1f73f86d4225e9803d47b题目链接:https://leetcode.cn/problems/reverse-words-in-a-string/classS......
  • [AGC061C] First Come First Serve 题解
    Description有\(n\)个人来过,第\(i\)个人在\(a_i\)时刻来在\(b_i\)时刻走,每个人可以在来时或走时登记,问可能的登记顺序有多少种。\(n\leq5\times10^5\),\(a_i,b_i\)互不相同,\(\foralli<n,a_i<a_{i+1},b_{i}<b_{i+1}\)。Solution首先如果每个人随便选,有\(2^n\)种方......
  • 代码随想录算法训练营day8|344.反转字符串 ● 541. 反转字符串II ● 卡码网:54.替换数
    学习资料:https://programmercarl.com/0344.反转字符串.html#算法公开课在python中字符串不可变,所以要增加空间lst=list(str)344.反转字符串(reverse库函数的基本代码)点击查看代码classSolution(object):defreverseString(self,s):""":types:List......
  • 代码随想录算法训练营 | 动态规划,509. 斐波那契数,70. 爬楼梯, 746. 使用最小花费爬楼梯
    动态规划:1.动态规划中每一个状态一定是由上一个状态推导出来的2.确定dp数组(dptable)以及下标的含义,确定递推公式dp,数组如何初始化,确定遍历顺序,举例推导dp数组;3.Debug:dp数组打印509.斐波那契数题目链接:509.斐波那契数文档讲解︰代码随想录(programmercarl.com)视频讲解︰斐波那......
  • [ARC112F] Die Siedler 题解
    智慧题。思路考虑第二种操作。我们会想到,我们可以先把所有牌转化成第一种牌。即:\[one=\sum_{i=1}^n\prod_{j=1}^i2^{j-1}(j-1)!c_i\]这就是第一种牌的数量。然后考虑,我们可以将第一种牌转化为第一种牌,花费的代价为:\[g=(\prod_{i=1}^n2^{i-1}(i-1)!)-1\]相当于对\(g\)......
  • P1437 [HNOI2004] 敲砖块 题解
    初拿到手感觉限制太多了,不好硬做,于是开始观察。若要取某一个数,我们要取其左上右上两个数,而这两个数又要取上面三个数,所以取一个数的前提条件其实是取这一个三角形。举例2234582712236493比如我要取第3行的6,我首先要取7和12,要取7和12,首先要取3,4,5,所以一层层拓展......