[数据结构与算法]PTA L1 题目合集

PTA题集（天梯）

L1-001 ~L1-063

这位大佬没写完，我帮他写完吧~
有的题比较简单，所以为了快点写，码风比较丑~

补充一点 L1-001 ~L1-063 中不好做的，下面是我的做法（全部是c++）

L1-006 连续因子

整体思路就是找到一个因子后，顺着它向后+1枚举判断；
注意特判质数情况。

试除法求全部约数的模板
试除法判定质数模板题

#include<bits/stdc++.h>
using namespace std;

int n, mx, s;
int main()
{
	cin >> n;
	
	for (int i = 2;i <= n/i;i ++) {
		if (n % i == 0) {
			int x = n, j = i, cnt = 0;
			while (x % j == 0) { // 如果 i 是因子，直接尝试着向后面找，一个个判断是否能整除 
				x /= j;
				j ++;
				cnt ++;
			}
			if (cnt > mx) {
				mx = cnt;
				s = i;
			}
		}
	}
	
	if (mx == 0) { // 质数的情况 
		cout << 1 << endl << n << endl;
	}
	else {
		cout << mx << endl;
		for (int i = 0;i < mx-1;i ++) 
			cout << s+i << '*';
		cout << s + mx-1 << endl;
	}
	return 0;
}

L1-009 N个数求和

主要是这个题帮助我回忆起了 scanf 的特别用法。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int n;

int main()
{
	cin >> n;
	LL a1 = 0, b1 = 1, a2, b2;
	for (int i = 0;i < n;i ++) {
		scanf ("%lld/%lld", &a2, &b2); // 直接匹配除号，所以直接获取到分子和分母 
		a1 = a1*b2+a2*b1;
		b1 = b1*b2;
		LL gcd = __gcd (a1, b1);
		a1 /= gcd, b1 /= gcd;
	}	
	
	if (a1 % b1 == 0) {
		cout << a1/b1 << endl;
	} else if (a1 > b1) {
		cout << a1/b1 << ' ' << a1%b1 << '/' << b1 << endl;
	} else {
		cout << a1 << '/' << b1 << endl;
	}
	
	return 0;
}

L1-011 A-B

这个题帮助我回忆起了如何获取一行的操作；
如果前面输入了其他的数据，注意getchar()

// https://pintia.cn/problem-sets/994805046380707840/problems/994805130426171392 
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
map<char, bool> isex;
int main()
{
	getline (cin, s1); // 获取一行，不会因为空格回车和tab结束 
	getline (cin, s2);
	for (auto ch : s2) isex[ch] = 1;
	for (auto ch : s1)
		if (!isex[ch]) 
			cout << ch;
	cout << endl;
}

L1-023 输出GPLT

这道题思考数据结构用时比较长。

#include<bits/stdc++.h>
using namespace std;
string str;

string Map = "GPLT";
int cnt[4];

int main()
{
	cin >> str;
	transform (str.begin (), str.end (), str.begin (), ::toupper);
	for (auto ch : str) {
		if (ch == 'G') cnt[0] ++;
		else if (ch == 'P') cnt[1] ++;
		else if (ch == 'L') cnt[2] ++;
		else if (ch == 'T') cnt[3] ++;
	}
	while (bool(cnt[0]) + bool(cnt[1]) + bool(cnt[2]) + bool(cnt[3])) {
		for (int i = 0;i < 4;i ++) 
			if (cnt[i]) 
				cout << Map[i], 
				cnt[i] --;
	}
	return 0;
}

L1-025 正整数A+B

考查处理字符串的题型不是我的强项（我根本就没强项

#include<bits/stdc++.h>
using namespace std;
string a, b;

/*
本题是要求a和b为[1,1000]的整数，否则算不出来 
*/ 
bool check (string s) {
	for (int i = 0;i < s.size();i ++)
		if (!isdigit(s[i])) return false;
	int x = atoi (s.c_str());
	if (x < 1 || x > 1000) return false; 
	return true;
}

int sum (string a, string b) {
	int x = atoi (a.c_str()), y = atoi (b.c_str());
	return x + y;
}

