pat甲级1077，1081题解

1077 Kuchiguse （20 point(s)）

The Japanese language is notorious for its sentence ending particles. Personal preference of such particles can be considered as a reflection of the speaker's personality. Such a preference is called "Kuchiguse" and is often exaggerated artistically in Anime and Manga. For example, the artificial sentence ending particle "nyan~" is often used as a stereotype for characters with a cat-like personality:

• Itai nyan~ (It hurts, nyan~)

• Ninjin wa iyada nyan~ (I hate carrots, nyan~)

Now given a few lines spoken by the same character, can you find her Kuchiguse?

Input Specification:

Each input file contains one test case. For each case, the first line is an integer N (2≤N≤100). Following are N file lines of 0~256 (inclusive) characters in length, each representing a character's spoken line. The spoken lines are case sensitive.

Output Specification:

For each test case, print in one line the kuchiguse of the character, i.e., the longest common suffix of all N lines. If there is no such suffix, write nai.

Sample Input 1:

3
Itai nyan~
Ninjin wa iyadanyan~
uhhh nyan~

Sample Output 1:

nyan~

Sample Input 2:

3
Itai!
Ninjinnwaiyada T_T
T_T

Sample Output 2:

nai

题目大意：输出最长后缀码。

解题思路：反转一下判断最长前缀码，得出结果再反转一下就是结果了。用getline的话注意用getchar吃一下回车。

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<time.h>
#include<math.h>
#include<set>
#include<list>
#include<climits>
#include<queue>
#include<cstring>
#include<map>
#include<stack>
#include<string>
using namespace std;
string a[105];
int main() {
	int N;
	cin >> N;
	int minl = 99999;
	getchar();
	for (int i = 0; i < N; i++) {
		getline(cin, a[i]);
		int len = a[i].size();
		minl = min(len, minl);
		reverse(a[i].begin(), a[i].end());
	}
	int index = 0;
	for (int i = 0; i < minl; i++) {
		char c = a[0][i];
		bool flag = true;
		for (int j = 1; j < N; j++) {
			if (a[j][i] != c) {
				flag = false;
				break;
			}
		}
		if (flag == false) {
			break;
		}
		else {
			index++;
		}
	}
	if (index == 0)cout << "nai" << endl;
	else {
		string res = a[0].substr(0, index);
		reverse(res.begin(), res.end());
		cout << res << endl;
	}
	return 0;
}

1081 Rational Sum （20 point(s)）

Given N rational numbers in the form numerator/denominator, you are supposed to calculate their sum.

Input Specification:

Each input file contains one test case. Each case starts with a positive integer N (≤100), followed in the next line N rational numbers a1/b1 a2/b2 ... where all the numerators and denominators are in the range of long int. If there is a negative number, then the sign must appear in front of the numerator.

Output Specification:

For each test case, output the sum in the simplest form integer numerator/denominator where integer is the integer part of the sum, numerator <denominator, and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.

Sample Input 1:

5
2/5 4/15 1/30 -2/60 8/3

Sample Output 1:

3 1/3

Sample Input 2:

2
4/3 2/3

Sample Output 2:

2

Sample Input 3:

3
1/3 -1/6 1/8

Sample Output 3:

7/24

题目大意：给若干个分数，按标准格式输出这些分数的和。

解题思路：模拟一下分数就行了，注意输出的格式讨论即可

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<time.h>
#include<math.h>
#include<set>
#include<list>
#include<climits>
#include<queue>
#include<cstring>
#include<map>
#include<stack>
#include<string>
using namespace std;
struct ff{
	long long int num;
	long long int den;
};
ff a[105];
long long int gcd(long long int a, long long int b) {
	while (b != 0) {
		long long int t = b;
		b = a%b;
		a = t;
	}
	return a;
}
ff sum(ff a, ff b) {
	ff res;
	res.den = a.den*b.den;
	res.num = a.den*b.num + a.num*b.den;
	long long int g = gcd(res.num, res.den);
	res.den /= g;
	res.num /= g;
	return res;
}
int main() {
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld/%lld", &a[i].num, &a[i].den);
	}
	ff ress = a[0];
	
	//cout << ress.den << " " << ress.num << endl;
	for (int i = 1; i < N; i++) {
		ress = sum(ress,a[i]);
		//cout << ress.den << " " << ress.num << endl;
	}
	if (ress.num / ress.den >= 1) {
		if (ress.num%ress.den == 0) {
			printf("%lld\n",ress.num/ress.den);
		}
		else {
			printf("%lld %lld/%lld\n",ress.num/ress.den,ress.num%ress.den,ress.den);
		}
	}
	else {
		if (ress.num == 0)printf("0\n");
		else {
			printf("%lld/%lld\n", ress.num, ress.den);
		}
	}
	return 0;
}