头像

Object_




离线:2020-08-19 09:44


最近来访(24)
用户头像
YF1994
用户头像
yaohui
用户头像
无糖奶茶
用户头像
明太子
用户头像
Aigrl
用户头像
konkayy
用户头像
祢遘
用户头像
空白_6
用户头像
DarksideCoder
用户头像
hlydxxz
用户头像
梨小畅
用户头像
zeda
用户头像
Misaka御坂
用户头像
acwing_11956
用户头像
Once.
用户头像
凡星
用户头像
huge_luck
用户头像
CHiCO酱
用户头像
WANGJUNJIE
用户头像
xihb183

活动打卡代码 AcWing 137. 雪花雪花雪花

Object_
2020-06-26 04:21
#include <bits/stdc++.h>
using namespace std;
const int K = 99991;
const int N=100000+10;
struct Node
{
    int c[7];
};
int m[N],n,ok,sum;
Node snow[N][10];//如果你写个100,你五十分,如果你写个50,恭喜你加了10分,如果你很疯狂写个20,恭喜你分数不变,如果你破釜沉舟,写个10,恭喜你Ac了,出题人是多么的有趣啊.
bool solve(Node x,Node y) 
{
    sort(x.c+1,x.c+7);//排序有利于身心健康
    sort(y.c+1,y.c+7);
    for(int i=1;i<=6;i++)
    {
        if(x.c[i]!=y.c[i])//只要不一样,就直接退出
            return false;
    }
    return true;
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        sum=0;
        Node now;
        for(int j=1; j<=6; j++)
        {
            scanf("%d",&now.c[j]);
            sum=(sum+now.c[j])%K;//取模运算也就是hash
        }
        for(int j=0; j<m[sum]; j++)//找到所有hash值是一样的雪花,然后每一个判断.
        {
            if(solve(now,snow[sum][j]))//如果这两个雪花一样大小
            {
                ok=1;//如果说hash值不一样,那么肯定不会一样,如果hash值一样,还要判断
                break;
            }
        }
        snow[sum][m[sum]]=now;//我们hash是记录这个值,以链表的方式存储,这里是静态存储,也就是数组模拟链表,我们要知道数据是死,人是活的,出题人是懒的.
        m[sum]++;
        if (ok)
            break;
    }
    if(ok)
        printf("Twin snowflakes found.\n");
    else
        printf("No two snowflakes are alike.\n");
    return 0;
}


活动打卡代码 AcWing 133. 蚯蚓

Object_
2020-06-20 12:45
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define int long long 
using namespace std;
struct Node;
int getNowLength(Node node,int nowSecond);
const int MAXN=1e5+20;

int second,q; 
struct Node{//蚯蚓 
    int length,//长度
        birth;//出生时间 
    bool operator <(const Node another)const{
        return length>another.length;//undo
    }
};

queue<Node> origNodes;//初始蚯蚓 
queue<Node> newNodes_short;//新蚯蚓 短的
queue<Node> newNodes_long;//新蚯蚓 长的


struct CutResult{//切除结果 
    int first,second;//两段 
};

CutResult cutNode(Node node,int u,int v){//切蚯蚓 u v(p=u/v)
    int origLength=node.length;
    int newLength1=((origLength)*u/v);
    int newLength2=origLength-newLength1;
    if(newLength1<newLength2)swap(newLength1,newLength2);
    return CutResult{newLength1,newLength2};
}

int u,v;//切开位置参数 
int getNowLength(Node node,int nowSecond){
    if(((nowSecond-node.birth)*q)<0)return node.length;
    return node.length+(nowSecond-node.birth)*q;
}

