投稿
  1. 首页
  2. C

PAT

code • 2022-4-26 • C • 阅读 83

PAT ,第1张

1051 Pop Sequence (25 分) 
#include
using namespace std;
const int N = 1e5+10;
int n, m, k;
int a[N], b[N];

int main()
{
	cin >> m >> n >> k;
	for (int i = 1;i <= n;i ++) a[i] = i;
	while (k --) {
		stack <int> stk;
		for (int i = 1;i <= n;i ++) cin >> b[i];
		
		for (int i = 1, j = 1;i <= n;i ++) {
			stk.push (a[i]);
			if (stk.size () > m) break;
			while (stk.size() && j <= n && stk.top () == b[j]) j ++, stk.pop ();
		}
		
		if (stk.size()) puts ("NO");
		else puts ("YES");
	}
	
	return 0;
}
1052 Linked List Sorting (25 分) 
#include
#define PII pair<int, int>
#define val first
#define add second
using namespace std;
const int N = 1e5+10, M = 1e7+10;

PII node[N];
vector <PII> v;

int n, head, add, key, nxt;
int a[M], st[M];

int main()
{
	cin >> n >> head;
	
	for (int i = 0;i < n;i ++) {
		cin >> add >> key >> nxt;
		node[i] = {key, add};
		a[add] = nxt;
	}	
	
	int p = head;
	while (p != -1) {
		st[p] = 1;
		p = a[p];
	}
	
	sort (node, node+n);
	
	for (int i = 0;i < n;i ++)
		if (st[node[i].add]) 
			v.push_back ({node[i].val, node[i].add});
	
	if (v.size()) {
		cout << v.size() << ' ';
		printf ("%05d\n", v[0].add);
		for (int i = 0;i < v.size()-1;i ++)
			printf ("%05d %d %05d\n", v[i].add, v[i].val, v[i+1].add);
		printf ("%05d %d -1\n", v[v.size()-1].add, v[v.size()-1].val);
	} else {
		cout << 0 << ' ' << -1 << endl; // 一个测试点 
	}
	
	return 0;
}
1053 Path of Equal Weight (30 分) 
#include
using namespace std;
const int N = 1e5+10;

int n, m, k, x, y, num;
vector <vector <int> > v;
vector <int> tv;
int h[N], e[N<<2], ne[N<<2], idx, w[N], st[N];