int main()
{
	cin >> a;
	getchar ();
	getline (cin, b); // 可能存在多个空格 
	bool fa = check (a), fb = check (b);
	
	if (fa) cout << a;
	else cout << "?";
	
	cout << " + ";
	
	if (fb) cout << b;
	else cout << "?";
	
	cout << " = ";
	
	if (fa && fb) cout << sum (a, b);
	else cout << "?";
	
	return 0;
}

L1-043 阅览室 (20 分)

这个题我的代码不能AC，听说什么test2数据很奇怪，具体原因可以自己百度一下，我也不想特意处理那个Bug了。直接pass了。

#include<bits/stdc++.h>
using namespace std;

map<int, string> s;

int diff (string a, string b) {
    int res = 0;
    int a_h = atoi(a.substr (0,2).c_str());
    int a_m = atoi(a.substr (3,2).c_str());
    int b_h = atoi(b.substr (0,2).c_str());
    int b_m = atoi(b.substr (3,2).c_str());
//    cout << a_h << ' ' << a_m << ' ' << b_h << ' ' << b_m << endl;
    if (a_m <= b_m) res += b_m - a_m;
    else res += b_m - a_m + 60, b_h --;
    res += 60 * (b_h - a_h);
    return res;
}

int main()  {
    int n;
    cin >> n;
    int cnt = 0, res = 0, day = 0;
    while (day < n) {
        int id;
        char op;
        string time;
        cin >> id >> op >> time;
        if (id == 0) { // new day
            if (cnt == 0) cout << 0 << ' ' << 0 << endl;
            else cout << cnt << ' ' << round(1.0*res/cnt) << endl;
            res = 0;
            cnt = 0;
            day ++;
            s.clear ();
        }
        if (op == 'S') {
            s[id] = time;
        } else {
            if (s[id] != "") {
                cnt ++;
                res += diff (s[id], time);
            }
        }
    }    
}

L1-049 天梯赛座位分配 (20 分)

其实代码还可以更精简一点，但懒得改了，马上校里选拔了，多刷点题去。

#include<bits/stdc++.h>
using namespace std;
const int N = 110;

int id[N][N][15];

int mmx, mx, mx_pos, mmx_pos, n, m[N], idx;

int main()
{
	memset (id, -1, sizeof id);
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> m[i];
		if (m[i] > mx) mmx = mx, mmx_pos = mx_pos, mx = m[i], mx_pos = i; // mx为最大值，mmx为次最大值 
		else if (m[i] > mmx) mmx = m[i], mmx_pos = i;
	}
	
	// 内外层的遍历顺序不能搞错 
	for (int j = 1;j <= mmx;j ++) // 把每个学校的前 mmx 只队伍id都赋上值 
	for (int k = 1;k <= 10;k ++)
	for (int i = 1;i <= n;i ++)
	if (j > m[i]) continue; // 如果当前学校的队伍数少于j只，那么就不对id赋值了，没意义。 
	else id[i][j][k] = ++ idx;
	
	// 如果最后一个被赋值的队员在mx对应的队伍中，那么idx需要加2，如果最大idx在别的学校的队伍中，则+1即可。 
	if (id[mx_pos][mmx][10] == idx) idx += 2; // 只有一个队伍的话 idx=0，而且id初始都为0的话，会导致从idx=2开始赋值，所以需要将id初始化为-1 
	else idx ++;
	
	for (int j = mmx+1;j <= mx;j ++)
	for (int k = 1;k <= 10;k ++)
	id[mx_pos][j][k] = idx, idx += 2;
	
	for (int i = 1;i <= n;i ++) {
		cout << "#" << i << endl;
		for (int j = 1;j <= m[i];j ++) {
			for (int k = 1;k < 10;k ++)
				cout << id[i][j][k] << ' ';
			cout << id[i][j][10] << endl;
		}
	}
	return 0;
}

