当前位置：首页 > news >正文

数据结构day13

news 来源：原创 2024/5/5 5:08:48

昨天写了一天transformer代码，就写了一题简单模拟题，今天打了球，也没补上，花费1.5h左右；

题目详情 - 1042 Shuffling Machine (pintia.cn)

思路：用两个数组储存，start装着一开始的0-53编号，然后把start中的值赋给end的转换位置后的地方，最后用end覆盖start，继续循环。

值得注意的是输出时数字和字符的下标需要清楚。

#include<iostream>
using namespace std;

int main() {
	string ss = "SHCDJ";//  /13, 0-12:S
	int k;
	cin >> k;
	const int n = 54;
	int arr[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];//记得-1取得下标
	}
	int start[n], end[n];
	for (int i = 0; i < n; i++) {//0-53,记得最后加1
		start[i] = i;
	}
	while (k--) {
		for (int i = 0; i < n; i++) {
			end[arr[i] - 1] = start[i];
		}
		for (int i = 0; i < n; i++) {
			start[i] = end[i];
		}
	}
	for (int i= 0; i < n; i++) {
		if (i != 0) {
			cout << ' ';
		}
		cout << ss[start[i] / 13] << start[i]%13 + 1;// /13和%13
	}
	return 0;
}

题目详情 - 1046 Shortest Distance (pintia.cn)

思路：空间换时间，一开始我写的是遍历left到right，取出值；但是容易发生运行超时，因为查询10^4，有10^5数据时，时间复杂度为10^9；所以需要用一个record数组储存每个点到第一个点的距离，不需要循环求值，复杂度就减少为10^4；

#include<iostream>
#pragma warning(disable:4996)
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	int* dis = new int[n+2];//从1开始
	int* record = new int[n + 2];
	record[1] = 0;//第一个点到第一个点距离为0，以第一个点为基准，record[i]=i到1的距离
	int sum=0, min;
	for (int i = 0; i < n; i++) {
		scanf("%d", &dis[i + 1]);
		sum += dis[i + 1];
		record[i + 2] = sum;
	}
	int m;
	scanf("%d", &m);
	int left, right;
	while (m--) {
		scanf("%d %d", &left, &right);
		min = 0;
		if (left > right) {
			int temp = left;
			left = right;
			right = temp;
		}
		min = record[right] - record[left];
		printf("%d\n", (min < sum - min ? min : sum - min));
	}
	return 0;
}

题目详情 - 1065 A+B and C (64bit) (pintia.cn)

思路：我想的是用字符串输入，使用字符串相加后再比较；书上直接用正负溢出表示，属实聪明；

值得一提的是，用long double可以直接用a+b>c解决，我查的是long double可以表示20位10进制数字，那么尾数部分肯定大于64位，但是sizeof(long double)却是8，属实没搞懂，待进一步学习；

还有如果直接用a+b而不是res=a+b也会出错，待进一步研究，我觉得是编译器的问题；

#include<iostream>
#pragma warning(disable:4996)
using namespace std;

int main() {
	int n;
	cin >> n;
	long long a, b, c;
	for (int i = 0; i < n; i++) {
		int flag = 1;
		scanf("%lld %lld %lld", &a, &b, &c);//%lld
		long long res = a + b;//不用res不行，why??
		if (a>0&&b>0&&res < 0) {//正溢出，a+b>2^63-1,c一定小于这个值
			flag = 1;
		}
		else if (a < 0 && b < 0 && res>=0) {
			flag = 0;//负溢出，两个负数相加大于等于0，c一定大于这个值
		}
		//其他情况不会溢出
		else if (res > c) {
			flag = 1;
		}
		else {
			flag = 0;
		}
		if (flag) {
			printf("Case #%d: true\n", i + 1);
		}
		else {
			printf("Case #%d: false\n", i + 1);
		}
	}
	return 0;
}

题目详情 - 1010 一元多项式求导 (pintia.cn)

思路：注意0 0；

#include<iostream>
#pragma warning(disable:4996)
using namespace std;

int main() {
	int k, e;
	int flag = 0;
    //注意只有一项时打印0 0；否则不打印0 0
    //使用flag操作是否打印0 0以及多的空格
	while (scanf("%d %d", &k, &e) != EOF) {
		if (!e) {
			continue;
		}
		if (flag) {
			cout << ' ';
		}
		cout << k * e << ' ' << e - 1;
		flag = 1;
	}
	if (!flag) {
		cout << "0 0";
	}
	return 0;
}

题目详情 - 1002 A+B for Polynomials (pintia.cn)

