1、算法訓練 圖形顯示 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個程序，首先輸入一個整數，例如5，然后在屏幕上顯示如下的圖形（5表示行數）：* * * * * * * * * * *#includeint main()int i,j,a100100,n; while(scanf(%d,&n)!=EOF) for(i=0;in;i+) for(j=0;jn-i;j+) printf(*); if(j!=n-i-1) printf( ); if(j=n-1-i) printf(n); 算法訓練 排序 時間限制：1.0s 內存限制：512.0MB 查看

2、參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個程序，輸入3個整數，然后程序將對這三個整數按照從大到小進行排列。輸入格式：輸入只有一行，即三個整數，中間用空格隔開。輸出格式：輸出只有一行，即排序后的結果。輸入輸出樣例樣例輸入9 2 30樣例輸出30 9 2#include#include#define num 100int main(void)int i,j,t,a3=0;for (i=0;i3;i+)scanf(%d,&ai);for (i=0;i3;i+)for (j=i;j3;j+)if (ai=aj)t=ai;ai=aj;aj=t;for (i=0;i3;i+)printf(%d,ai);

3、if(i!=2) printf( );printf(n);return 0; 算法訓練 2的次冪表示 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述任何一個正整數都可以用2進制表示，例如：137的2進制表示為10001001。將這種2進制表示寫成2的次冪的和的形式，令次冪高的排在前面，可得到如下表達式：137=27+23+20現在約定冪次用括號來表示，即ab表示為a（b）此時，137可表示為：2（7）+2（3）+2（0）進一步：7=22+2+20 （21用2表示）3=2+20 所以最后137可表示為：2（2（2）+2+2（0）+2（2+2（0）+2（0）

4、又如：1315=210+28+25+2+1所以1315最后可表示為：2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0）輸入格式正整數（1=n=20000）輸出格式符合約定的n的0，2表示（在表示中不能有空格）樣例輸入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)提示用遞歸實現會比較簡單，可以一邊遞歸一邊輸出#include int l=0;char temp1000=0;void show(int n) if(n=0) temp

5、l=0;l+;return ; if(n=2) templ=2,l+;return ; int a15=0,i=0,j; while(n!=0) ai=n%2; n/=2; i+; for(j=i-1;j=0;j-) if(aj=1) if(j=1) if(templ-1=) | templ-1=2 ) templ=+;l+;templ=2;l+; else if(templ-1=) | templ-1=2 ) templ=+;l+;templ=2;l+;templ=(;l+; show(j); templ=);l+; int main()int n;scanf(%d,&n);show(n);

6、printf(%s,temp); return 0;算法訓練 前綴表達式 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個程序，以字符串方式輸入一個前綴表達式，然后計算它的值。輸入格式為：“運算符 對象1 對象2”，其中，運算符為“+”（加法）、“-”（減法）、“*”（乘法）或“/”（除法），運算對象為不超過10的整數，它們之間用一個空格隔開。要求：對于加、減、乘、除這四種運算，分別設計相應的函數來實現。輸入格式：輸入只有一行，即一個前綴表達式字符串。輸出格式：輸出相應的計算結果（如果是除法，直接采用c語言的“/”運算符，結果為整數）。輸入輸出樣例

7、樣例輸入+ 5 2樣例輸出7#includeint main() int a2; int i,j; char c=getchar(); for(i=0;i2;i+) scanf(%d,&ai); if(c=+) j=a0+a1; else if(c=-) j=a0-a1; else if(c=*) j=a0*a1; else if(c=/) j=a0/a1; printf(%d,j); return 0;算法訓練 Anagrams問題 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述Anagrams指的是具有如下特性的兩個單詞：在這兩個單詞當中，每一個英文

