Noip2009普及组初赛(C++)试题及答案(2)

using namespace std;

const int maxn=50; void getnext(char str[]) {

int l=strlen(str),i,j,k,temp; k=l-2;

while(k>=0&&str[k]>str[k+1]) k--; i=k+1;

while(istr[k]) i++; temp=str[k]; str[k]=str[i-1]; str[i-1]=temp; for(i=l-1;i>k;i--) }

int main() {

char a[maxn]; int n;

cin >> a >> n; while(n>0) { }

cout << a << endl; return 0; }

getnext(a); n--;

for(j=k+1;j

if(str[j]>str[j+1]) { }

temp=str[j]; str[j]=str[j+1]; str[j+1]=temp;

return ;

输入：NOIP 3 输出：

四．完善程序 (前8空，每空3分，后2空，每空2分，共28分) 1．（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、

NOIP2009初赛

普及组 C++ 6

正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8时，输出16和7。

#include using namespace std;

int a[101];

int n,i,ans,len,tmp,beg;

int main(){ cin >> n;

for (i=1;i<=n;i++)

cin >> a[i];

tmp=0; ans=0; len=0;

beg= ① ; for (i=1;i<=n;i++){ }

cout << ans << \ return 0; }

if (tmp+a[i]>ans){ }

else if ( ② &&i-beg>len) } else

⑤ ; len=i-beg; beg= ④ ; tmp=0;

if (tmp+a[i] ③ ){

ans=tmp+a[i]; len=i-beg;

2. (国王放置) 在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读入三个数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0~m-1。

#include using namespace std;

NOIP2009初赛

普及组 C++ 7

int n,m,k,ans; int hash[5][5];

void work(int x,int y,int tot){ int i,j; if (tot==k){ } do{ }

while (1); }

int main(){

cin >> n >> m >> k; ans=0;

memset(hash,0,sizeof(hash));

while (hash[x][y]){ }

for (i=x-1;i<=x+1;i++)

if (i>=0&&i

for (j=y-1;j<=y+1;j++)

if (j>=0&&j

② ;

y++; if (y==m){

x++;

y= ① ; }

if (x==n)

return;

ans++; return;

③ ;

for (i=x-1;i<=x+1;i++)

if (i>=0&&i

for (j=y-1;j<=y+1;j++)

if (j>=0&&j

④ ;

y++; }

if (y==m){

x++; y=0;

if (x==n)

return;

NOIP2009初赛 普及组 C++ 8

⑤ ;

cout << ans << endl; return 0; }

答案部分

NOIP2009初赛 普及组 C++ 9

NOIP2009年普及组（C++语言）参考答案与评分标准

一、单项选择题：（每题1.5分）

1. D 2. B 3. A 4. A 5. B 6. D 7. C 8. B 9. C 10. D 11. C 12. C

13. B 14. D 15. D

16. B 17. D 18. A 19. C 20. B 二、问题求解：（共2题，每空5分，共计10分） 1．70 2．5

三、阅读程序写结果（共4题，每题8分，共计32分） 1. 4 2. 416 3. 782 4. NPOI

四．完善程序 (前8空，每空3分，后2空，每空2分，共28分)

（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 1. ① 0

② tmp+a[i]==ans 或者 a[i]+tmp==ans 或者ans==a[i]+tmp等 ③ <0 ④ i

⑤ tmp+=a[i] 或者 tmp=tmp+a[i] 2. ① 0

② hash[i][j]++ 或者 hash[i][j]= hash[i][j]+1 或者 ++hash[i][j]

③ work(x,y,tot+1)

④ hash[i][j]-- 或者 hash[i][j]= hash[i][j]-1 或者--hash[i][j] ⑤ work(0,0,0)

NOIP2009初赛

普及组 C++ 10

注意：② ④ 两空，不一定要++ 或者 - -。也可以是④ - - , ② ++. 也可以是 += k , 也可以 -= k, 甚至任何加标记的操作(如位运算)都可以，只要相互撤销。（所以答案非常多）。

NOIP2009初赛

普及组 C++ 11