藍橋杯vip試題以及答案解析

〃首先聲明這并不是本人原創(chuàng)，只不不過本人想總結(jié)出來方便大家，全為C++

代碼。

1.結(jié)點選擇

問題描述

有一棵n個節(jié)點的樹，樹上每個節(jié)點都有一個正整數(shù)權(quán)值。如果一個點被選擇了，

那么在樹上和它相鄰的點都不能被選擇。求選出的點的權(quán)值和最大是多少？

解題思路：

這題模型是樹形動態(tài)規(guī)劃入門題目，

dp[i][0]表示該節(jié)點不被選擇，dp[i][1]表示該結(jié)點被選擇。

轉(zhuǎn)移方程為：

dp[u][l]+=dp[v][0];〃選擇了u結(jié)點，則與它鄰接的結(jié)點不選；

dp[u][0]+=max(dp[v][0],dp[v][1]);不選擇u結(jié)點,則與它鄰接的結(jié)點選擇結(jié)果最

大的；

應該特別注意：該題結(jié)點數(shù)量較大，應該選用鄰接表存儲邊的關(guān)系

1.#include<cstdio>

2.#include<cstring>

3.ttdefinemax(a,b)((a)>(b)?(a):(b))

4.#definemaxn100010

5.boolvis[maxn];

6.intdp[maxn][2];

7.intfather[maxn];

8.inthead[maxn];

9.intn;

10.intent;

11.structEdge

12.{

13.intto,next;

14.}edge[2*maxn];

15.voidadd(intu,intv)

16.{

17.edge[cnt],to=v;

18.edge[cnt].next=head[u];

19.head[u]=cnt++;

20.}

21.voidtreedp(intu)

22.{

23.vis[u]=l;

24.for(inti=head[u];i!=-l;i=edge[i].next)

25.

26.intv=edge[i].to;

27.if(!vis[v])

28.{

29.treedp(v);

30.dp[u][l]+=dp[v][0];

31.dp[u][0]+=max(dp[v][l],dp[v][0]);

32.)

33.}

34.}

35.voidinit()

36.{

37.cnt=0;

38.memset(dp,sizeof(dp));

39.memset(father,0,sizeof(father));

40.memsetCvis^O,sizeof(vis));

41.memset(headJ-1,sizeof(head));

42.)

43.intmain()

