2021年藍(lán)橋杯練習(xí)題庫算法訓(xùn)練題

算法訓(xùn)練圖形顯示

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述編寫一種程序，一方面輸入一種整數(shù)，例如5，然后在屏幕上顯示如下圖形（5表達(dá)行數(shù)）：

*****

****

***

**

*#include<stdio.h>intmain(){inti,j,a[100][100],n;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)for(j=0;j<n-i;j++){printf("*");if(j!=n-i-1)printf("");if(j==n-1-i)printf("\n");}}}

算法訓(xùn)練排序

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述編寫一種程序，輸入3個整數(shù)，然后程序?qū)@三個整數(shù)按照從大到小進(jìn)行排列。

輸入格式：輸入只有一行，即三個整數(shù)，中間用空格隔開。

輸出格式：輸出只有一行，即排序后成果。

輸入輸出樣例樣例輸入9230樣例輸出3092#include<stdio.h>#include<stdlib.h>#definenum100intmain(void){ inti,j,t,a[3]={0}; for(i=0;i<3;i++) { scanf("%d",&a[i]); } for(i=0;i<3;i++) for(j=i;j<3;j++) if(a[i]<=a[j]){t=a[i];a[i]=a[j];a[j]=t;} for(i=0;i<3;i++) { printf("%d",a[i]); if(i!=2)printf(""); } printf("\n"); return0;}

算法訓(xùn)練2次冪表達(dá)

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述任何一種正整數(shù)都可以用2進(jìn)制表達(dá)，例如：1372進(jìn)制表達(dá)為10001001。

將這種2進(jìn)制表達(dá)寫成2次冪和形式，令次冪高排在前面，可得到如下表達(dá)式：137=2^7+2^3+2^0

當(dāng)前商定冪次用括號來表達(dá)，即a^b表達(dá)為a（b）

此時，137可表達(dá)為：2（7）+2（3）+2（0）

進(jìn)一步：7=2^2+2+2^0（2^1用2表達(dá)）

3=2+2^0

因此最后137可表達(dá)為：2（2（2）+2+2（0））+2（2+2（0））+2（0）

又如：1315=2^10+2^8+2^5+2+1

因此1315最后可表達(dá)為：

2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）輸入格式正整數(shù)（1<=n<=0）輸出格式符合商定n0，2表達(dá)（在表達(dá)中不能有空格）樣例輸入137樣例輸出2(2(2)+2+2(0))+2(2+2(0))+2(0)樣例輸入1315樣例輸出2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

提示

用遞歸實現(xiàn)會比較簡樸，可以一邊遞歸一邊輸出#include<stdio.h>intl=0;chartemp[1000]={0};voidshow(intn){if(n==0){temp[l]='0';l++;return;}if(n==2){ temp[l]='2',l++;return；}inta[15]={0},i=0,j;while(n!=0) { a[i]=n%2; n/=2; i++;} for(j=i-1;j>=0;j--)if(a[j]==1) {if(j==1) { if(temp[l-1]==')'||temp[l-1]=='2'){temp[l]='+';l++;} temp[l]='2';l++; }else { if(temp[l-1]==')'||temp[l-1]=='2'){temp[l]='+';l++;} temp[l]='2';l++; temp[l]='(';l++; show(j); temp[l]=')';l++; }} }intmain(){ intn; scanf("%d",&n); show(n); printf("%s",temp)； return0;}算法訓(xùn)練前綴表達(dá)式

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述編寫一種程序，以字符串方式輸入一種前綴表達(dá)式，然后計算它值。輸入格式為：“運算符對象1對象2”，其中，運算符為“+”（加法）、“-”（減法）、“*”（乘法）或“/”（除法），運算對象為不超過10整數(shù)，它們之間用一種空格隔開。規(guī)定：對于加、減、乘、除這四種運算，分別設(shè)計相應(yīng)函數(shù)來實現(xiàn)。

輸入格式：輸入只有一行，即一種前綴表達(dá)式字符串。

輸出格式：輸出相應(yīng)計算成果（如果是除法，直接采用c語言“/”運算符，成果為整數(shù)）。

輸入輸出樣例樣例輸入+52樣例輸出7#include<stdio.h>intmain(){inta[2];inti,j;charc=getchar();for(i=0;i<2;i++)scanf("%d",&a[i]);if(c=='+') j=a[0]+a[1];elseif(c=='-') j=a[0]-a[1];elseif(c=='*') j=a[0]*a[1];elseif(c=='/') j=a[0]/a[1];printf("%d",j);return0;}算法訓(xùn)練Anagrams問題

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述Anagrams指是具備如下特性兩個單詞：在這兩個單詞當(dāng)中，每一種英文字母（不區(qū)別大小寫）所浮現(xiàn)次數(shù)都是相似。例如，“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。編寫一種程序，輸入兩個單詞，然后判斷一下，這兩個單詞與否是Anagrams。每一種單詞長度不會超過80個字符，并且是大小寫無關(guān)。

輸入格式：輸入有兩行，分別為兩個單詞。

輸出格式：輸出只有一種字母Y或N，分別表達(dá)Yes和No。

