斐波那契数列（I）

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

输入格式:

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

输出格式:

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

输入样例

输出样例

代码示例

#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项。

输入样例

输出样例

代码示例

#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空格分隔。

输入样例

511 292

输出样例

73 2044

代码示例

#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的选课学生名单。格式为：对每一门课，首先在一行中输出课程编号和选课学生总数（之间用空格分隔），之后在第二行按字典序输出学生

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

输入样例

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 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

代码示例

#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`

输出样例

2 5

代码示例

#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

代码示例

#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，表示需要建设更多公路。

输入样例

输出样例

代码示例

还在做...