主頁 > 前端設計 > ccf csp 2020年09月 第三題：點亮數字人生（dfs + 判環）

ccf csp 2020年09月 第三題：點亮數字人生（dfs + 判環）

2020-10-05 02:06:34 前端設計

題目背景
土豪大學的計算機系開了一門數字邏輯電路課，第一個實驗叫做“點亮數字人生”，要用最基礎的邏輯元件組裝出實際可用的電路，時間已經是深夜了，盡管實驗箱上密密麻麻的連線已經拆裝了好幾遍，小君同學卻依舊沒能讓她的電路正常作業，你能幫助她模擬出電路的功能，成功點亮她的數字人生嗎？

問題描述
本題中，你需要實作一個簡單的數字邏輯電路模擬器，如果你已經有了此方面的基礎，可以直接跳過本節，在閱讀時，也可以參照前兩個樣例的圖示和解釋，這有助于你更好地理解數字邏輯電路的作業原理，

數字邏輯電路是用來傳輸數字信號（也就是二進制信號）的電路，一般來說，數字邏輯電路可以分為兩大類，即組合邏輯（combinational logic）電路和時序邏輯（sequential logic）電路，在本題中，我們僅關注組合邏輯電路，這種電路僅由邏輯門（logical gate）構成，一個邏輯門可以理解為一個多輸入單輸出的函式，輸入端連接至少一個信號，而后經過一定的邏輯運算輸出一個信號，常見的邏輯門包括與（AND）、或（OR）、非（NOT）、異或（XOR）等，均與編程語言中的按位運算是對應的，

將一系列的邏輯門連接起來，就能構成具有特定功能的電路，它的功能可能很簡單（如一位二進制加法只需要一個異或門），也可能極其復雜（如除法），無論復雜程度，這類電路的特點是：它不維持任何的狀態，任何時刻輸出只與輸入有關，隨輸入變化，真實世界中的邏輯器件由于物理規律的限制，存在信號傳播延時，為了簡單起見，本題中我們模擬的組合邏輯電路不考慮延時：一旦輸入變化，輸出立刻跟著變化，

考慮到組合邏輯電路的這一特性，設計時不能允許組合環路（combinational loop）的存在，即某邏輯門的輸入經過了一系列器件之后又被連接到了自己的輸入端，真實世界中，這種做法將導致電路變得不穩定，甚至損壞元器件，因此，你也需要探測可能的環路，需要注意，環路的存在性與邏輯門的具體功能沒有任何關系；只要連接關系上存在環路，電路就無法正常作業，
感想：考試的時候讀電路輸入輸出的時候以為編號只有一位，然后讀入時只讀了一個數字，實際上是可以有O10 ， I100這樣的讀入，讀的時候可以用字串流或者sscanf，
思路：先按照給出的電路圖存圖，然后dfs模擬即可，還有一個小坑是只要圖有環，就算要輸出的部分不涉及環路也判LOOP（我最開始只判斷要輸出的部分，得了80分），判環可以用拓撲排序，或者直接dfs加標記即可

代碼：
dfs + 拓撲排序判環

#include <bits/stdc++.h>


using namespace std;

const int maxn = 705 , N = 2e4 + 5;

struct gate{
	string func;
	vector <int> ii;
	vector <int> o;
	int out;
	gate() {
		out;
	}
	gate(string s) : func(s){}
};

int tin[N][maxn * 6] , tout[N] , mout[maxn] , in[N];
int vis[maxn];
vector <int> ans[N];
vector <gate> g;

bool dfs(int u , int k ) {
	//if(vis[u]) return false;
	if(mout[u] != -1)return mout[u];
	int res = 0;
	if(g[u].func[0] == 'X') {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res ^= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res ^= mout[v];
		}
		mout[u] = res;
		//cout << "u = " << u << "res = " << res << endl;
	}
	else if(g[u].func[0] == 'A') {
		res = 1;
		bool flag = 0;
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res &= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res &= mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func[0] == 'O') {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res |= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res |= mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func == "NOT") {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res = !tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res = !mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func == "NAND") {
		res = 1;
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res &= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res &= mout[v];
		}
		mout[u] = !res;
	}
	else {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res |= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res |= mout[v];
		}
		mout[u] = !res;
	}
	return true;
}

bool tp(int n ) {
	for(int i = 1 ; i <= n ; i++) {
		for(int j = 0; j < g[i].o.size() ; j++) {
			int v = g[i].o[j];
			in[v]++;
		}
	}
	queue <int> q;
	int cnt = 0;
	for(int i = 1 ; i <= n ; i++) {
		if(!in[i]) {
			cnt++;
			q.push(i);
		}
	}
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(in[v] == 1) {
				q.push(v);
				cnt++;
			}
			in[v]--;
		}
	}
	if(cnt < n)return false;
	else return true;
	
}