輸入輸出樣例樣例輸入Unclear

Nuclear樣例輸出Y#include<stdio.h>voidsort(chara[],intlen){ inti,j,max; for(i=0;i<len;i++) { max=i; for(j=i+1;j<len;j++) if(a[j]>a[max])max=j; j=a[i];a[i]=a[max];a[max]=j; }}voidstrtoupper(chara[],intlen){ inti; for(i=0;i<len;i++) if(a[i]>='a'&&a[i]<='z')a[i]-=32;}intmystrcmp(chara[],intl1,charb[],intl2){ if(l1!=l2)return0; inti; for(i=0;i<l1;i++) if(a[i]!=b[i])return0; return1;}intmystrlen(char*p){ intl=0; while(*p++!=0) l++; returnl;}intmain(){ chars1[1000]={0},s2[1000]={0}; intl1,l2; scanf("%s%s",s1,s2); l1=mystrlen(s1); l2=mystrlen(s2); strtoupper(s1,l1); strtoupper(s2,l2); sort(s1,l1); sort(s2,l2);if(mystrcmp(s1,l1,s2,l2))printf("Y");elseprintf("N");return0;}算法訓(xùn)練浮現(xiàn)次數(shù)最多整數(shù)

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼?問題描述

編寫一種程序，讀入一組整數(shù)，這組整數(shù)是按照從小到大順序排列，它們個數(shù)N也是由顧客輸入，最多不會超過20。然后程序?qū)@個數(shù)組進(jìn)行記錄，把浮現(xiàn)次數(shù)最多那個數(shù)組元素值打印出來。如果有兩個元素值浮現(xiàn)次數(shù)相似，即并列第一，那么只打印比較小那個值。

輸入格式：第一行是一種整數(shù)N，N￡20；接下來有N行，每一行表達(dá)一種整數(shù)，并且按照從小到大順序排列。

輸出格式：輸出只有一行，即浮現(xiàn)次數(shù)最多那個元素值。

輸入輸出樣例樣例輸入5

100

150

150

200

250樣例輸出150#include<stdio.h>intmain(){ intn,i,j,t,max=1,num=0; scanf("%d",&n); if(n>0) { inta[n]; for(i=0;i<n;i++) scanf("%d",a+i); j=num=a[0]; t=1; for(i=1;i<n;i++) if(a[i]==j) { ++t; if(t>max) { max=t;num=a[i]; } } else { t=1; j=a[i]; } printf("%d",num); } return0;}

算法訓(xùn)練字串記錄

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述給定一種長度為n字符串S，尚有一種數(shù)字L，記錄長度不不大于等于L浮現(xiàn)次數(shù)最多子串（不同浮現(xiàn)可以相交），如果有各種，輸出最長，如果依然有各種，輸出第一次浮現(xiàn)最早。輸入格式第一行一種數(shù)字L。

第二行是字符串S。

L不不大于0，且不超過S長度。輸出格式一行，題目規(guī)定字符串。

輸入樣例1：

4

bbaabbaaaaa

輸出樣例1：

bbaa

輸入樣例2：

2

bbaabbaaaaa

輸出樣例2：

aa數(shù)據(jù)規(guī)模和商定n<=60

S中所有字符都是小寫英文字母。

提示

枚舉所有也許子串，記錄浮現(xiàn)次數(shù)，找出符合條件那個#include<stdio.h>#include<string.h>intmain(){ charS[1000],str[1000][1000],temp[100],out[100]; intL,i=0,s,otongji=0,ttongji,a,b,c; scanf("%d%c%c",&L,&S[0],&S[0]); while(S[i]!='\n'){scanf("%c",&S[i+1]);i++;}S[i]='\0';for(s=i+1;L<=s;L++){for(a=0;a<s+1-L;a++){//賦值for(b=0;b<L;b++){str[a][b]=S[a+b];}str[a][b]='\0';}for(i=0;i<a-1;){//比較for(b=0;b<a;b++){if(str[b][0]!='\0'){for(c=0;c<L;c++){temp[c]=str[b][c];}temp[c]='\0';ttongji=1;i++;str[b][0]='\0';break;}}for(b++;b<a;b++){if(!strcmp(str[b],temp)){ttongji++;i++;str[b][0]='\0';}}if(ttongji>otongji||(ttongji==otongji&&strlen(temp)>strlen(out))){strcpy(out,temp);otongji=ttongji;}}}i=0;while(out[i]!='\0'){printf("%c",out[i]);i++;}getchar(); return0;}算法訓(xùn)練矩陣乘法

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述輸入兩個矩陣，分別是m*s，s*n大小。輸出兩個矩陣相乘成果。輸入格式第一行，空格隔開三個正整數(shù)m,s,n（均不超過200）。

接下來m行，每行s個空格隔開整數(shù)，表達(dá)矩陣A（i，j）。

接下來s行，每行n個空格隔開整數(shù)，表達(dá)矩陣B（i，j）。輸出格式m行，每行n個空格隔開整數(shù)，輸出相乘後矩陣C（i，j）值。樣例輸入232

