CSP認証2019.03の第四題

3350 ワード

メッセージングウィンドウは最近、CSP認証2019年3月の第4題をブラシし、主体構想はn個のキューを開き、それぞれn個のプロセスを維持することであり、これまでの考えは直接暴力であり、このn個のキューのチームトップ要素が一致しているかどうかを判断することであり、問題はないと思っていた.しかし玄学の誤りが発生し、公式サイトのテストではタイムアウトが報告された.後から読み込みが掛かっているのがわかりました.元の読み込みプログラムを添付します
cin >> T >> n;
	getchar();
	while (T--) {
        for (int i = 0; i < n; i++) {
            while(!q[i].empty()) q[i].pop();
        }
		int flag = 0, o = 0;
		for (int i = 0; i <= 10005; i++) fill(vis[i],vis[i] + 10,0);
		for (int i = 0; i < n; i++) {
			  do {
					scanf("%c%d",&tmp.ch,&tmp.num);
					q[i].push(tmp);

			  }while (getchar()!='
') }

ローカルで運行するのが正しいので、どこに掛けるか分かりません.以下に改善版を添付した読み込みプログラムの考え方も改善され、以前は暴力会T、後に広捜を採用した.具体的な考え方:初期化:n個のキューのキューヘッダ要素を広捜キューに入れる.次に、広捜キューのキューヘッダ要素を取り出し、他のnつのプロセスキューのキューヘッダ要素と一致するかどうかを判断し、一致すると、対応するプロセスの2つのキューのキューヘッダ要素がキューから出て、マークを付ける必要があります.(聞き取れなくても大丈夫です.以下、例で説明します)マッチングが一致しなくても、広捜キューのキューヘッダ要素がキューから出ることに注意してください.例:T=1,n=2 S 1 R 0 R 0 S 1初期化:広捜キューに
S1
R0
広捜キューの中のキューヘッダ要素を取り出します:S 1、プロセス1の中のR 0と一致することを発見して、そのため広捜キューの中のR 0をマークして、次回それに遍歴する時、直接スキップします;また、S 1,R 0をそれぞれ元のプロセスキューからpopして外に出す場合は、R 0とS 1をキューに入れる.プロセスキューからpopを出す場合、プロセスキューが空でない場合は、プロセスキューの新しいキューヘッダ要素を広検索キューに再入力する必要があることに注意してください.マークアップの仕方は1つのvis[a][b]//aでいくつかのプロセスを表し、bはプロセス内の位置S 1(vis[0][0])R 0(vis[0][1])R 0(vis[1][0])S 1(vis[1][1])を表す
しかし結局90点しか取れず、どこが間違っているのか分からなかった.皆さんのお役に立てばと思います.

#include 
using namespace std;
struct data {
	char ch;//  R/s 
	int num;//R/s       
	int belong;//       
	int pos;//          
};
queueq[10005];//           
queuemq; 
int vis[10005][10];
char str[20];
int main()
{
	char str[20];
	int T, n;
	data tmp, tmp1;
	cin >> T >> n;
	getchar();
	while (T--) {
        for (int i = 0; i < n; i++) {
            while(!q[i].empty()) q[i].pop();
        }
		int flag = 0, o = 0;
		for (int i = 0; i <= 10005; i++) fill(vis[i],vis[i] + 10,0);
		for (int i = 0; i < n; i++) {
			int number = 0;
			int ans = 0;
			gets(str);
			for (int j = 0; j < strlen(str); j++) {
				if (str[j] == 'R' || str[j] == 'S') {
					tmp.ch = str[j];
					int p = j + 1;
					while (str[p] >= '0' && str[p] <= '9') {
						number += str[p] - '0';
						ans = number;
						number *= 10;
						p++;
					}
					tmp.belong = i;
					tmp.num = ans;
					tmp.pos = o++;
					ans = 0;
					number = 0;
					q[i].push(tmp);
				}
			}
			
		}
		for (int i = 0; i < n; i++) {
			tmp = q[i].front();
			mq.push(tmp);
		}	
		while (!mq.empty()) {
			tmp = mq.front();
			mq.pop();
			if (vis[tmp.belong][tmp.pos]) continue;
			if (!q[tmp.num].empty())tmp1 = q[tmp.num].front();
			else continue;
			if ((tmp.ch == 'R' && tmp1.ch == 'S' && tmp1.num == tmp.belong) || (tmp.ch == 'S' && tmp1.ch == 'R' && tmp1.num == tmp.belong)) {
				q[tmp.num].pop();
				if (!q[tmp.num].empty()) mq.push(q[tmp.num].front());
				vis[tmp.num][tmp1.pos] = 1;
				q[tmp.belong].pop();
				if (!q[tmp.belong].empty()) mq.push(q[tmp.belong].front());			
			}			
		}	
		for (int i = 0; i < n; i++) {
			if (q[i].empty()) flag++;
		}
		if (flag == n) printf("0
");// else printf("1
");// } return 0; }