当前位置:网站首页>【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;
}
边栏推荐
- How to force activerecord to reload a class- How do I force ActiveRecord to reload a class?
- Mode in BST (binary tree & Notes on question brushing)
- Chapter 6 text processing tools for shell programming (awk)
- [crampon programming] lintcode decoding Encyclopedia - 872 termination process
- CUDA Programming atomic operation atomicadd reports error err:msb3721, return code 1
- Flink集群配置
- Setting up redis cluster cluster under Windows
- Leetcode hot topic Hot 100 day 33: "subset"
- A survey of automatic speech recognition (ASR) research
- [crampon programming] lintcode decoding Encyclopedia - 1100 strange printer
猜你喜欢
解密函数计算异步任务能力之「任务的状态及生命周期管理」
[AI bulletin 20220211] the hard core up owner has built a lidar and detailed AI accelerator
windows下Redis-cluster集群搭建
官宣!第三届云原生编程挑战赛正式启动!
Hypothesis testing -- learning notes of Chapter 8 of probability theory and mathematical statistics
Burpsuite grabs app packets
The 22nd Spring Festival Gala, an immersive stage for the yuan universe to shine into reality
[thingsboard] how to replace the homepage logo
TPG x AIDU | AI leading talent recruitment plan in progress!
函數(易錯)
随机推荐
Sword finger offer 07 Rebuild binary tree
Leetcode hot topic Hot 100 day 33: "subset"
flutter 对象和列表
Decryption function calculates "task state and lifecycle management" of asynchronous task capability
直播預告 | 容器服務 ACK 彈性預測最佳實踐
Stage experience
Neural networks and deep learning Chapter 3: linear model reading questions
The principle of attention mechanism and its application in seq2seq (bahadanau attention)
SQL set operation
10 programming habits that web developers should develop
[goweb development] Introduction to authentication modes based on cookies, sessions and JWT tokens
电源管理总线 (PMBus)
Neural network and deep learning Chapter 1: introduction reading questions
Label exchange experiment
Hypothesis testing -- learning notes of Chapter 8 of probability theory and mathematical statistics
Machine learning -- neural network
English topic assignment (26)
How can CIOs use business analysis to build business value?
[AI bulletin 20220211] the hard core up owner has built a lidar and detailed AI accelerator
Interface joint commissioning test script optimization V5.0 (end)