Node getNowLongestNode(int second){//获取当前最长蚯蚓 
    Node cutNode;//需要切的蚯蚓 
    int nowLen=0;//当前最长长度 
    int biggest=0;//最大的 1:原始 2:long 3:short 
    Node tmpNode;
    if(!origNodes.empty()){//还有老蚯蚓 
        tmpNode=origNodes.front();
        if(getNowLength(tmpNode,second)>nowLen){
            nowLen=getNowLength(tmpNode,second);
            cutNode=tmpNode;
            biggest=1;
        }
    }
    if(!newNodes_short.empty()){
        tmpNode=newNodes_short.front();
        if(getNowLength(tmpNode,second)>nowLen){
            nowLen=getNowLength(tmpNode,second);
            cutNode=tmpNode;
            biggest=3;
        }
    }
    if(!newNodes_long.empty()){
        tmpNode=newNodes_long.front();
        if(getNowLength(tmpNode,second)>nowLen){
            nowLen=getNowLength(tmpNode,second);
            cutNode=tmpNode;
            biggest=2;
        }
    }
    switch(biggest){
        case 1:
            origNodes.pop();
            break;
        case 2:
            newNodes_long.pop();
            break;
        case 3:
            newNodes_short.pop();
            break;
    }
    return cutNode;
}
int t;//输出参数 
void outputAll(){//输出所有蚯蚓
    int cntt=0;
    while(!(newNodes_long.empty()&&newNodes_short.empty()&&origNodes.empty())){
        cntt++;
        Node longgest=getNowLongestNode(second);
        if(!(cntt%t))cout<<getNowLength(longgest,second)<<" ";
    } 
    cout<<endl;
}
Node tmps[MAXN];
signed main(){
    int n,//初始蚯蚓数量
        m;//秒数
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);

    for(int i=1;i<=n;i++){
        int tmp;//长度 
        scanf("%lld",&tmp);
        tmps[i]=Node{tmp,1};
    }
    sort(tmps+1,tmps+n+1);
    for(int i=1;i<=n;i++){
        origNodes.push(tmps[i]);
    }

    //共执行m秒
    for(second=1;second<=m;second++){
        Node topNode=getNowLongestNode(second);
        int nowLength=getNowLength(topNode,second);
        topNode.length=nowLength;
        CutResult result=cutNode(topNode,u,v);
        newNodes_long.push(Node{result.first,second+1});
        newNodes_short.push(Node{result.second,second+1});
        if(!(second%t))cout<<nowLength<<" ";
    } 
    cout<<endl;
    outputAll();
    return 0;
}



Object_
2020-06-20 12:44

最难查出的问题,实际上是思想的盲区。深入地说,也就是对“思想算法”正确性的证明不足。
从这道题中,很容易想到蚯蚓长度在时间轴上具有单调性(粗略想法),以此为切入点。
如果从单调性联想到优先队列,会得到一种“标准”的错误解法,即使用了额外算力保证结果单调性
事实上,我们已经意识到了蚯蚓存在“潜在的单调性”了。但如果直接将切开产生的新蚯蚓放入队列中,此队列仍是“无序”的。
注意到每次“相对”切割点相同,从这个限制出发,意识到新蚯蚓如果将较长、较短分为两个队列存储,则可分别具备单调性。再附加一个初始队列储存原始蚯蚓,此题即求解完毕。


从这个题目中,我们理解了以“题目限制”为突破口的思想。更广泛地说,我们意识到了预设的“有序”即为我们最根本的依据。


#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define int long long 
using namespace std;
struct Node;
int getNowLength(Node node,int nowSecond);
const int MAXN=1e5+20;

int second,q; 
struct Node{//蚯蚓 
    int length,//长度
        birth;//出生时间 
    bool operator <(const Node another)const{
        return length>another.length;
    }
};

queue<Node> origNodes;//初始蚯蚓 
queue<Node> newNodes_short;//新蚯蚓 短的
queue<Node> newNodes_long;//新蚯蚓 长的


struct CutResult{//切除结果 
    int first,second;//两段 
};

CutResult cutNode(Node node,int u,int v){//切蚯蚓 u v(p=u/v)
    int origLength=node.length;
    int newLength1=((origLength)*u/v);
    int newLength2=origLength-newLength1;
    if(newLength1<newLength2)swap(newLength1,newLength2);
    return CutResult{newLength1,newLength2};
}

