?

2017 8.19 NOIP模擬賽

by coolyangzc

?

?

?

共3道題目，時(shí)間3小時(shí)

?

?

題目名	高級(jí)打字機(jī)	不等數(shù)列	經(jīng)營(yíng)與開發(fā)
源文件	type.cpp/c/pas	num.cpp/c/pas	exploit.cpp/c/pas
輸入文件	type.in	num.in	exploit.in
輸出文件	type.out	num.out	exploit.out
時(shí)間限制	1000MS	1000MS	1000MS
內(nèi)存限制	256MB	256MB	256MB
測(cè)試點(diǎn)	5+(5)	10	10
測(cè)試點(diǎn)分值	20	10	10

?

?

?

評(píng)測(cè)環(huán)境

?

操作系統(tǒng)：Windows XP SP3

CPU: Pentium(R) Dual-Core CPU E5300 @ 2.60Ghz(2CPUs)

系統(tǒng)內(nèi)存：2GB

?

?

?

?

?

?

Problem 1 高級(jí)打字機(jī)(type.cpp/c/pas)

【題目描述】

早苗入手了最新的高級(jí)打字機(jī)。最新款自然有著與以往不同的功能，那就是它具備撤銷功能，厲害吧。

請(qǐng)為這種高級(jí)打字機(jī)設(shè)計(jì)一個(gè)程序，支持如下3種操作：

1.T x：在文章末尾打下一個(gè)小寫字母x。(type操作)

2.U x：撤銷最后的x次修改操作。（Undo操作）

（注意Query操作并不算修改操作）

3.Q x：詢問當(dāng)前文章中第x個(gè)字母并輸出。（Query操作）

文章一開始可以視為空串。

?

【輸入格式】

第1行：一個(gè)整數(shù)n，表示操作數(shù)量。

以下n行，每行一個(gè)命令。保證輸入的命令合法。

?

【輸出格式】

每行輸出一個(gè)字母，表示Query操作的答案。

?

【樣例輸入】

7

T a

T b

T c

Q 2

U 2

T c

Q 2

【樣例輸出】

b

c

【數(shù)據(jù)范圍】

對(duì)于40%的數(shù)據(jù) n<=200;

對(duì)于100%的數(shù)據(jù) n<=100000；保證Undo操作不會(huì)撤銷Undo操作。

<高級(jí)挑戰(zhàn)>

對(duì)于200%的數(shù)據(jù) n<=100000；Undo操作可以撤銷Undo操作。

<IOI挑戰(zhàn)> type

必須使用在線算法完成該題。

?

#include<iostream> #include<cstdio> using namespace std; int n,top; char a[100001]; int main() {freopen("type.in","r",stdin);freopen("type.out","w",stdout);scanf("%d",&n);while(n--){char ch[2];scanf("%s",ch);if(ch[0]=='T')cin>>a[++top];else if(ch[0]=='U'){int x;scanf("%d",&x);if(top>=x)top-=x;else top=0;}else {int x;scanf("%d",&x);cout<<a[x]<<endl;}} return 0;} 蜜汁RE

黃學(xué)長(zhǎng)的代碼也是掛了50

?

?

Problem 2 不等數(shù)列(num.cpp/c/pas)

【題目描述】

將1到n任意排列，然后在排列的每?jī)蓚€(gè)數(shù)之間根據(jù)他們的大小關(guān)系插入“>”和“<”。問在所有排列中，有多少個(gè)排列恰好有k個(gè)“<”。答案對(duì)2012取模。

?

【輸入格式】

第一行2個(gè)整數(shù)n,k。

?

【輸出格式】

一個(gè)整數(shù)表示答案。

?

【樣例輸入】5 2

【樣例輸出】

66

【數(shù)據(jù)范圍】

對(duì)于30%的數(shù)據(jù)：n <= 10

對(duì)于100%的數(shù)據(jù)：k < n <= 1000,

?

?

#include<iostream> #include<cstdio> #include<cstring>#define mod 2012 #define N 1007using namespace std; int L[N][N],n,m,cnt,k;int main() {freopen("num.in","r",stdin);freopen("num.out","w",stdout);scanf("%d%d",&n,&k);if(k>=n) {printf("0\n");return 0;}for(int i=1;i<=n;i++) L[i][0]=1;for(int i=2;i<=n;i++)for(int j=1;j<=k;j++){if(j>=i) continue;L[i][j]=(L[i][j]+L[i-1][j-1]*(i-j)+(j+1)*L[i-1][j])%mod;}printf("%d\n",L[n][k]%mod);fclose(stdin);fclose(stdout);return 0; } 水水水DP