L1-059 敲笨钟

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	string s;
	cin >> n;
	getchar ();
	while (n --) {
		getline (cin, s);
		int d = s.find (',');
		int j = s.find ('.');
		string fir = s.substr (0, d);
		string sec = s.substr (d+1, j-d-1);
		// 一定要判前半句字符个数够不够3个，不够3个不能substr，会出错 
		if (fir.size() >= 3 && sec.size() >= 3 && fir.substr (fir.size()-3, 3) == "ong" && sec.substr (sec.size()-3, 3) == "ong") {
			int cnt = 0, idx = -1, k = sec.size ()-1;
			for (;;k --) {
				int newidx = sec.find (' ', k);
				if (newidx != string::npos && newidx != idx) {
					cnt ++;
					idx = newidx;
					if (cnt == 3) break;
				}
			}
			cout << fir << "," << sec.substr (0, k+1) << "qiao ben zhong." << endl;
		} else {
			cout << "Skipped" << endl;
		}
	}	

	return 0;
}

L1-064 估值一亿的AI核心代码 (20 分)

字符串处理，花了好长时间，直接血亏。

#include<bits/stdc++.h>
using namespace std;
string res = "";

bool ischar (char c) { // 判断是否为标点 
	if (!isdigit(c) && !isalpha(c)) return true;
	return false;
}

bool isindependent (int l, int r) {
	if ((l < 0 || ischar (res[l])) && (r > res.size() || ischar (res[r]))) return true; // 越界、或独立 
	return false;
}

bool judge1 (int p) {
	if (res[p] != 'I') return false; // 不是 I 
	int l = p-1, r = p+1;
	return isindependent (l, r);
}

bool judge2 (int p) {
	string ts = res.substr (p, 2);
	if (ts != "me") return false; // 不是 me 
	int l = p-1, r = p+2;
	return isindependent (l, r);
} 

bool judge3 (int p) {
	string ts = res.substr (p, 7);
	if (ts != "can you") return false; // 不是 I can 
	int l = p-1, r = p+7;
	return isindependent (l, r);
} 

bool judge4 (int p) {
	string ts = res.substr (p, 9);
	if (ts != "could you") return false; // 不是 I could 
	int l = p-1, r = p+9;
	return isindependent (l, r);
} 

int main()
{
	int n;
	cin >> n;
	getchar ();
	for (int i = 1;i <= n;i ++) {
		string s;
		res = "";
		getline (cin, s);
		// 输出原语句 
		cout << s << endl;
		
		// 去掉首尾的空格 
		int l = 0, r = s.size()-1;
		while (l < s.size() && s[l] == ' ') l ++;
		while (r >= 0 && s[r] == ' ') r --;
		s = s.substr (l, r-l+1);
		
//		cout << "s : " << s << endl; 
		
		// 中间空格最多连续出现1次，且保证符号前面没有空格 
		for (int i = 0;i < s.size();i ++) {
			int j = i;
			if (s[i] == ' ') {
				while (j < s.size() && s[j] == ' ') j ++;
				i = j-1;
				if (j < s.size() && ischar(s[j])) continue; // 如果s[j]（即连续空格后的第一个非空格字符）是符号，则不用添加这个空格 
			}
			res += s[i];
		}
		
//		cout << "res : " << res << endl;
		
		// 将除I之外的字符转为小写，且将？转为！ 
		for (int i = 0;i < res.size();i ++)
			if (isalpha(res[i]) && res[i] != 'I') res[i] = tolower (res[i]);
			else if (res[i] == '?') res[i] = '!';
		
		// 替换语句 
		string backup = "";
		for (int i = 0;i < res.size();i ++) {
			if (judge1 (i)) { // I
				backup += "you";
			} else if (judge2 (i)) { // me
				backup += "you";
				i ++;
			} else if (judge3 (i)) { // can you 长度为7，所以如果成立i后移6位，因为for还要i++ 
				backup += "I can";
				i += 6;
			} else if (judge4 (i)) { // could you 长度为9，所以如果成立i后移8位，因为for还要i++ 
				backup += "I could";
				i += 8;
			} else { // 没有匹配 
				backup += res[i];
			}
		} 
		
		// 输出  
		cout << "AI: " << backup << endl;
	}

	return 0;
}

L1-065 嫑废话上代码 (5 分)

#include<bits/stdc++.h>
using namespace std;