int u,v;//切开位置参数 
int getNowLength(Node node,int nowSecond){
    if(((nowSecond-node.birth)*q)<0)return node.length;
    return node.length+(nowSecond-node.birth)*q;
}

Node getNowLongestNode(int second){//获取当前最长蚯蚓 
    Node cutNode;//需要切的蚯蚓 
    int nowLen=0;//当前最长长度 
    int biggest=0;//最大的 1:原始 2:long 3:short 
    Node tmpNode;
    if(!origNodes.empty()){//还有老蚯蚓 
        tmpNode=origNodes.front();
        if(getNowLength(tmpNode,second)>nowLen){
            nowLen=getNowLength(tmpNode,second);
            cutNode=tmpNode;
            biggest=1;
        }
    }
    if(!newNodes_short.empty()){
        tmpNode=newNodes_short.front();
        if(getNowLength(tmpNode,second)>nowLen){
            nowLen=getNowLength(tmpNode,second);
            cutNode=tmpNode;
            biggest=3;
        }
    }
    if(!newNodes_long.empty()){
        tmpNode=newNodes_long.front();
        if(getNowLength(tmpNode,second)>nowLen){
            nowLen=getNowLength(tmpNode,second);
            cutNode=tmpNode;
            biggest=2;
        }
    }
    switch(biggest){
        case 1:
            origNodes.pop();
            break;
        case 2:
            newNodes_long.pop();
            break;
        case 3:
            newNodes_short.pop();
            break;
    }
    return cutNode;
}
int t;//输出参数 
void outputAll(){//输出所有蚯蚓
    int cntt=0;
    while(!(newNodes_long.empty()&&newNodes_short.empty()&&origNodes.empty())){
        cntt++;
        Node longgest=getNowLongestNode(second);
        if(!(cntt%t))cout<<getNowLength(longgest,second)<<" ";
    } 
    cout<<endl;
}
Node tmps[MAXN];
signed main(){
    int n,//初始蚯蚓数量
        m;//秒数
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);

    for(int i=1;i<=n;i++){
        int tmp;//长度 
        scanf("%lld",&tmp);
        tmps[i]=Node{tmp,1};
    }
    sort(tmps+1,tmps+n+1);
    for(int i=1;i<=n;i++){
        origNodes.push(tmps[i]);
    }

    //共执行m秒
    for(second=1;second<=m;second++){
        Node topNode=getNowLongestNode(second);
        int nowLength=getNowLength(topNode,second);
        topNode.length=nowLength;
        CutResult result=cutNode(topNode,u,v);
        newNodes_long.push(Node{result.first,second+1});
        newNodes_short.push(Node{result.second,second+1});
        if(!(second%t))cout<<nowLength<<" ";
    } 
    cout<<endl;
    outputAll();
    return 0;
}


活动打卡代码 AcWing 132. 小组队列

Object_
2020-06-16 04:24
#include<cstdio>
#include<iostream>
#include<cstring>
#include<deque>
using namespace std;
const int MAXID=1e6;

int teamID[MAXID];
int getTeamID(int playerID){
    return teamID[playerID];
}

bool isInMainQueue[MAXID];
bool isTeamInQueue(int teamID){//队伍是否在总队列里 
    return isInMainQueue[teamID];
}

deque<int> mainQueue;//存储队伍编号
void addTeamToQueue(int teamID){
    if(!isInMainQueue[teamID])mainQueue.push_back(teamID);
    isInMainQueue[teamID]=1;
} 

deque<int> teamQueue[5000];//小组队列 
void addPlayerToTeamQueue(int playerID){//将玩家加入到他自己的小组队伍中 
    int playerTeam=getTeamID(playerID);
    teamQueue[playerTeam].push_back(playerID);
}

void addPlayerToMainQueue(int playerID){//将一个人加入到主队列中 
    int playerTeam=getTeamID(playerID);
    if(!isTeamInQueue(playerTeam)){
        addTeamToQueue(playerTeam);
    }
    addPlayerToTeamQueue(playerID);
}

