列表

详情

NC14306. Debug

描述

Recently, Alice and Bob are working on a quantum computation model. In this model, all the variables are uncertain, and could be changed during any time. Fortunately, there are some techniques to construct the input data to make these variables show some certain feature at certain time. In other words, all condition statement can be controlled respectively from the input data.
To test some algorithms in this model, Alice wrote some codes to run on a prototype machine. As this machine requires a lots of resource to work, Alice wanted Bob to make a plan to debug these codes efficiently. Bob analysed the model and the machine, and found that in every unit of time, they can test exactly one program and exactly one input data. Bob want to minimize the time to debug the program. Now he asks for your help.
For your convenience, Bob would give you a simple edition of the codes. The new codes consist of some keywords, labels, and necessarily separative signs. Followings are formulas of sentence:
    1. A label can be any combination of letters and number except keywords.
    2. A label sentence is written as a label and a following colon without separative sign.
    3. An atomic sentence is written as a keyword STATEMENT.
    4. A jump sentence is written as a keyword GOTO and a following label, donating that the machine will jump to the label sentence which is with the same label. It is guaranteed that the each label sentence exists only once.
    5. A condition sentence would be donated as a keyword IF and a following jump sentence. You can control the machine to execute the jump sentence or not through the input data. Also, you can have difference choose on the same condition sentence even if the input is the same.
    6. A end sentence is written as a keyword END, donating that the code is over. End sentence exists once and at the end of a program. However, you can terminate the program at any position you want.
Additionally, separative signs could be space, tab or line break. Upper case letters and lower case letters are considered as different letters. The program would run starting at the first sentence and ending at the end sentence or your termination. To make sure the code is correct, you need to let every atomic sentence run at least once. Can you find the least time Bob need to debug this code?

输入描述

The first line is the number of test cases. For each test case, there is the code as described before. Each case contains no more than 100 labels, 100 atomic sentence, and 500 others sentences.

输出描述

For each test case, output a line containing the minimum time Bob need. If there is no solution, output -1.

示例1

输入: 

3
STATEMENT
IF GOTO L1
STATEMENT
GOTO L2
L1:
STATEMENT
L2:
END
STATEMENT
IF GOTO L1
STATEMENT
GOTO L2
L1: IF GOTO L1
L2:
END
STATEMENT
L0:
IF GOTO L1
STATEMENT
GOTO L2
L1: STATEMENT
L2: IF GOTO L0
END

输出: 

2
1
1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 78ms, 内存消耗: 700K, 提交时间: 2019-01-07 17:15:01 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <map>

using namespace std;

const int MAXN = 260;
const int MAXM = 11000;
const int MAXS = 30;

map<string, int> h;

int n;
int m;
bool a[MAXN][MAXN];
bool ena[MAXN];
bool g[MAXN][MAXN];
bool chk[MAXN];
int mat[MAXN];
int q[MAXN];
int f[MAXN];

int getHash(string &s)
{
 if (h[s] == 0) return h[s] = (++n);
 else return h[s];
}

void init()
{
 h.clear();
 string s;
 int cur = 1;
 bool d = true;
 n = 1;
 memset(a, false, sizeof(a));
 memset(ena, false, sizeof(ena));
 memset(f, 0xff, sizeof(f));
 memset(q, 0xff, sizeof(q));
 while (cin >> s && s != "END")
 {
  if (s == "STATEMENT")
  {
   if (!d)
   {
    a[cur][++n] = 1;
    cur = n;
   }
   ena[cur] = true;
  }
  else if (s == "GOTO")
  {
   cin >> s;
   a[cur][getHash(s)] = true;
   cur = 0;
  }
  else if (s == "IF")
  {
   cin >> s;
   cin >> s;
   a[cur][getHash(s)] = true;
   d = false;
  }
  else
  {
   int l = s.size();
   s = s.substr(0, l - 1);
   int v = getHash(s);
   a[cur][v] = true;
   cur = v;
   d = true;
  }
 }
 ena[1] = true;
}

int cnt;

void dfs(int v)
{
 if (chk[v]) return;
 chk[v] = true;
 
 for (int i = 1; i <= n; ++i)
 if (ena[i] && a[v][i])
  dfs(i);
  
 q[++cnt] = v;
}

void dfs2(int v)
{
 if (chk[v]) return;
 f[v] = cnt;
 chk[v] = true;
 for (int i = 1; i <= n; ++i)
  if (ena[i] && a[i][v])
   dfs2(i);
}

bool dfs3(int v)
{
 for (int i = 1; i <= cnt; ++i)
 if (g[v][i] && !chk[i])
 {
  chk[i] = true;
  int tmp = mat[i];
  mat[i] = v;
  if (tmp == -1) return true;
  if (dfs3(tmp)) return true;
  mat[i] = tmp;
 }
 return false;
}

void solve()
{
 if (ena[0])
 {
  printf("-1\n");
  return;
 }
 
 
 int ne = 0;
 for (int i = 1; i <= n; ++i)
 {
  
  //if (!ena[i])
  {
   for (int j = 1; j <= n; ++j)
   for (int k = 1; k <= n; ++k)
   if (a[j][i] && a[i][k]) a[j][k] = 1;
  }
  if (ena[i]) ++ne;
 }
 
 cnt = 0;
 memset(chk, 0, sizeof(chk));
 dfs(1);
 if (cnt != ne)
 {
  printf("-1\n");
  return;
 }
 memset(chk, 0, sizeof(chk));
 cnt = 0;
 for (int i = ne; i >= 1; --i)
 if (!chk[q[i]])
 {
  ++cnt;
  dfs2(q[i]);
 }
  
 memset(g, 0, sizeof(g));
 for (int i = 1; i <= n; ++i)
 if (ena[i])
 for (int j = 1; j <= n; ++j)
 if (ena[j] && a[i][j] && f[i] != f[j])
  g[f[i]][f[j]] = true;
  
 memset(mat, 0xff, sizeof(mat));
 int ans = cnt;
 for (int i = 1; i <= cnt; ++i)
 {
  memset(chk, 0, sizeof(chk));
  if (dfs3(i)) --ans;
 }
 printf("%d\n", ans);
}

int main()
{
 int tt;
 cin >> tt;
 while (tt--)
 {
  init();
  solve();
 }
 return 0;
}

上一题

© 2025 nowcoder.com