8、字母（不區分大小寫）所出現的次數都是相同的。例如，“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。編寫一個程序，輸入兩個單詞，然后判斷一下，這兩個單詞是否是Anagrams。每一個單詞的長度不會超過80個字符，而且是大小寫無關的。輸入格式：輸入有兩行，分別為兩個單詞。輸出格式：輸出只有一個字母Y或N，分別表示Yes和No。輸入輸出樣例樣例輸入UnclearNuclear樣例輸出Y#include void sort(char a,int len)int i,j,max;for(i=0;ilen;i+)max=i;for(j=i+1;jamax) ma

9、x=j;j=ai;ai=amax;amax=j;void strtoupper(char a,int len)int i;for(i=0;i=a & ai=z) ai-=32;int mystrcmp(char a,int l1,char b,int l2)if(l1!=l2) return 0;int i;for(i=0;il1;i+)if(ai!=bi) return 0;return 1;int mystrlen(char *p)int l=0;while(*p+!=0)l+;return l;int main()char s11000=0,s21000=0;int l1,l2;scan

10、f(%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); else printf(N);return 0;算法訓練 出現次數最多的整數 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個程序，讀入一組整數，這組整數是按照從小到大的順序排列的，它們的個數N也是由用戶輸入的，最多不會超過20。然后程序將對這個數組進行統計，把出現次

11、數最多的那個數組元素值打印出來。如果有兩個元素值出現的次數相同，即并列第一，那么只打印比較小的那個值。輸入格式：第一行是一個整數N，N 20；接下來有N行，每一行表示一個整數，并且按照從小到大的順序排列。輸出格式：輸出只有一行，即出現次數最多的那個元素值。輸入輸出樣例樣例輸入5100150150200250樣例輸出150#include int main()int n,i,j,t,max=1,num=0;scanf(%d,&n);if(n0)int an;for(i=0;in;i+)scanf(%d,a+i);j=num=a0;t=1;for(i=1;imax)max=t;num=ai; el

12、set=1;j=ai;printf(%d,num);return 0; 算法訓練 字串統計 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述給定一個長度為n的字符串S，還有一個數字L，統計長度大于等于L的出現次數最多的子串（不同的出現可以相交），如果有多個，輸出最長的，如果仍然有多個，輸出第一次出現最早的。輸入格式第一行一個數字L。第二行是字符串S。L大于0，且不超過S的長度。輸出格式一行，題目要求的字符串。輸入樣例1：4bbaabbaaaaa輸出樣例1：bbaa輸入樣例2：2bbaabbaaaaa輸出樣例2：aa數據規模和約定n=60S中所有字符都是小寫

13、英文字母。提示枚舉所有可能的子串，統計出現次數，找出符合條件的那個#include#includeint main()char S1000,str10001000,temp100,out100;int L,i=0,s,otongji=0,ttongji,a,b,c;scanf(%d%c%c,&L,&S0,&S0);while(Si!=n) scanf(%c,&Si+1); i+; Si = 0; for(s=i+1;L=s;L+) for(a=0;as+1-L;a+)/賦值 for(b = 0;b L;b+) strab=Sa+b; strab = 0; for(i = 0;i a-1;)/比