思路：数据结构第一周有这题的复杂版，用链表完成；这一题更简单，因为n最大1000，用数组完成，输入a数组，把b数组加进去，即可；

#include<iostream>
#pragma warning(disable:4996)
using namespace std;

int main() {
	double arr[1001] = { 0 };
	int n,m,e;
	double k;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> e >> k;
		arr[e] = k;
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> e >> k;
		arr[e] += k;
	}
	int ctn = 0;
	for (int i = 0; i < 1001; i++) {
		if (arr[i]!= 0) {
			++ctn;
		}
	}
	cout << ctn;
	for (int i = 1000; i >= 0; i--) {
		if (arr[i] != 0) {
			printf(" %d %.1f", i, arr[i]);
		}
	}
	return 0;
}

题目详情 - 1009 Product of Polynomials (pintia.cn)

思路：同多项式的乘法，简易版，用结构数组即可；

#include<iostream>
#pragma warning(disable:4996)
using namespace std;

struct node {
	double k;
	int e;
};
int main() {
	node arr[1001]={0}, res[2001] = {0};
	int n, m;
	cin >> n;
	int e;
	double k;
	for (int i = 0; i < n; i++) {
		cin >> e >> k;
		arr[i].e = e;//储存第一个数组的指数
		arr[i].k = k;
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> e >> k;
		for (int j = 0; j < n; j++) {
			res[e + arr[j].e].k += arr[j].k * k;//结果数组用下标表示指数
		}
	}
	int ctn = 0;
	for (int i = 0; i < 2001; i++) {
		if (res[i].k != 0) {
			ctn++;
		}
	}
	cout << ctn;
	for (int i = 2000; i >=0; i--) {
		if (res[i].k != 0) {
			printf(" %d %.1f", i, res[i].k);
		}
	}
	return 0;
}

题目详情 - 1041 考试座位号 (pintia.cn)

思路：我先想的是用结构数组储存num,k,s，然后通过arr[i].s==s查找；这样时间复杂度较高，可以但没必要；直接通过s作为数组下标进行储存和查找更省事；值得再次写；

#include<iostream>
#pragma warning(disable:4996)
using namespace std;

struct node {
	long long num;
	int k;//考试
};
int main() {
	node arr[1001];
	int n, k, s;
	long long num;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num >> s >> k;
		arr[s].num = num;
		arr[s].k = k;
	}
	int m, t;
	cin >> m;
	while (m--) {
		cin >> t;
		cout << arr[t].num << ' ' << arr[t].k << endl;
	}
	return 0;
}

题目详情 - 1004 成绩排名 (pintia.cn)

思路：太简单，看代码即可；

#include<iostream>
#include<vector>
#pragma warning(disable:4996)
using namespace std;

struct node {
	string name;
	string num;
	int score;
};
int main() {
	node max, min,temp;
	max.score = -1;
	min.score = 101;
	vector<node>v;
	int n;
	cin >> n;
	int score;
	string name, num;
	while (n--) {
		cin >> temp.name >> temp.num >> temp.score;
		v.push_back(temp);
		if (max.score < temp.score) {
			max.score = temp.score;
			max.name = temp.name;
			max.num = temp.num;
		}
		if (min.score > temp.score) {
			min.score = temp.score;
			min.name = temp.name;
			min.num = temp.num;
		}
	}
	cout << max.name << ' ' << max.num<<endl;
	cout << min.name << ' ' << min.num;
	return 0;
}

题目详情 - 1028 人口普查 (pintia.cn)

思路：用20140906与20130906整数进行比较会更便捷，这也是我上实践课写财务系统时候突然想到的，在这道简单题用上了，比答案简单不少；

#include<iostream>
#include<vector>
#pragma warning(disable:4996)
using namespace std;

int main() {
	int n;
	cin >> n;
	string name, max_name, min_name;
	int time,yr, month, dy;//<18140906,>20140906不符
	int max_time = 18140905, min_time = 20140907;
	int ctn = 0;
	while (n--) {
		cin >> name;
		scanf("%d/%d/%d", &yr, &month, &dy);
		time = yr * 10000 + month * 100 + dy;
		if (time > 20140906 || time < 18140906) {
			continue;
		}
		++ctn;
		if (max_time < time) {//max_time对应年纪最小
			max_time = time;
			min_name = name;
		}
		if (min_time > time) {
			min_time = time;
			max_name = name;
		}
	}
    if(!ctn){//对应测试点4；
        cout<<0;
    }else{
        cout << ctn << ' ' << max_name << ' ' << min_name;
    }
	return 0;
}