2022-08-21-星环科技-C++开发笔试-56分

17:00-21:00
睡了一下午到18:00，然后19:00-21:00还有一场ArcSoft虹软笔试，所以只剩下不到一小时时间做。

题目私聊。

// 11min 100% 30'

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

int main(){
    int n,m;cin>>n>>m;
    int t=0,t1,t2;
    vector<int> d(n,0);
    vector<vector<int>> next(n);
    unordered_map<string, int> stot;
    string s,st1,st2;
    for(int i=0;i<m;i++){
        cin>>s;
        int j=0;
        while(s[j]!='-') j++;
        st1=s.substr(0,j);
        st2=s.substr(j+2);
        if(stot.count(st1))
            t1=stot[st1];
        else {
            t1=stot[st1]=t;
            t++;
        }
        if(stot.count(st2))
            t2=stot[st2];
        else{
            t2=stot[st2]=t;
            t++;
        }
        d[t1]++;
        next[t2].push_back(t1);
    }
    queue<int> q;
    int c=0;
    for(int i=0;i<n;i++){
        if(d[i]==0){
            q.push(i);
            c++;
        }
    }
    while(!q.empty()){
        t1=q.front();
        q.pop();
        for(auto i:next[t1]){
            d[i]--;
            if(d[i]==0){
                q.push(i);
                c++;
            }
        }
    }
    if(c==n)cout<<"YES";
    else cout<<"NO";
    return 0;
}



// 25min 60% 30'
#include<iostream>
#include<string>
#include<vector>
#include<unordered_set>
using namespace std;

int dfs(int i, char ec, int l, unordered_set<string>& se, vector<unordered_set<string>>& b, vector<unordered_set<string>>& e){
    int tl=0;
    for(auto ei:e[ec-'a']){
        if(ei[0]=='a'+i&&se.count(ei)){
            tl=max(tl,l+(int)ei.length());
        }
    }
    if(tl==0) return 0;
    for(auto si:b[i]){
        if(se.count(si)==0)
            continue;
        se.erase(si);
        tl=max(tl,l+dfs(si[si.length()-1]-'a',ec,l+si.length(),se,b,e));
        se.insert(si);
    }
    return tl;
}

int main(){
    int n;cin>>n;
    vector<unordered_set<string>> b(26),e(26);
    unordered_set<string> se;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        b[s[0]-'a'].insert(s);
        e[s[s.length()-1]-'a'].insert(s);
        se.insert(s);
    }
    int maxl=0;
    for(int i=0;i<26;i++){
        if(b[i].size()==0||e[i].size()==0)
            continue;
        for(auto si:b[i]){
            unordered_set<string> se2=se;
            se2.erase(si);
            maxl=max(maxl,dfs(si[si.length()-1]-'a',si[0],si.length(),se2,b,e));
            se2.insert(si);
        }
    }
    cout<<maxl;
    return 0;
}


// 28min 20% 40'

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

bool testp(vector<vector<bool>>&a,vector<vector<bool>>&b,int li,int lj){
    int i1=0,j1=0,i2=0,j2=0;
    int n1=a.size(),m1=a[0].size(),n2=b.size(),m2=b[0].size();
    for(;i1<n1;i1++){
        for(;j1<m1;j1++){
            if(a[i1][j1])
                break;
        }
        if(a[i1][j1])
            break;
    }
    for(;i2<n2;i2++){
        for(;j2<m2;j2++){
            if(b[i2][j2])
                break;
        }
        if(b[i2][j2])
            break;
    }
    int ei=i1+li,ej=j1+lj;
    bool f=1;
    for(;i1<ei&&i2<n2;i1++,i2++){
        for(;j1<ej&&j2<m2;j1++,j2++){
            if(a[i1][j1]!=b[i2][j2]){
                return 0;
            }
        }
    }
    return f;
}

bool testflr(vector<vector<bool>>&a,vector<vector<bool>>&b,int li,int lj){
    int i1=0,j1=0,i2=0,j2=0;
    int n1=a.size(),m1=a[0].size(),n2=b.size(),m2=b[0].size();
    for(;i1<n1;i1++){
        for(;j1<m1;j1++){
            if(a[i1][j1])
                break;
        }
        if(a[i1][j1])
            break;
    }
    for(i2=0;i2<n2;i2++){
        for(j2=m2-1;j2>=0;j2--){
            if(b[i2][j2])
                break;
        }
        if(b[i2][j2])
            break;
    }
    int ei=i1+li,ej=j1+lj;
    bool f=1;
    for(;i1<ei&&i2<n2;i1++,i2++){
        for(;j1<ej&&j2>=0;j1++,j2--){
            if(a[i1][j1]!=b[i2][j2]){
                return 0;
            }
        }
    }
    return f;
}

bool testfud(vector<vector<bool>>&a,vector<vector<bool>>&b,int li,int lj){
    int i1=0,j1=0,i2=0,j2=0;
    int n1=a.size(),m1=a[0].size(),n2=b.size(),m2=b[0].size();
    for(;i1<n1;i1++){
        for(;j1<m1;j1++){
            if(a[i1][j1])
                break;
        }
        if(a[i1][j1])
            break;
    }
    for(i2=n2-1;i2>=0;i2--){
        for(j2=0;j2<m2;j2++){
            if(b[i2][j2])
                break;
        }
        if(b[i2][j2])
            break;
    }
    int ei=i1+li,ej=j1+lj;
    bool f=1;
    for(;i1<ei&&i2>=0;i1++,i2--){
        for(;j1<ej&&j2<m2;j1++,j2++){
            if(a[i1][j1]!=b[i2][j2]){
                return 0;
            }
        }
    }
    return f;
}

int main(){
    int n,m,t;
    int x;cin>>x;
    cin>>n>>m;
    vector<vector<bool>> b(n,vector<bool>(m));
    int ones=0;
    int si=-1,ei=0,sj=m,ej=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>t;
            if(t==1) {
                b[i][j]=true;
                ones++;
                if(si==-1){
                    si=i;
                }
                ei=i;
                sj=min(sj,j);
                ej=max(ej,j);
            }
            else b[i][j]=false;
        }
    int li=ei-si+1,lj=ej-sj+1;
    for(int w=1;w<x;w++){
        cin>>n>>m;
        int o=0;
        vector<vector<bool>> c(n,vector<bool>(m));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                cin>>t;
                if(t==1) {
                    c[i][j]=true;
                    o++;
                }
                else c[i][j]=false;
            }
        if(o!=ones){
            cout<<"false\n";
            continue;
        }
        if(testp(b,c,li,lj)){
            cout<<"true\n";
            continue;
        }
        if(testflr(b,c,li,lj)){
            cout<<"true\n";
            continue;
        }
        if(testfud(b,c,li,lj)){
            cout<<"true\n";
            continue;
        }
        cout<<"false\n";
    }
    return 0;
}