CF-1028-D. Gellyfish and Camellia Japonica（直接构造等于难，构造最小的大于等于） · znzryb
## 思路讲解
[https://www.luogu.com.cn/article/rae0b6wl](https://www.luogu.com.cn/article/rae0b6wl)
总体思路就是将等于目标转变为构造最小的 大于等于目标的构造
```cpp
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](https://codeforces.com/contest/2115/submission/323143930)
::: 源代码
```cpp
// 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/322643402)
比最大条件小的点是不被允许的，那么填什么最好呢？
[https://codeforces.com/contest/2115/submission/322665243](https://codeforces.com/contest/2115/submission/322665243)
```cpp
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
```
附随机数据生成器
::: 源代码
```cpp
#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](https://www.cnblogs.com/cjcf/p/18906536)
给出最后的结果和操作步骤，求初始数组
通过贪心，我们发现在A[x]有多条边的时候，只能选择满足最大的边（条件，边权为A[z]大小）
比最大条件小的点是不被允许的，那么我们就要看是就选这个最大条件还是选自己的值（如果自己的值比最大条件大）。
贪心的来说，如果自己的值是要被覆盖的，那么肯定选条件值，如果不被覆盖，那肯定就选自己的值。
当然，上面的这些只针对于不是多重覆盖的情况，如果出现多重覆盖情况，那么只保留最后覆盖情况（前面覆盖了也是白覆盖）。
那么我们发现，我们小瞧了这道题目，就是说操作之间是有可能互相影响的。
```cpp
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
```
当然，我们发现我们的贪心结论是没有什么大的问题的，只是适用范围错了，其仅在倒推时，不涉及传递的时候有用。