斐波那契数列(I)

已知斐波那契数列 Fn=Fn−1+Fn−2(n>=3),F1=1,F2=1 用递归的方法求解该数列的第n项。

输入格式:

输入一个正整数n (1<=n<=40)。

输出格式:

输出一个数,数列的第n项。

输入样例

1
1

输出样例

1
3

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#define maxSize 40
using namespace std;

int Fib(int n){
if(n==1||n==2) return 1;
else{
return Fib(n-2)+Fib(n-1);
}
}
int main()
{
int n;
cin>>n;
cout<<Fib(n)<<endl;
return 0;
}


斐波那契数列(II)

已知已知斐波那契数列 Fn=Fn−1+Fn−2(n>=3),F1=1,F2=1 求解该数列的第n项,结果对998244353取模。

输入格式:

输入一个正整数n (1<=n<=40)。

输出格式:

输出一个数,数列的第n项。

输入样例

1
1

输出样例

1
3

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
#define N 998244353
int main(){
int n;
int f1=1,f2=1,ans=0;
int fn;
cin>>n;
if(n==1||n==2) ans=1;
else{
for(int i=3;i<=n;i++){
fn=(f1+f2)%N;
f2=f1;
f1=fn;
}
ans=fn;
}
cout<<ans;
return 0;
}

最大公约数和最小公倍数

本题要求两个给定正整数的最大公约数和最小公倍数。

输入格式:

输入在一行中给出两个正整数M和N(≤1000)。

输出格式:

在一行中顺序输出M和N的最大公约数和最小公倍数,两数字间以1空格分隔。

输入样例

1
511 292

输出样例

1
73 2044

代码示例

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
cout<<gcd(n,m)<<" "<<lcm(n,m)<<endl;
return 0;
}

打印选课学生名单

假设全校有最多40000名学生和最多2500门课程。现给出每个学生的选课清单,要求输出每门课的选课学生名单。

输入格式:

输入的第一行是两个正整数:N(≤40000),为全校学生总数;K(≤2500),为总课程数。此后N行,每行包括一个学生姓名(3个大写英文字母+1位数

字)、一个正整数C(≤20)代表该生所选的课程门数、随后是C个课程编号。简单起见,课程从1到K编号。

输出格式:

顺序输出课程1到K的选课学生名单。格式为:对每一门课,首先在一行中输出课程编号和选课学生总数(之间用空格分隔),之后在第二行按字典序输出学生

名单,每个学生名字占一行。

输入样例

1
2
3
4
5
6
7
8
9
10
11
10 5
ZOE1 2 4 5
ANN0 3 5 2 1
BOB5 5 3 4 2 1 5
JOE4 1 2
JAY9 4 1 2 5 4
FRA8 3 4 2 5
DON2 2 4 5
AMY7 1 5
KAT3 3 5 4 2
LOR6 4 2 4 1 5

输出样例

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
1 4
ANN0
BOB5
JAY9
LOR6
2 7
ANN0
BOB5
FRA8
JAY9
JOE4
KAT3
LOR6
3 1
BOB5
4 7
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1
5 9
AMY7
ANN0
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1

代码示例

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
#include <bits/stdc++.h>
using namespace std;
struct node{
char name[5];
}course[2510][40000];

int num[2510];
bool cmp(node a,node b){
return strcmp(a.name,b.name)<0;
}
int main(){
int n, k;
cin>>n>>k;
int i, j;
for(i = 0; i < n; i++) {
char name[5];
cin>>name;
int c;
cin>>c;
int id;
for(j = 0; j < c; j++) {
cin>>id;
strcpy(course[id][num[id]++].name, name);
}
}
for(i = 1; i <= k; i++) {
sort(course[i], course[i] + num[i], cmp);//字典序排序
}
for(i = 1; i <= k; i++) {
cout<<i<<" "<<num[i]<<endl;
for(j = 0; j < num[i]; j++) {
printf("%s\n", course[i][j].name);
//cout<<course[i][j].name<<endl;
}
}
return 0;
}