int deTeamQueue(){//让第一个人出队  返回出队人编号 
    int firstTeamIndex=mainQueue.front();//第一个队伍编号
    int nowFront=teamQueue[firstTeamIndex].front();//第一个人 
    if(teamQueue[firstTeamIndex].size()==1){
        isInMainQueue[firstTeamIndex]=0;
        mainQueue.pop_front();
    }
    teamQueue[firstTeamIndex].pop_front();
    return nowFront;
}

void clearAll(){
    memset(isInMainQueue,0,sizeof(isInMainQueue));
    mainQueue.clear();
    for(int i=0;i<=1020;i++){
        teamQueue[i].clear();
    }
}

char strTmp[100];
int main(){
    int t=-1;
    int cnt=0;
    while(1){
        cnt++;
        clearAll();
        scanf("%d",&t);
        if(t==0)return 0;
        for(int i=1;i<=t;i++){
            int num;
            scanf("%d",&num);
            for(int j=1;j<=num;j++){
                int playerID;
                scanf("%d",&playerID);
                teamID[playerID]=i;
            }
        }
        cout<<"Scenario #"<<cnt<<endl;
        while(1){
            scanf("%s",&strTmp);
            if(strTmp[0]=='E'){//插入 
                int playerID;
                scanf("%d",&playerID);
                addPlayerToMainQueue(playerID);
            }else if(strTmp[0]=='D'){//出队 
                int playerID=deTeamQueue();
                cout<<playerID<<endl;
            }else if(strTmp[0]=='S'){//stop
                cout<<endl;
                break;
            }
        }

    }
    return 0;
} 



Object_
2020-06-16 04:23

思想:

  • 化整为零:将整个大队列的问题转化为多个小队列分开的问题,并使用一个主队列维护小队列编号。
  • 隐含条件:每组数据不保证出队数=入队数,即每次读入前应清空队列

(另:queue不能clear(),故需deque)


从这个题里,也可以看到基本的查错方法。即首先寻找一般性问题(数组越界等),再思考题目限制(1.手算样例 2.认真读题)


#include<cstdio>
#include<iostream>
#include<cstring>
#include<deque>
using namespace std;
const int MAXID=1e6;

int teamID[MAXID];
int getTeamID(int playerID){
    return teamID[playerID];
}

bool isInMainQueue[MAXID];
bool isTeamInQueue(int teamID){//队伍是否在总队列里 
    return isInMainQueue[teamID];
}

deque<int> mainQueue;//存储队伍编号
void addTeamToQueue(int teamID){
    if(!isInMainQueue[teamID])mainQueue.push_back(teamID);
    isInMainQueue[teamID]=1;
} 

deque<int> teamQueue[5000];//小组队列 
void addPlayerToTeamQueue(int playerID){//将玩家加入到他自己的小组队伍中 
    int playerTeam=getTeamID(playerID);
    teamQueue[playerTeam].push_back(playerID);
}

void addPlayerToMainQueue(int playerID){//将一个人加入到主队列中 
    int playerTeam=getTeamID(playerID);
    if(!isTeamInQueue(playerTeam)){
        addTeamToQueue(playerTeam);
    }
    addPlayerToTeamQueue(playerID);
}

int deTeamQueue(){//让第一个人出队  返回出队人编号 
    int firstTeamIndex=mainQueue.front();//第一个队伍编号
    int nowFront=teamQueue[firstTeamIndex].front();//第一个人 
    if(teamQueue[firstTeamIndex].size()==1){
        isInMainQueue[firstTeamIndex]=0;
        mainQueue.pop_front();
    }
    teamQueue[firstTeamIndex].pop_front();
    return nowFront;
}

void clearAll(){
    memset(isInMainQueue,0,sizeof(isInMainQueue));
    mainQueue.clear();
    for(int i=0;i<=1020;i++){
        teamQueue[i].clear();
    }
}