int main() {
	int Q;
	int m , n;
	ios::sync_with_stdio(0);
	cin >> Q;
	while(Q--) {
		cin >> m >> n;
		g.clear();
		g.push_back(gate());
		memset(in , 0 , sizeof(in));
		for(int i = 1 ; i <= n ; i++) {
			string func;
			int k;
			cin >> func >> k;
			gate g1 = gate(func);
			while(k--) {
				string s;
				cin >> s;
				int t = 0;
				stringstream ss(s.substr(1));
				ss >> t;
				if(s[0] == 'O')g1.o.push_back(t);
				else if(s[0] == 'I')g1.ii.push_back(t);
			}
			g.push_back(g1);
		}
		int s;
		cin >> s;
		for(int i = 1 ; i <= s ; i++) {
			for(int j = 1 ; j <= m ; j++) {
				cin >> tin[i][j];
			}
		}
		bool flag = 0;
		memset(vis , 0 , sizeof(vis));
		if( !tp(n) ) {
			flag = 1;
		}
		for(int i = 1 ; i <= s ; i++) {
			int si;
			for(int j = 1 ; j <= n ; j++)mout[j] = -1;
			cin >> si;
			for(int j = 1 ; j <= si ; j++) {
				cin >> tout[j];
			}
			
			for(int j = 1 ; j <= si && !flag; j++) {
				dfs(tout[j] , i);
				ans[i].push_back(mout[tout[j]]);
			}
		}
		if(!flag) {
			for(int i = 1 ; i <= s ; i++) {
				for(int j = 0 ; j < ans[i].size() ; j++) {
					if(j > 0)cout << " ";
					cout << ans[i][j];
				}
				cout << "\n";
			}
		}
		else {
			cout << "LOOP\n";
		}
		for(int i = 1 ; i <= s; i++) {
			ans[i].clear();
		}
	}
	return 0;
}

dfs + dfs判環：

#include <bits/stdc++.h>


using namespace std;

const int maxn = 705 , N = 2e4 + 5;

struct gate{
	string func;
	vector <int> ii;
	vector <int> o;
	int out;
	gate() {
		out;
	}
	gate(string s) : func(s){}
};

int tin[N][maxn * 6] , tout[N] , mout[maxn] , in[N];
int vis[maxn];
vector <int> ans[N];
vector <gate> g;

bool dfs(int u , int k ) {
	//if(vis[u]) return false;
	if(mout[u] != -1)return mout[u];
	int res = 0;
	if(g[u].func[0] == 'X') {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res ^= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res ^= mout[v];
		}
		mout[u] = res;
		//cout << "u = " << u << "res = " << res << endl;
	}
	else if(g[u].func[0] == 'A') {
		res = 1;
		bool flag = 0;
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res &= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res &= mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func[0] == 'O') {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res |= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res |= mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func == "NOT") {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res = !tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res = !mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func == "NAND") {
		res = 1;
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res &= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res &= mout[v];
		}
		mout[u] = !res;
	}
	else {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res |= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res |= mout[v];
		}
		mout[u] = !res;
	}
	return true;
}

bool solve(int u , int f) {
	if(vis[u]) {
		if( vis[u] == f )return false;
		return true;
	}
	vis[u] = f;
	for(int i = 0 ; i < g[u].o.size() ; i++) {
		int v = g[u].o[i];
		if(!solve(v , f) ) {
			return false;
		}
	}
	
	return true;
}

bool tp(int n ) {
	
	for(int i = 1 ; i <= n ; i++) {
		if(!vis[i] && !solve(i , i)) {
			
			return false; 
		}
	}
	return true;
}


