博客

2021 RoboCom 世界机器人开发者大赛-高职组（决赛）

1.小偷踩点

AC代码

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<string> v;
string s;
vector<int> row;
set<int> r;
vector<int> row_value[15];

signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    cin.get();
    for (int i = 1; i <= n; ++i) {
        getline(cin,s);
        v.push_back(s);
    }
    for (int i = 0; i < m; ++i) {
        int a;cin>>a;
        row.push_back(a);
        r.insert(a);
    }
    for (int i : row) {
        for (int j = 0; j < 10; ++j) {
            int b;cin>>b;
            row_value[i].push_back(b);
        }
    }
    int k;cin>>k;
    while(k--){
        int a,b,c;cin>>a;b = a / 10;c = a % 10;
        if (r.count(b) == 0){
            cout<<"?\n";
            continue;
        }
        if (row_value[b][c] == -1){
            cout<<"?\n";
            continue;
        }
        cout<<v[row_value[b][c] - 1]<<"\n";
    }
    return 0;
}

2.盲盒包装流水线

AC代码

#include<bits/stdc++.h>
using namespace std;

int n,s,a;
queue<string> q;
map<string,int> mp;
stack<int> sta;

signed main(){
    cin>>n>>s;
    for (int i = 0; i < n; ++i) {
        string t;cin>>t;
        q.push(t);
    }
    for (int i = 1; i <= n / s; ++i) {
        for (int j = 1; j <= s; ++j) {
            cin>>a;
            sta.push(a);
        }
        for (int j = 1; j <= s; ++j) {
            a = sta.top();sta.pop();
            mp[q.front()] = a;q.pop();
        }
    }
    int k;cin>>k;string t;
    while (k--){
        cin>>t;
        if (mp[t])
            cout<<mp[t]<<"\n";
        else
            cout<<"Wrong Number\n";
    }
    return 0;
}

3.到底爱不爱我

思路

看了样例说明就能知道了，这是一颗往上画的树，然后三种树枝就是逻辑与或非。

AC代码

#include<bits/stdc++.h>
using namespace std;

int n;
struct node{
    int p,ls,rs;
} x[35];
bool note[35];      //标记以找到根节点
int now;string s;
bool dfs(int tree){
    if (x[tree].p == 3){
        if (x[tree].ls == 0)
            return !(s[now++] - '0');
        else
            return !dfs(x[tree].ls);
    }
    else if (x[tree].p == 2){
        if (x[tree].ls == 0 && x[tree].rs == 0){
            bool f = (s[now] - '0') | (s[now + 1] - '0');
            now += 2;
            return f;
        }
        else if (x[tree].ls != 0 && x[tree].rs == 0){
            bool f = dfs(x[tree].ls);
            f = f | (s[now] - '0');
            ++now;
            return f;
        }
        else if (x[tree].ls == 0 && x[tree].rs != 0){
            bool f = (s[now] - '0');
            ++now;
            f = f | dfs(x[tree].rs);
            return f;
        }
        else{
            bool f = dfs(x[tree].ls);
            f = f | dfs(x[tree].rs);
            return f;
        }
    }
    else{
        if (x[tree].ls == 0 && x[tree].rs == 0){
            bool f = (s[now] - '0') & (s[now + 1] - '0');
            now += 2;
            return f;
        }
        else if (x[tree].ls != 0 && x[tree].rs == 0){
            bool f = dfs(x[tree].ls);
            f = f & s[now];
            now += 1;
            return f;
        }
        else if (x[tree].ls == 0 && x[tree].rs != 0){
            bool f = s[now] - '0';
            now += 1;
            f = f & dfs(x[tree].rs);
            return f;
        }
        else{
            bool f = dfs(x[tree].ls);
            f = f & dfs(x[tree].rs);
            return f;
        }
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for (int i = 1; i <= n; ++i) {
        cin>>x[i].p;
        if (x[i].p == 3)
            cin>>x[i].ls;
        else
            cin>>x[i].ls>>x[i].rs;
        note[x[i].ls] = note[x[i].rs] = true;
    }
    int tree = -1;
    for (int i = 1; i <= n; ++i)    //找根
        if (!note[i])
            tree = i;
    int k;cin>>k;
    while (k--){
        cin>>s;
        now = 0;
        if (dfs(tree))
            cout<<"Ai\n";
        else
            cout<<"BuAi\n";
    }
    return 0;
}

4.皆大欢喜

思路

这个题目就是个dfs爆搜，然后加上剪枝就行了，但是这个题目我被vector卡了，不知道是剪枝没剪好还是什么。总之就是我要用一个vector赋值给另一个vector，这种操作比数组的memcpy更慢。。。。

这里把两种代码都贴一下吧，也有可能是剪枝没剪好，大家可以帮我看看。

25分vector

#include<bits/stdc++.h>
using namespace std;

int n,m;
int x[15][15];
bool vis[15];
vector<int> ans;
vector<int> f_ans;

void dfs(const vector<int>& vv){
    for (int i = 1; i <= m; ++i) {
        if (vis[i]) continue;
        vector<int> v = vv;
        bool f = true;
        for (int j = 1; j <= n; ++j) {
            if (x[i][j] == 1)
                v[j] = 1;
            else if (x[i][j] == -1)
                v[j] = -1;
            if (v[j] != 1)
                f = false;
        }
        if (f){
            f_ans.push_back(i);
            if (ans.empty() || ans.size() > f_ans.size()){
                ans = f_ans;
            }
            f_ans.pop_back();
            return;
        }
        else{
            vis[i] = true;
            f_ans.push_back(i);
            dfs(v);
            f_ans.pop_back();
            vis[i] = false;
        }
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    vector<int> v(11,-1);       //记录猫咪的状态
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            cin>>x[i][j];
    dfs(v);
    cout<<ans[0];
    for (int i = 1; i < ans.size(); ++i) {
        cout<<" "<<ans[i];
    }
    return 0;
}

30分数组

#include<bits/stdc++.h>
using namespace std;

int n,m;
int x[15][15];
bool vis[15];
int note[15];
int ans[15],l;
int f_ans[15],cnt;

void dfs(){
    int note_note[15];
    for (int i = 1; i <= m; ++i) {
        if (vis[i]) continue;
        memcpy(note_note,note,60);
        bool f = true;
        for (int j = 1; j <= n; ++j) {
            if (x[i][j] == 1)
                note[j] = 1;
            else if (x[i][j] == -1)
                note[j] = -1;
            if (note[j] != 1)
                f = false;
        }
        if (f){
            f_ans[cnt++] = i;
            if (l == 0 || l > cnt){
                memcpy(ans,f_ans,60);
                l = cnt;
            }
            cnt--;
            return;
        }
        else{
            vis[i] = true;
            f_ans[cnt++] = i;
            dfs();
            cnt--;
            vis[i] = false;
        }
        memcpy(note,note_note,60);
    }
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (int i = 1; i <= n; ++i) note[i] = -1;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            cin>>x[i][j];
    dfs();
    cout<<ans[0];
    for (int i = 1; i < l; ++i) {
        cout<<" "<<ans[i];
    }
    return 0;
}