char strTmp[100];
int main(){
    int t=-1;
    int cnt=0;
    while(1){
        cnt++;
        clearAll();
        scanf("%d",&t);
        if(t==0)return 0;
        for(int i=1;i<=t;i++){
            int num;
            scanf("%d",&num);
            for(int j=1;j<=num;j++){
                int playerID;
                scanf("%d",&playerID);
                teamID[playerID]=i;
            }
        }
        cout<<"Scenario #"<<cnt<<endl;
        while(1){
            scanf("%s",&strTmp);
            if(strTmp[0]=='E'){//插入 
                int playerID;
                scanf("%d",&playerID);
                addPlayerToMainQueue(playerID);
            }else if(strTmp[0]=='D'){//出队 
                int playerID=deTeamQueue();
                cout<<playerID<<endl;
            }else if(strTmp[0]=='S'){//stop
                cout<<endl;
                break;
            }
        }

    }
    return 0;
} 


活动打卡代码 AcWing 129. 火车进栈

Object_
2020-06-14 07:39
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=50;
int n;

bool vis[MAXN];
int stck[MAXN],top=0;

int tmp[MAXN],tmpTop=0;//
void getLowToTmp(int index,int nowValue){//将编号之后比nowValue小的数字放入tmp数组
    for(int i=index+1;i<=top;i++){
        if(stck[i]<nowValue){
            tmp[++tmpTop]=stck[i];
        }
    } 

}

/**
 index:nowValue的编号(栈中的) 
*/
bool judge_low(int nowValue,int index){//是否 比nowValue小的数字都倒序 
    getLowToTmp(index,nowValue);
    int minn=nowValue; 
    bool isOk=true;//是否都倒序 
    for(int i=1;i<=tmpTop;i++){//如果从index+1开始向后枚举,枚举到的数都比当前的min小,则更新(此时合法),否则说明非倒序 
        if(tmp[i]>minn){
            isOk=false;
            break;
        }
        minn=min(minn,tmp[i]);
    }
    tmpTop=0;
    return isOk;
}


bool judge(){//是否合法 
    for(int i=1;i<=top;i++){
        int nowValue=stck[i];
        if(judge_low(nowValue,i)){//是否 比nowValue小的数字都倒序
            continue;
        }else{
            return 0;
        }
    }
    return 1;
}

int cnt=0;//输出计数 (超过20则关闭程序) 
void dfs(int nowNum,int siz){
    if(cnt==20){
        return;
    }
    if(siz==n){
        if(judge()){
            for(int i=1;i<=top;i++)cout<<stck[i];
            cout<<endl;
            cnt++;
        }
        return;
    }
    vis[nowNum]=1;
    for(int i=1;i<=n;i++){
        if(i!=nowNum&&(!vis[i])){
            stck[++top]=i;
            dfs(i,siz+1);
            top--;
        }
    }
    vis[nowNum]=0;

}


int main(){
    scanf("%d",&n);
    dfs(0,0);
    return 0;
}



Object_
2020-06-14 07:35

如果直接看这道题,很容易陷入一个思维误区,即直接使用DFS+栈进行解题
观察样例,很容易给我们一个“这是全排列”的错觉,但实际上他有一个限制,因此可能反而不去考虑全排列了
但事实上,此题输出为一个“缩小”后的全排列。考虑“缩小”的规则,并结合“”的性质,我们意识到这是“后进先出”所导致的
拓展“后进先出”这一结论,可以推广出一个规律:对于任何一个输出序列,其中的任意一数【其后面比它更小的数】,这个整体必为倒序,如“1423”即为不合法序列
于是,此题就转化为了求全排列+判断合法性


从这道题中,我们意识到了观察“结论”的特性,并以之倒推解题思路的重要性.在其中,也有着“复杂问题转化为多个简单问题和”的深刻思想。


#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=50;
int n;

bool vis[MAXN];
int stck[MAXN],top=0;