10-1

11-3

03

12

31樣例輸出-32

-82

提示

矩陣C應(yīng)當(dāng)是m行n列，其中C(i,j)等于矩陣A第i行行向量與矩陣B第j列列向量內(nèi)積。

例如樣例中C(1,1)=(1,0,-1)*(0,1,3)=1*0+0*1+(-1)*3=-3#include<stdio.h>intmain(){ intm,s,n,i,j,k,a[200][200],b[200][200],c[200][200]; scanf("%d%d%d",&m,&s,&n); for(i=1;i<=m;i++){ for(j=1;j<=s;j++) scanf("%d",&a[i][j]); } for(i=1;i<=s;i++){ for(j=1;j<=n;j++) scanf("%d",&b[i][j]); } for(i=1;i<=m;i++){ for(j=1;j<=n;j++) c[i][j]=0; } for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ for(k=1;k<=s;k++){ c[i][j]=c[i][j]+a[i][k]*b[k][j]; } } } for(i=1;i<=m;i++){ for(j=1;j<=n;j++) printf("%d",c[i][j]); printf("\n"); } return0;}算法訓(xùn)練大小寫轉(zhuǎn)換

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述編寫一種程序，輸入一種字符串（長度不超過20），然后把這個字符串內(nèi)每一種字符進(jìn)行大小寫變換，即將大寫字母變成小寫，小寫字母變成大寫，然后把這個新字符串輸出。

輸入格式：輸入一種字符串，并且這個字符串當(dāng)中只包括英文字母，不包括其她類型字符，也沒有空格。

輸出格式：輸出通過轉(zhuǎn)換后字符串。

輸入輸出樣例樣例輸入AeDb樣例輸出aEdB#include<stdio.h>intmain(){ inti; charch[100]; gets(ch); i=0; while(ch[i]!='\0') { if(ch[i]<='z'&&ch[i]>='a') ch[i]-=32; elsech[i]+=32; i++; } puts(ch); return0;}算法訓(xùn)練動態(tài)數(shù)組使用

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼從鍵盤讀入n個整數(shù)，使用動態(tài)數(shù)組存儲所讀入整數(shù)，并計算它們和與平均值分別輸出。規(guī)定盡量使用函數(shù)實現(xiàn)程序代碼。平均值為小數(shù)只保存其整數(shù)某些。樣例輸入5

34002樣例輸出91樣例輸入7

3275291樣例輸出294#include<stdio.h>intmain(){ inti,n,a[100],b[100],sum=0,avg=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&b[i]); a[i]=b[i]; sum=sum+a[i]; } avg=sum/n; printf("%d%d\n",sum,avg); return0;}算法訓(xùn)練刪除數(shù)組零元素

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼從鍵盤讀入n個整數(shù)放入數(shù)組中，編寫函數(shù)CompactIntegers，刪除數(shù)組中所有值為0元素，其后元素向數(shù)組首端移動。注意，CompactIntegers函數(shù)需要接受數(shù)組及其元素個數(shù)作為參數(shù)，函數(shù)返回值應(yīng)為刪除操作執(zhí)行后數(shù)組新元素個數(shù)。輸出刪除后數(shù)組中元素個數(shù)并依次輸出數(shù)組元素。樣例輸入：（輸入格式闡明：5為輸入數(shù)據(jù)個數(shù)，34002是以空格隔開5個整數(shù)）

5

34002

樣例輸出:（輸出格式闡明：3為非零數(shù)據(jù)個數(shù)，342是以空格隔開3個非零整數(shù)）

3

342樣例輸入7

0070090樣例輸出2

79樣例輸入3

000樣例輸出0算法訓(xùn)練最小乘積(基本型)

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述給兩組數(shù)，各n個。

請調(diào)節(jié)每組數(shù)排列順序，使得兩組數(shù)據(jù)相似下標(biāo)元素相應(yīng)相乘，然后相加和最小。規(guī)定程序輸出這個最小值。

例如兩組數(shù)分別為:13-5和-241

那么相應(yīng)乘積取和最小值應(yīng)為：

(-5)*4+3*(-2)+1*1=-25輸入格式第一種行一種數(shù)T表達(dá)數(shù)據(jù)組數(shù)。背面每組數(shù)據(jù)，先讀入一種n，接下來兩行每行n個數(shù)，每個數(shù)絕對值不大于等于1000。