两个有序链表序列的交集

已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的交集新链表S3。

输入格式:

输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。。

输出格式:

在一行中输出两个输入序列的交集序列,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。

输入样例

1
2
1 2 5 -1
2 4 5 8 10 -1

输出样例

1
2 5

代码示例

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
#include <iostream>
#define maxSize 1000
using namespace std;
struct Node {
int data;
Node* next;
Node() :data(0),next(NULL){}
Node(int num) :data(num),next(NULL) {}
};
class LinkList {
public:
Node* first;
LinkList() {first = new Node(); }
void CreateList(int val);
void Insert(int val);
void show();
};
void LinkList::CreateList(int val) {
Node* newNode, * last=first;
int d;
while (cin >> d && d != val) {
if (first->next == NULL) {
newNode = new Node(d);
first->next = newNode;
last = newNode;
}
else {
newNode = new Node(d);
last->next = newNode;
last = newNode;
}
}
}
void LinkList::show() {
Node* cur = first;
while (cur->next != NULL) {
cur = cur->next;
if (cur->next == NULL)
cout << cur->data;
else
cout << cur->data << " ";
}
if (first->next == NULL) cout << "NULL" << endl;
}
void LinkList::Insert(int val) {
Node* newNode = new Node(val);
Node* cur = first;
while (cur->next != NULL) cur = cur->next;
cur->next = newNode;
}
void CompareListNode(LinkList s1, LinkList s2, LinkList s3) {
Node* a = s1.first->next, * b = s2.first->next;
while (a && b)
{
if ((a->data) < (b->data))
a = a->next;
else if ((a->data) > (b->data))
b = b->next;
else if ((a->data) == (b->data))
{
s3.Insert(a->data);
a = a->next;
b = b->next;
}
}
}
int main() {
LinkList s1, s2,s3;
s1.CreateList(-1);
s2.CreateList(-1);
CompareListNode(s1, s2, s3);
s3.show();
return 0;
}

人以群分

社交网络中我们给每个人定义了一个“活跃度”,现希望根据这个指标把人群分为两大类,即外向型(outgoing,即活跃度高的)和内向型(introverted,即活
跃度低的)。要求两类人群的规模尽可能接近,而他们的总活跃度差距尽可能拉开。

输入格式:

输入第一行给出一个正整数N(2≤N≤10^5)。随后一行给出N个正整数,分别是每个人的活跃度,其间以空格分隔。题目保证这些数字以及它们的和都不会超过2^31。

输出格式:

1
2
3
Outgoing #: N1
Introverted #: N2
Diff = N3
其中N1是外向型人的个数;N2是内向型人的个数;N3是两群人总活跃度之差的绝对值。

输入样例

1
2
10
23 8 10 99 46 2333 46 1 666 555

输出样例

1
2
3
Outgoing #: 5
Introverted #: 5
Diff = 3611

代码示例

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
#include <bits/stdc++.h>
#define maxSize 100000

using namespace std;
typedef long long ll;
int compare(const void* a, const void* b)
{
return (*(ll*)a - *(ll*)b);
}
int main() {
int n;ll og = 0, it = 0;
ll* a = new ll[maxSize];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
qsort(a,n,sizeof(ll),compare);
if (n%2) {
for (int i = 0; i < n; i++) {
if (i < n / 2) it += a[i];
else og += a[i];
}
cout << "Outgoing #: " << n/2+1 << endl;
cout << "Introverted #: " << n/2 << endl;
cout << "Diff = " << og - it << endl;
}
else {
for (int i = 0; i < n; i++) {
if (i < n / 2) it += a[i];
else og += a[i];
}
cout << "Outgoing #: " << n / 2 << endl;
cout << "Introverted #: " << n / 2 << endl;
cout << "Diff = " << og - it << endl;
}
return 0;
}

公路村村通

现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数N(≤1000)和候选道路数目M(≤3N);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两

个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出−1,表示需要建设更多公路。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例

1
12

代码示例


1
还在做...