---

title: 洛谷练习1(updating
date: 2025-02-25 13:57:56
tags: [c++]
categories: c++

---

P1011 [NOIP 1998 提高组] 车站

题目描述

火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第 2 站，在第 2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 n−1 站），都满足此规律。现给出的条件是：共有 n 个车站，始发站上车的人数为 a，最后一站下车的人数是 m（全部下车）。试问 x 站开出时车上的人数是多少？

输入格式

输入只有一行四个整数，分别表示始发站上车人数 $a$，车站数 $n$，终点站下车人数 $m$ 和所求的站点编号 $x$。

输出格式

输出一行一个整数表示答案：从 $x$ 站开出时车上的人数。

输入输出样例 #1

输入 #1

5 7 32 4

输出 #1

13

说明/提示

对于全部的测试点，保证 1≤a≤20，1≤x≤n≤20，1≤m≤2×104。

NOIP1998 提高组 第一题

解题过程

首先列一个表格，表示一下样例输出的过程

站数	1	2	3	4	5	6	7
上	a	?	a+?	a+2?	2a+3?	3a+5?	0
下	0	?	?	a+?	a+2?	2a+3?	4a+4?
总	a	a	2a	2a+?	3a+2?	4a+4?	0

分析一下不难发现上为斐波那契数列。总为斐波那契数列-a+?。然后就可以写代码穷举?（这道题计算量不大可以这么做。

#include<iostream>
using namespace std;
int main(){
	int a,n,m,x;
	cin>>a>>n>>m>>x;
	int f[n] = {0};
	f[0] = a,f[1] = a,f[2] = 2*a;
	for(int i = 0;i < 1000;i++){
		for(int p = 3;p < n;p++){
			f[p] = f[p-1]+f[p-2]-a+i;
		}
		if(f[n-2] == m){
			cout<<f[x-1];
			break;
		}
	}
	
	return 0;
}

不过没有考虑到n = 1，2，3的情况也过了。若还有就在前面加上if，如果n符合条件直接输出即可。

总结

这道题不是很难，属于普及-的题目。我对于斐波那契数列这道题直接采用了结论的办法来解出题。看了眼提交记录好像还是挺快挺短的。 15ms / 680.00KB / 290B C++14 (GCC 9)

P1996 约瑟夫问题

题目描述

$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 $n-1$ 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数，按顺序输出每个出圈人的编号。

输入输出样例 #1

输入 #1

10 3

输出 #1

3 6 9 2 7 1 8 5 10 4

说明/提示

1≤m,n≤100

解题过程

这是从算法竞赛这本书上面找到的推荐题。

上代码

#include<iostream>
using namespace std;
struct node{
	int index;
	node* next;
};
struct list{
	node* head = nullptr;
	void thelist(int n,int ti){
		node* pre = nullptr;
		node* first = new node{n,head};
		head = first;
		for(int i = n-1;i > 0;i--){
			node* newnode = new node{i,head};
			head = newnode;
		}
		first ->next = head;
		
		while(head != nullptr){
			node* tp = nullptr;
			for(int i = 0;i < ti-1;i++){
				pre = head;
				head = head->next;
			}
			cout<<head->index<<" ";
			tp = head;
			pre->next = head -> next;
			head = head -> next;
			if(head == pre)
			{
				cout<<head->index;
				delete tp;
				return;
			}
		}
	}
};
int main(){
	list a;
	int n = 0,t1 = 0;
	cin>>n>>t1;
	a.thelist(n,t1);
}

创建链表然后对链表的熟练使用。