n<=8,T<=1000輸出格式一種數(shù)表達(dá)答案。樣例輸入2313-5-24151234510101樣例輸出-256#include<stdio.h>voidsort1(int*a,intn){ inti,j; inttmp; for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++) if(a[j]>a[j+1]) { tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; }}voidsort2(int*a,intn){ inti,j; inttmp; for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++) if(a[j]<a[j+1]) { tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; }}intmain(void){ intT; intn,i; inttotal; inta[8],b[8],c[8]; scanf("%d",&T); while(T) { total=0; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) scanf("%d",&b[i]); sort1(a,n); sort2(b,n); for(i=0;i<n;i++) c[i]=a[i]*b[i]; for(i=0;i<n;i++) total+=c[i]; printf("%d\n",total); T--; } return0;}算法訓(xùn)練Torry困惑(基本型)

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述Torry從小愛慕數(shù)學(xué)。一天，教師告訴她，像2、3、5、7……這樣數(shù)叫做質(zhì)數(shù)。Torry突然想到一種問題，前10、100、1000、10000……個質(zhì)數(shù)乘積是多少呢？她把這個問題告訴教師。教師愣住了，一時回答不出來。于是Torry求助于會編程你，請你算出前n個質(zhì)數(shù)乘積。但是，考慮到你才接觸編程不久，Torry只要你算出這個數(shù)模上50000值。輸入格式僅包括一種正整數(shù)n，其中n<=100000。輸出格式輸出一行，即前n個質(zhì)數(shù)乘積模50000值。樣例輸入1樣例輸出2#include<stdio.h>intpr[100010];inttop;intisPrime(intn){ inti; for(i=0；i<top；i++) { if(n%pr[i]==0) { return0; } } return1;}intfindNextPrime(void){ intn=pr[top-1]+1; while(!isPrime(n)) { n++; } pr[top++]=n; returnn;}intmain(void){ inti，n; intresult=2; scanf("%d"，&n); pr[0]=2; top=1; for(i=1；i<n；i++) { intx=findNextPrime(); result*=x; result%=50000; } printf("%d"，result); return0;}算法訓(xùn)練尋找數(shù)組中最大值

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述對于給定整數(shù)數(shù)組a[],尋找其中最大值，并返回下標(biāo)。輸入格式整數(shù)數(shù)組a[],數(shù)組元素個數(shù)不大于1等于100。輸出數(shù)據(jù)分作兩行：第一行只有一種數(shù)，表達(dá)數(shù)組元素個數(shù)；第二行為數(shù)組各個元素。輸出格式輸出最大值，及其下標(biāo)樣例輸入3321樣例輸出30#include<stdio.h>intmain(){ intn,i,k,max; scanf("%d",&n); inta[n]; for(i=0;i<n;i++) scanf("%d",&a[i]); max=a[0]; for(i=0;i<n;i++) { if(a[i]>=max) { max=a[i]; k=i; } } printf("%d%d",max,k); return0;}算法訓(xùn)練關(guān)聯(lián)矩陣

時間限制：1.0s

內(nèi)存限制：512.0MB

查看參照代碼問題描述有一種n個結(jié)點m條邊有向圖，請輸出她關(guān)聯(lián)矩陣。輸入格式第一行兩個整數(shù)n、m，表達(dá)圖中結(jié)點和邊數(shù)目。n<=100,m<=1000。

接下來m行，每行兩個整數(shù)a、b，表達(dá)圖中有(a,b)邊。

注意圖中也許具有重邊，但不會有自環(huán)。輸出格式輸出該圖關(guān)聯(lián)矩陣，注意請勿變化邊和結(jié)點順序。樣例輸入59

12

31

15

25

23

23

32

43

54樣例輸出1-11000000

-100111-100

0100-1-11-10

00000001-1

00-1-100001#include<stdio.h>intmain(){ inti，ii,n,m，a[1000][2]; scanf("%d%d"，&n，&m); for(i=0；i<m；i++) scanf("%d%d"，&a[i][0]，&a[i][1]); for(i=1；i<=n；i++) { for(ii=0；ii<m；ii++) { if(i==a[ii][0]) { printf("1"); } else if(i==a[ii][1]) { printf("-1"); } else { printf("0"); } } printf("\n"); } return0;}算法訓(xùn)練操作格子

時間限制：1.0s

內(nèi)存限制：256.0MB

查看參照代碼問題描述有n個格子，從左到右放成一排，編號為1-n。共有m次操作，有3種操作類型：1.修改一種格子權(quán)值，2.求持續(xù)一段格子權(quán)值和，3.求持續(xù)一段格子最大值。對于每個2、3操作輸出你所求出成果。輸入格式第一行2個整數(shù)n，m。接下來一行n個整數(shù)表達(dá)n個格子初始權(quán)值。接下來m行，每行3個整數(shù)p,x,y，p表達(dá)操作類型，p=1時表達(dá)修改格子x權(quán)值為y，p=2時表達(dá)求區(qū)間[x,y]內(nèi)格子權(quán)值和，p=3時表達(dá)求區(qū)間[x,y]內(nèi)格子最大權(quán)值。輸出格式有若干行，行數(shù)等于p=2或3操作總數(shù)。每行1個整數(shù)，相應(yīng)了每個p=2或3操作成果。樣例輸入43

1234

213

143

314樣例輸出6