14、較 for(b = 0;ba;b+) if(strb0!=0) for(c = 0;cL;c+) tempc=strbc; tempc = 0; ttongji = 1; i+; strb0 = 0; break; for(b+;b otongji|(ttongji=otongji&strlen(temp)strlen(out) strcpy(out,temp); otongji = ttongji; i = 0; while(outi != 0) printf(%c,outi); i+; getchar();return 0;算法訓練 矩陣乘法 時間限制：1.0s 內存限制：512.0MB

15、查看參考代碼 錦囊1錦囊2錦囊3問題描述輸入兩個矩陣，分別是m*s，s*n大小。輸出兩個矩陣相乘的結果。輸入格式第一行，空格隔開的三個正整數m,s,n（均不超過200）。接下來m行，每行s個空格隔開的整數，表示矩陣A（i，j）。接下來s行，每行n個空格隔開的整數，表示矩陣B（i，j）。輸出格式m行，每行n個空格隔開的整數，輸出相乘後的矩陣C（i，j）的值。樣例輸入2 3 21 0 -11 1 -30 31 23 1樣例輸出-3 2-8 2提示矩陣C應該是m行n列，其中C(i,j)等于矩陣A第i行行向量與矩陣B第j列列向量的內積。例如樣例中C(1,1)=(1,0,-1)*(0,1,3) = 1

16、* 0 +0*1+(-1)*3=-3 # includeint main()int m,s,n,i,j,k,a200200,b200200,c200200;scanf(%d%d%d,&m,&s,&n);for(i=1;i=m;i+)for(j=1;j=s;j+)scanf(%d,&aij);for(i=1;i=s;i+)for(j=1;j=n;j+)scanf(%d,&bij);for(i=1;i=m;i+)for(j=1;j=n;j+)cij=0;for(i=1;i=m;i+)for(j=1;j=n;j+)for(k=1;k=s;k+)cij=cij+aik*bkj;for(i=1;i=m;

17、i+)for(j=1;j=n;j+)printf(%d ,cij);printf(n);return 0;算法訓練 大小寫轉換 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述編寫一個程序，輸入一個字符串（長度不超過20），然后把這個字符串內的每一個字符進行大小寫變換，即將大寫字母變成小寫，小寫字母變成大寫，然后把這個新的字符串輸出。輸入格式：輸入一個字符串，而且這個字符串當中只包含英文字母，不包含其他類型的字符，也沒有空格。輸出格式：輸出經過轉換后的字符串。輸入輸出樣例樣例輸入AeDb樣例輸出aEdB#include int main()int i;ch

18、ar ch100;gets(ch);i=0;while(chi!=0)if(chi=a)chi-=32;else chi+=32;i+;puts(ch);return 0;算法訓練 動態數組使用 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3從鍵盤讀入n個整數，使用動態數組存儲所讀入的整數，并計算它們的和與平均值分別輸出。要求盡可能使用函數實現程序代碼。平均值為小數的只保留其整數部分。樣例輸入53 4 0 0 2樣例輸出9 1樣例輸入73 2 7 5 2 9 1樣例輸出29 4#include int main()int i,n,a100,b100,sum=0,

19、avg=0;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&bi);ai=bi;sum=sum+ai;avg=sum/n;printf(%d %dn,sum,avg);return 0;算法訓練 刪除數組零元素 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3從鍵盤讀入n個整數放入數組中，編寫函數CompactIntegers，刪除數組中所有值為0的元素，其后元素向數組首端移動。注意，CompactIntegers函數需要接受數組及其元素個數作為參數，函數返回值應為刪除操作執行后數組的新元素個數。輸出刪除后數組中元素的個數并依次輸出數組元

20、素。樣例輸入: （輸入格式說明：5為輸入數據的個數，3 4 0 0 2 是以空格隔開的5個整數）53 4 0 0 2樣例輸出:（輸出格式說明：3為非零數據的個數，3 4 2 是以空格隔開的3個非零整數）33 4 2樣例輸入70 0 7 0 0 9 0樣例輸出27 9樣例輸入30 0 0樣例輸出0算法訓練 最小乘積(基本型) 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述給兩組數，各n個。請調整每組數的排列順序，使得兩組數據相同下標元素對應相乘，然后相加的和最小。要求程序輸出這個最小值。例如兩組數分別為:1 3-5和-2 4 1那么對應乘積取和的最小值應為

21、：(-5) * 4 + 3 * (-2) + 1 * 1 = -25輸入格式第一個行一個數T表示數據組數。后面每組數據，先讀入一個n，接下來兩行每行n個數，每個數的絕對值小于等于1000。n=8,T=1000輸出格式一個數表示答案。樣例輸入231 3 -5-2 4 151 2 3 4 51 0 1 0 1樣例輸出-256#includevoid sort1(int *a,int n)int i,j;int tmp;for(i=0;in-1;i+)for(j=0;jaj+1)tmp=aj;aj=aj+1;aj+1=tmp;void sort2(int *a,int n)int i,j;int t