void add (int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs (int x, int sum) {
	
	if (sum >= k) {
		if (sum == k && !st[x]) v.push_back (tv); // 必须是叶子节点 
		return ;
	}
	
	for (int i = h[x];~i;i = ne[i]) {
		int j = e[i];
		tv.push_back (w[j]);
		dfs (j, sum + w[j]);
		tv.pop_back ();
	}
}

int main()
{
	memset (h, -1, sizeof h);
	
	cin >> n >> m >> k;
	
	for (int i = 0;i < n;i ++) cin >> w[i];
	
	while (m --) {
		cin >> x >> num;
		st[x] = 1;
		for (int i = 0;i < num;i ++) {
			cin >> y;
			add (x, y);
		}
	}
	
	tv.push_back (w[0]);
	dfs (0, w[0]);
	
	sort (v.begin(), v.end());
	
	for (int i = v.size()-1, flag = 0;i >= 0;i --, flag = 0, cout << endl)
		for (int j = 0;j < v[i].size();j ++) {
			if (flag) cout << ' ';
			flag = 1;
			cout << v[i][j];
		}
	return 0;
}
1054 The Dominant Color (20 分) 
#include
using namespace std;

vector <int> v;
int n, m, x;
map<int, int> cnt;

int main()
{
	cin >> n >> m;
	for (int i = 0;i < n;i ++)
		for (int j = 0;j < m;j ++) {
			cin >> x;
			if (!cnt[x]) v.push_back (x);
			cnt[x] ++;
		}
		
	for (int i = 0;i < v.size();i ++) {
		if (cnt[v[i]] > n * m / 2) return cout << v[i] << endl, 0;
	}
	
	return 0;
}
1055 The World’s Richest (25 分)

我是以年龄为索引保存的，每次询问都遍历范围内的年龄，将信息加入一个新的vector中进行排序，最坏时间复杂度 O ( K N l o g N ) O(KNlogN) O(KNlogN)，这样第三个测试点超时；

直接按照题目要求对全部的人进行排序，每次询问遍历全部的人，满足年龄范围且个数不超过要输出的个数，就输出，因为我们排序的第一个优先级是价值，所以先遇到的一定是满足题目要求的顺序的。如此可以保证AC。时间复杂度为 O ( K N ) O(KN) O(KN)。

#include
using namespace std;
const int maxn = 1e5+10;
struct node
{
	int age,val;
	string name;
}s[maxn];
bool cmp(node a,node b){
	if(a.val != b.val)
		return a.val > b.val;
	else if(a.age != b.age)
		return a.age < b.age;
	return a.name < b.name;
}
int main()
{
	ios::sync_with_stdio(false);
	int n, m, k ;
	cin>>n>>k;
	for(int i = 0 ; i < n; i ++)
		cin>> s[i].name >> s[i].age >> s[i].val;
	sort(s, s + n ,cmp);
	for(int i = 1; i <= k ; i++)
	{
		int m, amin, amax;
		cin >> m >> amin >> amax;
		cout<<"Case #"<< i << ":"<<endl;
		int cnt = 0;
		for(int j = 0 ; j < n; j++)
		{
			if(s[j].age >= amin && s[j].age <= amax){
				cout<<s[j].name << " " << s[j].age <<" "<<s[j].val<<endl;
				cnt ++;
			}
			if(cnt == m)
				break;
		}
		if(cnt == 0)
			cout<<"None"<<endl;
	}
    return 0;
}
1056 Mice and Rice (25 分)

题解链接

1057 Stack (30 分) 
#include
using namespace std;

int n;
string op;
stack <int> stk;
vector <int> order;

int main()
{
	cin >> n;
	while (n --) {
		cin >> op;
		if (stk.size() && op.back () == 'p') { // Pop
			order.erase (lower_bound (order.begin(), order.end(), stk.top()));
			cout << stk.top () << endl;
			stk.pop ();
		} else if (stk.size() && op.back () == 'n') { // PeekMedian
			cout << order[(order.size() - 1) / 2] << endl;
		} else if (op.back () == 'h') { // Push
			int x;
			cin >> x;
			stk.push (x);
			order.insert (lower_bound (order.begin(), order.end(), x), x);
		} else cout << "Invalid" << endl;
	}	

	return 0;
}
1058 A+B in Hogwarts (20 分) 
#include
using namespace std;
// 29 个 Knuts  <=> 1 个 Sickle
// 17 个 Sickle <=> 1 个 Galleon 

int main()
{
	int g1, g2, s1, s2, k1, k2;
	scanf ("%d.%d.%d", &g1, &s1, &k1);
	scanf ("%d.%d.%d", &g2, &s2, &k2);
	int k = k1+k2;
	int s = (s1+s2) + k/29;
	int g = (g1+g2+s/17);
	printf ("%d.%d.%d\n", g, s%17, k%29);

	return 0;
}
1059 Prime Factors (25 分)

坑点：输入为1的时候要输出“1=1”
分解质因数模板，注意最后if(n>1)的判断

#include
using namespace std;
typedef long long LL;
vector <pair <LL, int> > ans;
LL n;

int main()
{
	cin >> n;
	cout << n << '=';
	if (n == 1) return cout << 1 << endl, 0; // 测试点2
	for (int i = 2;i <= n/i;i ++) {
		if (n % i == 0) {
			int cnt = 0;
			while (n % i == 0) {
				n /= i;
				cnt ++;
			}
			ans.push_back ({i, cnt});
		}
	}
	if (n > 1) ans.push_back ({n, 1});
	
	for (int i = 0, flag = 0;i < ans.size();i ++) {
		if (flag) cout << '*';
		flag = 1;
		cout << ans[i].first;
		if (ans[i].second != 1) cout << '^' << ans[i].second;
	}

	return 0;
}
1060 Are They Equal (25 分)

坑点：

  1. 指数为负数不用加括号
  2. 存在前导零的情况（00100.0，000.01100等）
  3. 对于输入的值为0的情况（0.0，00.00等）结果应为0.0...0*10^0，小数部分n个0

测试点三和测试点六应该是测坑点2和坑点3。

比较难过的测试用例:
3 0.000 0
4 123.5678 123.5
5 0010.013 10.012
4 00100.000000012 100.000000013
4 0000.000000123 0.0000001230
3 0.0520 0.0521

#include
using namespace std;

int n;
string a, b;

string change (string s) {
	string sig = "";
	int exp, flag = 0;
	
	for (int i = 0;i < s.size();i ++)
		if (s[i] != '0' && s[i] != '.') {
			flag = 1;
			break;
		}
	
	if (!flag) {
		sig = "0." + string (n, '0');
		exp = 0;
	} else {
		int t = 0;
		while (t < s.size() && s[t] == '0') t ++;
		if (s[t] == '.') s = "0" + s.substr (t);
		else s = s.substr (t);
		int dot = min (s.size(), s.find ('.'));
		
		if (s[0] != '0') {
			for (int i = 0;i < s.size();i ++) {
				if (s[i] != '.') sig += s[i];
				if (sig.size() == n) break;
			}
			while (sig.size() != n) sig += "0";
			sig = "0." + sig;
			exp = dot;
		} else {
			int p = dot;
			while (p < s.size() && s[++p] == '0') ;
			sig = s.substr (p, n);
			while (sig.size() != n) sig += "0";
			sig = "0." + sig;
			exp = -(p-dot-1);
		}
	}
	return sig + "*10^" + to_string (exp);
}

int main()
{
	cin >> n;
	cin >> a >> b;
	
	string aa = change(a);
	string bb = change(b);
	
	if (aa == bb) cout << "YES" << ' ' << aa << endl;
	else cout << "NO" << ' ' << aa << ' ' << bb << endl;
	
	return 0;
}
1061 Dating (20 分)

题目大意：前两个字符串对应位置相同的第一对字符（A ~ G）表示星期几，第二对（0 ~ 9 A ~ N）表示小时，后两个字符串对应位置相同的第一对字符（任意）所在位置（从0开始）表示几分钟。

#include
using namespace std;
// 1:A 2:B 3:C 4:D 5:E 6:F 7:G

map <char, string> week = {{'A', "MON"}, {'B', "TUE"}, {'C', "WED"}, {'D', "THU"}, {'E', "FRI"}, {'F', "SAT"}, {'G', "SUN"}};
string s1, s2, s3, s4;
int pos1, pos2, pos3;

int main()
{
	cin >> s1 >> s2 >> s3 >> s4;
	int i = 0;
	while (i < s1.size() && i < s2.size()) {
		if (s1[i] == s2[i] && s1[i] >= 'A' && s1[i] <= 'G') {
			pos1 = i;
			break; 
		}
		i ++;
	} 
	i ++;
	while (i < s1.size() && i < s2.size()) {
		if (s1[i] == s2[i] && (isdigit(s1[i]) || (s1[i] >= 'A' && s1[i] <= 'N'))) {
			pos2 = i;
			break;
		}
		i ++;
	}
	i = 0;
	while (i < s3.size() && i < s4.size()) {
		if (s3[i] == s4[i] && isalpha (s3[i])) {
			pos3 = i;
			break;
		}
		i ++;
	}
	cout << week[s1[pos1]] << ' ';
	printf ("%02d:%02d", isdigit (s1[pos2]) ? s1[pos2] - '0' : s1[pos2] - 'A' + 10, pos3);
	return 0;
}
1062 Talent and Virtue (25 分)

先给出三个数N（成员人数），L（及格线），H（优秀线）
给出一组成员信息，包括id，品德，才能，给这组成员排序。
当该成员品德和才能都不低于H，则该成员分在优秀组
当该成员品德不低于H，才能不低于L，则该成员分在良好组
当该成员品德和才能都低于H，但都不低于L且品德大于等于才能，则该成员分在中等组。
其他人中品德和才能不低于L，则分在及合组，品德和才能任一低于L则不参与排名。
排名时优先级 优秀组>良好组>中等组>及格组
同组中品德和才能总分越高，排名越前。总分相同，品德分越高越前。品德分相同id越小越靠前。

#include
using namespace std;

struct node {
	string id;
	int vg;
	int tg;
};

vector <node> type[4];
int n, L, H, ans;
 

bool cmp (node a, node b) {
	if (a.tg + a.vg != b.tg + b.vg) return a.tg + a.vg > b.tg + b.vg;
	if (a.vg != b.vg) return a.vg > b.vg;
	return a.id < b.id;
}

int main()
{
	cin >> n >> L >> H;
	for (int i = 0;i < n;i ++) {
		string id;
		int vg, tg;
		cin >> id >> vg >> tg;
		node p = {id, vg, tg};
		if (vg >= H && tg >= H) type[0].push_back (p);
		else if (vg >= H && tg < H && tg >= L) type[1].push_back (p);
		else if (vg >= L && tg >= L && vg >= tg) type[2].push_back (p);
		else if (vg >= L && tg >= L) type[3].push_back (p);
	}	
	
	for (int i = 0;i < 4;i ++)
		sort (type[i].begin (), type[i].end (), cmp),
		ans += type[i].size();
	
	cout << ans << endl;
	for (int i = 0;i < 4;i ++) 	
		for (int j = 0;j < type[i].size();j ++) 
			cout << type[i][j].id << ' ' << type[i][j].vg << ' ' << type[i][j].tg << endl;
	
	return 0;
}
1063 Set Similarity (25 分)

做过中文版的，超时过一次了，还是忘记了可以采用全部个数和减去相同个数的 *** 作。

#include
using namespace std;

set <int> s[100];
int n, m, k, x, a, b;

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		scanf ("%d", &m);
		while (m --) scanf ("%d", &x), s[i].insert (x);
	}	
	cin >> k;
	while (k --) {
		scanf ("%d%d", &a, &b);
		int nt, nc = 0;
		
		set<int>::iterator ita = s[a].begin();
		set<int>::iterator itb = s[b].begin();
		while (ita != s[a].end() && itb != s[b].end()) {
			if (*ita == *itb) ita ++, itb ++, nc ++;
			else if (*ita < *itb) ita ++;
			else itb ++;
		}
//		for (int i : s[a]) if (s[b].count(i)) nc ++; // 可以注释掉上面的迭代器代码，采用这句话，但是速度较慢 
		nt = s[a].size() + s[b].size() - nc; // 用全部个数减去重复出现的个数 
		
		printf ("%.1lf%\n", 100.0 * nc / nt);
	}
	return 0;
}
1064 Complete Binary Search Tree (30 分)