44.{

45.init();

46.scanf("%d"^&n);

47.for(inti=l;i<=n;i++)

48.scanf("％d”，&dp[i][l]);

49.introot=0;

50.intbegin=l;

51.for(inti=0;i<n-l;i++)

52.{

53.inta,b;

54.scanf(H%d%d",&a,&b);

55.add(a,b);

56.add(b,a);

57.father[b]=a;

58.if(root==b||begin)

59.(

60.root=a;

61.}

62.}

63.

64.while(father[root])

65.root=father[root];

66.treedp(root);

67.intans;

68.ans=max(dp[root][0]dp[root][1]);

69.printfC^dXn'^ans);

70.}

2.K好數(shù)

問題描述

如果?個自然數(shù)N的K進制表示中任意的相鄰的兩位都不是相鄰的數(shù)字，那么我們就

說這個數(shù)是K好數(shù)。求L位K進制數(shù)中K好數(shù)的數(shù)目。例如K=4,L=2的時候，所有K

好數(shù)為11、13、20、22、30、31、33共7個。由于這個數(shù)目很大，請你輸出它對

1000000007取模后的值。

解題思路：

dp[i][j]表示第i位為j的時候的個I好數(shù)個數(shù)；

因此有轉(zhuǎn)移方程：

dp[i][j]=dp[iT][m]+dp[i][j];m為上?一位的值，滿足的條件應為m-j的絕對值不為

1.即不相鄰；

應當注意的是：最后在求和的時候不能簡單的統(tǒng)計0〈=m〈k;因為首位如果是

0的話，其實不足L位了，所以0<m<k,也許有人會疑問這是不統(tǒng)計L位的0,不是第一位

呀。。。。。。其實仔細想想，是等效的。

1.#include<cstdio>

2.#include<cstring>

3.#definemod1000000007

4.#defineabs(a,b)((a)>(b)?(a-b):(b-a))

5.intdp[110][110];

6.intmain()

7.{

8.intk,l;

9.memset(dp^0?sizeof(dp));

10.scanf(”%d%d”，&k,&l);

11.for(inti=0;i<k;i++)

12.dp[l][i]=l;

13.for(inti=2;i<=l;i++)

14.(

15.for(intj=0;j<k;j++)

16.{

17.for(intm=0;m<k;m++)

18.(

19.if(abs(m,j)!=1)

20.dp[i][j]=(dp[i][j]%mod+dp[i-l][m]%mod)%mod;

21.)

22.}

23.)

24.intans=0;

25.for(inti=l;i<k;i++)

26.ans=(ans%mod+dp[l][i]%mod)%mod;

27.printf("%d\n”,ans);

28.}

3.；懊作格子

問題描述

有n個格子，從左到右放成一排，編號為1-n。

共有m次操作，有3種操作類型：

1.修改一個格子的權(quán)值，

2.求連續(xù)■■段格子權(quán)值和，

3.求連續(xù)一段格子的最大值。

對于每個2、3操作輸出你所求出的結(jié)果。

解題思路：

這是線段樹的入門題目。直接建立線段樹，求解就0K了

1.#include<cstdio>

2.#definemax(a,b)((a)>(b)?(a):(b))

3.#definemin(a,b)((a)<(b)?(a):(b))

4.#defineN100010

5.#defineL(a)(a)<<l

6.#defineR(a)(a)<<l|1

7.structnode

8.{

9.intl,r,maxn,minn,sum;

10.}line[3*N];

11.intnum[N];

12.intfirstssecond;

13.voidcreate(intintx,inty)

14.(

15.line[k].l=x;line[k].r=y;

16.if(x==y)

17.(

18.line[k],sum=num[x];

19.line[k].maxn=line[k],minn=num[x];

20.return;

21.}

22.intmid=(x+y)>>l;

23.create(L(k)^x,mid);

24.create(R(k),mid+l,y);

25.line[k].maxn=max(line[L(k)].maxn,line[R(k)].maxn);

26.//line[k].minn=mymin(line[L(k)].minn,line[R(k)].minn);

27.line[k].sum=line[L(k)].sum+line[R(k)].sum;

28.}

29.voidupdata(intk^inta,intb)

30.{

31.if(line[k].l==line[k].r)

32.{

33.line[k].maxn=b;

34.line[k].sum=b;

35.return;

36.)

37.intmid=(line[k].l+line[k].r)>>l;

38.if(a<=mid)

39.updata(L(k),a,b);

40.else

41.updata(R(k),a,b);

42.line[k].sum=line[L(k)].sum+line[R(k)].sum;

43.line[k].maxn=max(line[L(k)].maxn,line[R(k)].maxn);

44.}

45.voidquary(intk,intx>inty)

46.(

47.if(line[k].l==x&&line[k].r==y)

48.{

49.second+=line[k].sum;

50.first=max(first3ine[k].maxn);

51.return;

52.)

53.intmid=(line[k].l+line[k].r)>>l;

54.if(y<=mid)

55.quary(L(k),x,y);

56.elseif(x>mid)

57.quary(R(k),x,y);

58.else

59.{

60.quary(L(k),x,mid);

61.quary(R(k),mid+l,y);

62.}

63.}

64.intmain()

65.(

66.int

67.scanf("%d%d",&n,&m);

68.for(inti=l;i<=n;i++)

69.scanf(M%d",&num[i]);

70.create(lJlJn);

71.for(inti=l;i<=m;i++)

72.{

73.inta,b,c;

74.scanf("%d%d%d;&a,&b,&c);

75.if(a==l)

76.{

77.updata(l,b4c);

78.}

79.elseif(a==2)

80.(

81.first=-10000;

82.second=0;

83.quary(l,b,c);

84.printf("%d\n",second);

85.}

86.else

87.(

88.first=-10000;

89.second=0;

90.quary(l,b,c);

91.printf("%d\n",first);

92.}

93.

94.}

95.)

4.2n皇后

問題描述

給定一個n*n的棋盤，棋盤中有一些位置不能放皇后?，F(xiàn)在要向棋盤中放入n個黑

皇后和n個白皇后，使任意的兩個黑皇后都不在同行、同一列或同一條對角線上，任

意的兩個白皇后都不在同一行、同一列或同一條對角線上。問總共有多少種放法？n小

于等于8。

解題思路：

深搜黑皇后的可能分布，達到n時候深搜白皇后。

1.#include<cstdio>

2.#include<iostream>

3.#include<cstring>

4.#include<algorithm>

5.usingnamespacestd;

6.intans;

7.boolrow[10]^colflO];

8.intmaze[10][10]；

9.intn;

10.boolz[20],f[20];

11.intc[20];

12.voiddd(intcur)〃這?段對白皇后的搜索為白書中對?八皇后問題求解的代碼

13.{

14.inti,j;

15.if(cur==n)

16.ans++;

17.else

18.for(i=0;i<n;i++)

19.{

20.intok=l;

21.if(maze[cur][i]==0)

22.continue;

23.c[cur]=i;

24.for(intj=0;j<cur;j++)

25.{

26.if(c[cur]==c[j]||cur-c[cur]==j-c[j]||cur+c[cur]==j+c[j])

27.{

28.ok=0;

29.break;

30.}

31.}

32.if(ok)

33.dd(cur+l);

34.)

35.}

36.voiddfs(intcount)

37.(

38.if(count==n)

39.(

40.dd(0);

41.return;

42?)

43.for(intj=0;j<n;j++)

44.{

45.if(!row[count]&&!col[j]&&maze[count][j]==l&&!z[count+j]&&!f[n-1-

j+count])

46.{

47.z[count+j]=true;

48.f[n-1-j+count]=true;

49.row[count]=true;

50.col[j]=true;

51.maze[count][j]=0；

52.dfs(count+l);

53.z[count+j]=false;

54.f[n-1-j+count]=false;

55.row[count]=false;

56.col[j]=false;

57.maze[count][j]=l；

58.}

59.)

60.return;

61.}

62.intmain()

63.{

64.cin>>n;

65.for(inti=0;i<n;i++)

66.for(intj=0;j<n;j++)

67.cin>>maze[i][j];

68.memset(row,0,sizeof(row));

69.memset(col,0,sizeof(col));

70.memset(z^O,sizeof(z));

71.memsetCf^O,sizeof(f));

72.memset(c^-1^sizeof(c));

73.ans=0;

;74.dfs(0);

75.cout<<ans<<endl;

76.

77.}

5,回形取數(shù)

問題描述

回形取數(shù)就是沿矩陣的邊取數(shù)，若當前方向上無數(shù)可取或己經(jīng)取過，則左轉(zhuǎn)90度。

一開始位于矩陣左上角，方向向下。

解題思路：

直接按下，右，上，左的方向進行深搜即可。同樣也可以用while循環(huán)實現(xiàn)，速度

要比深搜快。

1.#include<cstdio>

2.#include<iostream>

3.#include<cstring>

4.#include<algorithm>

5.#definefor(inti=0;i<n;i++)

6.#defineset(a,b)memset(a^b,sizeof(a))

7.usingnamespacestd;

8.intm,n;

9.intmaze[210][210];

10.boolvis[210][210];

11.inttt;

12.intans[50000];

13.boolin(intx,inty)

14.(

15.if(x>=0&&x<m&&y>=0&&y<n)

16.returntrue;

17.returnfalse;

18.}

19.voiddfs(intx,inty,intdir)

20.{

21.vis[x][y]=l;

22.ans[tt++]=maze[x][y];

23.if(dir==0)

24.{

25.if(in(x+l,y)&&!vis[x+l][y])

26.dfs(x+l,y,0);

27.elseif(in(x,y+l)&&!vis[x][y+1])

28.dfs(x,y+l,1);

29.)

30.elseif(dir==l)

31.(

32.if(in(x,y+l)&&!vis[x][y+l])

33.dfs(x,y+1,l);

34.elseif(in(x-l,y)&&!vis[x?l][y])

35.dfs(x-l,y,2);

36.}

37.elseif(dir==2)

38.{

39.if(in(x-l,y)&&!vis[x-l][y])

40.dfs(x-l,y,2);

41.elseif(in(x,y-l)&&!vis[x][y-1])

42.dfs(x,y-l,3);

43.)

44.elseif(dir==3)

45?{

46.if(in(x,y-l)&&!vis[x][y-1])

47.dfs(x,y?l,3);

48.elseif(in(x+l,y)&&!vis[x+l][y])

49.dfs(x+l,y,。)；

.50.}

51.)

52.intmain()

53.(

54.

.55.cin>>m>>n;

56.tt=0;

57.set(vis,。)；

58.set(ans,0);

59.

60.fr(i,m)

61.fr(j,n)

62.cin>>maze[i][j];

63.dfs(0,0,0);

64.intt=0;

65.fr(iJm)

66.fr(j,n)

67.if(i==m-l&&j==n-l)

68.cout<<ans[t++]<<endl;

69.else

70.cout<<ans[t++]<<"

71.)

6.2的次幕表示

問題描述

任何一個正整數(shù)都可以用2進制表示，例如：137的2進制表示為10001001o

將這種2進制表示寫成2的次幕的和的形式，令次塞高的排在前面，可得到如下表達

式：137=2*7+2*3+2*0

現(xiàn)在約定幕次用括號來表示，即a-b表示為a(b)

此時，137可表示為：2(7)+2(3)+2(0)

進一步：7=2、2+2+2”。(21用2表示)

3=2+2”0

所以最后137可表示為：2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：1315-2"10+2"8+2"5+2+1

所以1315最后可表示為：

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

解題思路：仔細觀察給出的幾個例子會發(fā)現(xiàn)，處理二進制串的時候，遇到1就要進行遞歸,

1之間遇到0就要填+號，進行遞歸時候要加括號，需要特判21,2-0

1.#include<cstdio>

2.#include<cstring>

3.#include<iostream>

4.#include<algorithm>

5.#include<cstdlib>

6.usingnamespacestd;

7.voiddfs(intn)

8.{

9.if(n==0)

10.(

11.cout<<"0";

12.return;

13.)

14.strings;

15.intnum=n;

16.while(num)

17.(

18.s+=num%2+'0';

19.num/=2;

20.)

21.reverse(s.begin(),s.end());

22.intflag=0;

23.for(inti=0;i<s.length();i++)

24.{

25.if(s[i]==-r)

26.(

27.if(flag)

28.cout<<"+";

29.flag=l;

30.if(s.length()-i-l==l)

31.{

32.cout<<,,2";

33.}

34.else

35.(

36.cout?"2,';

37.cout<<"(n；

38.dfs(s.length()-i-l)

39.cout?,,)n;

40.)

41.}

42.)

43.}

44.intmain()

45.{

46.intnum;

47.cin>>num;

48.strings;

49.while(num)

50.(

51.s+=num%2+'0';

52.num/=2;

53.}

54.reverse(s.begin(),s.end());

55.intflag=0;

56.for(inti=0;i<s.length();i++)

57.{

58.if(s[i]=='l')

59.(

60.if(flag)

61.cout<<"+";

62.flag=l;

63.if(s.length()-i-l==l)

64.{

65.cout<<"2";

66.}

67.else

68.{

69.cout<<"2";

70.cout?"(";

71.dfs(s.length()-i-l);

72.cout<<")";

73.)

74.

75.)

76.)

77.)

7.導彈攔截-動態(tài)規(guī)劃

問題描述

某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有

一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前

一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一

套系統(tǒng)，因此有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這

套系統(tǒng)最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)。

解題思路：

因為要求后面每一發(fā)炮彈都不能高于前一發(fā)，故問題就轉(zhuǎn)化成了求最長不下降子序列，用

n'2算法即可。

對于第二問，遇到高于前一項的，便要準備另外一套系統(tǒng)，而且要全部攔截，故求嚴格的

最長上升子序列。

dp[i]表示以i位置結(jié)束的最長不下降子序列;

dps[i]表示以i位置結(jié)束的最長上升子序列;

注意初始化問題，對于每一個dp[i],最少也會包括自身，所以都要初始化為1；

cpp]viewDlaincopy