22、mp;for(i=0;in-1;i+)for(j=0;jn-1-i;j+)if(ajaj+1)tmp=aj;aj=aj+1;aj+1=tmp;int main(void)int T;int n,i;int total;int a8,b8,c8;scanf(%d,&T);while(T)total=0;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i+)scanf(%d,&bi);sort1(a,n);sort2(b,n);for(i=0;in;i+)ci=ai*bi;for(i=0;in;i+)total+=ci;printf(%dn,

23、total);T-;return 0;算法訓練 Torry的困惑(基本型) 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述Torry從小喜愛數學。一天，老師告訴他，像2、3、5、7這樣的數叫做質數。Torry突然想到一個問題，前10、100、1000、10000個質數的乘積是多少呢？他把這個問題告訴老師。老師愣住了，一時回答不出來。于是Torry求助于會編程的你，請你算出前n個質數的乘積。不過，考慮到你才接觸編程不久，Torry只要你算出這個數模上50000的值。輸入格式僅包含一個正整數n，其中n=100000。輸出格式輸出一行，即前n個質數的乘積模50

24、000的值。樣例輸入1樣例輸出2#includeint pr100010;int top;int isPrime(int n)int i;for(i = 0; i top; i+)if(n % pri = 0)return 0;return 1;int findNextPrime(void)int n = prtop - 1 + 1;while(!isPrime(n)n+;prtop+ = n;return n;int main(void)int i, n;int result = 2;scanf(%d, &n);pr0 = 2;top = 1;for(i = 1; i n; i+)int x

25、 = findNextPrime();result *= x;result %= 50000;printf(%d, result);return 0;算法訓練 尋找數組中最大值 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述對于給定整數數組a,尋找其中最大值，并返回下標。輸入格式整數數組a,數組元素個數小于1等于100。輸出數據分作兩行：第一行只有一個數，表示數組元素個數；第二行為數組的各個元素。輸出格式輸出最大值，及其下標樣例輸入33 2 1樣例輸出3 0#include int main()int n,i,k,max;scanf (%d,&n);in

26、t an;for(i=0;in;i+)scanf(%d,&ai);max=a0;for(i=0;i=max)max=ai;k=i;printf(%d %d,max,k);return 0;算法訓練 關聯矩陣 時間限制：1.0s 內存限制：512.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述有一個n個結點m條邊的有向圖，請輸出他的關聯矩陣。輸入格式第一行兩個整數n、m，表示圖中結點和邊的數目。n=100,m=1000。接下來m行，每行兩個整數a、b，表示圖中有(a,b)邊。注意圖中可能含有重邊，但不會有自環。輸出格式輸出該圖的關聯矩陣，注意請勿改變邊和結點的順序。樣例輸入5 91 23 11

27、 52 52 32 33 24 35 4樣例輸出1 -1 1 0 0 0 0 0 0-1 0 0 1 1 1 -1 0 00 1 0 0 -1 -1 1 -1 00 0 0 0 0 0 0 1 -10 0 -1 -1 0 0 0 0 1#includeint main()int i, ii,n,m, a10002;scanf(%d%d, &n, &m);for ( i = 0; i m; i+)scanf(%d%d, &ai0, &ai1);for ( i = 1; i =n; i+)for (ii = 0; ii m; ii+)if (i=aii0)printf(1 );elseif (i=

28、aii1)printf(-1 );elseprintf(0 );printf(n);return 0;算法訓練 操作格子 時間限制：1.0s 內存限制：256.0MB 查看參考代碼 錦囊1錦囊2錦囊3問題描述有n個格子，從左到右放成一排，編號為1-n。共有m次操作，有3種操作類型：1.修改一個格子的權值，2.求連續一段格子權值和，3.求連續一段格子的最大值。對于每個2、3操作輸出你所求出的結果。輸入格式第一行2個整數n，m。接下來一行n個整數表示n個格子的初始權值。接下來m行，每行3個整數p,x,y，p表示操作類型，p=1時表示修改格子x的權值為y，p=2時表示求區間x,y內格子權值和，p=3