3數(shù)據(jù)規(guī)模與商定對于20%數(shù)據(jù)n<=100，m<=200。對于50%數(shù)據(jù)n<=5000，m<=5000。對于100%數(shù)據(jù)1<=n<=100000，m<=100000，0<=格子權(quán)值<=10000。錦囊1使用線段樹。錦囊2線段樹每個結(jié)點記錄下這一段區(qū)間所有數(shù)和以及最大值即可。#include<stdio.h>#defineN100000#defineA1000#defineB100intsum(int*a，intm，intn){inti，s=0;for(i=m；i<=n；i++)s+=a[i];returns;}intmax(int*a，intm，intn){inti，s=a[m];for(i=m+1；i<=n；i++)if(s<a[i])s=a[i];returns;}intmain(){inti，j，k，m，n;inta[100000]，b[100000][3]，c[A][2]={0};scanf("%d%d"，&n，&m);for(i=0；i<n；i++)scanf("%d"，&a[i]);for(i=0；i<m；i++)for(j=0；j<3；j++)scanf("%d"，&b[i][j]);for(i=0；i<(n+B-1)/B；i++){c[i][0]=c[i][1]=a[i*B];for(j=i*B+1；j<i*B+B&&j<n；j++){c[i][0]+=a[j];if(c[i][1]<a[j])c[i][1]=a[j];}}for(i=0；i<m；i++){if(b[i][0]==1){c[(b[i][1]-1)/B][0]+=b[i][2]-a[b[i][1]-1];k=(b[i][1]-1)/B;if(c[k][1]<=b[i][2]){c[k][1]=b[i][2];}elseif(a[b[i][1]-1]==c[k][1]){a[b[i][1]-1]=b[i][2];c[k][1]=max(a，k*B，k*B+B>n?n-1：k*B+B-1);}a[b[i][1]-1]=b[i][2];}elseif(b[i][0]==2){ints=0;b[i][1]--，b[i][2]--;into=b[i][2]/B-b[i][1]/B;if(o<2){s=sum(a，b[i][1]，b[i][2]);}else{s=sum(a，b[i][1]，(b[i][1]+B)/B*B-1);s+=sum(a，b[i][2]/B*B，b[i][2]);for(j=b[i][1]/B+1；j<b[i][2]/B；j++)s+=c[j][0];}printf("%d\n"，s);}elseif(b[i][0]==3){ints=0，t;b[i][1]--，b[i][2]--;into=b[i][2]/B-b[i][1]/B;if(o<2){s=max(a，b[i][1]，b[i][2]);}else{s=max(a，b[i][1]，(b[i][1]+B)/B*B-1);t=max(a，b[i][2]/B*B，b[i][2]);if(s<t)s=t;for(j=b[i][1]/B+1；j<b[i][2]/B；j++)if(s<c[j][1])s=c[j][1];}printf("%d\n"，s);}}return0;}//test//1.cpp/*ID：FirwalessLANG：C++TASK：*/#include<cstdio>#include<algorithm>structTree{intsum，max;};Treetree[1<<18];voidscan(int&n){charc;c=getchar();if(c==EOF){return;}while(c<'0'||c>'9'){c=getchar();}n=c-'0';while(c=getchar()，c>='0'&&c<='9'){n*=10;n+=c-'0';}}voidput(intn){intcnt=0;chars[16];if(n==0){putchar('0');return;}for(；n；n/=10){s[cnt++]=n%10+'0';}while(cnt--){putchar(s[cnt]);}}voidupdate(intn，intv){for(n+=(1<<17),tree[n].sum=tree[n].max=v，n>>=1；n；n>>=1){tree[n].max=std::max(tree[n+n].max，tree[n+n+1].max);tree[n].sum=tree[n+n].sum+tree[n+n+1].sum;}}intquery(ints，intt，intfunc){intsum=0，max=0;for(s+=(1<<17)-1，t+=(1<<17)+1；s^t^1；s>>=1，t>>=1){if(~s&1){sum+=tree[s^1].sum;max=std::max(max，tree[s^1].max);}if(t&1){sum+=tree[t^1].sum;max=std::max(max，tree[t^1].max);}}returnfunc?max：sum;}intmain(){intn，m，i，a，b，c;scan(n);scan(m);for(i=1；i<=n；++i){scan(a);update(i，a);}while(m--){scan(c);scan(a);scan(b);c==1&&(update(a，b)，0);c==2&&(put(query(a，b，0))，putchar('\n')，0);c==3&&(put(query(a，b，1))，putchar('\n')，0);}return0;}算法訓(xùn)練逆序?qū)?/p>

時間限制：1.0s

內(nèi)存限制：256.0MB

