截止至4月27日晚8時

Status(截止至4月27日晚8時)Users

Submitted5Users

Solved3Total

Submits14Accepted6Time

Limit

Exceed1Wrong

Answer5RuntimeError2題目梗概輸入由兩部分組成。第一部分給出一個程序。這個程序的由若干個過程（可以

理解為C中的函數(shù)）構(gòu)成，每個過程由若干個語句構(gòu)成。輸入的第二部分是查詢序列。題目任務(wù)是按照查詢序列中的過程名稱，輸出相應(yīng)過程的運行時間。特別之處在于過程中有的語句執(zhí)行方向不是確定的，具體執(zhí)行方向由一個隨機變量約束。詳細描述保留字：NOP","IF",

"GOTO",

"END",

"PROC","PROG_START",

and

"PROG_END”；程序以”PROG_START"

開始，以"PROG_END”結(jié)束；程序可以有一個或多個過程；每個過程以”PROC

[name]".開始，[name]是這個過

程的名字，它可以是任意由字母和數(shù)字組成的字符串，但不能為保留字；過程以“END;"結(jié)束；一個過程可以有一個或多個語句。除了”END;”語句執(zhí)行不耗時以外，執(zhí)行一個語句耗費1個單位的時間；詳細描述“NOP"程序?qū)⒃谙乱粋€單位時間里執(zhí)行下一行的語句；語句格式如下：“IF

x>[threshold]GOTO[line

number];”

程序在區(qū)間[0..1)中隨機地取一個數(shù)，如果此數(shù)比threshold大，在下一個單位時間里就轉(zhuǎn)到行數(shù)為line

number的行繼續(xù)執(zhí)行；否則，在下一個單位時間里執(zhí)行下一行的語句。"IF

x<[threshold]

GOTO

[line

number];”類似定義。“IF

x>[threshold]PROC

[procedure

name];”程序在區(qū)間[0..1)中隨機地取一個數(shù)，如果此數(shù)比threshold大，在下一個單位時間里執(zhí)行名稱為[procedure

name]的過程，執(zhí)行完此過程后，返回該處，并在下一個單位時間里執(zhí)行下一行的語句；否則，在下一個單位時間里執(zhí)行下一行的語句。"IF

x<[threshold]

PROC

[procedurename];"類似定義。詳細描述一個過程一遇到”END;”就立刻結(jié)束。在每個過程里，行數(shù)從1開始數(shù)。第一個語句標號為1，第二個語句標號為2，如此類推?！盓ND;”是過程里的最后一個語句。輸入里只有一個程序，輸出某些被查詢到的過程的期望運行時間，準確到小數(shù)點后3位。簡化條件”IF”語句總是比較一個隨

量和一個常量；不同語句的隨

量”x”是相互獨立的；沒有循環(huán)的遞歸調(diào)用（包括間接的）；從一個過程中的任何一個語句開始執(zhí)行總可結(jié)束；1≤過程數(shù)目≤100；所有輸入字符串長度≤100；樣例輸入：PROG_STARTPROC

AIF

x>0.5

GOTO

3;NOP;END;PROC

BIF

x<0.5

PROC

A;NOP;END;PROG_ENDBAREQUEST_END樣例輸出：2.7501.500很明顯是模擬題一個自然樸素的想法模擬過程的執(zhí)行，當遇到”IF”語句時，利用rand（C中）或random（Pascal中）取一個隨機值，經(jīng)過比較后決定執(zhí)行方向。當試驗次數(shù)足夠大時，能夠得出滿足精度要求的結(jié)果。但是，事實表明：在得到滿足精度要求的結(jié)果之前，就已經(jīng)TLE了?；蛘?，在Time

Limit前輸出，是WA。此路不通。再來分析語句三種，”NOP;”、”END;”辦，”IF”:比較復(fù)雜?！癐F

x>[threshold]PROC

[procedure

name];”好辦，因為沒有循環(huán)遞歸調(diào)用（包括間接遞歸），每個過程都可獨立的處理。至于"IF

x>[threshold]GOTO

[linenumber];"如果[linenumber]>當前行號，也好辦，我們可以按行號從大到小遞推。PROC

A２NOP;３END;１IF

x>0.5

GOTO

3;

(0.5×0

+

0.5×1)