int tmp[MAXN],tmpTop=0;//
void getLowToTmp(int index,int nowValue){//将编号之后比nowValue小的数字放入tmp数组
    for(int i=index+1;i<=top;i++){
        if(stck[i]<nowValue){
            tmp[++tmpTop]=stck[i];
        }
    } 

}

/**
 index:nowValue的编号(栈中的) 
*/
bool judge_low(int nowValue,int index){//是否 比nowValue小的数字都倒序 
    getLowToTmp(index,nowValue);
    int minn=nowValue; 
    bool isOk=true;//是否都倒序 
    for(int i=1;i<=tmpTop;i++){//如果从index+1开始向后枚举,枚举到的数都比当前的min小,则更新(此时合法),否则说明非倒序 
        if(tmp[i]>minn){
            isOk=false;
            break;
        }
        minn=min(minn,tmp[i]);
    }
    tmpTop=0;
    return isOk;
}


bool judge(){//是否合法 
    for(int i=1;i<=top;i++){
        int nowValue=stck[i];
        if(judge_low(nowValue,i)){//是否 比nowValue小的数字都倒序
            continue;
        }else{
            return 0;
        }
    }
    return 1;
}

int cnt=0;//输出计数 (超过20则关闭程序) 
void dfs(int nowNum,int siz){
    if(cnt==20){
        return;
    }
    if(siz==n){
        if(judge()){
            for(int i=1;i<=top;i++)cout<<stck[i];
            cout<<endl;
            cnt++;
        }
        return;
    }
    vis[nowNum]=1;
    for(int i=1;i<=n;i++){
        if(i!=nowNum&&(!vis[i])){
            stck[++top]=i;
            dfs(i,siz+1);
            top--;
        }
    }
    vis[nowNum]=0;

}


int main(){
    scanf("%d",&n);
    dfs(0,0);
    return 0;
}


活动打卡代码 AcWing 237. 程序自动分析

Object_
2020-06-10 00:27
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=3e6;

int sortTmp[MAXN],sortTmpN=0;//离散化 

int fa[MAXN];//并查集 

void merge(int i,int j){//merge j to i
    while(i!=fa[i]){
        i=fa[i];
        fa[i]=fa[fa[i]];
    }
    while(j!=fa[j]){
        j=fa[j];
        fa[j]=fa[fa[j]];
    }
    fa[j]=i;
}

int getFa(int i){
    while(fa[fa[i]]!=fa[i])fa[i]=fa[fa[i]];
    return fa[i];
}

struct SingleSet{
    int i,j,type;
}setsZero[MAXN],setsOne[MAXN];
int setZeroN=0,setOneN=0;

int findNum(int value){
    return lower_bound(sortTmp+1,sortTmp+sortTmpN+1,value)-sortTmp;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(sortTmp,0,sizeof(sortTmp));
        memset(fa,0,sizeof(fa));
        setZeroN=0;
        setOneN=0;
        sortTmpN=0;
        int n;
        scanf("%d",&n);
        bool notOk=0;
        for(int QWQ=1;QWQ<=n;QWQ++){
            int i,j,type;
            scanf("%d%d%d",&i,&j,&type);
            if(i==j&&type==1)continue;
            if(i==j&&type==0){
                notOk=1;
            }
            if(type==0){
                setsZero[++setZeroN].i=i,setsZero[setZeroN].j=j,setsZero[setZeroN].type=type;
            }else if(type==1){
                setsOne[++setOneN].i=i,setsOne[setOneN].j=j,setsOne[setOneN].type=type;

            }
            sortTmp[++sortTmpN]=i;
            sortTmp[++sortTmpN]=j;
        }
        if(notOk){
            cout<<"NO"<<endl;
            continue;
        }

        sort(sortTmp+1,sortTmp+sortTmpN+1);
        int newN=unique(sortTmp+1,sortTmp+sortTmpN+1)-(sortTmp+1);
        sortTmpN=newN;

        for(int i=1;i<=sortTmpN;i++){
            fa[i]=i;

        }
        for(int i=1;i<=setOneN;i++){
                int newI=findNum(setsOne[i].i),newJ=findNum(setsOne[i].j);

            if(setsOne[i].type==1){
                merge(newI,newJ);
            }
        }
        for(int i=1;i<=setZeroN;i++){
            int newI=findNum(setsZero[i].i),newJ=findNum(setsZero[i].j);
            if(setsZero[i].type==0){
                if(getFa(newI)==getFa(newJ)){
                    cout<<"NO"<<endl;
                    notOk=true;
                    break;
                }
            }
        }
        if(notOk)continue;
        else{
            cout<<"YES"<<endl;
            continue;
        }
    }
    return 0;
}