1.#include<cstdio>

2.#include<cstring>

3.#include<algorithm>

4.#definemax(a,b)((a)>(b)?(a):(b))

5.usingnamespacestd;

6.intmain()

7.{

8.intdp[10010];

9.intdps[10010];

10.memset(dp^0,sizeof(dp));

11.memset(dps,0?sizeof(dps));

12.intn=0;

13.intnum[10010];

14.intx;

15.while(-scanf("%d",&x))

16.num[++n]=x;

17.for(inti=l;i<=n;i++)

18.dp[i]=dps[i]=l;

19.for(inti=l;i<=n;i++)

20.{

21.for(intj=l;j<i;j++)

22.{

23.if(num[i]<=num[j])

24.{

25.dp[i]=max(dp[i],dp[j]+l);

26.}

27.if(num[i]>num[j])

28.{

29.dps[i]=max(dps[i],dps[j]+l);

30.)

31.)

32.)

33.intansl=0,ans2=0;

34.for(inti=l;i<=n;i++)

35.{

36.ansl=max(ansl4dp[i]);

37.ans2=max(ans2>dps[i]);

38.}

39.printf("%d\n",ansl);

（）

40.printf"%d\n",ans2;

141.}

9.藍橋杯回文數(shù)

問題描述

若一個數(shù)（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數(shù)。

