HW0902

HW0902

Solution1

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
using namespace std;

int main(){
    int N;
    while(cin>>N){
        int color, num;
        vector<pair<int, int>> red, blue;
        unordered_set<int> visitedred, visitedblue;
        for(int i=0;i<N;++i){
            cin>>num>>color;
            if(color==1){
                if(visitedred.count(num)){
                    cout<<"null"<<endl;
                    break;
                }
                visitedred.emplace(num);
                red.emplace_back(i+1, num);
            }else if(color==2){
                if(visitedblue.count(num)){
                    cout<<"null"<<endl;
                    break;
                }
                visitedblue.emplace(num);
                blue.emplace_back(i+1, num);
            }else{
                cout<<"null"<<endl;
                break;
            }
        }
        auto comp=[](pair<int, int>& a, pair<int, int>& b){
            return a.second<b.second;
        };
        sort(red.begin(), red.end(), comp);
        sort(blue.begin(),blue.end(), comp);
        int redlen=red.size(), bluelen=blue.size();
        vector<int> tmp;
        for(int i=1;i<=3;++i){
            tmp.emplace_back(blue[bluelen-i].first);
        }
        if(redlen<3&&bluelen<3){
            cout<<"null"<<endl;
        }else{
            vector<int> tmp;
            int color;
            int sum=0;
            if(redlen>=3&&bluelen<3){
                color=1;
                for(int i=1;i<=3;++i){
                    tmp.emplace_back(red[redlen-i].first);
                    sum+=red[redlen-i].second;
                }
            }else if(redlen<3&&bluelen>=3){
                color=2;
                for(int i=1;i<=3;++i){
                    tmp.emplace_back(blue[bluelen-i].first);
                    sum+=blue[bluelen-i].second;
                }
            }else{
                int sumred=red[redlen-1].second+red[redlen-2].second+red[redlen-3].second;
                int sumblue=blue[bluelen-1].second+blue[bluelen-2].second+blue[bluelen-3].second;
                if(sumred>sumblue){
                    color=1;
                    for(int i=1;i<=3;++i){
                        tmp.emplace_back(red[redlen-i].first);
                    }
                    sum=sumred;
                }else if(sumblue>sumred){
                    color=2;
                    for(int i=1;i<=3;++i){
                        tmp.emplace_back(red[redlen-i].first);
                    }
                    sum=sumblue;
                }else{
                    if(red[redlen-3]<blue[bluelen-3]){
                        color=1;
                        for(int i=1;i<=3;++i){
                            tmp.emplace_back(red[redlen-i].first);
                        }
                        sum=sumred;
                    }else{
                        color=2;
                        for(int i=1;i<=3;++i){
                            tmp.emplace_back(red[redlen-i].first);
                        }
                        sum=sumblue;
                    }
                }
            }
            sort(tmp.begin(),tmp.end());
            cout<<tmp[0]<<' '<<tmp[1]<<' '<<tmp[2]<<endl;
            cout<<color<<endl;
            cout<<sum<<endl;
        }
    }
    return 0;
}

Solution2

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

void dfs(vector<vector<char>>& grid, int row, int  column){
    grid[row][column]='H';
    vector<int> dx{-1,0,1,0}, dy{0,1,0,-1};
    for(int i=0;i<4;++i){
        int a=row+dx[i], b=column+dy[i];
        if(a>=0&&a<grid.size()&&b>=0&&b<grid[0].size()&&grid[a][b]=='S')
            dfs(grid,a,b);
    }
}

void bfs(vector<vector<char>>& grid, int row, int column){
    queue<pair<int, int>> q;
    q.emplace(row, column);
    vector<int> dx{-1,0,1,0}, dy{0,1,0,-1};
    while(!q.empty()){
        int xx=q.front().first;
        int yy=q.front().second;
        q.pop();
        grid[xx][yy]='H';
        for(int i=0;i<4;++i){
            int a=xx+dx[i];
            int b=yy+dy[i];
            if(a>=0&&a<grid.size()&&b>=0&&b<grid[0].size()&&grid[a][b]=='S')
                q.emplace(a,b);
        }
    }
}

int numisland(vector<vector<char>>& grid){
    int count=0;
    for(int i=0;i<grid.size();++i){
        for(int j=0;j<grid[0].size();++j){
            if(grid[i][j]=='S'){
                ++count;
//                dfs(grid, i, j);
                bfs(grid, i, j);
            }
        }
    }
    return count;
}
int main(int argc, const char * argv[]) {
    int M, N;
    while(cin>>M>>N){
        vector<vector<char>> grid(M, vector<char>(N));
        string s;
        for(int i=0;i<M;++i){
            cin>>s;
            if(s.length()!=N){
                cout<<-1<<endl;
                break;
            }
            for(int j=0;j<N;++j)
                grid[i][j]=s[j];
        }
        cout<<numisland(grid)<<endl;
    }
    return 0;
}

Solution3

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

int main(int argc, const char * argv[]) {
    int k, N;
    while(cin>>k>>N){
        vector<int> wt, val;
        int tmp;
        for(int i=0;i<N;++i){
            cin>>tmp;
            wt.emplace_back(tmp);
        }
        for(int i=0;i<N;++i){
            cin>>tmp;
            val.emplace_back(tmp);
        }
        vector<int> dp(k+1, 0);
        for(int i=1;i<=N;++i){
            for(int j=k;j>=wt[i-1];--j){
                dp[j]=max(dp[j], dp[j-wt[i-1]]+val[i-1]);
            }
        }
        sort(dp.begin(), dp.end(), greater<int>());
        cout<<dp[0]<<endl;
    }
    return 0;
}