Object_
2020-06-10 00:26
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=3e6;

int sortTmp[MAXN],sortTmpN=0;//离散化 

int fa[MAXN];//并查集 

void merge(int i,int j){//merge j to i
    while(i!=fa[i]){
        i=fa[i];
        fa[i]=fa[fa[i]];
    }
    while(j!=fa[j]){
        j=fa[j];
        fa[j]=fa[fa[j]];
    }
    fa[j]=i;
}

int getFa(int i){
    while(fa[fa[i]]!=fa[i])fa[i]=fa[fa[i]];
    return fa[i];
}

struct SingleSet{
    int i,j,type;
}setsZero[MAXN],setsOne[MAXN];
int setZeroN=0,setOneN=0;

int findNum(int value){
    return lower_bound(sortTmp+1,sortTmp+sortTmpN+1,value)-sortTmp;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(sortTmp,0,sizeof(sortTmp));
        memset(fa,0,sizeof(fa));
        setZeroN=0;
        setOneN=0;
        sortTmpN=0;
        int n;
        scanf("%d",&n);
        bool notOk=0;
        for(int QWQ=1;QWQ<=n;QWQ++){
            int i,j,type;
            scanf("%d%d%d",&i,&j,&type);
            if(i==j&&type==1)continue;
            if(i==j&&type==0){
                notOk=1;
            }
            if(type==0){
                setsZero[++setZeroN].i=i,setsZero[setZeroN].j=j,setsZero[setZeroN].type=type;
            }else if(type==1){
                setsOne[++setOneN].i=i,setsOne[setOneN].j=j,setsOne[setOneN].type=type;

            }
            sortTmp[++sortTmpN]=i;
            sortTmp[++sortTmpN]=j;
        }
        if(notOk){
            cout<<"NO"<<endl;
            continue;
        }

        sort(sortTmp+1,sortTmp+sortTmpN+1);
        int newN=unique(sortTmp+1,sortTmp+sortTmpN+1)-(sortTmp+1);
        sortTmpN=newN;

        for(int i=1;i<=sortTmpN;i++){
            fa[i]=i;

        }
        for(int i=1;i<=setOneN;i++){
                int newI=findNum(setsOne[i].i),newJ=findNum(setsOne[i].j);

            if(setsOne[i].type==1){
                merge(newI,newJ);
            }
        }
        for(int i=1;i<=setZeroN;i++){
            int newI=findNum(setsZero[i].i),newJ=findNum(setsZero[i].j);
            if(setsZero[i].type==0){
                if(getFa(newI)==getFa(newJ)){
                    cout<<"NO"<<endl;
                    notOk=true;
                    break;
                }
            }
        }
        if(notOk)continue;
        else{
            cout<<"YES"<<endl;
            continue;
        }
    }
    return 0;
}

sortSet的时候RE了,就先处理1,再处理0




Object_
2020-05-27 00:44
#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stck;
    stack<int> minStck;
    MinStack() {

    }

    void push(int x) {
        stck.push(x);
        if(minStck.empty()||minStck.top()>stck.top()){
            minStck.push(x);
        }
    }

    void pop() {
        if(minStck.top()==stck.top())minStck.pop();
        stck.pop();
    }

    int top() {
        return stck.top();
    }

    int getMin() {
        return minStck.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */