CSP認証2019.03の第四題
3350 ワード
メッセージングウィンドウは最近、CSP認証2019年3月の第4題をブラシし、主体構想はn個のキューを開き、それぞれn個のプロセスを維持することであり、これまでの考えは直接暴力であり、このn個のキューのチームトップ要素が一致しているかどうかを判断することであり、問題はないと思っていた.しかし玄学の誤りが発生し、公式サイトのテストではタイムアウトが報告された.後から読み込みが掛かっているのがわかりました.元の読み込みプログラムを添付します
ローカルで運行するのが正しいので、どこに掛けるか分かりません.以下に改善版を添付した読み込みプログラムの考え方も改善され、以前は暴力会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点しか取れず、どこが間違っているのか分からなかった.皆さんのお役に立てばと思います.
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;
}