大学的网站设计,重庆慕尚网站建设,网站建设公司的岗位职责,简述网站建设的方法4.小花和小草正在沙滩上玩挖沙洞的游戏。他们划了一条长度为n米的线作为挖沙洞的参考线路#xff0c;小花和小草分别从两头开始沿着划好的线开始挖洞#xff0c;小花每隔a米挖一个洞#xff0c;小草每隔b米挖一个洞#xff0c;碰到已经挖过洞的就不需要再挖了。那么#x…4.小花和小草正在沙滩上玩挖沙洞的游戏。他们划了一条长度为n米的线作为挖沙洞的参考线路小花和小草分别从两头开始沿着划好的线开始挖洞小花每隔a米挖一个洞小草每隔b米挖一个洞碰到已经挖过洞的就不需要再挖了。那么你能帮小花和小草算算他们全部挖到头之后一共挖了多少个洞吗?(两头端点位置都要挖洞)
输入格式 第1行:一个正整数n,代表线路的长度。(3n10000) 第2行:用空格分隔的两个正整数,代表a和b的值。(1a,b50)
输出格式 输出1行1个整数表示最终挖出来的沙洞的个数。
输入输出样列 输入样例1 6 23 输出样例1 5 输入样例2 100 5 10 输出样例2 21
思路 如果kan-qb0k,q那么这个洞就重复了。计算两个人在路上应该挖的洞减去重复挖的洞。
AC代码
#includestdio.h
int main()
{int n;int a,b;scanf(%d,n);scanf(%d%d,a,b);int k0,m0;int countn/an/b2;for(k1;kn/a;k){for(m1;mn/b;m){if(a*kn-m*b){count--;}}}printf(%d\n,count);
} 给定线路长度n以及小花和小草挖洞的间隔a和b计算最终挖出来的沙洞的个数。
程序首先读取输入的n、a和b。然后初始化计数器count为n/an/b2表示最初能够挖到的洞的个数加2是因为两头的端点位置也要挖洞。
接下来是两重循环外层循环遍历从1到n/a的所有可能取值k内层循环遍历从1到n/b的所有可能取值m。对于每一组k和m的取值判断ak是否等于n-mb。如果相等说明这是一处已经挖过的洞count减1。
最后输出答案count。
该程序的时间复杂度为O(n/a*n/b)其中a和b为输入的整数。
网上代码
#includeiostream
using namespace std;
typedef long long ll;
int main()
{ll n,a,b;int cnt_a0;int cnt_b0;ll ans0;cinnab;cnt_an/a;cnt_bn/b;anscnt_acnt_b2;
if(a1||b1) coutn1endl;else for(int i0;icnt_a;i){for(int j0;jcnt_b;j){if(i*aj*bn){ans--;}else if(i*aj*bn){//怕超时剪枝break;}}}
coutansendl;
return 0;
}
这段代码是一个求解整数拆分问题的程序。给定一个整数n以及两个整数a和b要求将n拆分成若干个数相加的形式使得其中包含至少一个a和至少一个b计算不同的拆分方式总数。
程序首先读取输入的n、a和b然后初始化计数器cnt_a和cnt_b为0用于记录a和b在拆分中出现的次数。同时初始化答案ans为0用于记录不同的拆分方式总数。
程序接着计算cnt_a和cnt_b分别为n除以a和n除以b的商表示a和b在拆分中最多可以出现的次数。
然后答案ans加上cnt_a和cnt_b再加2表示拆分中至少包含一个a和一个b的情况。
接下来是一个双重循环外层循环遍历从0到cnt_a的所有可能取值i内层循环遍历从0到cnt_b的所有可能取值j。对于每一组i和j的取值判断iajb是否等于n。如果等于n则说明这是一种有效的拆分方式ans减1。如果iajb大于n则跳出内层循环进行下一组i和j的取值。
最后输出答案ans。
该程序的时间复杂度为O(n/a*n/b)其中a和b为输入的整数。
