摘要
在这里给大家提供9道题的题解，都是比较容易想到的题(其他题也不会啊)，希望有需要的人能够从中得到一些启发。可能有些会存在一些小错误因为是我自己通过记忆来描述的，希望理解。
第一次算法期末考试
A 水二分查找
输入:多组输入、n、n个数(按顺序排好的)、q、m(q次查询，看n个数中是否存在与m相同的数)
输出:存在输出Yes，不存在输出No，对于每个q输出q行
分析
这n个数的数据范围应该是在106内的，所以可以很自然的想到直接用桶装即可解决，而不需要二分查找，具体二分查找这里就不给代码了，因为后面第二次的A题会给出的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<stdio.h>
#include<string.h>
int a[1000005],num[1000005];
int main(){
int n,q,m;
while(~scanf("%d",&n)){
memset(num,0,sizeof(num));
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
num[a[i]]=1;
}
scanf("%d",&q);
while(q--){
scanf("%d",&m);
if(num[m]) printf("Yes\n");
else printf("No\n");
}
}
}
|
B KMP
输入:多组输入、两个字符串s、t
输出:t在s中出现的所有位置，用空格隔开、输出t对应得next数组
分析
显然是直接套用KMP即可，因为要输出所有位置，所以需要把判断条件放在while循环内部，具体可以看代码就很清楚了。next数组则一样非常简单即可求出。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1000005
using namespace std;
int next[MAX];
char s[MAX],t[MAX];
void getnext(int next[],char *t){
int j=0,k=-1;
next[0]=-1;
int lent=strlen(t);
while(j<lent){
if(k==-1||t[j]==t[k]){
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
int KMP(char *s,char *t){
getnext(next,t);
int i=0,j=0;
int lens=strlen(s),lent=strlen(t);
while(i<lens){
while(j!=-1&&t[j]!=s[i]){
j=next[j];
}
i++;j++;
if(j==lent){
printf("%d\n",i-j+1);
}
}
return 0;
}
int main(){
while(~scanf("%s%s",s,t)){
memset(next,0,sizeof(next));
KMP(s,t);
int lent=strlen(t);
for(int i=1;i<=lent;i++){
printf("%d ",next[i]);
}
printf("\n");
}
}
|
C 线段
这道题具体的输入输出不太记得了，大致意思应该是输入n条线段的左右坐标(在数轴上)，然后判断最多有多少条线段满足不和别的线段相交并输出最多的数量，并且端点重合可以认为不相交。
分析
因为有助教给的提示，这道题就很简单了，就是对这些线段的右端点进行排序，然后通过贪心来从左到右遍历即可。
代码
可能输入输出有些问题，大家能明白大体就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<stdio.h>
#include<stdlib.h>
#define MAX 100005
struct node{
int l,r;
}a[MAX];
int cmp(void const *a,void const *b){
struct node c,d;
c=*(struct node*)a;
d=*(struct node*)b;
if(c.r!=d.r) return c.r-d.r;
else return c.l-d.l;
}
int main(){
int n,ans=1;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&a[i].l,&a[i].r);
}
qsort(a,n,sizeof(struct node),cmp);
int k=0;
for(int i=1;i<n;i++){
if(a[i].l>=a[k].r){
ans++;
k=i;
}
}
printf("%d\n",ans);
}
|
D 字符串
输入:串t、q、q个串s。然后对t、s进行比较，规则如下
- s和t长度相同，若s和t完全相同，输出myw，否则输出friend
- s比t长度大，若t是s的子串，输出teacher，否则输出senior
- s比t长度小，若s是t的子串，输出child，否则输出dd
分析
很简单的KMP，直接套板子即可，注意长度相同的时候不需要用KMP，直接strcmp就可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100005
using namespace std;
int next[MAX];
char s[MAX],t[MAX];
void getnext(int next[],char *t){
int j=0,k=-1;
next[0]=-1;
int lent=strlen(t);
while(j<lent){
if(k==-1||t[j]==t[k]){
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
int KMP(char *s,char *t){
getnext(next,t);
int i=0,j=0;
int lens=strlen(s),lent=strlen(t);
while(i<lens&&j<lent){
if(j==-1||t[j]==s[i]){
i++;j++;
}
else j=next[j];
}
if(j>=lent) return 1;
else return 0;
}
int main(){
scanf("%s",t);
int q;
scanf("%d",&q);
while(q--){
scanf("%s",s);
int lens=strlen(s),lent=strlen(t);
if(lent==lens){
if(strcmp(s,t)==0) printf("myw\n");
else printf("friend\n");
}
else if(lens>lent){
memset(next,0,sizeof(next));
if(KMP(s,t)==1) printf("teacher\n");
else printf("senior\n");
}
else{
memset(next,0,sizeof(next));
if(KMP(t,s)==1) printf("child\n");
else printf("dd\n");
}
}
}
|
G 圆
这道题考试中因为时间问题没能做出来，所以代码的正确性也不确定，有错误希望大家指出来。
输入:圆心坐标、半径以及两个点的坐标
输出:两点最近且不穿过圆的距离
分析
首先肯定是两点连线不与圆相交就直接算两点距离，这个怎么判断呢，也不难，圆心到直线的距离与半径比较即可，但是这个距离怎么算比较方便呢，可以通过叉积先算出这两点与圆心围成的三角形面积再除以两点的距离来算得，这样比较好写。然后如果两点连线与圆相交的话，这样怎么算最近距离呢，很容易可以想到是和切线相关，即两点分别对圆作切线然后取两距离较近的切点，两切点之间的弧长加上这两个切点到其原来两个点的距离之和即为所要求的距离了。即下图的线段AA’加上线段BB’加上弧A’B’即可。
然后是算AA’和BB’的问题了，很显然直接用勾股定理还是很容易算出来的，即AO和BO都很容易得到，用勾股定理就能得到AA’和BB’了。最后就是算弧A’B’的问题了，想算弧，显然先算角，即算图中对应得θ角，我的想法是先通过余弦定理算出α角然后知道角AOA’的余弦值，通过数学库的acos即可得到AOA’角，然后同理对于BOB’角，然后用α角减去这两个角就得到了θ角，然后通过周长和θ角求得弧长。
代码
这里就给出一些函数，具体代码就不给了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<stdlib.h>
#include<math.h>
const double PI = 2.0*asin(1.0);
struct point{
double x,y;
};
double dis(point p1,point p2){
return ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double area(point p1,point p2,point p3){
return fabs(xmult(p1,p2,p3))/2;
}
double alpha(point p1,point p2,point p0){
return acos((dis(p1,p0)+dis(p2,p0)-dis(p1,p2))/
(2*sqrt(dis(p1,p0))*sqrt(dis(p2,p0))));
}
bool isx(point p1,point p2,point p0,double r){
return ((2*area(p1,p2,p0))/sqrt(dis(p1,p2)))>r;
}
|
第二次算法期末考试
A 真二分查找
输入输出和上文的A大致一样，这里就不再赘述
分析
由于a[i]数据范围到了109，所以没法投机取巧用桶装了，老老实实写二分，由于这次还要输出第一次出现的位置，因此找到一个位置后还应该向前排查是否存在相同的。其他还是比较好写了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int a[100005]={};
int main(){
int n,m,q;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&q);
while(q--){
scanf("%d",&m);
int l=0,r=n-1,mid,ans=-1;
while(l<=r){
mid=(l+r)/2;
if(m==a[mid]){
ans=mid;
int tmp=mid;
if(a[tmp-1]==m){
do{
tmp--;
}while(a[tmp]==m);
ans=tmp+1;
}
break;
}
else if(m>a[mid]) l=mid+1;
else r=mid-1;
}
if(ans!=-1) printf("Yes %d\n",ans+1);
else printf("No\n");
}
}
|
B
题目名字忘了，这道题很简单，就是一个优先队列的问题。代码也不给了真的很简单。需要注意的就是优先队列默认是从大到小的，这里需要让它从小到大，即用greater对应得那个初始化定义即可。
1
2
3
| #include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q;
|
C 三角形
输入:n、n个数、m、l、r(m次查询)
输出:每次查询是否存在可以构成三角形的三个数，存在输出Yes，否则输出No
分析
虽然到最后也没能看懂助教的提示，只混了0.5分，但是后来一想还是觉得自己很脑残。。。
不说废话了，首先肯定暴力是很好想到的，即对[l,r]区间进行排序然后遍历找是否存在i使得a[i]+a[i+1]>a[i+2]即可，存在就break输出Yes，遍历完都没找到就输出No，但是这样明显也会超时没因为排序复杂度是O(nlogn)，那助教给的提示有什么用呢，显然对于斐波拉契数列，a[i]+a[i+1]是等于a[i+2]的，即是三角形存在的最差情况，即这个数列永远不可能存在三个数组成三角形，但是这个数列在i>50后会爆int，由于我们的数据是在int范围内的，所以这个数列在i>50后是肯定存在三个数能组成三角形的，因为a[50]+a[51]肯定比任何其他int内的数都大，所以肯定存在了。斐波拉契这个最坏情况在i>50后都一定存在三个数能组成三角形了，那对于一个普通的序列，那就更是这样了，所以对于所有r-l>=50的查询我们就直接认为它一定存在三个数能组成三角形了，<50的情况则用暴力即可，时间复杂度也不可能会超了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
int a[100005],tmp[100005];
int main(){
int n,m,l,r;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
tmp[i]=a[i];
}
scanf("%d",&m);
while(m--){
int flag=0;
scanf("%d%d",&l,&r);
if((r-l)>=50) printf("Yes\n");
else{
std::sort(tmp+l,tmp+r+1);
for(int i=l;i<=r-2;i++){
if(tmp[i]+tmp[i+1]>tmp[i+2]){
printf("Yes\n");
flag=1;
break;
}
}
if(!flag) printf("No\n");
for(int i=l;i<=r;i++) tmp[i]=a[i];
}
}
}
|
E k进制a*b
输入:t组数据，k、a、b
输出:每组数据输出k进制的a*b的结果
分析
一看数据是105，肯定不是普通的乘法模拟了，直接就是FFT，套板子即可，k进制的问题就直接在最后还原的时候处理即可，很简单。不过y1s1，板子真的要敲很久。。。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define N 1000005
const double pi=3.1415926535;
char s1[N>>1],s2[N>>1];
double rea[N],ina[N],reb[N],inb[N];
int ans[N>>1];
void Swap(double *x,double *y){
double t=*x;
*x=*y;
*y=t;
}
int Rev(int x,int len){
int ans=0;
int i;
for(i=0;i<len;i++){
ans<<=1;
ans|=(x&1);
x>>=1;
}return ans;
}
void FFT(double *reA,double *inA,int n,bool flag){
int s;
double lgn=log((double)n)/log((double)2);
int i;
for(i=0;i<n;i++){
int j=Rev(i,lgn);
if(j>i){
Swap(&reA[i],&reA[j]);
Swap(&inA[i],&inA[j]);
}
}
for(s=1;s<=lgn;s++){
int m=(1<<s);
double reWm=cos(2*pi/m),inWm=sin(2*pi/m);
if(flag) inWm=-inWm;
int k;
for(k=0;k<n;k+=m){
double reW=1.0,inW=0.0;
int j;
for(j=0;j<m/2;j++){
int tag=k+j+m/2;
double reT=reW*reA[tag]-inW*inA[tag];
double inT=reW*inA[tag]+inW*reA[tag];
double reU=reA[k+j],inU=inA[k+j];
reA[k+j]=reU+reT;
inA[k+j]=inU+inT;
reA[tag]=reU-reT;
inA[tag]=inU-inT;
double rew_t=reW*reWm-inW*inWm;
double inw_t=reW*inWm+inW*reWm;
reW=rew_t;
inW=inw_t;
}
}
}
if(flag){
for(i=0;i<n;i++){
reA[i]/=n;
inA[i]/=n;
}
}
}
int main(){
int t,k;
scanf("%d",&t);
while(t--){
scanf("%d",&k);
scanf("%s%s",s1,s2);
memset(ans,0,sizeof(ans));
memset(rea,0,sizeof(rea));
memset(reb,0,sizeof(reb));
memset(ina,0,sizeof(ina));
memset(inb,0,sizeof(inb));
int i,lent,len=1,len1,len2;
len1=strlen(s1),len2=strlen(s2);
lent=(len1>len2?len1:len2);
while(len<lent) len<<=1;
len<<=1;
for(i=0;i<len;i++){
if(i<len1) rea[i]=(double)s1[len1-i-1]-'0';
if(i<len2) reb[i]=(double)s2[len2-i-1]-'0';
ina[i]=inb[i]=0.0;
}
FFT(rea,ina,len,0);
FFT(reb,inb,len,0);
for(i=0;i<len;i++){
double rec=rea[i]*reb[i]-ina[i]*inb[i];
double inc=rea[i]*inb[i]+ina[i]*reb[i];
rea[i]=rec;ina[i]=inc;
}
FFT(rea,ina,len,1);
for(i=0;i<len;i++){
ans[i]=(int)(rea[i]+0.4);
}
for(i=0;i<len;i++){
ans[i+1]+=ans[i]/k;
ans[i]%=k;
}
int len_ans=len1+len2+2;
while(ans[len_ans]==0&&len_ans>0) len_ans--;
for(i=len_ans;i>=0;i--){
printf("%d",ans[i]);
}
printf("\n");
}
}
|
上述所有如有谬误请一定指出，以便快速修改防止误导他人。