全国提高组 CSP-S 初赛模拟试题 (9)
一、单项选择题
（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
11) 有以下程序段: const int N=1000, M = 10000; int h[N], tot, n, m;struct edge(double c; int nxt, v;} e[M << 1]; double d[N];其占用的静态空间大小约为( )。
12) 下列表达式中，不论变量p,q如何取值，恒为真的只有( )。 (1) ((!p)&&q)||(p&&q) (2) ((!p)&&q)&&(p||q) (3) (!p)||q)&&(p||q))||p||(!q) (4) (p&&(!q)&.&)||(((!p)||q)&&(p||q))
二、阅读程序
（程序输入不超过数组或字符串定义的范围;除特殊说明外，判断题1.5分，选择题3分，共计40分）
# include<algorithm>
# include<iostream>
using namespace std ;
const int MAXN = 1000;
int a[MAXN], c[MAXN];
int main() {
int n, x, y;
cin>> n>> x>> y;
int sum=(x^y)+((x&y)<<1);
n=n<<3^5&3|2;
for(int i=1; i<=n; ++i)
cin >> a[i];
int answer;
answer = c[1] = max(a[1], 0);
for (int i= 2; i<= n; ++i) {
c[i] = max(c[i-1] + a[i],a[i]);
if (c[i]<= 0)
c[i] = 0;
answer = max(answer, c[i]);
}
if (answer <= sum)
puts("Good.");
else
puts("It's too sad.");
return 0 ;
}# include <cmath>
# include <cstring>
# include <iostream>
const int MAXN =1000000;
int n;
int f1[MAXN], f2[MAXN],f3[MAXN];
int calc_f1(int x) {
int ans=1;
int maxNum = sqrt(x);
for (int i= 2; i<= maxNum; ++i)
if(x%i==0) {
ans=-ans;
x/=i;
if (x%i== 0)
return 0;
}
if(x!=1)
ans =-ans;
return ans;
}
int calc_f2(int x) {
return x;
}
void convolute( ) {
memset(f3, 0, sizeof(f3));
for (int i = 1; i<= n; ++i)
for (int j= 1; j<= n/i; ++j)
if(i*j<=n)
f3[i*j]= f3[i* i]+ f1[i]*f2[j];
}
int main() {
scanf("%d", &n);
for (int i= 1; i<= n; ++i)
f1[i] = calc_f1(i);
for (int i= 1; i<= n; ++i)
f2[i] - calc_f2(i);
convolute();
printf("% d\backslashn", f3[n]);
return 0;
}#include <iostream>
using namespace std;
const int maxn =10000000;
int n,size ;
int prime[maxn+5];
bool vis[maxn+5];
int main() {
cin >>n;
size = 0;
for (int i= 2; i<=n; ++i) {
if (!vis[i]) {
size = size + 1;
prime[size]= i;
}
for (int j=1; i*prime[j]<=n; ++j) {
vis[i * prime[j]]= 1;
if (i % prime[j]==0)
break ;
}
}
int sum = 0;
for (int i=1; i<=size; ++i)
sum=sum + prime[i];
cout<<sum<<endl;
return 0;
}三、完善程序
（单选题，每题3分，共计30分）
1.(背包问题1)有一个质量上限为m的背包和n个物品。物品分三类，第一类物品有取的数量限制，第二类物品只能取一个,第三类物品可以无限取。
第i个物品的类别为tp[i](tp[i]∈[1,2,3])质量为w[i]，价值为c[i]，如果tp[i]=1 ，还会有一个a[0]表示这种物品最多只能取a[i]个。求这个背包可以装下的最大价值。
M≤1000,n ≤100,w[i],c[i]≤1000,a[i]<10,1≤tp[i]≤3。
试补全程序。
第i个物品的类别为tp[i](tp[i]∈[1,2,3])质量为w[i]，价值为c[i]，如果tp[i]=1 ，还会有一个a[0]表示这种物品最多只能取a[i]个。求这个背包可以装下的最大价值。
M≤1000,n ≤100,w[i],c[i]≤1000,a[i]<10,1≤tp[i]≤3。
试补全程序。
# include <iostream>
using namespace std;
int n, m, ans;
int f[100],a[101],tp[101],w[101],c[101];
int main() {
cin>>m>>n;
for(int i= 1; i<=n; ++i) {
cin>> tp[i]>> w[i]>> c[i];
if(tp[i] == 1) cin>> a[i];
}
f[0]= 0;
for (int i= 1; i<= m; ++i)
f[i]=___(1)___;
for(int i= 1; i<=n; ++i) {
if(tp[i]==1) {
for (int j= 1; j<= a[i]; ++j)
for(int v= m; v>=w[i]; --v)
f[v] = max(f[v], ___(5)___ );
}
else if(tp[i]== ___(2)___) {
for(int v=m; v>= ___(3)___ ; --v)
f[v]=max(f[v], ___(5)___ );
}
else {
for( ___(4)___ )
f[v]=max(f[v], ___(5)___ ) ;
}
}
printf("%d", f[m]);
return 0;
}(背包问题2)有N(O<N≤50)个物品，第i个物品体积为v[i](0≤v[i]≤10^18)，价值为w[i](0≤w[i]≤10^17)。现有一个容量为V(0≤V≤10^18)的背包。你需要选择一些物品使
得体积之和不超过V且价值最大。求出最大价值及方案。如有多种方案，尽可能选择编号较大的方案(即尽量选第n个，仍有多组解选第n-1个，以此类推)。
提示:将物品按标号是否大于n/2分成两组，每组内枚举如何选择。再在两组间确定方案。
试补全程序。
得体积之和不超过V且价值最大。求出最大价值及方案。如有多种方案，尽可能选择编号较大的方案(即尽量选第n个，仍有多组解选第n-1个，以此类推)。
提示:将物品按标号是否大于n/2分成两组，每组内枚举如何选择。再在两组间确定方案。
试补全程序。
#include <iostream>
using namespace std;
const long long inf=___(1)___;
long long v[41];
long long w[41];
struct Item {
long long value, weight, choose;
} itm[2][1<<20];
bool cmp1(Item a, Item b) {
return a.value < b.value||(a.value == b.value && a.choose < b.choose);
}
bool cmp2(Item a, Item b) {
return a.value < b.value||(a. value == b.value && a.choose==b.choose);
}
int get_id(int n) {
for(int i=0; ; ++i)
if(!(n>>i)) return i-1;
}
void sort(Item item[], int L, int R) {
if(L>= R) return;
int x=rand()%(R-L+1)+L;
swap(item[L], item[x]);
int a=L+1,b= R;
while (a<b) {
while (a<b&& cmp1(item[a], item[L]))
++a;
while(a< b&& ___(2)___)
--b;
swap(item[a],item[b]);
}
while (b<= R&& item[b].value == item[L].value)
++b;
if (item[a].value < item[L].value)
swap(item[a],item[L]);
sort(item, L, a-1);
sort(item, b, R);
}
int solve(int L, int R, Item item[]) {
item[0].value=0;
item[0].choose = 0;
int len = ___(3)___;
for (int i=1; i <= len; ++i) {
int tmp= ___(4)___;
item[i].value = item[i - tmp].value + v[L + get_id(tmp)];
item[i].weight = item[i - tmp].weight + w[L + get_id(tmp)];
if (item[i].value > inf) item[i].value = inf;
item[i].choose = i;
}
sort(item, 0, len);
return len;
}
int main() {
int N;
long long V, ans = 0;
cin>>N>>V;
for (int i = 1; i<= N; ++i)
cin>> v[i] >> w[i];
int len1 = solve(1,N/2, itm[0]);
int len2 = solve(N/2 + 1, N, itm[1]);
for (int i= 1; i<= len2; ++i)
itm[1][i].value=max(itm[1][i].value, itm[1][i-1].value);
long long choose = 0;
for (int i= 0; i<= len1; ++i) {
while (len2 >= 0 && itm[0][i].value + itm[1][len2].value>V)
--len2;
if(len2>=0) {
long long new_value = itm[0][i].weight + itm[1][len2].weight;
long long new_choose = ___(5)___ ;
if (ans == new_value)
choose = max( choose, new_choose);
if (ans < new_value) {
ans = new_value ;
choose = new_choose ;
}
}
}
cout<<ans<<endl;
for (int i= 0; i< N; i++)
if (choose & (1LL<<i))
cout<<i+1<<' ';
cout << endl;
}
