CF-1028-D. Gellyfish and Camellia Japonica（直接构造等于难，构造最小的大于等于）

思路讲解

https://www.luogu.com.cn/article/rae0b6wl

总体思路就是将等于目标转变为构造最小的 大于等于目标的构造

ROF(i,Q,1){
	ll x=Op[i][0],y=Op[i][1],z=Op[i][2];
	C[x]=max(C[x],C[z]);
	C[y]=max(C[y],C[z]);
	if(x!=z && y!=z) C[z]=0; 
}

既然是要被覆盖的，我们还要构造最小的吗，所以我们令

AC代码

https://codeforces.com/contest/2115/submission/323143930

源代码

// Problem: B. Gellyfish and Camellia JaponicaB. 水母和山茶花
// Contest: Codeforces - Codeforces Round 1028 (Div. 1)Codeforces 第 1028 轮（第 1 组）
// URL: https://codeforces.com/contest/2115/problem/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)


using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(1e9)+9;	// 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN],C[MAXN];
/*

*/
arr3 Op[MAXN];
inline void solve(){
	cin>>N>>Q;
	FOR(i,1,N){
		cin>>B[i];
		C[i]=B[i];
	}
	FOR(i,1,Q){ll x,y,z;cin>>x>>y>>z;Op[i]={x,y,z};}
	// 总体思路就是将等于目标转变为构造最小的 大于等于目标的构造
	ROF(i,Q,1){
		ll x=Op[i][0],y=Op[i][1],z=Op[i][2];
		C[x]=max(C[x],C[z]);
		C[y]=max(C[y],C[z]);
		if(x!=z && y!=z) C[z]=0; 
	}
	FOR(i,1,N) A[i]=C[i];
	FOR(i,1,Q){
		ll x=Op[i][0],y=Op[i][1],z=Op[i][2];
		C[z]=min(C[x],C[y]);
	}
	FOR(i,1,N){
		if(C[i]!=B[i]){
			cout<<-1<<"\n";
			return;
		}
	}
	FOR(i,1,N){
		cout<<A[i]<<' ';
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2115/submission/323143930
*/

心路历程（WA，TLE，MLE……）

https://codeforces.com/contest/2115/submission/322643402

比最大条件小的点是不被允许的，那么填什么最好呢？

https://codeforces.com/contest/2115/submission/322665243

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

附随机数据生成器

源代码

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
// #define getFro(vec) (vec.empty()?0:vec.front())
// #define getBac(vec) (vec.empty()?0:vec.back())
#define debug(var) cerr << #var <<":"<<var<<"\n";
// #define DEBUG(variable) do { std::cerr << #variable << ":"; for (const auto& elem : \
// variable) { std::cerr << elem << " ";}std::cerr << "\n";} while (0)
// #define uniVec(var) do {  sort(var.begin(),var.end());var.resize(unique(var.begin(), \
// var.end())-var.begin());} while (0)
// #define debugN(var,N) do{ std::cerr<<#var<<":"; FOR(i,1,N){ std::cerr<<var[i]<<" "; } \ 
// std::cerr<<"\n"; }while(0)
// #define debugMap(variable) do { std::cerr << #variable << ":\n"; for (const auto \
// & pair : variable) \
// { std::cerr << "  " << pair.first << " => " << pair.second << "\n"; } \
// std::cerr << std::endl; } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
// #define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9;	// 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
/*

*/
arr3 xyz[MAXN];
inline void solve(){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	N=10,Q=10;
	uniform_int_distribution<> dist(1,N),dist2(1,N);
	printf("1\n");
	printf("%lld %lld\n",N,Q);
	FOR(i,1,N){
		A[i]=dist(rng);
	}
	FOR(i,1,Q){
		ll x=dist2(rng),y=dist2(rng),z=dist2(rng);
		A[z]=min(A[x],A[y]);
		xyz[i]={x,y,z};
	}
	FOR(i,1,N){
		printf("%lld ",A[i]);
	}
	printf("\n");
	FOR(i,1,Q){
		int x=xyz[i][0],y=xyz[i][1],z=xyz[i][2];
		printf("%d %d %d\n",x,y,z);
	}
	
}

int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	
	// scanf("%lld",&lT);
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

https://www.cnblogs.com/cjcf/p/18906536

给出最后的结果和操作步骤，求初始数组

通过贪心，我们发现在A[x]有多条边的时候，只能选择满足最大的边（条件，边权为A[z]大小）

比最大条件小的点是不被允许的，那么我们就要看是就选这个最大条件还是选自己的值（如果自己的值比最大条件大）。

贪心的来说，如果自己的值是要被覆盖的，那么肯定选条件值，如果不被覆盖，那肯定就选自己的值。

当然，上面的这些只针对于不是多重覆盖的情况，如果出现多重覆盖情况，那么只保留最后覆盖情况（前面覆盖了也是白覆盖）。

那么我们发现，我们小瞧了这道题目，就是说操作之间是有可能互相影响的。

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

当然，我们发现我们的贪心结论是没有什么大的问题的，只是适用范围错了，其仅在倒推时，不涉及传递的时候有用。