int main()
{
	cout << "Talk is cheap. Show me the code." << endl;
	return 0;
}

L1-066 猫是液体 (5 分)

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	cout << a * b * c << endl;	
	return 0;
}

L1-067 洛希极限 (10 分)

#include<bits/stdc++.h>
using namespace std;

int main()
{
	double luo, bi;
	int at;
	cin >> luo >> at >> bi;
	int t = int (luo * (at?1.26:2.455) * 100 + 0.5);
	printf ("%d.%02d ", t/100, t%100);
	if (1.0 * t / 100  > bi) cout << "T_T" << endl;
	else cout << "^_^" << endl;
	return 0;
}

L1-068 调和平均 (10 分)

#include<bits/stdc++.h>
using namespace std;
double ans, x;
int n;
int main()
{
	cin >> n;
	int m = n;
	while (m--) {
		cin >> x;
		ans += 1.0 / x;
	}
	ans /= n;
	ans = 1.0/ans;
	int f = 0;
	if (ans < 0) f = 1;
	ans = fabs (ans);
	int t = round (ans * 100);
	if (f) cout << '-';
	printf ("%d.%02d\n", t/100, t%100);
}

L1-069 胎压监测 (15 分)

#include<bits/stdc++.h>
using namespace std;
vector <int> v;
int a[10];
int main()
{
	int mn, th, mx = 0;
	for (int i = 1;i <= 4;i ++) cin >> a[i], mx = max (mx, a[i]);
	cin >> mn >> th;
	
	for (int i = 1;i <= 4;i ++) 
		if (abs (a[i] - mx) > th || a[i] < mn) 
			v.push_back (i);

	if (v.size() == 0) puts("Normal");
	else if (v.size() == 1) printf ("Warning: please check #%d!", v[0]);
	else puts("Warning: please check all the tires!");

	return 0;
}

L1-070 吃火锅 (15 分)

一开始理解错了，以为要输出“吃火锅”出现的全部次数，结果只用输出出现“吃火锅”的信息数。

#include<bits/stdc++.h>
using namespace std;

int cnt, sum, res;
string s;

int main()
{
	while (1) {
		getline (cin, s);
		if (s == ".") {
			cout << cnt << endl;
			if (sum == 0) cout << "-_-#" << endl; // 一次“吃火锅”都没出现
			else cout << res << ' ' << sum << endl;
			return 0;
		}
		cnt ++; // 信息序号
		int num = 0; // 该条信息中是否含有“吃火锅”
		if (s.find ("chi1 huo3 guo1") != string::npos) num ++;
		if (!res && num) res = cnt; // res记录第一次出现“吃火锅”的信息编号
		sum += num; // 总共多少条信息出现了“吃火锅”
	}	

	return 0;
}

L1-071 前世档案 (20 分)

二叉树

#include<bits/stdc++.h>
using namespace std;
int n, m;
int ques (int x, int op) {
	if (x < (1<<(n-1))) return op?(x<<1):(x<<1|1);
	int id = x - (1<<(n-1)) + 1;
	return op?(id<<1)-1:(id<<1);
}

int main()
{
	string s;
	cin >> n >> m;
	while (m --) {
		cin >> s;
		int ans = 1;
		for (int i = 0;i < n;i ++) 
			ans = ques (ans, s[i]=='y');
		cout << ans << endl;
	}

	return 0;
}

L1-072 刮刮彩票 (20 分)

题意太模糊了！

1. 输入彩票时的九个数，$1～9$表示的就是对应位置的数值，而如果某个位置的输入为$0$，需要自己推算哪个数没有出现过，这里就是没有出现过的那个数；
2. 将哪些位置的刮开看，并不影响我们最后计算哪一行、哪一列或者哪个对角线的值.

#include<bits/stdc++.h>
using namespace std;

int money[25] = {0, 0, 0, 0, 0, 0, 
				 10000, 36, 720, 360, 80, 252, 108, 72, 54, 180, 72, 180, 119, 36, 306, 1080, 144, 1800, 3600};

int a[4][4], flag[10];

