头像

QZX




离线:19小时前


最近来访(21)
用户头像
Foraino0267
用户头像
ACWing的用户
用户头像
Tenko_
用户头像
yxc
用户头像
冰之韵
用户头像
itdef
用户头像
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ
用户头像
十字军东征
用户头像
zombotany
用户头像
坠落的余晖

活动打卡代码 AcWing 413. 乒乓球

QZX
4天前

2022.8.11

这题着实有些恶心人了。

#include<iostream>
#include<string>
using namespace std;

inline void OutPutAnswer(int wScore, int lScore)
{
    cout<<wScore<<':'<<lScore<<endl;
}

int main(){
    char input;
    string races;
    while(!cin.fail()){
        cin>>input;
        if(input>='A'&&input<='Z'){
            races+=input;
        }
        if(input=='E'){
            break;
        }
    }
    cin.clear();

    int wScore=0,lScore=0;
    int rounds=0;
    //11
    for(auto race:races){
        if(race=='E'){
            OutPutAnswer(wScore,lScore);
        }
        if(race=='W')wScore++;
        if(race=='L')lScore++;
        if((wScore>=11||lScore>=11)&&abs(wScore-lScore)>=2){
            OutPutAnswer(wScore,lScore);
            wScore=lScore=0;
            rounds++;
        }
    }
    puts("");
    //21
    wScore=0;lScore=0;
    rounds=0;
    for(auto race:races){
        if(race=='E'){
            if(wScore!=0||lScore!=0||rounds==0){
                OutPutAnswer(wScore,lScore);
            }else{
                break;
            }
        }
        if(race=='W')wScore++;
        if(race=='L')lScore++;
        if((wScore>=21||lScore>=21)&&abs(wScore-lScore)>=2){
            OutPutAnswer(wScore,lScore);
            wScore=lScore=0;
            rounds++;
        }
    }
    return 0;
}



QZX
6天前

请大家和我一起膜拜Foraino老师stO Orz




QZX
7天前

2022.8.8

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

#define MAX_N 100010

enum Color{
    WHITE,
    BLACK,
    EMPTY
};

Color ReverseColor(Color color){
    if(color == WHITE)
        return BLACK;
    else if(color == BLACK)
        return WHITE;
    else
        return EMPTY;
}

vector<int> edges[MAX_N];
Color color[MAX_N];
int n, m;

bool BFSDye(int startId){
    queue<int> q;
    q.push(startId);
    color[startId] = BLACK;

    while(q.size()){
        int currentNode=q.front();
        q.pop();

        for(auto next:edges[currentNode]){
            if(color[next] == EMPTY){
                color[next] = ReverseColor(color[currentNode]);
                q.push(next);
            }
            else if(color[next] == color[currentNode]){
                return false;
            }
        }
    }
    return true;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    //init color
    for(int i = 1; i <= n; i++){
        color[i] = EMPTY;
    }

    for(int i = 1; i <= n; i++){
        if(color[i] == EMPTY){
            if(!BFSDye(i)){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}



QZX
7天前

2022.8.8

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_N 100010

struct Edge{
    int from,to,weight;
    bool operator<(const Edge& e) const{
        return weight<e.weight;
    }
};

vector<Edge> edges;
//并查集记录是否连通
int father[MAX_N];

int QueryAncestor(int id){
    if(father[id]==0) return id;
    //返回并且路径压缩
    return father[id]=QueryAncestor(father[id]);
}

inline bool HaveSameAncestor(int id1,int id2){
    return QueryAncestor(id1)==QueryAncestor(id2);
}

void Merge(int id1,int id2){
    if(HaveSameAncestor(id1,id2)) return;
    father[QueryAncestor(id1)]=QueryAncestor(id2);
}

int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edges.push_back((Edge){u,v,w});
    }

    //sort the edges
    sort(edges.begin(),edges.end());

    //traverse the edges
    int ans=0,count=0;
    for(auto edge:edges){
        if(!HaveSameAncestor(edge.from,edge.to)){
            ans+=edge.weight;
            count++;
            Merge(edge.from,edge.to);
        }
    }
    //check whether the graph is connected to another
    if(count<n-1){
        cout<<"impossible"<<endl;
    }else{
        cout<<ans<<endl;
    }
    return 0;
}



QZX
11天前

2022.8.4

#include<iostream>
#include<cstring>
using namespace std;

#define MAX_N 510
int map[MAX_N][MAX_N];
//点到集合的距离
int dist[MAX_N];
bool isInGather[MAX_N];

int main(){
    int n,m;
    int answer=0;

    cin>>n>>m;

    //init
    memset(dist,0x3f,sizeof(dist));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            map[i][j]=0x3f3f3f3f;
        }
    }

    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        map[a][b]=map[b][a]=min(map[a][b],c);
    }

    //Prim
    for(int i=1;i<=n;i++){
        //select min point from not in gather
        int minDistancePoint=-1;
        for(int j=1;j<=n;j++){
            if(!isInGather[j] && (minDistancePoint==-1 || dist[j]<dist[minDistancePoint])){
                minDistancePoint=j;
            }
        }

        //判断连通性:
        //非第一个点且到集合距离是INF则说明不连通
        if(i!=1&&dist[minDistancePoint]==0x3f3f3f3f){
            cout<<"impossible"<<endl;
            return 0;
        }
        if(i!=1){
            answer+=dist[minDistancePoint];
        }

        //add to gather
        isInGather[minDistancePoint]=true;

        //update dist
        for(int j=1;j<=n;j++){
            if(!isInGather[j]){
                dist[j]=min(dist[j],map[minDistancePoint][j]);
            }
        }
    }
    cout<<answer<<endl;

    //DEBUG:
    // for(int i=1;i<=n;i++){
    //     cout<<dist[i]<<" ";
    // }
    // puts("");

    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

