2024天梯赛选拔

发表于 更新于 分类于 本文字数： 723 阅读时长 ≈ 3 分钟

良心评测机

这是一道队列和栈的题。

对于所有提交用一个队列维护，而每个选手的提交分别用一个栈来维护，再开一个标记数组标记提交是否已评测即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

using ll=long long;

ll n, id;
string tmp;
queue<array<int,3>> q;
stack<array<int,2>> st[(int)1e5+9];
bitset<(int)1e6+9> vis;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1,op,uid;i<=n;++i){
    	cin>>op;
    	if(op==1){
    		cin>>uid>>tmp;
    		q.push({uid,i,tmp == "CORRECT"});
    		st[uid].push({i,tmp == "CORRECT"});
    	}else{
    		if(id){
    			while(!st[id].empty()&&vis[st[id].top()[0]])st[id].pop();
    			if(!st[id].empty()){
    				auto [aa,bb]=st[id].top();st[id].pop();

    				cout<<aa<<"\n";
    				vis[aa]=true;
    				if(!bb)id=0;
    				continue;
    			}
    		}

    		while(!q.empty()&&vis[q.front()[1]])q.pop();

    		if(!q.empty()){
    			auto [aa,bb,cc] = q.front();q.pop();

    			cout<<bb<<"\n";
    			vis[bb]=true;

    			if(cc)id=aa;
    			else id=0;

    		}else cout<<"NOTHING HAPPENED\n";
    	}
    }
    return 0;
}

寻径指津

这是一道bfs题目，因为无压力桩的版本已经在22年的萌新赛出过，所以今天的是有压力桩的版本。

用一个三维数组维护位置为在地图的压力桩为状态下的最短路即可，剩下部分就是一个bfs板子了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

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

using pii=pair<int,int>;
using ll=long long;

constexpr int N = 109;

constexpr pii dirs[]={{1,0},{0,1},{-1,0},{0,-1}};

pii st,en;

int a[N][N],n,m,tot;
int dis[N][N][1<<11],vis[N][N][1<<11],ans=0x3f3f3f3f;
pair<array<int,3>,char> lst[N][N][1<<11];
map<pii,char> covdirs;
char c;
map<pii,int> ylz;
pii cov[20];

queue<array<int,3>> q;

int add(int x,int y){
    if(ylz.count({x,y}))return 1ll<<ylz[{x,y}];
    else return 0;
}

void solmp(int x,int sta){
    if(sta){
        for(int i=0;i<10;++i)if((x>>i)&1){
            auto [xx,yy]=cov[i];
            a[xx][yy]=2;
        }
    }else{
        for(int i=0;i<10;++i)if((x>>i)&1){
            auto [xx,yy]=cov[i];
            a[xx][yy]=3;
        }
    }
}

int main()
{
    {
        covdirs[{-1,0}]='U';
        covdirs[{1,0}]='D';
        covdirs[{0,-1}]='L';
        covdirs[{0,1}]='R';
    }

    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
        scanf(" %c",&c);
        if(c=='.')a[i][j]=1;
        else if(c=='#')a[i][j]=2;
        else if(c=='?'){
            a[i][j]=3,ylz[{i,j}]=tot,cov[tot]={i,j};
            tot+=1;
        }
        else if(c=='S')a[i][j]=4,st={i,j};
        else a[i][j]=5,en={i,j};
    }
    dis[st.first][st.second][0]=0;
    q.push({st.first,st.second,0});

    while(!q.empty()){
        auto [aa,bb,cc]=q.front();q.pop();
        if(vis[aa][bb][cc])continue;
        vis[aa][bb][cc]=1;

        solmp(cc,1);
        for(auto [xx,yy]:dirs){
            int ta=aa,tb=bb,tc=cc;


            while(a[ta+xx][tb+yy]!=2){
                 tc|=add(ta,tb);
                 ta+=xx,tb+=yy;
                 if((pii){ta,tb}==en)break;
            }
            if(dis[ta][tb][tc]>dis[aa][bb][cc]+1)dis[ta][tb][tc]=dis[aa][bb][cc]+1,lst[ta][tb][tc]={{aa,bb,cc},covdirs[{xx,yy}]};
            if((pii){ta,tb}==en){
                ans=min(ans,dis[ta][tb][tc]);
            }else q.push({ta,tb,tc});
        }
        solmp(cc,0);
    }

    if(ans==0x3f3f3f3f){
        printf("-1\n");
    }else{
        printf("%d\n",ans);

        vector<char> res;

        for(int i=0;i<(1ll<<10);++i){
            if(dis[en.first][en.second][i] == ans){
                auto [aa,bb]=en;int cc=i;
                while((pii){aa,bb}!=st){
                    auto [tx,ty]=lst[aa][bb][cc];
                    res.push_back(ty);
                    aa=tx[0],bb=tx[1],cc=tx[2];
                }
                break;
            }
        }
        reverse(res.begin(),res.end());
        for(auto it:res)printf("%c\n",it);

    }

    return 0;
}