当前位置:网站首页>Gym - 102219J Kitchen Plates(暴力或拓扑序列)
Gym - 102219J Kitchen Plates(暴力或拓扑序列)
2022-07-07 07:09:00 【moyangxian】
题意:略
题记:
做法一:拓扑排序。五个盘子相当于一个有五个点的有向图,A<B相当于A有一条边指向B。那么建图后做一遍基于BFS的拓扑排序即可。
时间复杂度O(5+5)
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int head[N],tot;
int s[N];
vector<int>ans;
struct Edge{
int to,next;
}e[N];
void init(){
memset(head,-1,sizeof(head));
memset(s,0,sizeof(s));
tot=0;
}
void addedge(int u,int v){
e[tot].to=v;
e[tot].next=head[u];
head[u]=tot++;
}
bool topsort(){
queue<int>q;
for(int i=0;i<5;i++)
if(!s[i]){
q.push(i);
ans.push_back(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(--s[v]==0){
q.push(v);
ans.push_back(v);
}
}
}
return ans.size()==5;
}
int main(){
init();
for(int i=0;i<5;i++){
char u,v,op;
cin>>u>>op>>v;
if(op=='>') swap(u,v);
addedge(u-'A',v-'A');
s[v-'A']++;
}
if(!topsort()) cout<<"impossible"<<endl;
else{
for(int i=0;i<ans.size();i++)
cout<<(char)(ans[i]+'A');
cout<<endl;
}
return 0;
}
做法二:
暴力。next_permutation()算出"ABCDE"的全排列,然后查看排列是否符合题目条件即可。
时间复杂度O(5!)
#include<bits/stdc++.h>
using namespace std;
const int N=10;
char a[]={
'A','B','C','D','E'};
char s[5][3];
bool check(){
for(int i=0;i<5;i++){
int p1,p2;
for(int j=0;j<5;j++){
if(a[j]==s[i][0]) p1=j;
if(a[j]==s[i][2]) p2=j;
}
if(p1>p2) return false;
}
return true;
}
int main(){
for(int i=0;i<5;i++){
cin>>s[i];
if(s[i][1]=='>') swap(s[i][0],s[i][2]);
}
do{
if(check()) break;
}while(next_permutation(a,a+5));
if(check()) for(int i=0;i<5;i++) cout<<a[i];
else cout<<"impossible"<<endl;
return 0;
}
边栏推荐
- nlohmann json
- Binary tree high frequency question type
- 【BW16 应用篇】安信可BW16模组/开发板AT指令实现MQTT通讯
- How to become a senior digital IC Design Engineer (5-3) theory: ULP low power design technology (Part 2)
- 牛客网——华为题库(61~70)
- Oracle installation enhancements error
- Kubernetes cluster capacity expansion to add node nodes
- JS reverse tutorial second issue - Ape anthropology first question
- Can flycdc use SqlClient to specify mysqlbinlog ID to execute tasks
- 信息安全实验三 :PGP邮件加密软件的使用
猜你喜欢
[bw16 application] Anxin can realize mqtt communication with bw16 module / development board at instruction
Dynamics 365online applicationuser creation method change
12、 Sort
Binary tree high frequency question type
软件建模与分析
AI从感知走向智能认知
Lecture 1: stack containing min function
Sqlplus garbled code problem, find the solution
ComputeShader
其实特简单,教你轻松实现酷炫的数据可视化大屏
随机推荐
章鱼未来之星获得25万美金奖励|章鱼加速器2022夏季创业营圆满落幕
Install pyqt5 and Matplotlib module
根据热门面试题分析Android事件分发机制(二)---事件冲突分析处理
C# Socke 服务器,客户端,UDP
Information Security Experiment 4: implementation of IP packet monitoring program
[cloud native] Devops (I): introduction to Devops and use of code tool
What is MD5
[4g/5g/6g topic foundation-146]: Interpretation of white paper on 6G overall vision and potential key technologies-1-overall vision
Thinkphp3.2 information disclosure
Windows starts redis service
大佬们,请问 MySQL-CDC 有什么办法将 upsert 消息转换为 append only 消
[4G/5G/6G专题基础-146]: 6G总体愿景与潜在关键技术白皮书解读-1-总体愿景
小程序弹出半角遮罩层
进程间的通信方式
How to solve the problem of golang select mechanism and timeout
Communication mode between processes
HCIP 第一天 笔记整理
在EXCEL写VBA连接ORACLE并查询数据库中的内容
The configuration and options of save actions are explained in detail, and you won't be confused after reading it
Nested (multi-level) childrn routes, query parameters, named routes, replace attribute, props configuration of routes, params parameters of routes