?

?

?

Problem 3 經(jīng)營(yíng)與開發(fā)(exploit.cpp/c/pas)

【題目描述】

4X概念體系，是指在PC戰(zhàn)略游戲中一種相當(dāng)普及和成熟的系統(tǒng)概念，得名自4個(gè)同樣以“EX”為開頭的英語單詞。

eXplore（探索）

eXpand（拓張與發(fā)展）

eXploit（經(jīng)營(yíng)與開發(fā)）

eXterminate（征服）

——維基百科

?

今次我們著重考慮exploit部分，并將其模型簡(jiǎn)化：

你駕駛著一臺(tái)帶有鉆頭（初始能力值w）的飛船，按既定路線依次飛過n個(gè)星球。

?

星球籠統(tǒng)的分為2類：資源型和維修型。（p為鉆頭當(dāng)前能力值）

1.資源型：含礦物質(zhì)量a[i]，若選擇開采，則得到a[i]*p的金錢，之后鉆頭損耗k%，即p=p*(1-0.01k)

2.維修型：維護(hù)費(fèi)用b[i]，若選擇維修，則支付b[i]*p的金錢，之后鉆頭修復(fù)c%，即p=p*(1+0.01c)

??? 注：維修后鉆頭的能力值可以超過初始值（你可以認(rèn)為是翻修+升級(jí)）

?

請(qǐng)作為艦長(zhǎng)的你仔細(xì)抉擇以最大化收入。

?

【輸入格式】

第一行4個(gè)整數(shù)n,k,c,w。

以下n行，每行2個(gè)整數(shù)type,x。

type為1則代表其為資源型星球，x為其礦物質(zhì)含量a[i]；

type為2則代表其為維修型星球，x為其維護(hù)費(fèi)用b[i]；

?

【輸出格式】

一個(gè)實(shí)數(shù)（保留2位小數(shù)），表示最大的收入。

?

【樣例輸入】

5 50 50 10

1 10

1 20

2 10

2 20

1 30

【樣例輸出】

375.00

【數(shù)據(jù)范圍】

對(duì)于30%的數(shù)據(jù) n<=100

另有20%的數(shù)據(jù) n<=1000；k=100

對(duì)于100%的數(shù)據(jù) n<=100000; 0<=k,c,w,a[i],b[i]<=100；保證答案不超過10^9? ?

?

/* 可以發(fā)現(xiàn)，當(dāng)前的決策只對(duì)后面的開采有影響，且剩余耐久度與之后的開采收益成正比，如果倒著考慮這個(gè)問題，得出i-n的星球1點(diǎn)耐久度所能獲得的最大收益，從后往前dp，得出最大值最后乘w就是答案 */ #include<cstdio> #include<algorithm> using namespace std; const int maxn=100001; int n,w,t[maxn],a[maxn]; double k,c,ans; int main() {freopen("exploit.in","r",stdin);freopen("exploit.out","w",stdout);scanf("%d%lf%lf%d",&n,&k,&c,&w);k=1-0.01*k;c=1+0.01*c;for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&a[i]);for(int i=n;i;i--)if(t[i]==1)ans=max(ans,ans*k+a[i]);elseans=max(ans,ans*c-a[i]);printf("%.2lf\n",ans*w); } 還是不大懂

?

?

/*T1個(gè)人覺得沒問題啊，，，，，， T2水dp，第一次考場(chǎng)上A dp題，太弱了，，，，， T3沒耐心讀(我不會(huì)告訴你是在聊QQ...)寫了個(gè)20分暴力光榮爆零...... 有這么兩個(gè)問題吧: 1.讀題不認(rèn)真，導(dǎo)致開始就寫錯(cuò)。 2.推dp方程不耐心。 還有就是不能不能不能畏懼dp，，，，，， */ conclusion

?

轉(zhuǎn)載于:https://www.cnblogs.com/L-Memory/p/7396631.html

總結(jié)

以上是生活随笔為你收集整理的8.19noip模拟题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。