29、時表示求區間x,y內格子最大的權值。輸出格式有若干行，行數等于p=2或3的操作總數。每行1個整數，對應了每個p=2或3操作的結果。樣例輸入4 31 2 3 42 1 31 4 33 1 4 樣例輸出63 數據規模與約定對于20%的數據n = 100，m = 200。對于50%的數據n = 5000，m = 5000。對于100%的數據1 = n = 100000，m = 100000，0 = 格子權值 = 10000。錦囊1使用線段樹。 錦囊2線段樹的每個結點記錄下這一段區間所有數的和以及最大值即可。 #include #define N 100000#define A 1000#define

30、 B 100int sum(int* a, int m, int n) int i, s = 0; for (i = m; i = n; i+) s += ai; return s;int max(int* a, int m, int n) int i, s = am; for (i = m + 1; i = n; i+) if (s ai) s = ai; return s;int main() int i, j, k, m, n; int a100000, b1000003, cA2 = 0; scanf(%d%d, &n, &m); for (i = 0; i n; i+) scanf(

31、%d, &ai); for (i = 0; i m; i+) for (j = 0; j 3; j+) scanf(%d, &bij); for (i = 0; i (n + B - 1) / B; i+) ci0 = ci1 = ai * B; for (j = i * B + 1; j i * B + B & j n; j+) ci0 += aj; if (ci1 aj) ci1 = aj; for (i = 0; i m; i+) if (bi0 = 1) c(bi1 - 1) / B0 += bi2 - abi1 - 1; k = (bi1 - 1) / B; if (ck1 n ?

32、n - 1 : k * B + B - 1); abi1 - 1 = bi2; else if (bi0 = 2) int s = 0; bi1-, bi2-; int o = bi2 / B - bi1 / B; if (o 2) s = sum(a, bi1, bi2); else s = sum(a, bi1, (bi1 + B) / B * B - 1); s += sum(a, bi2 / B * B, bi2); for (j = bi1 / B + 1; j bi2 / B; j+) s += cj0; printf(%dn, s); else if (bi0 = 3) int

33、s = 0, t; bi1-, bi2-; int o = bi2 / B - bi1 / B; if (o 2) s = max(a, bi1, bi2); else s = max(a, bi1, (bi1 + B) / B * B - 1); t = max(a, bi2 / B * B, bi2); if (s t) s = t; for (j = bi1 / B + 1; j bi2 / B; j+) if (s cj1) s = cj1; printf(%dn, s); return 0;/ test/ 1.cpp/* ID: Firwaless LANG: C+ TASK: */

34、#include #include struct Tree int sum, max;Tree tree1 18;void scan(int &n) char c; c = getchar(); if (c = EOF) return ; while (c 9) c = getchar(); n = c - 0; while (c = getchar(), c = 0 & c = 9) n *= 10; n += c - 0; void put(int n) int cnt = 0; char s16; if (n = 0) putchar(0); return ; for( ; n; n /

35、= 10) scnt+ = n % 10 + 0; while (cnt-) putchar(scnt); void update(int n, int v) for (n += (1 = 1; n; n = 1) treen.max = std:max(treen + n.max, treen + n + 1.max); treen.sum = treen + n.sum + treen + n + 1.sum; int query(int s, int t, int func) int sum = 0, max = 0; for (s += (1 17) - 1, t += (1 = 1,

36、 t = 1) if (s & 1) sum += trees 1.sum; max = std:max(max, trees 1.max); if (t & 1) sum += treet 1.sum; max = std:max(max, treet 1.max); return func ? max : sum;int main() int n, 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); return 0;算法訓練 逆序對 時間限制：1.0s 內存限制：256.0MB 查看參考代碼 錦囊1使用平衡樹。 錦囊2從葉子到根依次處理，每次