P1572 计算分数
题目描述
Csh 被老妈关在家里做分数计算题，但显然他不愿意做这么多复杂的计算。况且在家门口还有 Xxq 在等着他去一起看电影。为了尽快地能去陪 Xxq 看电影，他把剩下的计算题交给了你，你能帮他解决问题吗？
输入格式
输入一行，为一个分数计算式。
计算式中只包含数字、+、-、/。其中/为分数线，分数线左边为分子，右边为分母。输入数据保证不会出现繁分数。如果输入计算式的第一项为正，不会有前缀+号；若为负，会有前缀-号。
所有整数均以分数形式出现。
输出格式
输出一行，为最后的计算结果（用为整数则用整数表示，否则用最简分数表示）。
保证答案内出现的所有数（如果答案是分数即为分子和分母）均在 32 位带符号整数的表示范围之内。
输入输出样例
输入 #1复制
2/1+1/3-1/4
输出 #1复制
25/12
说明/提示
数据范围及约定
对于所有测试点，输入计算式长度在 100 以内，分子、分母在 1000 以内。同时保证，直接从前往后直接计算分数的和或者差，然后立刻化简，这么做的中间结果不会超过 int 的范围。
注意输入的分数不一定是最简分数。
2024/2/13 添加 2 组 hack 数据。
实现代码：
#include <bits/stdc++.h> using namespace std; struct fs { long long fm,fz; }; fs yf(fs a) { long long m=__gcd(a.fm,a.fz); a.fm/=m; a.fz/=m; return a; } fs jia(fs x,fs y) { long long z=x.fm*y.fm; x.fz*=y.fm; y.fz*=x.fm; x.fm=z; y.fm=z; fs answer; answer.fz=x.fz+y.fz; answer.fm=x.fm; return yf(answer); } fs jian(fs x,fs y) { long long z=x.fm*y.fm; x.fz*=y.fm; y.fz*=x.fm; x.fm=z; y.fm=z; fs answer; answer.fz=x.fz-y.fz; answer.fm=x.fm; return yf(answer);//约分是个好习惯 } int main() { fs a,b; char ysf; scanf("%lld/%lld",&a.fz,&a.fm); a=yf(a); cin>>ysf; while (scanf("%lld/%lld",&b.fz,&b.fm)!=EOF) { if (ysf==EOF)break; else if (ysf=='+'){a=jia(a,b);} else if (ysf=='-'){a=jian(a,b);} cin>>ysf; } if (a.fm<0&&a.fz>0) { a.fm=abs(a.fm); a.fz-=a.fz*2; } if (a.fm==1)cout<<a.fz; else cout<<a.fz<<'/'<<a.fm; return 0; }P4057 [Code+#1] 晨跑
题目描述
“无体育，不清华”、“每天锻炼一小时，健康工作五十年，幸福生活一辈子”
在清华，体育运动绝对是同学们生活中不可或缺的一部分。为了响应学校的号召，模范好学生王队长决定坚持晨跑。不过由于种种原因，每天都早起去跑步不太现实，所以王队长决定每 a 天晨跑一次。换句话说，假如王队长某天早起去跑了步，之后他会休息 a−1 天，然后第 a 天继续去晨跑，并以此类推。
王队长的好朋友小钦和小针深受王队长坚持锻炼的鼓舞，并决定自己也要坚持晨跑。为了适宜自己的情况，小钦决定每 b 天早起跑步一次，而小针决定每 c 天早起跑步一次。
某天早晨，王队长、小钦和小针在早起跑步时相遇了，他们非常激动、相互鼓励，共同完成了一次完美的晨跑。为了表述方便，我们把三位同学相遇的这天记为第0天。假设三位同学每次晨跑的时间段和路线都相同，他们想知道，下一次三人在跑步时相遇是第几天。由于三位同学都不会算，所以希望由聪明的你来告诉他们答案。
输入格式
输入共一行，包含三个正整数 a,b,c，表示王队长每隔 a 天晨跑一次、小钦每隔 b 天晨跑一次且小针每隔 c 天晨跑一次。
输出格式
输出共一行，包含一个正整数 x，表示三位同学下次将在第 x 天相遇。
输入输出样例
输入 #1复制
2 3 5
输出 #1复制
30
输入 #2复制
3 4 6
输出 #2复制
12
输入 #3复制
10 100 1000
输出 #3复制
1000
说明/提示
来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/何昊天 命题/何昊天 验题/卢政荣
Git Repo：https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。
实现代码：
#include <bits/stdc++.h> using namespace std; int main() { long long a,b,c; scanf("%lld%lld%lld",&a,&b,&c); printf("%lld",a*b*c/__gcd(b,c)/__gcd(a,b*c/__gcd(b,c))); return 0; }P1414 又是毕业季II
题目背景
“叮铃铃铃”，随着高考最后一科结考铃声的敲响，三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍，憧憬着未来仍毋忘逝去的歌。一千多个日夜的欢笑和泪水，全凝聚在毕业晚会上，相信，这一定是一生最难忘的时刻！
题目描述
彩排了一次，老师不太满意。当然啦，取每位同学的号数来找最大公约数显然不太合理。于是老师给每位同学评了一个能力值。于是现在问题变为，从 n 个学生中挑出 k 个人使得他们的默契程度（即能力值的最大公约数）最大。但因为节目太多了，而且每个节目需要的人数又不知道。老师想要知道所有情况下能达到的最大默契程度是多少。这下子更麻烦了，还是交给你吧~
PS：一个数的最大公约数即本身。
输入格式
第一行一个正整数 n。
第二行为 n 个空格隔开的正整数，表示每个学生的能力值。
输出格式
总共 n 行，第 i 行为 k=i 情况下的最大默契程度。
输入输出样例
输入 #1复制
4 1 2 3 4
输出 #1复制
4 2 1 1
说明/提示
【题目来源】
lzn 原创
【数据范围】
记输入数据中能力值的最大值为 inf。
- 对于 20% 的数据，n≤5，inf≤103；
- 对于另 30% 的数据，n≤100，inf≤10；
- 对于 100% 的数据，n≤104，inf≤106。
实现代码：
#include<bits/stdc++.h> using namespace std; const int inf=1e6+1; int n,x,sum; int t[inf]; int ans[10005]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&x),t[x]++; for(int i=1;i<inf;i++){ sum=0; for(int j=1;i*j<inf;j++) sum+=t[i*j]; ans[sum]=i; } for(int i=n-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); }P2651 添加括号III
题目描述
现在给出一个表达式，形如 a1/a2/a3/.../an。
如果直接计算，就是一个个除过去，比如 1/2/1/4=1/8。
然而小A看到一个分数感觉很不舒服，希望通过添加一些括号使其变成一个整数。一种可行的办法是 (1/2)/(1/4)=2 。
现在给出这个表达式，求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。
输入格式
一个测试点中会有多个表达式。
第一行 t ，表示表达式数量。
对于每个表达式，第一行是 n，第二行 n 个数，第 i 个数表示 ai。
输出格式
输出 t 行。
对于每个表达式，如果可以通过添加括号改变顺序使其变成整数，那么输出Yes，否则输出No。
输入输出样例
输入 #1复制
2 4 1 2 1 4 5 6 5 7 9 12
输出 #1复制
Yes No
说明/提示
- 对于 40% 的数据，n≤16。
- 对于 70% 的数据，n≤100。
- 对于 100% 的数据， 2≤n≤10000，1≤t≤100，1≤ai≤231−1。
实现代码：
#include<bits/stdc++.h> using namespace std; int a[10001],t,n; int main() { cin>>t; for(int i=1;i<=t;i++) { cin>>n>>a[1]>>a[2]; a[2]/=__gcd(a[1],a[2]); for(int i=3;i<=n;i++) { cin>>a[i]; a[2]/=__gcd(a[2],a[i]); } if(a[2]==1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
)