例如：給定一個10進制數(shù)56,將56加65（即把56從右向左讀），得到121是一-個回

文數(shù)。

又如：對于10進制數(shù)87：

STEP1：87+78=165STEP2：165+561=726

STEP3：726+627=1353STEP4：1353+3531=4884

在這里的一步是指進行了一次N進制的加法，上例最少用了4步得到回文數(shù)4884。

寫?個程序，給定?個N（2<=N<=10或N=16）進制數(shù)M（其中16進制數(shù)字為0-9與A-

F）,求最少經(jīng)過幾步可以得到回文數(shù)。

如果在3。步以內(nèi)（包含3。步）不可能得到回文數(shù),則輸出“Impossible!"

輸入格式

兩行，N與M

輸出格式

如果能在3。步以內(nèi)得到回文數(shù)，輸出“STEP=xx"（不含引號），其中xx是步數(shù)；否則輸

出一行"Impossible!"（不含引號）

樣例輸入

9

87

問題描述

若?個數(shù)（首位不為零）從左向右讀與從右向左讀都?樣，我們就將其稱之為回文數(shù)。

例如：給定一個10進制數(shù)56,將56加65（即把56從右向左讀），得到121是一個回

文數(shù)。

又如：對于1。進制數(shù)87：

STEP1：87+78=165STEP2：165+561=726

