当前位置:网站首页>Gym - 102219j kitchen plates (violent or topological sequence)
Gym - 102219j kitchen plates (violent or topological sequence)
2022-07-07 09:47:00 【moyangxian】
The question : A little
. :
Practice one : A topological sort . Five plates are equivalent to a digraph with five points ,A<B amount to A One side points to B. Then do it again after drawing based on BFS Topology sorting of .
Time complexity 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;
}
Practice two :
violence .next_permutation() Work out "ABCDE" The whole arrangement , Then check whether the arrangement meets the conditions of the topic .
Time complexity 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;
}
边栏推荐
- 小程序弹出半角遮罩层
- Information Security Experiment 4: implementation of IP packet monitoring program
- Unity shader (to achieve a simple material effect with adjustable color attributes only)
- 有没有大佬帮忙看看这个报错,有啥排查思路,oracle cdc 2.2.1 flink 1.14.4
- How does mongodb realize the creation and deletion of databases, the creation of deletion tables, and the addition, deletion, modification and query of data
- 大佬们,有没有遇到过flink cdc读MySQLbinlog丢数据的情况,每次任务重启就有概率丢数
- 沙龙预告|GameFi 领域的瓶颈和解决方案
- 基础篇:带你从头到尾玩转注解
- How to become a senior digital IC Design Engineer (5-2) theory: ULP low power design technology (Part 1)
- PostgreSQL reports an error when creating a trigger,
猜你喜欢
【原创】程序员团队管理的核心是什么?
In fact, it's very simple. It teaches you to easily realize the cool data visualization big screen
H5网页播放器EasyPlayer.js如何实现直播视频实时录像?
How to use clipboard JS library implements copy and cut function
Lesson 1: finding the minimum of a matrix
Unity shader (learn more about vertex fragment shaders)
Unity shader (basic concept)
第一讲:寻找矩阵的极小值
Oracle安装增强功能出错
Colorbar of using vertexehelper to customize controls (II)
随机推荐
印象笔记终于支持默认markdown预览模式
Diffusion模型详解
Unity shader (learn more about vertex fragment shaders)
Over 100000 words_ Ultra detailed SSM integration practice_ Manually implement permission management
iNFTnews | 时尚品牌将以什么方式进入元宇宙?
The industrial chain of consumer Internet is actually very short. It only undertakes the role of docking and matchmaking between upstream and downstream platforms
大佬们,有没有遇到过flink cdc读MySQLbinlog丢数据的情况,每次任务重启就有概率丢数
小程序实现页面多级来回切换支持滑动和点击操作
2020CCPC威海 J - Steins;Game (sg函数、线性基)
Selenium+bs4 parsing +mysql capturing BiliBili Tarot data
第十四次试验
Install pyqt5 and Matplotlib module
高斯消元
Oracle installation enhancements error
How to become a senior digital IC Design Engineer (5-2) theory: ULP low power design technology (Part 1)
Pick up the premise idea of programming
HCIP 第一天 笔记整理
NETCORE 3.1 solves cross domain problems
Sqlplus garbled code problem, find the solution
[Frida practice] "one line" code teaches you to obtain all Lua scripts in wegame platform