PAT

目录

1063 Set Similarity (25分)

1060 Are They Equal (25分)

---

 

1063 Set Similarity (25分)

Given two sets of integers, the similarity of the sets is defined to be N​c​​/N​t​​×100%, where N​c​​ is the number of distinct common numbers shared by the two sets, and N​t​​ is the total number of distinct numbers in the two sets.

Your job is to calculate the similarity of any given pair of sets.

Input Specification:

Each input file contains one test case. Each case first gives a positive integer N (≤50) which is the total number of sets. Then N lines follow, each gives a set with a positive M (≤10^​4​​) and followed by M integers in the range [0,10^​9​​].

After the input of sets, a positive integer K (≤2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.

Output Specification:

For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.

Sample Input:

3 3 99 87 101 4 87 101 5 87 7 99 101 18 5 135 18 99 2 1 2 1 3

Sample Output:

50.0% 33.3%

样例解释：给定n个序列，K次查询

集合1和2；不同元素个数=4（99 87 101 5），集合1和2公共元素个数=2（87 101互不相同） 2/4=0.5

集合1和3；不同元素个数=6（99 87 101 18 5 135），集合1和2公共元素个数=2（99 101互不相同） 2/6=0.33

思路：在输入的时候就对每个集合去重（用unordered_set），

#include <cstdio> #include <vector> #include <set> #include<unordered_set> using namespace std; int main() { int n, m, k, temp, a, b; scanf("%d", &n); vector<unordered_set<int>> v(n); for(int i = 0; i < n; i++) { scanf("%d", &m); unordered_set<int> s; for(int j = 0; j < m; j++) { scanf("%d", &temp); s.insert(temp); } v[i] = s; } scanf("%d", &k); for(int i = 0; i < k; i++) { scanf("%d %d", &a, &b); int nc = 0, nt = v[b-1].size(); for(auto it = v[a-1].begin(); it != v[a-1].end(); it++) { if(v[b-1].find(*it) == v[b-1].end()) nt++; else nc++; } double ans = (double)nc / nt * 100; printf("%.1f%%\n", ans); } return 0; }

 

1060 Are They Equal (25分)

If a machine can save only 3 significant digits, the float numbers 12300 and 12358.9 are considered equal since they are both saved as 0.123×10^​5 ​​with simple chopping. Now given the number of significant digits on a machine and two float numbers, you are supposed to tell if they are treated equal in that machine.

Input Specification:

Each input file contains one test case which gives three numbers N, A and B, where N (<100) is the number of significant digits, and A and B are the two float numbers to be compared.

Each float number is non-negative, no greater than 10​100​​, and that its total digit number is less than 100.

Output Specification:

For each test case,

print in a line YES if the two numbers are treated equal, and then the number in the standard

form 0.d[1]...d[N]*10^k (d[1]>0 unless the number is 0); or NO if they are not treated equal,

and then the two numbers in their standard form. All the terms must be separated by a space, with no extra space at the end of a line.                Note:Simple chopping is assumed without rounding.

Sample Input 1:

3 12300 12358.9

Sample Output 1:

YES 0.123*10^5

Sample Input 2:

3 120 128

Sample Output 2:

NO 0.120*10^3 0.128*10^3

样例解释：两个数字（string）转化为科学计数法表示，保留n位小数，是否相等，（不用四舍五入）

思路：对于这两个数字，只需要求出他们的小数点后n位x，以及指数e，

对于 0.a1a2a3...am型数字，x为‘.’后第一个非0数字往后数n位的数字，（不够补0），e为第一个非0数字所在位置-1；

对于b1b2b3...bm.a1a2a3...ak型数字，x为第一个数字往后数n位的数字），e为m；

4 0000 0000.00 4 00123.5678 00001235 3 0.0520 0.0521 4 00000.000000123 0.000000123 4 000100.000012 100.000012 YES 0.1000*10^3

会有上面的一些情况，所以string要先去除所有的前导0，

然后，若第一位是'.'  则用solve1处理（0.a1a2型），否则用solve2处理（b1b2b3...bm.a1a2a3...ak型）

#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<vector> #include<set> #include<unordered_set> #include<map> #include<cmath> #define pb push_back using namespace std; int n; string a,b,ans; void solve1(string str,int &e){ //0.r1r2...rn*10^e 求 r1r2...rn e str.erase(str.begin()); ans.clear(); int len=str.length(),num=0; int i=0; while(str[i]=='0' && i<len)i++; //0.000123 if(i<len){ e=-i; }else{ e=0; } while(i<len && num<n){ ans+=str[i]; i++; num++; } while(num<n) {ans+='0';num++;} } void solve2(string str,int &e){ int len=str.length(),i=0,j=0,num=0; ans.clear(); while(j<len && str[j]!='.') j++; e=j; while(i<len && num<n){ if(str[i]=='.') i++; else{ ans+=str[i]; num++; i++; } } while(num<n) {ans+='0'; num++;} } int main(){ cin>>n>>a>>b; int e1=0,e2=0; while(a.length() > 0 && a[0] == '0'){// delete 前导零 a.erase(a.begin()); } while(b.length() > 0 && b[0] == '0'){ b.erase(b.begin()); } if(a[0]=='.'){ solve1(a,e1); }else{ solve2(a,e1); } string ansa=ans; if(b[0]=='.'){ solve1(b,e2); }else{ solve2(b,e2); } string ansb=ans; if(e1!=e2 || ansa!=ansb){ cout<<"NO "<<"0."<<ansa<<"*10^"<<e1<<' '<<"0."<<ansb<<"*10^"<<e2<<'\n'; }else{ cout<<"YES "<<"0."<<ansa<<"*10^"<<e1; } return 0; }