CCF真題答案匯總(部分)

1、2015-09-1數(shù)據(jù)分段給定一個(gè)整數(shù)數(shù)列，數(shù)列中連續(xù)相同的最長整數(shù)序列算成一段，問數(shù)列中共有多少段？#include<iostream>using namespace std;int main()int n,a1000;cin>>n;for(int i=0;i<n;i+)cin>>ai;int d=a0,m=1;for(int i=1;i<n;i+)if(ai!=d)m+;d=ai;cout<<m<<endl;return 0;2015-09-2日期計(jì)算給定一個(gè)年份y和一個(gè)整數(shù)d，問這一年的第d天是幾月幾日？ 注意閏年的

2、2月有29天。滿足下面條件之一的是閏年： 1） 年份是4的整數(shù)倍，而且不是100的整數(shù)倍； 2） 年份是400的整數(shù)倍。#include <iostream>using namespace std;int main()int y,d,m=1;cin>>y;cin>>d;if(y%4=0&&y%100!=0|y%400=0)int a12=31,29,31,30,31,30,31,31,30,31,30,31;for(int i=0;i<12;i+)if(d>=ai)m+;d=d-ai;elseint a12=31,28,31,30

3、,31,30,31,31,30,31,30,31;for(int i=0;i<12;i+)if(d>=ai)m+;d=d-ai;cout<<m<<endl;cout<<d<<endl;return 0;2015-09-3 模板生成系統(tǒng)成成最近在搭建一個(gè)網(wǎng)站，其中一些頁面的部分內(nèi)容來自數(shù)據(jù)庫中不同的數(shù)據(jù)記錄，但是頁面的基本結(jié)構(gòu)是相同的。例如，對(duì)于展示用戶信息的頁面，當(dāng)用戶為 Tom 時(shí)，網(wǎng)頁的源代碼是#include<iostream> using namespace std; #include<string.h>

4、; #define maxn 0x7fffffff #include<map> #include<stdio.h> int m,n; int main() int i,j; string s105; string s1,s2,s3,s4; cin>>n>>m; getchar(); for(i=0;i<n;i+) getline(cin,si); map<string,string>v; for(j=0;j<m;j+) int k,k1=0; cin>>s1; getchar(); getline(cin,s2

