截止至4月27日晚8時(shí)

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

Submitted5Users

Solved3Total

Submits14Accepted6Time

Limit

Exceed1Wrong

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

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

"GOTO",

"END",

"PROC","PROG_START",

and

"PROG_END”；程序以”PROG_START"

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

[name]".開始，[name]是這個(gè)過

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

x>[threshold]GOTO[line

number];”

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

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

x<[threshold]

GOTO

[line

number];”類似定義?！癐F

x>[threshold]PROC

[procedure

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

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

x<[threshold]

PROC

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

量和一個(gè)常量；不同語句的隨

量”x”是相互獨(dú)立的；沒有循環(huán)的遞歸調(diào)用（包括間接的）；從一個(gè)過程中的任何一個(gè)語句開始執(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很明顯是模擬題一個(gè)自然樸素的想法模擬過程的執(zhí)行，當(dāng)遇到”IF”語句時(shí)，利用rand（C中）或random（Pascal中）取一個(gè)隨機(jī)值，經(jīng)過比較后決定執(zhí)行方向。當(dāng)試驗(yàn)次數(shù)足夠大時(shí)，能夠得出滿足精度要求的結(jié)果。但是，事實(shí)表明：在得到滿足精度要求的結(jié)果之前，就已經(jīng)TLE了。或者，在Time

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

x>[threshold]PROC

[procedure

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

x>[threshold]GOTO

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

A２NOP;３END;１IF

x>0.5

GOTO

3;

(0.5×0

+

0.5×1)

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

number]≤當(dāng)前行號來分析一個(gè)例子：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這樣的方法是可行的解齊次線性方程組再看一個(gè)稍微復(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算法是：從下往上推，得出一個(gè)齊次線性方程組。每當(dāng)轉(zhuǎn)移行號≤當(dāng)前行號，就往當(dāng)前表達(dá)式中添未知元，未知元個(gè)數(shù)加一，如果當(dāng)前表達(dá)式中的未知元序號=當(dāng)前行號，就得到一個(gè)方程。顯然，在從下往上推的過程當(dāng)中，每個(gè)未知元都會到達(dá)它所表達(dá)的行，并且這種到達(dá)僅有一次。從而，設(shè)n為最終表達(dá)式中未知元的數(shù)目，恰能得出n個(gè)方程。這樣再用現(xiàn)成的代數(shù)學(xué)上的解齊次現(xiàn)行方程組的方法就能順利求解。進(jìn)一步簡化：由于實(shí)際上每個(gè)過程不長，出于編程方便的考慮，每行都認(rèn)為得到一個(gè)未知元。設(shè)正在計(jì)算的過程有n個(gè)語句，那么就有n個(gè)未知元。從下往上推，每處理一條語句就得到一個(gè)方程。一共有n個(gè)方程。再解這個(gè)齊次線性方程組。這樣就省去了要判斷當(dāng)前行是否可以得到一個(gè)方程的麻煩。題目保證從每條語句開始都可中止，這就保證了這個(gè)方程組肯定有解，且變量?；氐絼偛诺睦覲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ù)項(xiàng)矩陣合在一起，得到增廣矩陣

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消元法代碼至于字符串的處理，這是選手的基本功，而且每個(gè)人