QZX
14天前

2022.8.1

#include<iostream>
#include<cstring>
using namespace std;

#define MAX_N 210
#define INF 1e9

//dist[i][j]表示从i到j的最短路径长度,一开始的图也用dist存储
int dist[MAX_N][MAX_N];
int n,m,k;

int main(){
    cin>>n>>m>>k;

    //init
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dist[i][j]=INF;
            if(i==j){
                dist[i][j]=0;
            }
        }
    }

    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        dist[u][v]=min(dist[u][v],w);
    }

    //Calculate shortest path between every pair of points
    for(int transitPoint=1;transitPoint<=n;transitPoint++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dist[i][j]=min(dist[i][j],dist[i][transitPoint]+dist[transitPoint][j]);
            }
        }
    }

    //Query
    while(k--){
        int a,b;
        cin>>a>>b;
        if(dist[a][b]>=2e8){
            cout<<"impossible"<<endl;
        }else{
            cout<<dist[a][b]<<endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

QZX
15天前

2022.7.31

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

#define MAX_N 2010

struct Edge{
    int to,w;
};

vector<Edge> map[MAX_N];
int dist[MAX_N];
//用于记录路径长度
int cnt[MAX_N];
int n,m;

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        map[u].push_back((Edge){v,w});
    }

    //spfa

    //init
    queue<int> updated;
    //放置所有点原因:防止存在1点到达不了的负环
    for(int i=1;i<=n;i++){
        updated.push(i);
    }

    while(updated.size()){
        int point=updated.front();
        updated.pop();
        for(auto edge:map[point]){
            if(dist[edge.to]>dist[point]+edge.w){
                dist[edge.to]=dist[point]+edge.w;
                updated.push(edge.to);
                cnt[edge.to]=cnt[point]+1;
                //抽屉原理判断负环
                if(cnt[edge.to]>=n){
                    cout<<"Yes"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

QZX
15天前

2022.7.31

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

struct Edge{
    int to,w;
};

#define MAX_N 100010

vector<Edge> map[MAX_N];
int dist[MAX_N];
int n,m;

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        map[u].push_back((Edge){v,w});
    }

    //初始化
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    //记录被更新过的点
    queue<int> updated;
    updated.push(1);

    while(updated.size()){
        int point=updated.front();
        updated.pop();
        for(auto edge:map[point]){
            //若可以更新则放入更新队列
            if(dist[point]+edge.w<dist[edge.to]){
                dist[edge.to]=dist[point]+edge.w;
                updated.push(edge.to);
            }
        }
    }

    if(dist[n]==0x3f3f3f3f){
        cout<<"impossible"<<endl;
    }else{
        cout<<dist[n]<<endl;
    }
    return 0;
}



QZX
16天前

2022.7.30

#include<iostream>
#include<cstring>
using namespace std;
#define MAX_N 510

int map[MAX_N][MAX_N];
int dist[MAX_N];
bool isShortest[MAX_N];
int n,m;

int main(){
    cin>>n>>m;

    //init
    memset(map,0x3f,sizeof(map));
    memset(dist,0x3f,sizeof(dist));

    for(int i=1;i<=m;i++){
        int from,to,weight;
        cin>>from>>to>>weight;
        map[from][to]=min(map[from][to],weight);
    }

    //dijkstra
    dist[1]=0;

    for(int i=1;i<=n;i++){
        //find shortest distance
        int shortestPoint=-1;
        for(int j=1;j<=n;j++){
            if(!isShortest[j] && (shortestPoint==-1 || dist[j]<dist[shortestPoint])){
                shortestPoint=j;
            }
        }

        //update
        isShortest[shortestPoint]=true;
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[shortestPoint]+map[shortestPoint][j]);
        }
    }
    if(dist[n]==0x3f3f3f3f){
        cout<<-1<<endl;
    }else 
    {
        cout<<dist[n]<<endl;
    }
    return 0;
}



QZX
16天前

2022.7.30

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define MAX_N 10010

struct Edge{
    int from,to,weight;
};

vector<Edge> edges;
int dist[MAX_N];
//backup用于保存上一次的dist,新一次dist在backup基础上推导出
//防止更新[该次更新的边]的边已经变化
int backup[MAX_N];

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int from,to,weight;
        cin>>from>>to>>weight;
        edges.push_back({from,to,weight});
    }

    //初始化
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;

    for(int updateTime=1;updateTime<=k;updateTime++){
        //保存上一个状态
        memcpy(backup,dist,sizeof(backup));
        for(auto edge:edges){
            int from=edge.from,to=edge.to,weight=edge.weight;
            //用上一状态更新当前状态
            dist[to]=min(dist[to],backup[from]+weight);
        }
    }
    if(dist[n]>1e8){
        cout<<"impossible"<<endl;
    }else{
        cout<<dist[n]<<endl;
    }
    return 0;
}