题解链接

1065 A+B and C (64bit) (20 分)

处理一下溢出，即负数相加得到正数、正数相加得到负数的情况

#include
using namespace std;
typedef long long LL;

LL a, b, c;

int main()
{
	int n, flag;
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		printf ("Case #%d: ", i);
		scanf ("%lld%lld%lld", &a, &b, &c); // 最后一个测试点 
		LL res = a + b;
		if (a < 0 && b < 0 && res >= 0) flag = 0;
		else if (a > 0 && b > 0 && res <= 0) flag = 1;
		else if (res > c) flag = 1;
		else flag = 0;
		if (flag) puts ("true");
		else puts ("false");
	}

	return 0;
}
1067 Sort with Swap(0, i) (25 分)

题解链接

1068 Find More Coins (30 分)

和“L3-001 凑零钱 (30 分)”一样。

#include
using namespace std;
int n,m,dp[105],w[10005],ans[10005],cnt;
bool ch[10005][105],flag;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i];
    sort(w+1,w+n+1,greater<int>());
    for(int i=1;i<=n;i++)
        for(int j=m;j>=w[i];j--)
            if(dp[j]<=dp[j-w[i]]+w[i])
            {
                dp[j]=dp[j-w[i]]+w[i];
                ch[i][j]=1;
            }
    if(dp[m]<m)return cout<<"No Solution",0;
    for(int i=n;i>=1&&m;i--)
    {
        if(ch[i][m])
        {
            if(flag)cout<<' ';
            cout<<w[i];
            m-=w[i];
            flag=1;
        }
    }
    return 0;
}
1069 The Black Hole of Numbers (20 分)