int getsum (int x) {
	int res = 0;
	if (x <= 3) 
		for (int i = 1;i <= 3;i ++) res += a[x][i];
	else if (x <= 6)
		for (int i = 1;i <= 3;i ++) res += a[i][x-3];
	else if (x == 7)
		for (int i = 1;i <= 3;i ++) res += a[i][i];
	else 
		for (int i = 1;i <= 3;i ++) res += a[i][4-i];
	return res;	
}

int main()
{
	int lack = 0;
	for (int i = 1;i <= 3;i ++)
	for (int j = 1;j <= 3;j ++)
		cin >> a[i][j], 
		flag[a[i][j]] = 1;
	
	for (int i = 1;i <= 9;i ++) 
		if (!flag[i]) lack = i;
		
	for (int i = 1;i <= 3;i ++)
	for (int j = 1;j <= 3;j ++)
		if (!a[i][j]) a[i][j] = lack;
	
	int m = 3, r, c, n;
	while (m --) {
		cin >> r >> c;
		cout << a[r][c] << endl;
	}
	
	cin >> n;
	cout << money[getsum (n)];

	return 0;
}

L1-073 人与神 (5 分)

#include<bits/stdc++.h>
using namespace std;

int main()
{
	cout << "To iterate is human, to recurse divine.";
	return 0;
}

L1-074 两小时学完C语言 (5 分)

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n, k, m;
	cin >> n >> k >> m;
	cout << n - m * k << endl;
	return 0;
}

L1-075 强迫症 (10 分)

注意，时间、日期等的输出需要控制输出位数！

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int ym;
	cin >> ym;
	if (ym / 10000) printf ("%d-%02d", ym/100, ym%100); 
	else if (ym / 100 < 22) printf ("20%02d-%02d", ym/100, ym%100);
	else printf ("19%02d-%02d", ym/100, ym%100);
	return 0;
}

L1-076 降价提醒机器人 (10 分)

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	double m;
	cin >> n >> m;
	while (n --) {
		double p;
		cin >> p;
		if (p < m) 
		printf ("On Sale! %.1f\n", p);
	}
	return 0;
}

L1-077 大笨钟的心情 (15 分)

看到图片和题干我笑出了声……

#include<bits/stdc++.h>
using namespace std;

int a[30], n;

int main()
{
	for (int i = 0;i < 24;i ++) cin >> a[i];
	while (cin >> n && n >= 0 && n < 24) {
		cout << a[n] << ' ';
		if (a[n] > 50) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

L1-078 吉老师的回归 (15 分)

#include<bits/stdc++.h>
using namespace std;

string s;
vector <string> v;

int main()
{
	int n, m;
	cin >> n >> m;
	getchar (); // !
	for (int i = 1;i <= n;i ++) {
		getline(cin, s);
		if (s.find ("qiandao") != string::npos || s.find ("easy") != string::npos) continue; // find ("") != string::npos 用于判断是否找到（标准用法） 
		if (!m) {
			cout << s << endl;
			return 0;
		}
		m --;
	}
	cout << "Wo AK le" << endl;
	return 0;
}

L1-079 天梯赛的善良 (20 分)

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int cnt[N];
int n, x, mx = -1, mn = N;

int main()
{
	cin >> n;
	while (n -- ) {
		cin >> x;
		cnt[x] ++;
		mx = max(mx, x);
		mn = min(mn, x);
	}	
	
	cout << mn << ' ' << cnt[mn] << endl << mx << ' ' << cnt[mx] << endl;

	return 0;
}

L1-080 乘法口诀数列 (20 分)

#include<bits/stdc++.h>
using namespace std;
vector <int> v;
int main()
{
	int a1, a2, n;
	
	cin >> a1 >> a2 >> n;
	v.push_back (a1);
	v.push_back (a2);
	for (int i = 0;i < n;i ++) {
		a1 = v[i], a2 = v[i+1];
		int x = a1 * a2;
		if (x / 10) v.push_back (x / 10);
		v.push_back (x % 10);
		if (v.size () > n) break;
	}	
	cout << v[0];
	for (int i = 1;i < n;i ++)
		cout << ' ' << v[i];
		
	return 0;
}