5、); s1.insert(0," "); s1=s1+" " s2.erase(0,1); s2.erase(s2.end()-1,s2.end(); vs1=s2; int j120,j220,k,k1; for(i=0;i<n;i+) k1=0; memset(j1,-1,sizeof(j1); memset(j2,-1,sizeof(j2); for(j=0;sij!=0;j+) if(sij=''&&sij+1='') j1k1=j; if(sij=''&&si

6、j+1='') j2k1=j+1; if(j1k1!=-1&&j2k1!=-1) k1+; int t=0; for(j=0;j<k1;j+) s3="" for(k=j1j+t;k<=j2j+t;k+) s3.insert(s3.end(),sik); if(v.count(s3) si.replace(si.begin()+j1j+t,si.begin()+j2j+1+t,vs3); t=t+vs3.size()-s3.size();/注意替代后字符串的長度發(fā)生改變，t為變化的長度。 else si.replace(si.be

7、gin()+j1j+t,si.begin()+j2j+1+t,""); t=t-s3.size(); cout<<si<<endl; return 0; 2015-09-4高速公路某國有n個(gè)城市，為了使得城市間的交通更便利，該國國王打算在城市之間修一些高速公路，由于經(jīng)費(fèi)限制，國王打算第一階段先在部分城市之間修一些單向的高速公路。 現(xiàn)在，大臣們幫國王擬了一個(gè)修高速公路的計(jì)劃?？戳擞?jì)劃后，國王發(fā)現(xiàn)，有些城市之間可以通過高速公路直接（不經(jīng)過其他城市）或間接（經(jīng)過一個(gè)或多個(gè)其他城市）到達(dá)，而有的卻不能。如果城市A可以通過高速公路到達(dá)城市B，而且城市B也可以通

8、過高速公路到達(dá)城市A，則這兩個(gè)城市被稱為便利城市對(duì)。#include <iostream> #include <cstdio> #include <cstring> #include <set> #include <queue> using namespace std; const int ADJ_NUM = 50; const int SIZE = 10001; struct _graph int adjADJ_NUM; / 來記錄鄰接點(diǎn)的下標(biāo) int num; / 指示鄰接點(diǎn)的數(shù)目 ; _graph VSIZE = 0; int

9、LOWSIZE = 0; int DFNSIZE = 0; bool instackSIZE = false; / 用來記錄一個(gè)頂點(diǎn)是否在棧里面 int StapSIZE = 0; int BelongSIZE = 0; int Dindex, Stop, Bcnt; int answer = 0; void tarjan(int i) int j; int index = 0; DFNi = LOWi = +Dindex; / 標(biāo)記 instacki = true; / 表示這個(gè)節(jié)點(diǎn)在棧里面 Stap+Stop = i; / 入棧 while (true) / 尋找鄰節(jié)點(diǎn) j = Vi.ad

10、jindex+; if (j = 0) break; if (!DFNj) / 如果該點(diǎn)還未有入棧 tarjan(j); / 從這個(gè)節(jié)點(diǎn)開始訪問,也就是遞歸 if (LOWj < LOWi) / j節(jié)點(diǎn)訪問完成之后，LOWj可能發(fā)生了變化，要更新LOWi LOWi = LOWj; else if (instackj && DFNj < LOWi) / 該節(jié)點(diǎn)已經(jīng)在棧里面了 LOWi = DFNj; if (DFNi = LOWi) / DFNi = LOWi這說明有一個(gè)強(qiáng)連通分量 int sum = 0; Bcnt+; / 這里表示聯(lián)通分量的數(shù)量加一 do j =

11、StapStop-; instackj = false; / 這里表示出棧 Belongj = Bcnt; sum+; while (j != i); if (sum != 0) answer += (sum * (sum - 1) / 2; void solve(int N) int i; Stop = Bcnt = Dindex = 0; memset(DFN, 0, sizeof(DFN); for (i = 1; i <= N; i+) if (!DFNi) tarjan(i); int main() int n, m; int a, b; cin >> n >

12、> m; while (m-) cin >> a >> b; Va.adjVa.num = b; / 從 a到b有一條邊 Va.num+; / 計(jì)數(shù)器加1 solve(n); cout << answer << endl; return 0; 2015-09-5 暫無2015-03-1圖像旋轉(zhuǎn)旋轉(zhuǎn)是圖像處理的基本操作，在這個(gè)問題中，你需要將一個(gè)圖像逆時(shí)針旋轉(zhuǎn)90度。 計(jì)算機(jī)中的圖像表示可以用一個(gè)矩陣來表示，為了旋轉(zhuǎn)一個(gè)圖像，只需要將對(duì)應(yīng)的矩陣旋轉(zhuǎn)即可。#include<iostream>using namespace std;i

13、nt a10001000;int b10001000;int main()int m,n;cin>>m>>n;for(int i=0;i<m;i+)for(int j=0;j<n;j+)cin>>aij;for(int i=0;i<m;i+)for(int j=0;j<n;j+)bn-1-ji=aij;for(int i=0;i<n;i+)for(int j=0;j<m;j+)cout<<bij<<" "cout<<endl;return 0;2015-03-2數(shù)字排

14、序給定n個(gè)整數(shù)，請(qǐng)統(tǒng)計(jì)出每個(gè)整數(shù)出現(xiàn)的次數(shù)，按出現(xiàn)次數(shù)從多到少的順序輸出。#include<iostream>using namespace std;int a1000,b1000;int swap(int &a,int &b)int k;k=a;a=b;b=k;int main() int n,max=0,m; cin>>n;for(int i=0;i<n;i+)cin>>ai;bi=1;/從小到大排序 for(int i=0;i<n-1;i+)for(int j=i+1;j<n;j+)if(ai>aj)swap(a

15、i,aj);（/每個(gè)數(shù)出現(xiàn)的次數(shù) for(int i=1;i<n;i+)if(ai=ai-1)bi=bi-1+1;bi-1=0;/for(int i=0;i<n;i+) if(bi>max) max=bi;for(int i=max;i>=1;i-)for(int j=0;j<n;j+)if(bj=i) cout<<aj<<" "<<i<<endl;return 0;2015-03-3節(jié)日有一類節(jié)日的日期并不是固定的，而是以“a月的第b個(gè)星期c”的形式定下來的，比如說母親節(jié)就定為每年的五月的第二個(gè)

16、星期日#include <iostream>using namespace std;int day212=31,28,31,30,31,30,31,31,30,31,30,31,31,29,31,30,31,30,31,31,30,31,30,31;int year(int a)int run=0,ping=0,s; for(int i=1850;i<a;i+)if(i%400=0|i%100!=0&&i%4=0)run+;elseping+;s=run*366+ping*365;return s;int month(int b,int tab)int s=0

17、;for(int i=0;i<b-1;i+)s+=daytabi;return s;int main() int a,b,c,y1,y2;cin>>a>>b>>c>>y1>>y2;for(int i=y1;i<=y2;i+)int tab=0,count=0;if(i%400=0|i%100!=0&&i%4=0)tab=1;int s=year(i)+month(a,tab);int week=(s-1)%7+3;int j=0;for(j=0;j<daytaba-1;j+) if(week=c) c

18、ount+;if(count=b)cout<<i<<'/'<<setw(2)<<setfill('0')<<a<<'/'<<setw(2)<<setfill('0')<<(j+1)<<endl;break;week=week%7+1;if(j=daytaba-1) cout<<"none"<<endl;return 0;2015-03-4網(wǎng)絡(luò)延時(shí)2014-12-1門禁系

19、統(tǒng)濤濤最近要負(fù)責(zé)圖書館的管理工作，需要記錄下每天讀者的到訪情況。每位讀者有一個(gè)編號(hào)，每條記錄用讀者的編號(hào)來表示。給出讀者的來訪記錄，請(qǐng)問每一條記錄中的讀者是第幾次出現(xiàn)。#include<iostream>using namespace std;int main()int n,a1000,b1000;cin>>n;for(int i=0;i<n;i+)cin>>ai;bi=1;for(int i=1;i<n;i+)for(int j=0;j<i;j+)if(ai=aj)bi+;for(int i=0;i<n;i+)cout<<

20、;bi<<" " return 0; 2014-12-2 Z字形掃描在圖像編碼的算法中，需要將一個(gè)給定的方形矩陣進(jìn)行Z字形掃描(Zigzag Scan)。給定一個(gè)n×n的矩陣，Z字形掃描的過程如下圖所示：#include<iostream>using namespace std;int main() int n,a500500; cin>>n; for(int i=0;i<n;i+) for(int j=0;j<n;j+) cin>>aij; for(int k=0;k<2*n-1;k+) for(

21、int i=0;i<n;i+) for(int j=0;j<n;j+) if(i+j=k) if(k%2=0) cout<<aji<<" " else cout<<aij<<" " return 0;2014-09-1 相鄰數(shù)對(duì)給定n個(gè)不同的整數(shù)，問這些數(shù)中有多少對(duì)整數(shù)，它們的值正好相差1。#include<iostream>using namespace std;int main()int n,a1000;int count=0;cin>>n;for(int i=0;i

22、<n;i+)cin>>ai; for(int i=0;i<n-1;i+)for(int j=i+1;j<n;j+)if(ai=aj+1|ai=aj-1)count+;cout<<count<<endl;return 0;2014-09-2 畫圖在一個(gè)定義了直角坐標(biāo)系的紙上，畫一個(gè)(x1,y1)到(x2,y2)的矩形指將橫坐標(biāo)范圍從x1到x2，縱坐標(biāo)范圍從y1到y(tǒng)2之間的區(qū)域涂上顏色。#include<iostream>using namespace std;int main() int n; cin>>n; int

23、bn4;for(int i=0;i<n;i+)for(int j=0;j<4;j+)cin>>b；;int a100100=0;for(int x=0;x<n;x+)for(int i=bx0;i<bx2;i+)for (int j=bx1;j<bx3;j+)aij=1; int m=0;for(int i=0;i<100;i+)for(int j=0;j<100;j+)if(aij=1)m+=1;cout<<m<<endl;return 0;2014-03-1 相反數(shù)有 N 個(gè)非零且各不相同的整數(shù)。請(qǐng)你編一個(gè)程序求

24、出它們中有多少對(duì)相反數(shù)(a 和 -a 為一對(duì)相反數(shù))。#include<iostream>using namespace std;int main()int N,a500;int count=0;cin>>N;for(int i=0;i<N;i+)cin>>ai; for(int i=0;i<N-1;i+)for(int j=i+1;j<N;j+)if(ai=-aj)count+;cout<<count<<endl;return 0;2014-03-2 窗口在某圖形操作系統(tǒng)中,有 N 個(gè)窗口,每個(gè)窗口都是一個(gè)兩邊與坐

25、標(biāo)軸分別平行的矩形區(qū)域。窗口的邊界上的點(diǎn)也屬于該窗口。窗口之間有層次的區(qū)別,在多于一個(gè)窗口重疊的區(qū)域里,只會(huì)顯示位于頂層的窗口里的內(nèi)容。#include<iostream>using namespace std;int main()int M,N;int a104,b102;cin>>N>>M;for(int i=0;i<N;i+)for(int j=0;j<4;j+)cin>>aij;for(int i=0;i<M;i+)for(int j=0;j<2;j+)cin>>bij; int m10=0; for(

26、int k=0;k<M;k+) for(int i=0;i<N;i+)if(bk0>=ai0&&bk0<=ai2&&bk1>=ai1&&bk1<=ai3)mk+; for(int i=0;i<M;i+) if(mi=0) cout<<"IGNORED"<<endl;else cout<<mi<<endl;return 0; 2013-12-1 出現(xiàn)次數(shù)最多的數(shù)給定n個(gè)正整數(shù)，找出它們中出現(xiàn)次數(shù)最多的數(shù)。如果這樣的數(shù)有多個(gè)，請(qǐng)輸出其中最小的

27、一個(gè)。#include<iostream>using namespace std;int swap(int &a,int &b)int k;k=a;a=b;b=k;int main()int n,s1000,b1000;cin>>n;for(int i=0;i<n;i+)cin>>si;bi=1;for(int i=0;i<n-1;i+)for(int j=i+1;j<n;j+)if(si>sj)swap(si,sj);for(int i=1;i<n;i+)if(si=si-1)bi=bi-1+1;bi-1=0;

28、int max=0;for(int i=0;i<n;i+)if(bi>max)max=bi;for(int i=0;i<n;i+)if(bi=max) cout<<si; break; return 0;2014-12-2每一本正式出版的圖書都有一個(gè)ISBN號(hào)碼與之對(duì)應(yīng)，ISBN碼包括9位數(shù)字、1位識(shí)別碼和3位分隔符，其規(guī)定格式如“x-xxx-xxxxx-x”，其中符號(hào)“-”是分隔符（鍵盤上的減號(hào)），最后一位是識(shí)別碼，例如0-670-82162-4就是一個(gè)標(biāo)準(zhǔn)的ISBN碼。ISBN碼的首位數(shù)字表示書籍的出版語言，例如0代表英語；第一個(gè)分隔符“-”之后的三位數(shù)字代表

29、出版社，例如670代表維京出版社；第二個(gè)分隔之后的五位數(shù)字代表該書在出版社的編號(hào)；最后一位為識(shí)別碼。#include<iostream>#include<string>using namespace std;int main()int a10; string s; int sum=0; cin>>s;/ 字符型轉(zhuǎn)換為整型 a0=s0-'0'a1=s2-'0'a2=s3-'0'a3=s4-'0'a4=s6-'0'a5=s7-'0'a6=s8-'0'a

30、7=s9-'0'a8=s10-'0'a9=s12-'0'for(int i=0,j=1;i<9;i+,j+) sum=sum+ai*j; int m=sum%11; char c=m=10? 'X':(char)('0'+m);if(s12=c)cout<<"Right"<<endl;elses12=c; cout<<s<<endl;return 0;2014-12-3 最大的矩形在橫軸上放了n個(gè)相鄰的矩形，每個(gè)矩形的寬度是1，而第i（1 i

31、 n）個(gè)矩形的高度是hi。這n個(gè)矩形構(gòu)成了一個(gè)直方圖。例如，下圖中六個(gè)矩形的高度就分別是3, 1, 6, 5, 2, 3。#include <iostream> #include <assert.h> using namespace std; /* ccf標(biāo)準(zhǔn)算法 TLE! */ /? static void largestRectangle() int n; /直方圖柱形數(shù)目 cin>>n; int *height = new intn; for(int i = 0; i < n; i+) cin>>heighti; long long

32、sum, max = 0; for(int i = 0; i < n; i+) int h = heighti; for(int j = i; j < n; j+) /向右掃描 if( heightj < h ) /高度小時(shí)改為小的高度 h = heightj; sum = (j - i +1) * h; /計(jì)算高度h的矩形面積 if(sum > max) /比原來大則替換 max = sum; while( i < n - 1 && heighti+1 < heighti ) /改進(jìn)：比當(dāng)前heighti小的不用再計(jì)算（i后面高度比i小的不

33、可能有更大面積的矩形） i+; cout<<max<<endl; static void largestRectangle1() int n; cin>>n; /while(n) int *height = (int *)malloc(sizeof(int) * n); for(int i = 0; i < n; i+) cin>>heighti; int j, k, sum, max = 0; for(int i = 0; i < n; i+) sum = 1; /初始只有一個(gè)這樣高度的 j = i - 1; k = i + 1; while(j >= 0 && heightj >= heighti) /向左