查看參照代碼錦囊1使用平衡樹。錦囊2從葉子到根依次解決，每次把結(jié)點個數(shù)少樹中結(jié)點依次添加到結(jié)點個數(shù)多里面，并順便計算逆序?qū)€數(shù)和兩棵子樹互換后逆序?qū)€數(shù)。問題描述Alice是一種讓人非常愉躍人!她總是去學(xué)習(xí)某些她不懂問題，然后再想出許多稀奇古怪題目。這幾天，Alice又沉浸在逆序?qū)Ω吲d當(dāng)中，她已近學(xué)會了如何求逆序?qū)?shù)，動態(tài)維護(hù)逆序?qū)?shù)等等題目，她以為把這些題讓你做簡直是太沒追求了，于是，通過一天思考和完善，Alice終于拿出了一道她以為差不多題目：有一顆2n-1個節(jié)點二叉樹，它有正好n個葉子節(jié)點，每個節(jié)點上寫了一種整數(shù)。如果將這棵樹所有葉子節(jié)點上數(shù)從左到右寫下來，便得到一種序列a[1]…a[n]。當(dāng)前想讓這個序列中逆序?qū)?shù)量至少，但唯一操作就是選樹上一種非葉子節(jié)點，將它左右兩顆子樹互換。她可以做任意多次這個操作。求在最優(yōu)方案下，該序列逆序?qū)?shù)至少有多少。Alice自己已近想出了題目正解，她打算拿來和你分享，她規(guī)定你在最短時間內(nèi)完畢。輸入格式第一行一種整數(shù)n。下面每行，一種數(shù)x。如果x=0，表達(dá)這個節(jié)點非葉子節(jié)點，遞歸地向下讀入其左孩子和右孩子信息，如果x≠0，表達(dá)這個節(jié)點是葉子節(jié)點，權(quán)值為x。輸出格式輸出一種整數(shù)，表達(dá)至少有多少逆序?qū)?。樣例輸?

0

0

3

1

2樣例輸出1數(shù)據(jù)規(guī)模與商定對于20%數(shù)據(jù)，n<=5000。對于100%數(shù)據(jù)，1<=n<=00，0<=a[i]<2^31。#include<stdio.h>#defineN10longlongans=0;intleft[N]，right[N];intlen[N];intvals[N];intvTop=1;intlRotate(intrt){intnRt=right[rt];right[rt]=left[nRt];left[nRt]=rt;len[nRt]=len[rt];len[rt]=len[left[rt]]+len[right[rt]]+1;returnnRt;}intrRotate(intrt){intnRt=left[rt];left[rt]=right[nRt];right[nRt]=rt;len[nRt]=len[rt];len[rt]=len[left[rt]]+len[right[rt]]+1;returnnRt;}intadjust(intrt，intisLeft){if(isLeft){if(len[left[left[rt]]]>len[right[rt]]||len[right[left[rt]]]>len[right[rt]]){if(len[right[left[rt]]]>len[right[rt]]){left[rt]=lRotate(left[rt]);}returnrRotate(rt);}}else{if(len[left[right[rt]]]>len[left[rt]]||len[right[right[rt]]]>len[left[rt]]){if(len[left[right[rt]]]>len[left[rt]]){right[rt]=rRotate(right[rt]);}returnlRotate(rt);}}returnrt;}intinsert(intrt，intnode){len[rt]++;if(vals[node]<vals[rt]){if(left[rt]==0){left[rt]=node;}else{left[rt]=insert(left[rt]，node);}}else{if(right[rt]==0){right[rt]=node;}else{right[rt]=insert(right[rt]，node);}}returnadjust(rt，vals[node]<vals[rt]);}intrank(intrt，intval){if(rt==0){return0;}elseif(val>=vals[rt]){returnrank(right[rt]，val);}else{returnrank(left[rt]，val)+1+len[right[rt]];}}intmerge(intdes，intvBegin，intvEnd){longlongca=0，cb=0;inti;for(i=vBegin；i<vEnd；i++){ca+=rank(des，vals[i]);cb+=len[des]-rank(des，vals[i]-1);}ans+=ca<cb?ca：cb;for(i=vBegin；i<vEnd；i++){left[i]=right[i]=0;len[i]=1;des=insert(des，i);}returndes;}intbuildTree(){intval;scanf("%d"，&val);if(val!=0){left[vTop]=right[vTop]=0;len[vTop]=1;vals[vTop]=val;returnvTop++;}intls=vTop;intrlt=buildTree();intrs=vTop;intrrt=buildTree();intre=vTop;if(rs-ls>re-rs){returnmerge(rlt，rs，re);}else{returnmerge(rrt，ls，rs);}}intmain(void){intn;scanf("%d"，&n);buildTree();printf("%I64d"，ans);return0;}

算法訓(xùn)練安慰奶牛

時間限制：1.0s

內(nèi)存限制：256.0MB

查看參照代碼錦囊1使用最小生成樹算法。錦囊2將每條邊(a，b)權(quán)值Lj變化為2Lj+Ca+Cb，然后使用最小生成樹來計算。問題描述FarmerJohn變得非常懶，她不想再繼續(xù)維護(hù)供奶牛之間供通行道路。道路被用來連接N個牧場，牧場被持續(xù)地編號為1到N。每一種牧場都是一種奶牛家。FJ籌劃除去P條道路中盡量多道路，但是還要保持牧場之間連通性。你一方面要決定那些道路是需要保存N-1條道路。第j條雙向道路連接了牧場Sj和Ej(1<=Sj<=N；1<=Ej<=N；Sj!=Ej)，并且走完它需要Lj時間。沒有兩個牧場是被一條以上道路所連接。奶牛們非常傷心，由于她們交通系統(tǒng)被削減了。你需要到每一種奶牛住處去安慰她們。每次你到達(dá)第i個牧場時候(雖然你已經(jīng)到過)，你必要花去Ci時間和奶牛交談。你每個晚上都會在同一種牧場(這是供你選取)過夜，直到奶牛們都從悲哀中緩過神來。在早上起來和晚上回去睡覺時候，你都需要和在你睡覺牧場奶牛交談一次。這樣你才干完畢你交談任務(wù)。假設(shè)FarmerJohn采納了你建議，請計算出使所有奶牛都被安慰至少時間。輸入格式第1行包括兩個整數(shù)N和P。接下來N行，每行包括一種整數(shù)Ci。接下來P行，每行包括三個整數(shù)Sj，Ej和Lj。輸出格式輸出一種整數(shù)，所需要總時間(包括和在你所在牧場奶牛兩次談話時間)。樣例輸入57

