当前位置:网站首页>【acwing】240. food chain
【acwing】240. food chain
2022-07-05 04:41:00 【The wind is a little strong】
subject
Train of thought
How to merge different query sets , For the same kind (1) Come on :
For different classes (2) Come on :
Code 1
#include<iostream>
using namespace std;
const int N=50005;
int p[N],d[N];
int n,m;
int find(int x){
// Record the distance to the root node
if(p[x]!=x){
int t=find(p[x]);
d[x]+=d[p[x]];
p[x]=t;
}
return p[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
p[i]=i; // All parent nodes are themselves
}
int res=0;
while(m--){
int t,x,y;
cin>>t>>x>>y;
if(x>n || y>n){
//x,y Greater than n The scope of the , This sentence is a lie
res++;
}else{
int px=find(x);//x The root node
int py=find(y);//y The root node
if(t==1){
//x and y It's the same kind
if(px==py && (d[x]-d[y])%3!=0){
// In the same tree , The distance difference between two points %3 Not for 0, It means it's not the same kind
res++;
}else if(px != py){
//x,y Not in the same tree
p[px]=py; //x The root node of is connected to y On the root node of
d[px]=d[y]-d[x];
}
}else{
//x eat y
if(px==py && (d[x]-d[y]-1)%3!=0){
//x,y In the same tree ,x Distance ratio y Freshman , namely (dx-dy-1)%3==0
res++;
}else if(px != py){
//x,y Not in the same tree ,
p[px]=py;//x The root node of is connected to y On the root node of
d[px]=d[y]+1-d[x];
}
}
}
}
cout<<res<<endl;
return 0;
}
Train of thought two
Union checking set ( Expanding domain )
This topic is mainly to open three expanded domains , That is, the natural enemy domain , Homogeneous domain , And predatory areas .
If x,y It's the same kind , however x Of Predatory domain
Yes y, that
If x,y It's the same kind , however x Of Natural enemy territory
Yes y, that
If x,y It's the same kind , however x Of Homogeneous domain
Yes y, that
If x yes y The natural enemies of , however x Of Homogeneous domain
There is y, that
If x yes y The natural enemies of , however x Of Natural enemy territory
There is y, that
If x yes y The world of , however x Of Predatory domain
There is y, that
Let's make the present X The predation domain of is X+N, At present X The natural enemy domain of is X+N+N
Code 2
// Let's make the present X The predation domain of is X+N, At present X The natural enemy domain of is X+N+N
#include<iostream>
using namespace std;
const int N=50000*3+5;
int p[N];
int n,m;
int find(int x){
if(x!=p[x]){
p[x]=find(p[x]);
}
return p[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=3*n;i++){
p[i]=i;
}
int res=0;
while (m -- ){
int k,x,y;
cin>>k>>x>>y;
if(x>n || y>n){
res++;
}else if(k==1){
//x and y similar
if(find(x)==find(y+n) || find(x)==find(y+n+n)){
//x stay y In the predatory domain ,x stay y In the field of natural enemies
res++;
}else{
p[find(x)]=p[find(y)]; //x and y similar
p[find(x+n)]=p[find(y+n)]; //x Predatory domain and y Predatory domain of the same
p[find(x+n+n)]=p[find(y+n+n)]; //x Natural enemy domain and y The natural enemy domain of
}
}else{
//x yes y The natural enemies of
if(x==y || find(x)==find(y) || find(x)==find(y+n)){
//x and y Is the same ,x and y It's the same kind ,x yes y The predator-prey area
res++;
}else{
p[find(x)]=p[find(y+n+n)]; //y Add... To your natural enemy domain x
p[find(x+n)]=p[find(y)]; //x In the predator-prey domain y
p[find(x+n+n)]=p[find(y+n)]; //x Natural enemy domain and y The predatory domain of is the same
}
}
}
cout<<res<<endl;
return 0;
}
边栏推荐
- Neural networks and deep learning Chapter 6: Circular neural networks reading questions
- Machine learning -- neural network
- [AI bulletin 20220211] the hard core up owner has built a lidar and detailed AI accelerator
- [crampon programming] lintcode decoding Encyclopedia - 872 termination process
- The difference between bundle, chunk and module
- flutter 对象和列表
- OWASP top 10 vulnerability Guide (2021)
- Rk3399 platform development series explanation (network debugging) 7.29 summary of network performance tools
- [crampon game] MC tutorial - first day of survival
- After the deployment of web resources, the navigator cannot obtain the solution of mediadevices instance (navigator.mediadevices is undefined)
猜你喜欢
Setting up redis cluster cluster under Windows
10 programming habits that web developers should develop
Sequence diagram of single sign on Certification Center
MySQL in-depth learning - index creation and deletion, index design principles, index failure scenarios, query optimization, index push down ICP
Is there a sudden failure on the line? How to make emergency diagnosis, troubleshooting and recovery
Discussion on the dimension of confrontation subspace
Invalid bound statement (not found) in idea -- problem solving
Qt蓝牙:搜索蓝牙设备的类——QBluetoothDeviceDiscoveryAgent
Official announcement! The third cloud native programming challenge is officially launched!
Power management bus (pmbus)
随机推荐
Is there a sudden failure on the line? How to make emergency diagnosis, troubleshooting and recovery
49 pictures and 26 questions explain in detail what is WiFi?
Fluent objects and lists
What are the building energy-saving software
flutter 对象和列表
PHP读取ini文件并修改内容写入
How can CIOs use business analysis to build business value?
Components in protective circuit
Flink集群配置
A solution to the problem that variables cannot change dynamically when debugging in keil5
线上故障突突突?如何紧急诊断、排查与恢复
Observable time series data downsampling practice in Prometheus
解密函数计算异步任务能力之「任务的状态及生命周期管理」
[phantom engine UE] the difference between running and starting, and the analysis of common problems
How should programmers learn mathematics
Here comes the Lantern Festival red envelope!
SPI read / write flash principle + complete code
QT Bluetooth: a class for searching Bluetooth devices -- qbluetooth devicediscoveryagent
JVM 原理和流程简介
Power management bus (pmbus)