STEP3：726+627=1353STEP4：1353+3531=4884

在這里的一步是指進行「一次N進制的加法，上例最少用了4步得到回文數(shù)4884。

寫一個程序，給定一個N（2<=N<=10或N=16）進制數(shù)M（其中16進制數(shù)字為0-9與A-

F）,求最少經(jīng)過幾步可以得到回文數(shù)。

如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“工mpossible!”

輸入格式

兩行，N與M

輸出格式

如果能在30步以內(nèi)得到回文數(shù)，輸出“STEP二xx”（不含引號），其中xx是步數(shù)；否則輸

出一行“工impossible!”（不含引號）

樣例輸入

9

87

1.#include<iostream>

2.#include<cmath>

3.#include<algorithm>

4.usingnamespacestd;

5.longlongtol0(intnum^strings)

6.{

7.longlongt=0;

8.intlen=s.length();

9.if(num<=10)

10.{

11.intlen=s.length();

12.for(inti=0;i<len;i++)

13.{

14.if(s[i]!='0')

15.{

16.t+=(s[i]-'0")*pow(num>len-i-1);

17.}

18.}

19.}

20.else

21.{

22.for(inti=0;i<len;i++)

23.{

24.if(s[i]>,9')

25.{

26.t+=(s[i]-'A'+10)*pow(numJlen-i-1);

27.}

28.else

29.(

30.t+=(s[i]-'0')*pow(num,len-i-1);

31.)

32.}

33.)

34.returnt;

35.)

36.booljudge(intnum,longlongt)

37.(

38.strings;

39.while(t)

40.{

41.intcur=t%num;

42.t/=num;

43.if(cur<=9)

44.(

45.s+=cur+'0';

46.}

47.else

48.{

49.s+=cur-10+'A';

50.}

51.)

52.reverse(s.begin(),s.end());

53.intlen=s.length();

54.for(inti=0;i<len/2;i++)

55.{

56.if(s[i]!=s[len-l-i])

57.returnfalse;

58.)

59.returntrue;

60.}

61.intmain()

62.{

63.intnum;

64.strings;

65.cin>>num>>s;

66.intcount=0;

67.while(count<31)

68.{

69.count++;

70.stringss=s;

71.reverse(ss.begin(),ss.end());

72.longlongtl=tol0(num,s);

73.longlongt2=tol0(num,ss);

74.if(judge(num,tl+t2))

75.break;

76.s.clear();

77.longlongt=tl+t2;

78.while(t)

79.{

80.intcur=t%num;

81.t/=num;

82.if(cur<=9)

83.(

84.s+=cur+'0';

85.}

86.else

87.(

88.s+=cur-10+'A';

89.}

90.)

91.reverse(s.begin()^s.endO);

92.)

93.if(count<31)

94.cout<<"STEP="<<count<<endl;

95.else

96.cout<<"Impossible!"<<endl;

97.}

10.旅行家的預算

問題描述

?個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設(shè)出發(fā)時油箱是空

的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距

離D2、出發(fā)點每升汽油價格P和沿途油站數(shù)N（N可以為零），油站i離出發(fā)點的距離Di、每

升汽油價格Pi（i=l,2,.…N）。計算結(jié)果四舍五入至小數(shù)點后兩位。如果無法到達目的地，

則輸出"NoSolution"。

輸入格式

第?行為4個實數(shù)DI、C、D2、P與一個非負整數(shù)N；

接下來N行，每行兩個實數(shù)Di、Pio

輸出格式

如果可以到達目的地，輸出一個實數(shù)（四舍五入至小數(shù)點后兩位），表示最小費用；否則

輸出“NoSolution”（不含引號）。

樣例輸入

275.611.927.42.82

102.02.9

220.02.2

樣例輸出

26.95

解題思路：

貪心規(guī)則：

從當前點開始，再c*d2的距離內(nèi)，找第一個油價低于當前結(jié)點汕價的站點

如果找到：

如果當前結(jié)點剩余油量可以抵達，更新下一個站點的剩余油量；

如果當前結(jié)點剩余油量不可以抵達，更新當前結(jié)點需要添加的油量；

如果找不到：

則在本站加滿油，將相鄰的結(jié)點當做下一個目的結(jié)點；------》條件1

如果超過c*d2,則不可以到達；

需要注意的是：判斷找沒找到時候應當注意用目的結(jié)點與當前結(jié)點的差值〈c*d2,判斷。

如果單單用一個flag標志的話，當遇到最后?個結(jié)點，即目的地，你會直接跳到一-》

條件1--那個條件中，從而多加了油，使得結(jié)果偏大；

viewolaincoDV

1.#include<cstdio>

2.#include<algorithm>

3.usingnamespacestd;

4.

5.structnode

6.{

7.doubledis;

8.doublecost;

9.doublehas;

10.doubleadd;

11.intid;

12.）；

13.

14.intmain()

15.{

16.//freopen("test.txt","r",stdin);

17.doubledistance;

18.doublec;

19.doublev;

20.doublescost;

21.intn;

22.nodesta[10001];

23.nodestart;

24.

25.scanf(,&distance,&c,&v,&scost,&n);

26.

27.sta[0].dis=0;

28.sta[0].cost=scost;

29.sta[0].has=0;

30.sta[0].id=0;

31.sta[0].add=0;

32.sta[n+l].dis=distance;

33.sta[n+l].cost=100000000;

34.sta[n+l].id=n+l;

35.sta[n+l].has=0;

36.sta[n+l].add=0;

37.start=sta[0];

38.

39.for(inti=l;i<=n;i++)

40.(

41.scanf",&sta[i].dis>&stafi].cost);

42.sta[i].has=0;

43.sta[i].id=i;

44.sta[i].add=0;

45.}

46.

47.boolgoal=true;

48.doubleans=0;

49.while(start.id<n+l)

50.{

51.doublelen=c*v;

52.if(sta[start.id+1].dis-start.dis>len)

53.{

54.goal=false;

55.printf("NoSolution'll");

56.break;

57.)

58.

59.intflag=false;

60.intk=l;

61.while(k<=n)

62.(

63.if(sta[k].id>start.id&&sta[k].dis-

start.dis<len&&sta[k].cost<=start.cost)

64.(

65.flag=true;

66.break;

67.}

68.k++;

69.)

70.

71.if(sta[k].dis-start.dis<len)

72.{

73.if(start.has*v<sta[k].dis-start.dis)

74.{

75.start.add=(sta[k].dis-start.dis)/v-start.has;

76.start?has+=start.add;

77.sta[start.id]=start;

78.start=sta[k];

79.}

80.else

81.(

82.sta[k].has=start.has-(sta[k].dis-start.dis)/v;

83.start=sta[k];

84.}

85.}

86.else

87.{

88.k=start.id+1;

89.start.add=c-start.has;

90.start.has=c;

91.sta[start.id]=start;

92.sta[k].has=start.has-(sta[k].dis-start.dis)/v;

93.start=sta[k];

94.

95.)

96.}

97.if(goal)

98.(

99.for(inti=0;i<=n;i++)

100.{

101.ans+=sta[i].add*sta[i].cost;

102.}

,103.priirtf("%.21f\n”，ans);

104.}

105.

106.

107.}

11.集合運算

問題描述

給出兩個整數(shù)集合A、B,求出他們的交集、并集以及B在A中的余集。

輸入格式

第一行為一個整數(shù)n,表示集合A中的元素個數(shù)。

第二行有n個互不相同的用空格隔開的整數(shù)，表示集合A中的元素。

第三行為?個整數(shù)m,表示集合B中的元素個數(shù)。

第四行有m個互不相同的用空格隔開的整數(shù)，表示集合B中的元素。

集合中的所有元素均為int范圍內(nèi)的整數(shù)，n、m<=1000,

輸出格式

第一行按從小到大的順序輸出A、B交集中的所有元素。

第二行按從小到大的順序輸出A、B并集中的所有元素。

第三行按從小到大的順序輸出B在A中的余集中的所有元素。

樣例輸入

5

12345

5

246810

樣例輸出

24

123456810

135

樣例輸入

4

1234

3

567

樣例輸出

1234567

1234

1.#include<cstdio>

2.#include<iostream>

3.#include<algorithm>

4.#definefr(a,b,c)for(inta=b;a<c;a++)

5.#defineread(a)cin>>a

6.#include<set>

7.usingnamespacestd;

8.intmain()

9.{

10.intn,m;

11.read(n);

12.set<int>a,b,c;

13.intnum;

14.

15.{

16.read(num);

17.a.insert(num);

18.c.insert(num);

19?}

20.read(m);

21.fr(i^0,m)

22.{

23.read(num);

24.b.insert(num);

25.c.insert(num);

26.}

27.set<int>::iteratorit;

28.boolflag=false;

29.for(it=a.begin();it!=a.end();it++)

30.(

31.

32.if(b.find(*it)!=b.end())

33.(

34.cout<<*it<<"

35.flag=true;

36.)

37.)

38.if(flag)

39.(

40.cout<<endl;

41.flag=false;

42.}

43.for(it=c.begin();it!=c.end();it++)

44.{

45.cout?(*it)?"

46.)

47.cout<<endl;

48.for(it=a.begin();it!=a.end();it++)

49.{

50.if(b.find(*it)==b.end())

51.(

52.flag=true;

53.cout<<*it<<"

54.)

55.}

56.if(flag)

57.(

58.cout<<endl;

59.flag=false;

60.)

61.

62.}

12.擺動序列

問題描述

如果一個序列滿足下面的性質(zhì),我們就將它稱為擺動序列：

1.序列中的所有數(shù)都是不大于k的正整數(shù)；

2.序列中至少有兩個數(shù)。

3.序列中的數(shù)兩兩不相等；

4.如果第i-1個數(shù)比第i-2個數(shù)大，則第i個數(shù)比第i-2個數(shù)小;如果第i-1個數(shù)

比第i-2個數(shù)小，則第i個數(shù)比第i-2個數(shù)大。

比如，當k=3時，有下面幾個這樣的序列：

12

13

21

213

23

231

31

32

一共有8種，給定k,請求出滿足上面要求的序列的個數(shù)。

解題思路：

說的是動態(tài)規(guī)劃的題目，但最終還是沒有想出來轉(zhuǎn)移方程，如果有大牛知道，可以留言,

謝謝。

給定K,則序列最多K位，可以遞歸搜索每一層，當滿足條件時候，ans++即可。

[cppjviewolaincooyCZ

1.#include<cstdio>

2.#include<cstring>

3.#include<iostream>

4.#include<algorithm>

5.usingnamespacestd;

,6.#defineread(a)cin>>a

7.#defineset(a,b)memset(a,sizeof(a))

8.boolvis[21];

9.intsans[21];

10.intn;

11.intans;

12.voiddfs(intcount)

13.{

14.if(count>n)

115.return;

16.for(inti=l;i<=n;i++)

17.{

18.if(!vis[i])

19.{

20.sans[count]=i;

21.if(count==l)