+1=1.5１０來分析一個例子：唯一難辦的是[line

number]≤當前行號來分析一個例子：PROC

A１NOP;２IF

x>0.3

GOTO1;３NOP;４END;(0.7×①

+0.3×1)

+

1

=0.7①

+

1.30.3.(0.7①1.3)

1

0.7①

2.3

①

①

2.3

7.66701這樣的方法是可行的解齊次線性方程組再看一個稍微復(fù)雜的例子：PROCI_AM_EXP_2１NOP;２NOP;３NOP;４IF

x>0.4

GOTO

2;５NOP;６IF

x>0.3

GOTO

1;７NOP;８NOP;９END;0.28①

0.6②

4.04

①0.28①

0.6②

3.04

②0.28①

0.6②

3.04(0.6②

0.4(00.7①

2.6(0.7①

0.3２)

1

0.7①

1.6210

0.72①

0.6②

4.04

0.28①

0.4②

3.04

0.28①

0.6②

2.04算法是：從下往上推，得出一個齊次線性方程組。每當轉(zhuǎn)移行號≤當前行號，就往當前表達式中添未知元，未知元個數(shù)加一，如果當前表達式中的未知元序號=當前行號，就得到一個方程。顯然，在從下往上推的過程當中，每個未知元都會到達它所表達的行，并且這種到達僅有一次。從而，設(shè)n為最終表達式中未知元的數(shù)目，恰能得出n個方程。這樣再用現(xiàn)成的代數(shù)學上的解齊次現(xiàn)行方程組的方法就能順利求解。進一步簡化：由于實際上每個過程不長，出于編程方便的考慮，每行都認為得到一個未知元。設(shè)正在計算的過程有n個語句，那么就有n個未知元。從下往上推，每處理一條語句就得到一個方程。一共有n個方程。再解這個齊次線性方程組。這樣就省去了要判斷當前行是否可以得到一個方程的麻煩。題目保證從每條語句開始都可中止，這就保證了這個方程組肯定有解，且變量?；氐絼偛诺睦覲ROCI_AM_EXP_2１NOP;２NOP;３NOP;４IF

x>0.4

GOTO

2;５NOP;６IF

x>0.3

GOTO

1;７NOP;８NOP;９END;

x9

00.7

x1

x6

0.7

x

x

8

1x7

2Gauss消元法系數(shù)矩陣和常數(shù)項矩陣合在一起，得到增廣矩陣

0.720.60000000

5.04

0.28

0.40000000

4.04

0.280.61000000

3.04

0.280.60100000

2.040000001010000000100

0

0

0

0

0

1

0

0

2

001.6

2.6

0.7000100000.700001000從增廣矩陣得到行階梯形矩陣

0

0000000101000000010

0

0

0

0

0

01

0

0

0

0

0

0

0

36

0

1

0

0

0

0

0

0

35

0

0

1

0

0

0

0

0

34

0

0

0

1

0

0

0

0

28.50

0

0

0

1

0

0

0

27.50

0

0

0

0

1

0

0

2

1

0.

7從行階梯形矩陣得到簡化行階梯形矩陣

0

0

05

05

0

0

01000000036010000003500100000340001000028.0000100027.000001002000000101000000010

0

1

0

0

0

0

0

0

0

0

37

void

Gauss(int

n,int

A[MAXN][MAXN

+1])){int

i,

j,

k;for

(j=

1;j<=n;

j++){for

(i=

j;

i<=

n;

i++)if

(!(fabs(A[i][j])

<

zero))break;if

(i!=

j)for

(k=

1;

k

<=

n

+

1;

k++)swap(A[i][k],

A[j][k]);r=

A[j][j];for

(k=

j;k

<=

n+

1;

k++)A[j][k]/=

r;for

(i=

j+

1;

i<=

n;

i++){r=

A[i][j];for

(k=

j;k

<=

n+

1;

k++)A[i][k]

-=

r*

A[j][k];}}化為行階梯形矩陣for

(j=

n;

j

>=

1;

j--){for

(i=j

-

1;

i

>=

1;

i--){r=

A[i][j];for

(k=

1;

k

<=n

+

1;

k++)A[i][k]-=

A[j][k]

*r;}}}化為簡化行階梯形矩陣Gauss消元法代碼至于字符串的處理，這是選手的基本功，而且每個人