10

10

20

6

30

125

235

2412

3417

2515

356樣例輸出176數(shù)據(jù)規(guī)模與商定5<=N<=10000，N-1<=P<=100000，0<=Lj<=1000，1<=Ci<=1,000。#include<stdio.h>#include<stdlib.h>#defineM100000typedefstructNode{ intu; intv; intw;}Node;Nodee[100002];intfa[100002];intc[100002];intrank[100002];intsum=0;intn，m;intcmp(constvoid*a，constvoid*b){ Node*c=(Node*)a; Node*d=(Node*)b; returnc->w-d->w;}intfind(intx){ inti，k，r; r=x; while(fa[r]>=0) r=fa[r]; k=x; while(k!=r) { i=fa[k]; fa[k]=r; k=i; } returnr; /*if(x!=fa[x]) fa[x]=find(fa[x]); returnfa[x];*/}voidUnion(intu，intv){/* if(rank[u]>rank[v]) fa[v]=u; else { if(rank[u]==rank[v]) rank[v]++; fa[u]=v; }*/ intr1,r2;intnum;r1=find(u);r2=find(v);num=fa[r1]+fa[r2];if(fa[r1]<fa[r2]){fa[r2]=r1;fa[r1]=num;}else{fa[r1]=r2;fa[r2]=num;}}intKruskal(){inti;intu,v;intsumweight=0,count=0;for(i=0;i<n;i++)fa[i]=-1;qsort(e,m,sizeof(e[0]),cmp);for(i=0;i<m;i++){u=e[i].u;v=e[i].v;if(find(u)!=find(v)){sumweight+=e[i].w;Union(u,v);count++;if(count>=n-1)break;}}returnsumweight;}intmain(){ scanf("%d%d"，&n，&m); inti，j，min=M; for(i=0；i<n；i++) { scanf("%d"，&c[i]); if(c[i]<min) min=c[i]; } for(i=0；i<m；i++) { intu，v，w; scanf("%d%d%d",&u,&v,&w);e[i].u=u-1;e[i].v=v-1;e[i].w=w*2+c[u-1]+c[v-1]; } printf("%d\n"，min+Kruskal()); return0;}

算法訓(xùn)練最短路

時間限制：1.0s

內(nèi)存限制：256.0MB

查看參照代碼錦囊1使用最短路算法。錦囊2使用Dijkstra算法，此圖邊數(shù)比點數(shù)平方要少諸多，因而應(yīng)當(dāng)使用帶堆優(yōu)化Dijkstra。問題描述給定一種n個頂點，m條邊有向圖（其中某些邊權(quán)也許為負(fù)，但保證沒有負(fù)環(huán)）。請你計算從1號點到其她點最短路（頂點從1到n編號）。輸入格式第一行兩個整數(shù)n，m。接下來m行，每行有三個整數(shù)u，v，l，表達(dá)u到v有一條長度為l邊。輸出格式共n-1行，第i行表達(dá)1號點到i+1號點最短路。樣例輸入33

12-1

23-1

312樣例輸出-1

-2數(shù)據(jù)規(guī)模與商定對于10%數(shù)據(jù)，n=2，m=2。對于30%數(shù)據(jù)，n<=5，m<=10。對于100%數(shù)據(jù)，1<=n<=0，1<=m<=00，-10000<=l<=10000，保證從任意頂點都能到達(dá)其她所有頂點。

#include<stdio.h>#include<string.h>#defineinf100000structIn{inte;intw;intnext;}map[10];intdis[0],Q[0];intvis[0],head[0];voidSPFA(intn){inti,j,front,rear,temp;for(i=1;i<=n;i++){dis[i]=inf;}dis[1]=0;vis[1]=1;front=0;rear=1;Q[front]=1;while(front<rear){temp=Q[front++];vis[temp]=0;j=head[temp];while(j>0){if(dis[map[j].e]>map[j].w+dis[temp]){dis[map[j].e]=map[j].w+dis[temp];if(!vis[map[j].e]){Q[rear++]=map[j].e;vis[map[j].e]=1；}}j=map[j].next;}}}intmain(){intn,m,i,j,a,b,val;while(~scanf("%d%d",&n,&m)){memset(Q,0,sizeof(Q));memset(head,0,sizeof(head));memset(vis,0,sizeof(vis));for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&val);map[i].e=b;map[i].w=val;map[i].next=head[a];head[a]=i;}SPFA(n);for(i=2;i<=n;i++){printf("%d\n",dis[i]);}}return0;}#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#defineMAX_E00#defineINF0x3f3f3f3fusingnamespacestd;structedge{intfrom，to，cost;};edgees[MAX_E];intd[MAX_E];intV，E;voidshortest_path(ints){for(inti=0；i<=V；i++){d[i]=INF;}d[s]=0;while(true){boolupdate=false;for(inti=0；i<E；i++){edgee=es[i];if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){d[e.to]=d[e.from]+e.cost;update=true;}}if(!update)break;}}intmain(){scanf("%d%d"，&V，&E);for(inti=0；i<E；i++){scanf("%d%d%d"，&es[i].from，&es[i].to，&es[i].cost);}shortest_path(1);for(inti=2；i<=V；i++){printf("%d\n"，d[i]);}return0;}算法訓(xùn)練結(jié)點選取

