27.卷2的答案

CSP-J离我们不远了，加加油啦！

1.堆排序最坏时间复杂度是？

解析：平时多多练习可知，最坏时间复杂度是O(n log n)。

2.哪条能将s中的数值保留一位，并将第二位四舍五入？

解析：经过试验可知，只有s=(int)(s*10+0.5)/10.0起效哦！要带进去算！否则逝世！！！

3.HTTP是什么？

解析：平时多多练习可知，他是协议对应应用层。

4.n=25，n&(n+1>>1)=?

解析：这里考察位运算，&的意思是与， >>1是往右移动一位，最终答案为9。

5.1,2,3,4,5,6,7，保证每一对相邻数字都互质，有几种？

解析：采用枚举法，每种方法列出来，找到规律，最后相乘为720种。

6.假设G是一张有n个点m条边的连通图，小明想将其变成一棵n个节点的树，必须删去几条边才能将其变成这样的一棵树？

解析：图最开始有m条边，变成n个节点的树以后是n-1条边。需要删除m-(n-1)=m-n+1条边。

7.程序题

#include <bits/stdc++.h>
using namespace std;
unsigned int ksm(unsigned int x,unsigned int y)
{unsigned int ans=1;while(y){if(y&1){ans=ans*x;}y>>=1;x=x*x;}return ans;
}
int main()
{int x,y;cin>>x>>y;cout<<(int)(ksm(x,y))<<'\n';return 0;
}
//本题简单的考察了一下快速幂函数，但是这个函数有个BUG：中间运算会超过int的范围。

时间复杂度是O(log x)。   错误

解析：快速幂与y有关。

空间复杂度是O(1)。   正确

解析：只用了普通变量，O(1)没问题。

如果进入ksm函数，则程序第10行代码最少执行1次。   错误

解析：当y=0的时候，这段代码不会执行，因此最小0次。

若输入数据为5 3，则输出为？    125

解析：直接模拟一个快速幂。

8.程序题

#include <bits/stdc++.h>
using namespace std;
int mwm(int x)
{int ans=0;if(x==1) return 1;for(int i=2;i*i<=x;i++){if(x%i==0){;}else{continue;}ans+=mwm(i)+mwm(x/i);}return ans+x+1;
}
int main()
{int x;cin>>x;cout<<mwm(x)<<'\n';return 0;
}
//本题是简单数论套了一个DFS。

若输入18，则程序输出为？    58

解析：考虑到f(18)=1+18+f(2)+f(3)+f(6)+f(9),f(9)=1+9+f(3)+f(3)，f(6)=1+6+f(2)+f(3)。

在数据范围内，有多少个mwm(x)=x+1?    8

解析：变相询问1-20有多少个质数。

9.程序题

#include <cstdio>
typedef long long LL;
const int M=1e3+5;
int n;
LL b[M],ans;
int main()
{scanf("%d",&n);if(((1+n)*n/2)&1) puts("0");else{for(int i=0;i<(1<<(n/2));++i){int cur=0;for(int j=0;(i>>j)>0;++j){if((i>>j)&1) cur+=(j+1);b[cur]++;}}for(int i=0;i<(1<<(n-n/2));++i){int cur=0;for(int j=0;(i>>j)>0;++j){if((i>>j)&1) cur+=j+n/2+1;if((1+n)*n/4>=cur){ans+=b[(1+n)*n/4-cur];}}}printf("%lld\n",ans/2);}return 0;
}
//给一个1到n的数字集合，询问将其分为合相同的两个子集合的方案数（每个元素都在一个子集
//合）。这里用一个状压加折半搜索。

此题目时间复杂度为O(2的n次方)。    错误

解析：不对，这里是折半，复杂度是O(n2的n分之2)。

输入5以内的整数，则输出的和是？   2

解析：只有3 4有值且都为1，即输出2。

10.程序题

//这里考察模拟，第一是大小写互换，第二是自然数倒转
#include <bits/stdc++.h>
using namespace std;
int n;
string s[1001];
int main()
{while(cin>>s[++n]);n--; //我错了的地方（现在改好了）for(int i=n;i>=1;i--){for(int j=0;j<(int)s[i].size();j++){if(s[i][j]>='a'&&s[i][j]<='z'){s[i][j]-='a'-'A';}else if(s[i][j]>='A'&&s[i][j]<='Z'){s[i][j]-='A'-'a';}}if(s[i][0]>='0'&&s[i][0]<='9'){for(int j=(int)s[i].size()-1;j>=0;j--){cout<<s[i][j];}}else{cout<<s[i];}if(i!=1) cout<<" ";}return 0;
}

 错误1：阅读题目知道最后一个回车不管，因此这里多输出了。

11.程序题

//按时间排序后，记录当前空调能达到温度的上界与下界，只要判断顾客来的时候温度要求是否符合条件就。
#include <cstdio>
#include <algorithm>
#define N 105
struct node
{int t,l,r;
}a[N];
inline bool cmp(const node &x,const node &y)
{return x.t<y.t;
}
//using namespace std;
int main()
{int T;scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i){scanf("%d%d%d",&a[i].t,&a[i].l,&a[i].r);std::sort(a+1,a+n+1,cmp);int l=m,r=m;int fail=0;for(int i=1;i<=n;++i){l-=a[i].t-a[i-1].t,r+=a[i].t-a[i-1].t;//我错了的地方（现在改好了）if(l>a[i].r||r<a[i].l){fail=1;//我错了的地方（现在改好了）break;}l=std::max(l,a[i].l);//我错了的地方（现在改好了）r=std::min(r,a[i].r);//我错了的地方（现在改好了）}if(fail){puts("NO");}else{puts("YES");}}}return 0;
}