测试点5为输入为6174的情况，此时也要输出一行，所以要使用do-while

#include
using namespace std;

int num[4], n;

int main()
{
	cin >> n;
	int a = n / 1000;
	int b = n / 100 % 10;
	int c = n / 10 % 10;
	int d = n % 10;
	if (a == b && b == c && c == d) return printf ("%04d - %04d = 0000\n", n, n), 0;
	
	do {
		num[0] = n / 1000;
		num[1] = n / 100 % 10;
		num[2] = n / 10 % 10;
		num[3] = n % 10;
		sort (num, num+4);
		int res_max = 0, res_min = 0;
		for (int i = 0, base = 1;i < 4;i ++, base *= 10) res_max += base * num[i];
		for (int i = 3, base = 1;i >= 0;i --, base *= 10) res_min += base * num[i];
		n = res_max - res_min;
		printf ("%04d - %04d = %04d\n", res_max, res_min, n);
	} while (n != 6174);

	return 0;
}
1070 Mooncake (25 分)

中文题也有啊，叫“月饼”

#include
using namespace std;
const int N = 1e6+10;
int n;
double D, ans = 0;

struct node {
	double a, b, c;	
} yb[N];

bool cmp (node a, node b) {
	return a.c > b.c;
}

int main()
{
	cin >> n >> D;
	for (int i = 0;i < n;i ++) cin >> yb[i].a;
	for (int i = 0;i < n;i ++) cin >> yb[i].b, yb[i].c = 1.0 * yb[i].b / yb[i].a;
	
	sort (yb, yb+n, cmp);
	
	for (int i = 0;i < n && D;i ++) {
		if (D >= yb[i].a) {
			D -= yb[i].a;
			ans += yb[i].b;
		} else {
			ans += D * yb[i].c;
			break;
		}
	}
	
	printf ("%.2f\n", ans); // 原来可以直接这样控制保留小数 // 这我都忘记了

	return 0;
}
1071 Speech Patterns (25 分) 
#include
using namespace std;

