全国提高组 CSP-S 初赛模拟试题 (6)
一、单项选择题
（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
15) 给定长为n (n≤1000)的字符串，每次可以将连续一段回文序列消去，消去后左右两边会 接到一起，求最少消去几次能消完整个序列(单个字符也算回文字符串)。设f(i,j)表示消去闭区间[i,j]内字符串所需要的最小次数，那么当1≤i≤j≤n时，在不考虑回文串的情况下，f(i,j)的动态规划方程中包含( )。
二、阅读程序
（程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题1.5分，选择题4分，共计40分）
# include <iostream>
# include <cstdio>
using namespace std;
int L, ans;
char a[2002][2002];
int cross(int x, int y) {
int length=1;
if(x<=1||x>=L)return 1;
for (int i=1;; i++) {
if(x-i<=0||x+i>=L+1) return length;
else if (a[x-i][y]!=a[x+i][y]) return length;
else length +=2;
}
}
int down(int x, int y) {
int length=1;
if(y<=1||y>=L) return 1;
for (int i=1;; i++) {
if(y-i<=0||y+i>=L+1)return length;
else if (a[x][y-i]!=a[x][y+i]) return length;
else length += 2;
}
}
int MAXN(int a, int b) {
if(a >= b) return a;
else return b;
}
int main() {
cin>>L;
for(int i=1; i<=L; i++)
for(int j=1; j<=L; j++)
cin>>a[i][j];
int x, y;
cin>>x>>y;
ans=MAXN(cross(x,y),down(x,y));
cout<<ans;
return 0;
}#include <cstdio>
#include <cmath>
const int N = 1e9;
int isnp[50005],p[50005],pcnt;
inline void getPrime(const int n = sqrt(N)) {
isnp[0]= isnp[1]=1;
for (register int i=2; i<=n; ++i) {
if (!isnp[i]) p[pcnt++]=i;
for (register int j=0; i*p[j]<=n && j<pcnt; ++j) {
isnp[i*p[j]]=1;
if (!(i% p[j])) break ;
}
}
}
int main() {
getPrime(); int n;
while (scanf(" %d", &n) && n) {
int _sqrt = sqrt(n),ans= n;
for (register int j = 0; p[j]<=_sqrt && j<pcnt; ++j) {
if (n % p[j]==0) {
while (n % p[j]==0)n/=p[j];
ans = 1ll * ans *(p[j]-1)/ p[j];
}
}
if (n!=1) ans = 1ll* ans * (n-1)/n;
printf("%d\n", ans);
}
return 0;
}#include <iostream>
using namespace std;
const int inf =0x3f3f3f3,N=4e5+5;
struct edge {
int to,nt ;
}E[N<<1];
int cnt, n,m,rt,MX;
int H[N],sz[N],mxs[N];
void add_edge(int u, int v) {
E[++cnt]=(edge) {v,H[u]};
H[u]=cnt;
}
void dfs(int u, int fa) {
sz[u]=1;
for (int e=H[u]; e; e=E[e].nt) {
int v=E[e].to;
if (v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u] =max(mxs[u],n-sz[u]);
if (mxs[u]<mxs[rt])rt=u;
if (mxs[u]==mxs[rt] &&u<rt)rt=u;
}
int main() {
cin>>n,
rt =cnt= 0;
for (int i=1; i<=n; i++) {
int u,v;
cin>>u>>v;
add_edge(u,v);
add_edge(v,u);
}
mxs[0] = inf ;
dfs(1,0);
cout<<rt<<' '<<mxs[rt]<<'\n';
return 0;
}三、完善程序
（单选题，每题2.5分，共计30分）
(翻硬币)
一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们整体一起翻面后放回原处(如101111前5个翻面结果是000101)，再取3枚，取4枚……直至m枚。然后再从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中每一枚又是正面朝上为止。例如，m为1时，翻两次即可；m 为4时﹐翻11次；m为9时，翻80 次。
【输入】
仅有的一个数字是这摞硬币的枚数m(0 <m < 1000),
【输出】
为了使这握硬币中的每一枚都是正面朝上所必须翻的次数。
【输入样例】
30
【输出样例】
899
一摞硬币共有m枚，每一枚都是正面朝上。取下最上面的一枚硬币，将它翻面后放回原处。然后取下最上面的2枚硬币，将他们整体一起翻面后放回原处(如101111前5个翻面结果是000101)，再取3枚，取4枚……直至m枚。然后再从这摞硬币最上面的一枚开始，重复刚才的做法。这样一直做下去，直到这摞硬币中每一枚又是正面朝上为止。例如，m为1时，翻两次即可；m 为4时﹐翻11次；m为9时，翻80 次。
【输入】
仅有的一个数字是这摞硬币的枚数m(0 <m < 1000),
【输出】
为了使这握硬币中的每一枚都是正面朝上所必须翻的次数。
【输入样例】
30
【输出样例】
899
#include <iostream>
using namespace std;
int solve(int m);
int main() {
freopen("demo.out","w", stdout);
int m;
do {
scanf("%d",&m);
if(m>0 && m<1000)
printf("%d\n",___(1)___);
} while (m>0 && m< 1000);
return 0;
}
int solve(int m) {
int i,t,s;//翻转的次数
int flag;
if(m==1)
s=___(2)___;
else {
d=2*m+1;
//确定硬币是经过偶数次翻转还是奇数次翻转
t= 2;
//表示一个COIN必须翻转偶数次，才能从正面继续翻到正面
i=1;//翻转的轮数，每轮为从1翻转到m
flag=0;//退出循环标志，翻转完成标志
do {
if(t==1) {
s=___(3)___;
flag = 1;
} else if(___(4)___) {
s=i*m-1;
flag=1;
} else {
t=___(5)___;
}
i=i+1;
} while(!flag);
}
return s;
}(FBZ串问题)
已知一个由0,1字符组成的长度为2^n的字符串。请按以下规则分解为FBZ串:
·若其中字符全为1，则称其为B串:
·若其中字符全为0，则称其为Z串;
·若不全为0，也不全为1,则称F串。
若此串为F串,则应将此串分解为2个长为2^(i-1)的子串。对分解后的子串，仍按以上规则继续分解直到全部为B串或为Z串为止。例如n=3时,给出0-1串为“10111001”
最后输出:FFFBZBFFBZFZB。给定一个0-1串，分解成FBZ串。
已知一个由0,1字符组成的长度为2^n的字符串。请按以下规则分解为FBZ串:
·若其中字符全为1，则称其为B串:
·若其中字符全为0，则称其为Z串;
·若不全为0，也不全为1,则称F串。
若此串为F串,则应将此串分解为2个长为2^(i-1)的子串。对分解后的子串，仍按以上规则继续分解直到全部为B串或为Z串为止。例如n=3时,给出0-1串为“10111001”
最后输出:FFFBZBFFBZFZB。给定一个0-1串，分解成FBZ串。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int n= 8;
char str1[2*n][n];
char str2[40]=" ";
int main() {
int s1,s2,x,s,t;
s1=s2=x= 0;
gets(str1[0]);
while(___(1)___) {
s=t=0;
for (int i = 0; i< n; i++) {
if (str1[s2][i]=='1')
s++;
if (str1[s2][i]=='0')
t++;
}
if(___(2)___)
str2[x++]='B';
else if(___(3)___)
str2[x++]='Z';
else {
str2[x++]='F';
int j=(s+t)>>1;
for (int k=n*2-2; k>=___(4)___; k--)
for (int i=0; i<n; i++)
str1[k+2][i]=str1[k][i];
s1 += 2;
for (int i=0; i<j; i++) {
str1[s2+1][i]=str1[s2][i];
str1[s2+2][i]=___(5)___;
}
for (int i=___(6)___; ___(7)___; i++) {
str1[s2+1][i]=' ';
str1[s2+2][i]=' ';
}
}
s2++;
}
puts(str2);
return 0;
}
