首页 > 其他分享 >题解:P10733 [NOISG2019 Prelim] Lost Array

题解:P10733 [NOISG2019 Prelim] Lost Array

时间:2024-07-18 10:22:15浏览次数:12  
标签:Lost int 题解 long max Prelim NOISG2019

题解:P10733 [NOISG2019 Prelim] Lost Array

思路

对于任意 \(\min(X_{A_{i}},X_{B_{i}})=C_{i}\)。

只要让 \(X_{A_{i}}\) 与 \(C_{i}\) 取 \(\max\) 值。

\(X_{B_{i}}\) 与 \(C_{i}\) 取 \(\max\) 值。

这样可以让 \(\min(X_{A_{i}},X_{B_{i}})\) 绝对是 \(C_{i}\)。

对于为赋值的数,初始化时都初始化为 \(1\) 即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,m,f[10000000],a,b,c;
signed main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++)f[i]=1;
	for(int i=1; i<=m; i++) {
		cin>>a>>b>>c;
		f[a]=max(f[a],c);
		f[b]=max(f[b],c);
	}
	for(int i=1; i<=n; i++)cout<<f[i]<<" ";
	return 0;
}

标签:Lost,int,题解,long,max,Prelim,NOISG2019
From: https://www.cnblogs.com/AUBSwords/p/18308880

相关文章

  • 题解:P10781 【MX-J1-T1】『FLA - III』Spectral
    本题的主要思路就是数学。首先,让我们先来打一个表。\(i\)\(1\)\(2\)\(3\)\(4\)\(\dots\)\(T_{i}\)\(k\)\(1.5k\)\(1.5k\)\(1.375k\)\(\dots\)易用肉眼看见,自\(T_{3}\)之后数越来越小,于是我们大胆猜测,若\(n\ne1\),则它的最大值是\(1.5k\)否则\(k\)。......
  • 题解 P1031 [NOIP2002 提高组] 均分纸牌
    link贪心题中描述每一堆牌只能移动若干张牌到相邻的牌堆上确定了局部最优解必定能推导出全局最优解。易知均分完后,每堆牌的数量都为纸牌总数的平均数\(\mathrm{arg}\)。所以我们可以预处理每堆牌跟\(\mathrm{arg}\)的差距for(inti=1;i<=n;++i)sum+=a[i];......
  • [题解]POJ3675 Telescope——求多边形与圆相交部分的面积
    POJ3675Telescope题意简述多测。每次给定一个\(N\)边形(保证相邻输入的顶点在多边形上也是邻接的),再给定一个以\((0,0)\)为圆心,半径为\(r\)的圆。请计算出多边形和圆相交部分的面积(保留\(2\)位小数)。\(3\leN\le50\)\(0.1\ler\le1000\)\(-1000\lex_i,y_i\le1000\)。......
  • ABC361-D题解
    背景保佑LC能来一中。题意给你一个长度为\(n\)的初始字符串和目标字符串,都由W和B两种字符构成。现在初始字符串末尾接有两个空格字符,每次你可以在该字符串中选出连续两个非空格字符,并把它们按顺序与两个空格交换位置。问最少需要几步能得到目标字符串。分析首先如果两......
  • ABC361-C题解
    背景昨天打比赛的时候查了中考分,心快停跳了。题意从\(n\)个数字中删除\(k\)个数字,问剩下的数字中极差的最小值。分析首先把这\(n\)个数字排序,然后问题就可以转化为求这\(n\)个数字中所有长度为\(n-k\)的连续子段的极差的最小值。采用尺取法,可以从\(1\)开始枚举......
  • 题解:AT_abc360_c [ABC360C] Move It
    背景机房大佬掉大分了,乐悲。题意给你几个箱子和每个箱子里装有的东西\(a\)和对应的重量\(w\),现在要让每个箱子里都装有一个东西,每次可以移动任意一个箱子中的任意一个东西,代价为它的重量,问最小代价。分析贪心。首先最终状态里所有箱子一定只有一个东西,那么对于所有装东西......
  • 题解:P10723 [GESP202406 七级] 黑白翻转
    背景汗流浃背了。分析容易想到一个显然的思路:以任意节点为根,开始遍历。如果一个节点的子树里面有黑点,那么它必须保留,否则如果它是白点,则可以删去。但这个方法很容易举出反例:在这颗树中,如果以最上面的白点为根,那么手推发现算法显然错误。尝试进行修改,容易发现,对于类似的情况......
  • 题解:P10722 [GESP202406 六级] 二叉树
    题意一颗\(n\)节点的二叉树,每个节点非黑即白,给你\(Q\)次操作,每次给你一个\(u\),把\(u\)的子树内所有节点颜色反转,问最终每个节点的颜色。分析看到数据范围,首先把操作离线。容易发现如果一个节点重复操作奇数次,等效于操作一次,如果重复操作偶数次,等效于没操作。所以我们可......
  • 题解:B3646 数列前缀和 3
    分析板子题,线段树维护矩阵区间积,除了难写没什么思维难度。所以直接放代码吧。Code#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;inlineintread(){ intx=0,f=1;charch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getcha......
  • Masked Popcount 题解
    背景罚了一发,太菜了。为什么我终于有时间的时候她要考试?题意给你\(n,m\),问\(\sum_{i=0}^{n}popcount(i\&m)\)。其中\(\&\)代表位运算,\(popcount\)代表一个数字二进制下\(1\)的个数。分析两个数字在二进制下根据数据范围有\(60\)位。所以我们考虑每一位对答案的贡......