PAT1114 Family Property
并查集,麻烦的是需要把人的编号映射到0-n,同时还需要把0-n逆映射到原来的编号。
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 10010;
const double eps = 1e-6;
//1.2.3映射到原来多的数字
int map1[MAXN];
//数字映射到1.2.3.。。。
int map2[MAXN];
int cnt[MAXN], pre[MAXN], sets[MAXN], sum[MAXN];
int n, num = 1;
struct node {
int num, cnt;
double sets, sum;
node(int _num, int _cnt, double _sets, double _sum) : num(_num), cnt(_cnt), sets(_sets), sum(_sum) {};
bool operator<(node &a) const {
if (abs(sum - a.sum) > eps)
return sum > a.sum;
else
return num < a.num;
}
};
vector<node> ans;
int find(int a) {
return a == pre[a] ? a : pre[a] = find(pre[a]);
}
int main() {
int a, b, c, len, t, estate, sts;
cin >> n;
while (n--) {
vector<int> arr;
cin >> a >> b >> c >> len;
arr.push_back(a);
if (b != -1)
arr.push_back(b);
if (c != -1)
arr.push_back(c);
for (int i = 0; i < len; i++) {
cin >> a;
arr.push_back(a);
}
for (int i = 0; i < arr.size(); i++) {
//当前人之前没有遇到过,分配一个编号给他
if (!map2[arr[i]]) {
map2[arr[i]] = num;
map1[num] = arr[i];
cnt[num] = 1;
pre[num] = num;
++num;
}
if (!i)
continue;
int aa = find(map2[arr[i - 1]]);
int bb = find(map2[arr[i]]);
if (aa != bb) {
//编号小的为根
if (map1[aa] < map1[bb]) {
pre[bb] = aa;
cnt[aa] += cnt[bb];
sets[aa] += sets[bb];
sum[aa] += sum[bb];
} else {
pre[aa] = bb;
cnt[bb] += cnt[aa];
sets[bb] += sets[aa];
sum[bb] += sum[aa];
}
}
}
a = find(map2[arr[0]]);
cin >> sts >> estate;
sets[a] += sts;
sum[a] += estate;
}
for (int i = 1; i < num; i++)
if (i == find(i))
ans.push_back(node(map1[i], cnt[i], (double) sets[i] / cnt[i], (double) sum[i] / cnt[i]));
cout << ans.size() << endl;
sort(ans.begin(), ans.end());
for (node &a:ans)
printf("%04d %d %.3lf %.3lf\n", a.num, a.cnt, a.sets, a.sum);
return 0;
}
PAT1145 Hashing - Average Search Time
简单的哈希映射。
#include<iostream>
#define ac cin.tie(0);cin.sync_with_stdio(0);
using namespace std;
const int MAXN = 100010;
int arr[MAXN];
int N, M, K;
bool check(int N) {
for (int i = 2; i * i <= N; i++)
if (N % i == 0)
return false;
return true;
}
void insert(int a) {
int pos = a % N;
for (int i = 0; i < N; i++) {
if (arr[(pos + i * i) % N] == -1) {
arr[(pos + i * i) % N] = a;
return;
}
}
cout << a << " cannot be inserted." << endl;
}
int main() {
ac
int a;
for (int i = 0; i < MAXN; i++)
arr[i] = -1;
cin >> N >> M >> K;
while (!check(N))
++N;
while (M--) {
cin >> a;
insert(a);
}
int cnt = 0;
for (int j = 0; j < K; j++) {
cin >> a;
int pos = a % N, i = 0;
//该位置是空位置但是不是该元素,也需要退出循环,代表这个数字不在序列中
while (i < N && arr[(pos + i * i) % N] != a && arr[(pos + i * i) % N] != -1)
++i;
cnt += i + 1;
}
printf("%.1lf", (double) cnt / K);
return 0;
}
PAT1136 A Delayed Palindrome
简单的高精度运算。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
bool check(const string &a) {
for (int i = 0; i < a.length() / 2; i++)
if (a[i] != a[a.length() - 1 - i])
return false;
return true;
}
void add(string &a, string &b) {
int carry = 0;
for (int i = a.length() - 1; i >= 0; i--) {
a[i] += b[i] - '0' + carry;
carry = (a[i] - '0') / 10;
a[i] = (a[i] - '0') % 10 + '0';
}
if (carry)
a = '1' + a;
}
int main() {
string a, b;
cin >> a;
for (int i = 0; i < 10; i++) {
if (check(a)) {
cout << a << " is a palindromic number.";
return 0;
}
b = a;
reverse(b.begin(), b.end());
cout << a << " + " << b + " = ";
add(a, b);
cout << a << endl;
}
if (check(a))
cout << a << " is a palindromic number.";
else
cout << "Not found in 10 iterations.";
return 0;
}