string s, best_str, tmp;
map <string, int> cnt;

int main()
{
	getline (cin, s);
	transform (s.begin(), s.end(), s.begin(), ::tolower);
	
	for (int i = 0;i < s.size();i ++) {
		if (isalpha (s[i]) || isdigit (s[i])) tmp += s[i];
		else if (tmp.size()){
			cnt[tmp] ++;
			if (cnt[tmp] > cnt[best_str] || (cnt[tmp] == cnt[best_str] && tmp < best_str)) 
				best_str = tmp;
			tmp = "";
		}
	}
	if (tmp.size()) {
		cnt[tmp] ++;
		if (cnt[tmp] > cnt[best_str] || (cnt[tmp] == cnt[best_str] && tmp < best_str))
			best_str = tmp;
	}
	
	cout << best_str << ' ' << cnt[best_str] << endl;

	return 0;
}
1072 Gas Station (30 分)

中文题目“垃圾箱分布”

#include
#define PII pair <int, int>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 5e4 + 10;

int n, m, k, MAXDIST;
int best_pos, best_mindist = INF;
int maxmindist = -1; // 最大的最短距离 
int d[N];
int w[N], e[N], ne[N], h[N], idx;
double best_sum;

void add (int a, int b, int c) {
	w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void Dijkstra (int x) { // Dijkstra优先队列优化模板 
	
	memset (d, 0x3f, sizeof d);
	d[x] = 0;
	
	priority_queue <PII> q;
	q.push ({0, x});
	
	while (q.size()) {
		PII tt = q.top ();
		q.pop ();
		int t = tt.second;
		int dist = tt.first;
		
		if (dist != d[t]) continue;
		
		for (int i = h[t];~i;i = ne[i]) {
			int j = e[i];
			if (d[j] > d[t] + w[i]) {
				d[j] = d[t] + w[i];
				q.push ({d[j], j});
			}
		}
	}
	
}


int main()
{
	memset (h, -1, sizeof h);
	cin >> n >> m >> k >> MAXDIST;
	while (k --) {
		string a, b;
		int c;
		cin >> a >> b >> c;
		int aa, bb;
		if (a[0] == 'G') aa = atoi (a.substr(1).c_str()) + n; // 如果是垃圾箱就让编号从n+1开始 
		else aa = atoi (a.c_str());
		if (b[0] == 'G') bb = atoi (b.substr(1).c_str()) + n;
		else bb = atoi (b.c_str());
		add (aa, bb, c);
		add (bb, aa, c);
	}	
	
	for (int i = n+1;i <= n+m;i ++) {
		double sum = 0.0;
		int maxdist = -1, mindist = INF;
		Dijkstra (i);
// 		cout << "such as : ";
		for (int j = 1;j <= n;j ++) {
			sum += 1.0 * d[j];
			maxdist = max (maxdist, d[j]); // 以第i-n号垃圾桶为起点到其他各个居民的距离的最大值 
			mindist = min (mindist, d[j]); // 以第i-n号垃圾桶为起点到其他各个居民的距离的最小值 
// 			cout << d[j] <<  ' ';
		}
// 		cout << endl;
		// 最大距离必须小于要求  判断最小距离是否大于最大最短距离（若大于则更新）或者最小距离等于最大的最短距离，比较均值，也就是比较分子（距离和） 
		if (maxdist <= MAXDIST && (mindist > maxmindist || (mindist == maxmindist && sum < best_sum))) {
			// 保存最佳输出答案 
			best_pos = i;
			best_sum = sum;
			best_mindist = mindist;
			// 更新用于更新最佳输出答案的数据 
			maxmindist = mindist;
		}
	}
	if (!best_pos) puts ("No Solution");
	else printf ("G%d\n%.1lf %.1lf", best_pos-n, 1.0 * best_mindist, (int(best_sum / n * 10 + 0.5)) / 10.0);
	// 这个输出真离谱，样例都过不了却能AC 

	return 0;
}
1075 PAT Judge (25 分)

题解链接

1076 Forwards on Weibo (30 分) 
#include
using namespace std;
const int N = 1e5+10;

int n, k, L, x, st[N], ans;
vector<int> e[N];

void bfs (int x) {
	
	ans = 0;
	
	queue<int> q;
	st[x] = 1;
	q.push (x);
	
	while (q.size()) {
		int t = q.front ();
		q.pop ();
		ans ++;
		
		if (st[t] == L+1) continue;
		
		for (int i = 0;i < e[t].size();i ++) {
			int j = e[t][i];
			if (st[j]) continue;
			st[j] = st[t] + 1;
			q.push(j);
		}
	}
}

int main()
{
	cin >> n >> L;
	for (int i = 1;i <= n;i ++) {
		cin >> k;
		while (k --) {
			cin >> x;
			e[x].push_back (i);
		}
	}
	
	cin >> k;
	while (k --) {
		cin >> x;
		memset (st, 0, sizeof st);
		bfs (x);
		cout << ans-1 << endl;
	}

	return 0;
}
1077 Kuchiguse (20 分)

找最长公共后缀。

#include
using namespace std;
int n;
string s;
map <string, int> cnt;
int main()
{
	cin >> n;
	getchar();
	for (int i = 0;i < n;i ++) {
		getline (cin, s);
		for (int i = 0;i < s.size();i ++) {
			string tmp = s.substr(i);
			cnt[tmp] ++;
			if (cnt[tmp] == n) return cout << tmp << endl, 0;
		}
	}
	cout << "nai";	
	
	return 0;
}
1078 Hashing (25 分)

坑点：

  1. 1既不是合数也不是质数
  2. 二次探测只考虑正增量
  3. 二次探测每次变到的值的计算： ( x + s t e p ∗ s t e p ) % m s i z e (x+step*step)\%{msize} (x+step∗step)%msize，而不是 x % m s i z e + s t e p ∗ s t e p x\%msize+step*step x%msize+step∗step

探测次数：

#include
using namespace std;
const int N = 1e6+10;

int n, m;
int h[N], a[N], b[N];

int insert (int x) {
	int t, base = 0;
	for (int i = 0;i < m;i ++) {
		int t = (x + i * i) % m;
		if (!h[t]) return h[t] = x, t;
	}
	return -1;
}

bool isprime (int x) {
	if (x <= 1) return false;
	for (int i = 2;i <= x / i;i ++) 
		if (x % i == 0) return false;
	return true;
}

int main()
{
	cin >> m >> n;
	for (int i = m;;i ++) 
		if (isprime(i)) {
			m = i;
			break;
		}

	for (int i = 0;i < n;i ++) {
		cin >> a[i];
		b[i] = insert (a[i]);
	}

	for (int i = 0, flag = 0;i < n;i ++) {
		if (flag) cout << ' ';
		flag = 1;
		if (b[i] == -1) cout << '-';
		else cout << b[i];
	}

	return 0;
}
1079 Total Sales of Supply Chain (25 分) 
#include
using namespace std;
const int N = 1e5+10;
int n, num[N];
double p, r, ans, rate[N];
vector <int> e[N];

void bfs () {
	
	queue <int> q;
	q.push (0);
	rate[0] = p;
	
	while(q.size()) {
		int t = q.front ();
		q.pop ();
		
		if (e[t].size() == 0) ans += num[t] * rate[t];
		
		for (int i = 0;i < e[t].size();i ++) {
			int j = e[t][i];
			rate[j] = rate[t] * (0.01 * r + 1);
			q.push (j);
		}
	}
}

int main()
{
	cin >> n >> p >> r;
	for (int i = 0;i < n;i ++) {
		int k;
		cin >> k;
		if (k == 0) {
			cin >> num[i];
		} else {
			while (k --) {
				int x;
				cin >> x;
				e[i].push_back (x);
			}
		}
	}
	
	bfs ();
	
	printf ("%.1lf", ans);
	
	return 0;
}
1081 Rational Sum (20 分)

最后一个测试点的浮点数错误是因为溢出，需要每次进行加法后进行化简。

#include
using namespace std;
typedef long long LL;
LL n, a1, b1, a2, b2, ans;
int main()
{
	scanf ("%lld", &n);
	LL a1 = 0, b1 = 1;
	while (n --) {
		scanf ("%lld/%lld", &a2, &b2);
		a1 = (a1 * b2 + a2 * b1);
		b1 = b1 * b2;
		LL gcd = __gcd (a1, b1);
		a1 /= gcd;
		b1 /= gcd;
	}	
	
	ans = a1 / b1;
	LL gcd = __gcd (a1, b1);
	a1 /= gcd;
	b1 /= gcd;
	a1 %= b1;
	if (ans == 0) {
		if (a1) cout << a1 << '/' << b1 << endl;
		else cout << 0 << endl;
	} else {
		cout << ans;
		if (a1) cout << ' ' << a1 << '/' << b1 << endl;
	}

	return 0;
}
1083 List Grades (25 分) 
#include
using namespace std;

struct node {
	string name;
	string id;
	int score;
} stu[100000];

int n, l, r, flag;

bool cmp (node a, node b) {
	return a.score > b.score;
}

int main()
{
	cin >> n;
	for (int i = 0;i < n;i ++) 
		cin >> stu[i].name >> stu[i].id >> stu[i].score;
	sort (stu, stu + n, cmp);
	
	cin >> l >> r;
	for (int i = 0;i < n;i ++) {
		if (stu[i].score <= r && stu[i].score >= l) 
			flag = 1, cout << stu[i].name << ' ' << stu[i].id << endl;
	}

	if (!flag) puts ("NONE");
	return 0;
}
1085 Perfect Sequence (25 分)

最后一个测试点是LL

#include
using namespace std;
const int N = 1e6+10;
typedef long long LL;

LL n, p, ans;
LL a[N];

int main()
{
	cin >> n >> p;
	for (int i = 0;i < n;i ++) cin >> a[i];
	sort (a, a+n); 
	
	for (int i = 0;i < n;i ++) {
		if (n - i <= ans) break;
		LL len = upper_bound (a+i, a+n, a[i] * p) - a - i;
		ans = max (len, ans);
	}
	cout << ans << endl;

	return 0;
}
1086 Tree Traversals Again (25 分)

题解链接

欢迎分享，转载请注明来源：内存溢出

原文地址: https://www.outofmemory.cn/langs/727025.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-26
下一篇 2022-04-26

发表评论

登录后才能评论

评论列表（0条）

保存