時間限制：1.0s

內(nèi)存限制：256.0MB

查看參照代碼錦囊1使用樹型動態(tài)規(guī)劃。錦囊2用F[i]表達(dá)從子樹i中選取結(jié)點，且結(jié)點i必要被選取最大值，用G[i]表達(dá)從子樹i中選取結(jié)點，且結(jié)點i必要不被選取最大值。則F[i]=a[i]+\sum(G[j])，其中a[i]表達(dá)結(jié)點i權(quán)值，j是i子結(jié)點。G[i]=\sum(max(F[j]，G[j]))，其中j是i子結(jié)點。問題描述有一棵n個節(jié)點樹，樹上每個節(jié)點均有一種正整數(shù)權(quán)值。如果一種點被選取了，那么在樹上和它相鄰點都不能被選取。求選出點權(quán)值和最大是多少？輸入格式第一行包括一種整數(shù)n。接下來一行包括n個正整數(shù)，第i個正整數(shù)代表點i權(quán)值。接下來一共n-1行，每行描述樹上一條邊。輸出格式輸出一種整數(shù)，代表選出點權(quán)值和最大值。樣例輸入5

12345

12

13

24

25樣例輸出12樣例闡明選取3、4、5號點，權(quán)值和為3+4+5=12。數(shù)據(jù)規(guī)模與商定對于20%數(shù)據(jù)，n<=20。對于50%數(shù)據(jù)，n<=1000。對于100%數(shù)據(jù)，n<=100000。權(quán)值均為不超過1000正整數(shù)。#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructNode{intto;intnext;}Node;#defineN100020intmax(inta，intb){returna>b?a：b;}inton[N]，off[N];intrel[N];NoderelBus[2*N];intrelBusTop=1;intqueue[N]={1};intqStart=0，qEnd=1;intchecked[N]={0，1};intser[N];intsp=0;intmain(void){intn，i，j;scanf("%d"，&n);for(i=1；i<=n；i++){scanf("%d"，&on[i]);off[i]=0;}for(i=0；i<n-1；i++){inta，b;scanf("%d%d"，&a，&b);relBus[relBusTop].to=b;relBus[relBusTop].next=rel[a];rel[a]=relBusTop++;relBus[relBusTop].to=a;relBus[relBusTop].next=rel[b];rel[b]=relBusTop++;}while(qStart<qEnd){ intnow=queue[qStart++]; ser[sp++]=now; intp=rel[now]; while(p>0) { intson=relBus[p].to; if(checked[son]==0) { queue[qEnd++]=son; checked[son]=1; } p=relBus[p].next; }}for(i=n-1；i>=0；i--){ intson=ser[i]; intp=rel[son]; while(p>0) { intfather=relBus[p].to; on[father]+=off[son]; off[father]+=max(on[son]，off[son]); p=relBus[p].next; }}printf("%d"，max(on[1]，off[1]));return0;}#include<stdio.h>constintNO=1000005;intdp[NO][2];intdu[NO];intfirst[NO],next[NO],v[NO],num=1;boolmark[NO];intn,a;intt[NO],tip,top;intmax(inta,int&b){returna>b?a:b;}voidinput(int&num){ num=0; charch=getchar(); while(ch<'0'||'9'<ch) ch=getchar(); while('0'<=ch&&ch<='9') { num=10*num+ch-'0'; ch=getchar(); }}voidadd(int&a,int&b){ v[num]=b; next[num]=first[a]; first[a]=num++; v[num]=a; next[num]=first[b]; first[b]=num++;}intwork(){ inti; while(tip<top) { a=t[tip++]; mark[a]=1; for(i=first[a];i!=-1;i=next[i]) if(mark[v[i]]) { dp[a][0]+=max(dp[v[i]][0],dp[v[i]][1]); dp[a][1]+=dp[v[i]][0]; } elseif(--du[v[i]]==1) t[top++]=v[i]; } returnmax(dp[a][0],dp[a][1]);}intmain(){ inti,a,b; scanf("%d",&n); for(i=1;i<=n;i++) input(dp[i][1]),first[i]=-1; for(i=1;i<n;i++) input(a),input(b),add(a,b),du[a]++,du[b]++; for(