全国提高组 CSP-S 初赛模拟试题 (8)
一、单项选择题
（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
6) 学号为1到30的小朋友顺时针排成一圈，从1号小朋友开始顺时针报数，从数字1开始数下去:1,2,3,...,28,29,30,31,32...一圈又一圈，当数到数字n时，所在的小朋友的学号是( )。
二、阅读程序
（程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题1.5分，选择题3分，共计40分）
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005],f[1005];
int main() {
int i, j;
cin>> n; int ans=0;
for (i=0; i<n; i++)cin>>a[i];
for (i=0; i<n; ++i) {
f[i] = 1;
for(j= i-1; j>=0; --j)
if(a[i]>a[j])f[i]= max(f[i],f[j]+1);
ans =max(ans,f[i]);
}
cout<< ans<<"\n";
return 0;
}# include <iostream>
using namespace std;
const int maxn=100005;
int n;
int a[maxn];
int b[maxn];
void solve(int l, int r)
{
if (l==r) return ;
int mid=(l+r)/2;
solve(l, mid); solve(mid+1,r);
int i=1,j=mid+1,k=1;
while(i<=mid &&j<=r)
{
if (a[i]<=a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for (int i=l; i<=r; i++) a[i]=b[i];
}
int main(){
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
solve(1,n);
int ans=0;
for (int i=1; i<=n; i++) ans=ans+a[i]*i;
cout<<ans<<endl;
return 0;
}#include <stdio.h>
char c[200][200];
int s[200], m, n;
void numara() {
int i,j, cod, nr;
for(j=0; j<n; j++) {
nr=0; cod=1;
for(i=0; i<m; i++) {
if(c[i][j]=='1') {
if(!cod) {cod=1;s[nr]++;nr=0;}
}
else {
if (cod) {nr=1;cod=0;}
else nr++;
}
}
if(!cod) s[nr]++;
}
}
int main() {
int i,j;
scanf("%d %d\n", &m, &n);
for(i= 0; i<m; i++) gets(c[i]);
numara();
for(i=1; i<=m; i++)
if(s[i]!= 0) printf("%d %d",i, s[i]);
return 0;
}三、完善程序
（单选题，每题3分，共计30分）
(YY的树)题目给出m颗非空有根(根节点编号为1)区分左右儿子的二叉树。
将某一棵给出二叉树的叶子节点换成任意一棵二叉树称为一次变换，即给出的二叉树变换到新二叉树。
同一棵二叉树进行多次变换是指在每次变换后得到的新二叉树上继续进行变换。
若任意一棵大小超过1的二叉树都可以由给出的某一棵给出的二叉树通过有限次变换得到，则输出“Almost Complete”，否则输出“No”。
题目第一行首先读入一个数m，表示二叉树的棵数。
接下来进行m次这样的操作。
读入一个数n，接下来n行每行2个数li和ri分别表示这棵二叉树第i个点的左右儿子编号，若没有左儿子，则li=0，若没有右儿子，则ri=0。
将某一棵给出二叉树的叶子节点换成任意一棵二叉树称为一次变换，即给出的二叉树变换到新二叉树。
同一棵二叉树进行多次变换是指在每次变换后得到的新二叉树上继续进行变换。
若任意一棵大小超过1的二叉树都可以由给出的某一棵给出的二叉树通过有限次变换得到，则输出“Almost Complete”，否则输出“No”。
题目第一行首先读入一个数m，表示二叉树的棵数。
接下来进行m次这样的操作。
读入一个数n，接下来n行每行2个数li和ri分别表示这棵二叉树第i个点的左右儿子编号，若没有左儿子，则li=0，若没有右儿子，则ri=0。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n, m, tot;
vector <int> t;
int lc[N], rc[N];
inline bool isleaf(int u) { ___(1)___;}
inline bool solve(vector <int> t) {
if (t.empty()) return false;
for (auto o : t) if (isleaf(o)) return true;
vector<int> t1,t2,t3,t4;
for (auto o : t) {
if(!lc[o]) t2.push_back(rc[o]);
if(!rc[o]) t1.push_back(lc[o]);
if( ___(2)___ ) {
if (isleaf(lc[o])) t3.push_back(rc[o]);
if (isleaf(rc[o])) t4.push_back(lc[o]);
}
}
___(3)___;
}
int main() {
scanf("%d", &m);
for (int i=1; i<=m; ++i) {
int n; scanf("%d" ,&n);___(4)___;
for (int j=1; j<=n; ++j) {
scanf("%d", &lc[tot+j]); if (lc[tot+j]) lc[tot+j] += tot;
scanf("%d", &rc[tot+j]); if (rc[tot+j]) rc[tot+j] += tot;
}
___(5)___;
}
if (solve(t)) printf("Almost Complete\n");
else printf("No\n");
return 0;
}逻辑游戏
题目描述:
一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。
对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。
输入:
输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。
输入的第一行是n（0<n<100）。以下的n行每行包括n个整数，分别给出对应的单元里的整数（这n个整数之间用空格分开）。图4给出了输入样例对应的图形。
输出:
当可以画出满足题意的曲线的时候，输出“YES”；否则，输出“NO”。
输入样例:
3
1 1 2
1 2 2
1 1 2
输出样例:
YES
程序：
题目描述:
一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。
对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。
输入:
输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。
输入的第一行是n（0<n<100）。以下的n行每行包括n个整数，分别给出对应的单元里的整数（这n个整数之间用空格分开）。图4给出了输入样例对应的图形。
输出:
当可以画出满足题意的曲线的时候，输出“YES”；否则，输出“NO”。
输入样例:
3
1 1 2
1 2 2
1 1 2
输出样例:
YES
程序：
#include <stdio.h>
#include <math.h>
int orig, n, ns, a [102][102], bun;
int d[]= {1,0,-1,0,0,1,___(1)___};
void plimba(int x, int y) {
int i,xx, yy;
a[x][y]=-a[x][y] ;
if(abs(a[x-1][y] ) != orig&&( ___(2)___ != a[x-1][y]||abs (a[x][y-1] ) != orig)) ns++;
if(abs (a[x+1][y] ) != orig&& (a[x+1][y-1] !=a[x+1][y]||abs (a[x][y-1] ) !=orig)) ns++;
if(abs (a[x][y-1] )!=orig&&( ___(3)___ !=a[x][y-1] ||abs (a[x-1][y] ) !=orig)) ns++;
if(abs(a[x][y+1] ) !=orig&&(a[x-1][y+1]!=a[x][y+1]||abs(a[x-1][y]) !=orig)) ns++;
for(i=0; i<4 ; i++) {
xx=x+d[2*i]; yy=y+___(4)___;
if(xx>=1&&xx<=n&&yy>=1&&yy<=n&& ___(5)___ )plimba(xx,yy);
}
}
int main () {
int i,j;
bun=1;
scanf("%d",&n);
for (i=0; i<=n+1; i++)
for (j=0; j<=n+1; j++) a[i][j]=0;
a[0][0]=-1; a[n+1][0]=-1;
a[0][n+1]=-1; a[n+1][n+1]=-1;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++) scanf("%d",&a[i][j]);
for (i=1; i<=n ; i++)
for(j=1; j<=n; j++) {
if(a[i][j]>-1) {
ns=0; ___(6)___;
plimba (i,j);
if(ns%2==1) bun=0;
}
}
if (bun)printf("YES\n");else printf("NO\n");
return 0;
}