int main() {
	int Q;
	int m , n;
	ios::sync_with_stdio(0);
	cin >> Q;
	while(Q--) {
		cin >> m >> n;
		g.clear();
		g.push_back(gate());
		memset(in , 0 , sizeof(in));
		for(int i = 1 ; i <= n ; i++) {
			string func;
			int k;
			cin >> func >> k;
			gate g1 = gate(func);
			while(k--) {
				string s;
				cin >> s;
				int t = 0;
				stringstream ss(s.substr(1));
				ss >> t;
				if(s[0] == 'O')g1.o.push_back(t);
				else if(s[0] == 'I')g1.ii.push_back(t);
			}
			g.push_back(g1);
		}
		int s;
		cin >> s;
		for(int i = 1 ; i <= s ; i++) {
			for(int j = 1 ; j <= m ; j++) {
				cin >> tin[i][j];
			}
		}
		bool flag = 0;
		memset(vis , 0 , sizeof(vis));
		if( !tp(n) ) {
			flag = 1;
		}
		for(int i = 1 ; i <= s ; i++) {
			int si;
			for(int j = 1 ; j <= n ; j++)mout[j] = -1;
			cin >> si;
			for(int j = 1 ; j <= si ; j++) {
				cin >> tout[j];
			}
			
			for(int j = 1 ; j <= si && !flag; j++) {
				dfs(tout[j] , i);
				ans[i].push_back(mout[tout[j]]);
			}
		}
		if(!flag) {
			for(int i = 1 ; i <= s ; i++) {
				for(int j = 0 ; j < ans[i].size() ; j++) {
					if(j > 0)cout << " ";
					cout << ans[i][j];
				}
				cout << "\n";
			}
		}
		else {
			cout << "LOOP\n";
		}
		for(int i = 1 ; i <= s; i++) {
			ans[i].clear();
		}
	}
	return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/156063.html

標籤：其他

上一篇：【基礎版】大學計算機-計算思維導論

下一篇：2020年（2021屆計算機保研）（北航、國防科大、信工所、上科大、武大、哈深、哈工本部）

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • vue移動端上拉加載

    可能做得過于簡單或者比較low，請各位大佬留情，一起探討技術 ......

    uj5u.com 2020-09-10 04:38:07 more
  • 優美網站首頁，頂部多層導航

    一個個人用的瀏覽器首頁，可以把一下常用的網站放在這里，平常打開會比較方便。 第一步，HTML代碼 <script src=https://www.cnblogs.com/szharf/p/"js/jquery-3.4.1.min.js"></script> <div id="navigate"> <ul> <li class="labels labels_1"> ......

    uj5u.com 2020-09-10 04:38:47 more
  • 頁面為要加<!DOCTYPE html>

    最近因為寫一個js函式，需要用到$(window).height(); 由于手寫demo的時候，過于自信，其實對前端方面的認識也不夠體系，用文本檔案直接敲出來的html代碼，第一行沒有加上<!DOCTYPE html> 導致了$(window).height();的結果直接是整個document的高 ......

    uj5u.com 2020-09-10 04:38:52 more
  • WordPress網站程式手動升級要做好資料備份

    WordPress博客網站程式在進行升級前，必須要做好網站資料的備份，這個問題良家佐言是遇見過的；在剛開始接觸WordPress博客程式的時候，因為升級問題和博客網站的修改的一些嘗試，良家佐言是吃盡了苦頭。因為購買的是西部數碼的空間和域名，每當佐言把自己的WordPress博客網站搞到一塌糊涂的時候 ......

    uj5u.com 2020-09-10 04:39:30 more
  • WordPress程式不能升級為5.4.2版本的原因

    WordPress是一款個人博客系統，受到英文博客愛好者和中文博客愛好者的追捧，并逐步演化成一款內容管理系統軟體；它是使用PHP語言和MySQL資料庫開發的,用戶可以在支持PHP和MySQL資料庫的服務器上使用自己的博客。每一次WordPress程式的更新，就會牽動無數WordPress愛好者的心， ......

    uj5u.com 2020-09-10 04:39:49 more
  • 使用CSS3的偽元素進行首字母下沉和首行改變樣式

    網頁中常見的一種效果，首字改變樣式或者首行改變樣式，效果如下圖。 代碼： <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, ......

    uj5u.com 2020-09-10 04:40:09 more
  • 關于a標簽的講解

    什么是a標簽？ <a> 標簽定義超鏈接，用于從一個頁面鏈接到另一個頁面。 <a> 元素最重要的屬性是 href 屬性，它指定鏈接的目標。 a標簽的語法格式：<a href=https://www.cnblogs.com/summerxbc/p/"指定要跳轉的目標界面的鏈接">需要展示給用戶看見的內容</a> a標簽 在所有瀏覽器中，鏈接的默認外觀如下： 未被訪問的鏈接帶 ......

    uj5u.com 2020-09-10 04:40:11 more
  • 前端輪播圖

    在需要輪播的頁面是引入swiper.min.js和swiper.min.css swiper.min.js地址： 鏈接：https://pan.baidu.com/s/15Uh516YHa4CV3X-RyjEIWw 提取碼：4aks swiper.min.css地址 鏈接：https://pan.b ......

    uj5u.com 2020-09-10 04:40:13 more
  • 如何設定html中的背景圖片（全屏顯示，且不拉伸）

    1 <style>2 body{background-image:url(https://uploadbeta.com/api/pictures/random/?key=BingEverydayWallpaperPicture); 3 background-size:cover;background ......

    uj5u.com 2020-09-10 04:40:16 more
  • Java學習——HTML詳解（上）

    HTML詳解 初識HTML Hyper Text Markup Language（超文本標記語言） 1 <!--DOCTYPE:告訴瀏覽器我們要使用什么規范--> 2 <!DOCTYPE html> 3 <html lang="en"> 4 <head> 5 <!--meta 描述性的標簽，描述一些 ......

    uj5u.com 2020-09-10 04:40:33 more
最新发布
  • 我的第一個NPM包:panghu-planebattle-esm(胖虎飛機大戰)使用說明

    好家伙,我的包終于開發完啦 歡迎使用胖虎的飛機大戰包!! 為你的主頁添加色彩 這是一個有趣的網頁小游戲包,使用canvas和js開發 使用ES6模塊化開發 效果圖如下: (覺得圖片太sb的可以自己改) 代碼已開源!! Git: https://gitee.com/tang-and-han-dynas ......

    uj5u.com 2023-04-20 07:59:23 more
  • 生產事故-走近科學之消失的JWT

    入職多年，面對生產環境，盡管都是小心翼翼，慎之又慎，還是難免捅出簍子。輕則滿頭大汗，面紅耳赤。重則系統停擺，損失資金。每一個生產事故的背后，都是寶貴的經驗和教訓，都是專案成員的血淚史。為了更好地防范和遏制今后的各類事故，特開此專題，長期更新和記錄大大小小的各類事故。有些是親身經歷，有些是經人耳傳口授 ......

    uj5u.com 2023-04-18 07:55:04 more
  • 記錄--Canvas實作打飛字游戲

    這里給大家分享我在網上總結出來的一些知識，希望對大家有所幫助 打開游戲界面，看到一個畫面簡潔、卻又富有挑戰性的游戲。螢屏上，有一個白色的矩形框，里面不斷下落著各種單詞，而我需要迅速地輸入這些單詞。如果我輸入的單詞與螢屏上的單詞匹配，那么我就可以獲得得分；如果我輸入的單詞錯誤或者時間過長，那么我就會輸 ......

    uj5u.com 2023-04-04 08:35:30 more
  • 了解 HTTP 看這一篇就夠

    在學習網路之前，了解它的歷史能夠幫助我們明白為何它會發展為如今這個樣子，引發探究網路的興趣。下面的這張圖片就展示了“互聯網”誕生至今的發展歷程。 ......

    uj5u.com 2023-03-16 11:00:15 more
  • 藍牙-低功耗中心設備

    //11.開啟藍牙配接器 openBluetoothAdapter //21.開始搜索藍牙設備 startBluetoothDevicesDiscovery //31.開啟監聽搜索藍牙設備 onBluetoothDeviceFound //30.停止監聽搜索藍牙設備 offBluetoothDevi ......

    uj5u.com 2023-03-15 09:06:45 more
  • canvas畫板（滑鼠和觸摸）

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>canves</title> <style> #canvas { cursor:url(../images/pen.png),crosshair; } #canvasdiv{ bo ......

    uj5u.com 2023-02-15 08:56:31 more
  • 手機端H5 實作自定義拍照界面

    手機端 H5 實作自定義拍照界面也可以使用 MediaDevices API 和 <video> 標簽來實作，和在桌面端做法基本一致。 首先，使用 MediaDevices.getUserMedia() 方法獲取攝像頭媒體流，并將其傳遞給 <video> 標簽進行渲染。 接著，使用 HTML 的 < ......

    uj5u.com 2023-01-12 07:58:22 more
  • 記錄--短視頻滑動播放在 H5 下的實作

    這里給大家分享我在網上總結出來的一些知識，希望對大家有所幫助 短視頻已經無數不在了，但是主體還是使用 app 來承載的。本文講述 H5 如何實作 app 的視頻滑動體驗。 無聲勝有聲，一圖頂百辯，且看下圖： 網址鏈接（需在微信或者手Q中瀏覽） 從上圖可以看到，我們主要實作的功能也是本文要講解的有： ......

    uj5u.com 2023-01-04 07:29:05 more
  • 一文讀懂 HTTP/1 HTTP/2 HTTP/3

    從 1989 年萬維網（www）誕生，HTTP（HyperText Transfer Protocol）經歷了眾多版本迭代，WebSocket 也在期間萌芽。1991 年 HTTP0.9 被發明。1996 年出現了 HTTP1.0。2015 年 HTTP2 正式發布。2020 年 HTTP3 或能正... ......

    uj5u.com 2022-12-24 06:56:02 more
  • 【HTML基礎篇002】HTML之form表單超詳解

    ??一、form表單是什么

    ??二、form表單的屬性

    ??三、input中的各種Type屬性值

    ??四、標簽 ......

    uj5u.com 2022-12-18 07:17:06 more

Copyright © 2010-2020 有解無憂