东莞专业网站建设公司,南宁品牌网站建设公司,科技学堂,wordpress搜索引擎源码切面条-蓝桥杯-基础-CSDN算法技能树https://edu.csdn.net/skill/algorithm/algorithm-530255df51be437b967cbc4524fe66ea?category188
目录
切面条
大衍数列
门牌制作
方阵转置
微生物增殖
成绩统计
星系炸弹
判断闰年的依据:
特别数的和 *日志统计*#xff08;双指…切面条-蓝桥杯-基础-CSDN算法技能树https://edu.csdn.net/skill/algorithm/algorithm-530255df51be437b967cbc4524fe66ea?category188
目录
切面条
大衍数列
门牌制作
方阵转置
微生物增殖
成绩统计
星系炸弹
判断闰年的依据:
特别数的和 *日志统计*双指针
双指针 猜年龄
合并检测
排它平方数 *四平方和定理*
*大数乘法* 切面条
一根高筋拉面中间切一刀可以得到2根面条。
如果先对折1次中间切一刀可以得到3根面条。
如果连续对折2次中间切一刀可以得到5根面条。 那么连续对折10次中间切一刀会得到多少面条呢
想法
找规律
1、不对折对折零次从中间切一刀得到 2 根面条 2 2 2、对折一次从中间切一刀得到 3 根面条 3 2 2^0 3、对折两次从中间切一刀得到 5 根面条 5 2 2^0 2^1 4、对折三次从中间切一刀得到 9 根面条 9 2 2^0 2^1 2^2 … 11、对折十次从中间切一刀得到 2 2^0 2^1 2^2 ...... 2^9 根面条
#include stdio.hint cut_noodles(int times)
{int result 2, t 1;for (int i 0; i times; i){result t;t t * 2;}return result;
}int main()
{int result;int times 0;result cut_noodles(times);printf( 对折 %d 次从中间切一刀得到的面条数是: %d\n, times, result);return 0;
}
大衍数列
中国古代文献中曾记载过“大衍数列”, 主要用于解释中国传统文化中的太极衍生原理。
它的前几项是0、2、4、8、12、18、24、32、40、50 …
其规律是对偶数项是序号平方再除2奇数项是序号平方减1再除2。
以下的代码打印出了大衍数列的前 100 项。
请填补空白处的内容。
#include stdio.h
int main()
{int i;for (i 1; i 100; i){if (__________________)printf(%d , i * i / 2);elseprintf(%d , (i * i - 1) / 2);}printf(\n);
}
想法
其规律是对偶数项是序号平方再除2奇数项是序号平方减1再除2。
i%20
门牌制作
小蓝要为一条街的住户制作门牌号。
这条街一共有 2020 位住户门牌号从 1 到 2020 编号。
小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符最后根据需要将字符粘贴到门牌上例如门牌 1017 需要依次粘贴字符 1、0、1、7即需要 1 个字符 02 个字符 11 个字符 7。
请问要制作所有的 1 到 2020 号门牌总共需要多少个字符 2
#include bits/stdc.h
using namespace std;
int main()
{int ans 0, x;for (int i 1; i 2020; i){x i;while (x){________________;}}cout ans;return 0;
}
提示
利用循环将当前数字的每一位求出分别进行判断即可 利用循环将当前数字的每一位求出分别进行判断即可
#include iostream
using namespace std;int ans;void check(int n)
{while(n){int t n % 10;if(t 2) ans ;n / 10;}
}int main()
{for (int i 1; i 2020; i )check(i);cout ans endl;return 0;
}另一种比较笨拙 但比较好理解的方法:
虽然有点笨拙但比较好理解。
let count 0;
for (let i 1; i 2020; i) {
let x i;
//个位符合的x, 并摘掉个位的2 符合的个数;
if (x % 10 2) {
x - 2;
// console.log(x);
count;
}
//十位符合的x, 并摘掉十位的2 符合的个数;
if (parseInt(x / 10) % 10 2) {
x - 20;
// console.log(x);
count;
}
//百位符合的x, 并摘掉百位的2 符合的个数;
if (parseInt(x / 100) % 10 2) {
x - 200;
// console.log(x);
count;
}
//千位符合的x, 并摘掉千位的2 符合的个数;
if (parseInt(x / 1000) % 10 2) {
x - 2000;
// console.log(x);
count;
}
}
console.log(符合个数: count);
//结果624 方阵转置
问题描述
给定一个n×m矩阵相乘求它的转置。其中1≤n≤201≤m≤20矩阵中的每个元素都在整数类型4字节的表示范围内。
输入格式
第一行两个整数n和m
第二行起每行m个整数共n行表示n×m的矩阵。数据之间都用一个空格分隔。
输出格式
共m行每行n个整数数据间用一个空格分隔表示转置后的矩阵。
样例输入
2 4
34 76 -54 7
-4 5 23 9
样例输出
34 -4
76 5
-54 23
7 9
请从以下四个选项中选择正确的代码填补空白处实现方阵转置功能。
提示
对一个方阵转置就是把原来的行号变列号原来的列号变行号
#include bits/stdc.h
using namespace std;int main()
{int m, n;int a[20][20];int i, j;cin m n;for (i 0; i m; i){for (j 0; j n; j){cin a[j][i];}}__________________;return 0; 矩阵的转置实际就是把n行m列的矩阵 转换为m行n列的矩阵 所以只需要改变 i j 位置即可 微生物增殖
假设有两种微生物 X 和 Y
X出生后每隔3分钟分裂一次数目加倍Y出生后每隔2分钟分裂一次数目加倍。
一个新出生的X半分钟之后吃掉1个Y并且从此开始每隔1分钟吃1个Y。
现在已知有新出生的 X10, Y89求60分钟后Y的数目。
如果X10Y90呢
本题的要求就是写出这两种初始条件下60分钟后Y的数目。
以下程序实现了这一功能请你补全空白处内容
提示
分析可知Y分别会在0.5,1.5,2.5······时被吃所以把60分钟分成120份则在除以2余数为1时Y的数目减少X个
#include iostream
using namespace std;
int main()
{int x 10, y 90;for (int i 1; i 120; i){________________;}cout y endl;
} 思路一般来说这种题都是找规律的题在纸上笔算是不可能算出结果的本体也不例外只要找到x与y关于时间的对应关系即可。
计算代码
#includestdio.h
#includestdlib.h
int main()
{int n,m;double x,y;scanf(%d%lf%lf,n,x,y);m1;while(mn){if(m%2!0)yy-x;if(m%20)y(y-x)*2;if(m%30)x*2;//printf(m%d x%.0lf y%.0lf\n,m,x,y);m;}printf(x%.0lf y%.0lf\n,x,y);system(pause);return 0;
}
成绩统计
问题描述
编写一个程序建立了一条单向链表每个结点包含姓名、学号、英语成绩、数学成绩和C成绩并通过链表操作平均最高的学生和平均分最低的学生并且输出。
输入格式
输入n1行第一行输入一个正整数n表示学生数量接下来的n行每行输入5个数据分别表示姓名、学号、英语成绩、数学成绩和C成绩。注意成绩有可能会有小数。
输出格式
输出两行第一行输出平均成绩最高的学生姓名。第二行输出平均成绩最低的学生姓名。
样例输入
2
yx1 1 45 67 87
yx2 2 88 90 99
样例输出
yx2
yx1
请从以下四个选项中选择空白处的内容。
#include bits/stdc.h
using namespace std;int main()
{struct student{string xm;int xh;double yy;double sx;double cpp;};student a[1000];int n;double sum 0, min 301, max 0;string mins, maxs;cin n;for (int i 0; i n; i){cin a[i].xm a[i].xh a[i].yy a[i].sx a[i].cpp;sum a[i].yy a[i].sx a[i].cpp;__________________;}cout maxs endl mins;return 0;
}
提示 类似冒泡法求最大值最小值 如果有相同成绩的最高分和最低分取序号小的还是取序号大的最高最低分。 ifsummax)这是取序号小的最高分。 ifsummax)这是取序号大的最高分。
题解 模拟
#include iostream
#include cmath
using namespace std;int main()
{int n;cin n;int a 0, b 0;for (int i 0; i n; i ){int x;cin x;if(x 60) a ;if(x 85) b ;}cout round(100.0 * a / n) % endl;cout round(100.0 * b / n) % endl;return 0;
} 星系炸弹
在X星系的广袤空间中漂浮着许多X星人造“炸弹”用来作为宇宙中的路标。
每个炸弹都可以设定多少天之后爆炸。
比如阿尔法炸弹2015年1月1日放置定时为15天则它在2015年1月16日爆炸。
有一个贝塔炸弹2014年11月9日放置定时为1000天请你计算它爆炸的准确日期。
以下程序实现了这一功能请你填补空白处内容
提示 json 先判断是否为闰年这会影响2月份是28还是29如果是闰年2月份是29如果不是就是28
#include stdio.hint main()
{int monthDays[12] {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int days 1000;int year 2014, month 11, day 9;int i;for (i 0; i days; i){day;if (day monthDays[month - 1]){day 1;month;if (month 12){month 1;year;____________________;}}}printf(%d-%d-%d\n, year, month, day);getchar();return 0;
}
if ((year % 400 0) || (year % 4 0 year % 100 ! 0)) monthDays[1] 29; else monthDays[1] 28;
判断闰年的依据: 闰年的计算方法 ①、普通年能被4整除且不能被100整除的为闰年。如2004年就是闰年1900年不是闰年 ②、世纪年能被400整除的是闰年。如2000年是闰年1900年不是闰年 ③、对于数值很大的年份这年如果能整除3200并且能整除172800则是闰年。如172800年是闰年86400年不是闰年因为虽然能整除3200但不能整除172800 闰年怎么来 地球绕日运行周期为365天5小时48分46秒合365.24219天即一回归年 tropical year。公历的平年只有365日比回归年短约0.2422 日每四年累积约一天把这一天加于2月末即2月29日使当年时间长度变为366日这一年就为闰年。 需要注意的是现在的公历是根据罗马人的儒略历改编而《中华民俗万年历》得。由于当时没有了解到每年要多算出0.0078天的问题从公元前46年到16世纪一共累计多出了10天。为此当时的教皇格列高利十三世将1582年10月5日人为规定为10月15日。并开始了新闰年规定。即规定公历年份是整百数的必须是400的倍数才是闰年不是400的倍数的就是平年。比如1700年、1800年和1900年为平年2000年为闰年。此后平均每年长度为365.2425天约4年出现1天的偏差。按照每四年一个闰年计算平均每年就要多算出0.0078天经过四百年就会多出大约3天来因此每四百年中要减少三个闰年。闰年的计算归结起来就是通常说的四年一闰百年不闰,四百年再闰。 由于地球的自转速度逐渐降低而公转速度则相对更加稳定所以上述的系统经过更长的周期也会发生微小的误差。据计算每8000年会有一天的误差所以英国的天文学家John Herschel提议公元4000为平年以后类推12000年20000年亦为平年。但此提议从未被正式采纳。原因是到了4000年地球自转的精确速度并非现在可以预测所以届时参照真实数据方可做出判断。因此在长远的将来针对闰年的微小调整应该不是由预定的系统决定而是随时不定性的。 特别数的和
题目描述
小明对数位中含有 2、0、1、9 的数字很感兴趣不包括前导 0在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40共 28 个他们的和是 574。
请问在 1 到 n 中所有这样的数的和是多少
输入格式
共一行包含一个整数 n。
输出格式
共一行包含一个整数表示满足条件的数的和。
数据范围
1≤n≤10000
输入样例
40
输出样例
574
以下代码实现了这一功能请你填补空白处的内容
#include iostreamusing namespace std;int ans, n;bool check(int n)
{while (n){int tmpn n % 10;if (tmpn 2 || tmpn 0 || tmpn 1 || tmpn 9)return true;__________________;}return false;
}int main()
{cin n;for (int i 1; i n; i){if (check(i))ans i;}cout ans endl;return 0;
}
提示
只要利用模除找出含有2,0,1,9的数即可 #include iostream
using namespace std;bool check(int x)
{while(x){int t x % 10;if(t 2 || t 0 || t 1 || t 9) return true;x / 10;}return false;
}int main()
{int n;cin n;int ans 0;for (int i 1; i n; i )if(check(i))ans i;cout ans endl;return 0;
} 蛇形填数
如下图所示小明用从1 开始的正整数“蛇形”填充无限大的矩阵。 容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20 行第20 列的数是多少
以下程序实现了这一功能请你补全以下空白处内容
提示
当到达边界时判断它应该向右走还是向下走向右走完就直接向左下走向下走完就直接向右上走
#include bits/stdc.husing namespace std;
int main()
{int i 0;int j 0;int cnt 2;int a[250][250];a[0][0] 1;while (cnt 1000){j;while (i ! -1 j ! -1){a[i][j] cnt;if (j 0)break;i;j--;}i;while (i ! -1 j ! -1){___________;}}for (int i 0; i 20; i){for (int j 0; j 20; j){cout setw(5) a[i][j] ;}cout \n;}cout a[19][19];return 0;
}
我们讨论 n n n行 n n n列位置上的数可以发现要求这个 ( n , n ) (n,n) (n,n)可以通过求 p 1 p1 p1和 p 2 p2 p2计算它们的平均数。 p 1 p1 p1是 n n n阶三角形的最大一个数 p 2 p2 p2是 n − 1 n-1 n−1阶三角形的最大一个数再加上1。 a n s w e r ( f ( m ) f ( m − 1 ) 1 ) / 2 answer(f(m)f(m-1)1)/2 answer(f(m)f(m−1)1)/2 而 p 1 p 2 p1p2 p1p2且 p 1 p1 p1和 p 2 p2 p2都可通过计算三角形底边 m m m得到。从1开始累加到 m m m即可得到 n n n阶三角形中最大的数字。于是先计算底边 m m m。 f ( x ) x ∗ ( x 1 ) / 2 f(x)x*(x1)/2 f(x)x∗(x1)/2
不是每个三角形的底边都穿过 n n n行 n n n列而是隔一个三角形才出现一个由此出现线性关系 2 n 2n 2n。三角形最长的边为 m m m代入 n 2 n2 n2时 m 5 m5 m5由此有 m 2 n − 1 m2n-1 m2n−1
代码
#includeiostream
using namespace std;//计算从1累加到x的值
int f(int x){return x*(x1)/2;
}int main(){int n;while(1){cinn;//计算三角形的底边int m2*n-1;//大三角形小三角形加一两数取平均数cout((f(m)f(m-1)1)/2)endl;} system(pause);return 0;
} *日志统计*双指针
题目描述
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志日志共有 N 行。
其中每一行的格式是
ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞小明就认为这个帖子曾是”热帖”。
具体来说如果存在某个时刻 T 满足该帖在 [T,TD) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞该帖就曾是”热帖”。
给定日志请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K。
以下 N 行每行一条日志包含两个整数 ts 和 id。
输出格式
按从小到大的顺序输出热帖 id。
每个 id 占一行。
数据范围
1≤K≤N≤10E5, 0≤ts,id≤10E5, 1≤D≤10000
输入样例
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
输出样例
1 3
下面的程序实现了这一功能请你补全空白处的内容 #include bits/stdc.h using namespace std; const int N 1e5 10; typedef pairint, int PII; #define x first #define y second PII logs[N]; bool st[N]; int cnt[N]; int main() { int n, d, k; cin n d k; for (int i 0; i n; i) cin logs[i].x logs[i].y; sort(logs, logs n); for (int i 0, j 0; i n; i) { cnt[logs[i].y]; while (logs[i].x - logs[j].x d) __________________; if (cnt[logs[i].y] k) st[logs[i].y] true; } for (int i 0; i N; i) if (st[i]) cout i endl; return 0; } 提示
尺取法
双指针
先根据时刻排序
因为序列是有序的所以可以保证区间内的时刻是存在单调性的
所以我们只需要枚举每一个基准点利用双指针基于该起始点右移如果在范围内且大于等于 K K K个点赞就存入答案
基准点右移时需要将该基准点的值减一因为已经移除区间不必再统计点赞个数。
时间复杂度
O ( n l o g n ) O(nlogn) O(nlogn)
C 代码
#include iostream
#include algorithm
using namespace std;#define x first
#define y secondtypedef pairint,int PII;
const int N 100010;
PII w[N];
int cnt[N];
bool res[N]; // 存放答案
int n, d, k;int main()
{cin n d k;int a, b;for(int i 0;i n;i ) {scanf(%d%d,a,b);w[i] {a,b};}sort(w,w n);for(int i 0,j 0;i n;i ) {while(j n w[j].x - w[i].x d){cnt[w[j].y] ;if(cnt[w[j].y] k) res[w[j].y] true;j ;}cnt[w[i].y] --;}for(int i 0;i N;i ) if(res[i]) printf(%d\n,i);return 0;
} 猜年龄
【问题描述】 美国数学家维纳(N.Wiener)智力早熟11岁就上了大学。他曾在1935~1936年应邀来中国清华大学讲学。 一次他参加某个重要会议年轻的脸孔引人注目。于是有人询问他的年龄他回答说 “我年龄的立方是个4位数。我年龄的4次方是个6位数。这10个数字正好包含了从0到9这10个数字每个都恰好出现1次。” 请你推算一下他当时到底有多年轻。
【问题分析】 穷举算法对年龄进行穷举从问题描述可以将年龄穷举范围定义在11~30之间1~100也可以。在穷举过程中对年龄进行检查如果符合以下条件则输出结果
1年龄的立方是个4位数
2年龄的4次方是个6位数
310个数字不重复
【程序代码】1 public class 蓝桥杯_第四届_猜年龄2 {3 public static void main(String[] args) {4 // TODO code application logic here5 long t30,t40;6 for(int i11;i30;i)7 {8 String str;9 t3i*i*i;
10 t4i*i*i*i;
11 strString.valueOf(t3) String.valueOf(t4);
12 if(str.length()!10)
13 continue;
14 else if(noRepeat(str))
15 {
16 System.out.print(i);
17 break;
18 }
19 }
20 }
21
22 public static boolean noRepeat(String str)
23 {
24 for(int j0;jstr.length()-1;j)
25 {
26 char xstr.charAt(j);
27 for(int mj1;mstr.length();m)
28 {
29 char ystr.charAt(m);
30 if(yx)
31 {
32 return false;
33 }
34 }
35 }
36 return true;
37 }
38 } 【运行结果】 18 【相关知识】
数值与字符串之间的转换
字符串重复检测 【类似问题】 蓝桥杯/第五届/猜年龄
转载于:https://www.cnblogs.com/yzzdzy/p/4364675.html 合并检测
新冠疫情由新冠病毒引起最近在 A 国蔓延为了尽快控制疫情A 国准 备给大量民众进病毒核酸检测。
然而用于检测的试剂盒紧缺。为了解决这一困难科学家想了一个办法合并检测。即将从多个人k 个采集的标本放到同一个试剂盒中进行检测。如果结果为阴性则说明这 k 个人都是阴性用一个试剂盒完成了 k 个人的检测。如果结果为阳性则说明 至少有一个人为阳性需要将这 k 个人的样本全部重新独立检测从理论上看 如果检测前 k−1 个人都是阴性可以推断出第 k 个人是阳性但是在实际操作中 不会利用此推断而是将 k 个人独立检测加上最开始的合并检测一共使用 了 k 1 个试剂盒完成了 k 个人的检测。
A 国估计被测的民众的感染率大概是 1%呈均匀分布。请问 k 取多少能最节省试剂盒
以下程序实现了这一功能请你补全以下空白处内容
#include stdio.h
int main()
{double m 4537;double min 9999999;double k, sum, ans;for (k 1; k 100; k){sum (m - k) / k 0.01 * m * k 1;__________________;}printf(%d\n, (int)ans);return 0;
}
提示
设检测人数为100人根据概率为1%则只有1个为阳性。k个人一组则需要的试剂数量为对所有分组进行合并检测所需要的试剂数100/k其中1个分组阳性所需要的试剂数k未分组人数所需的试剂数量。 因为感染率是百分之一 并且感染率服从均匀分布 所以结果应是1到99之间的一个数.
为了方便计算取整 我们每次假设i个人用一个试剂盒有100 * i个人参加了检测
那么统一检测每次需要100个试剂盒 由于呈均匀分布所以每100人都会出现一个病例 一个病例需要i个试剂盒 总共有i个病例 所以总共需要need 100 i * i 个试剂盒
最后我们在data种添加每百人平均消耗试剂盒和当前i值 对试剂盒消耗量排序 输出最小每百人平均消耗试剂盒对应的人数 i 即可
Code
data []
for i in range(1, 100):need 100 i * idata.append([need / i, i])
data.sort(keylambda x: x[0])
print(data[0][1])Answer 10 排它平方数
203879 * 203879 41566646641
这有什么神奇呢仔细观察203879 是个6位数并且它的每个数位上的数字都是不同的并且它平方后的所有数位上都不出现组成它自身的数字。
具有这样特点的6位数还有一个请你找出它
再归纳一下筛选要求
6位正整数
每个数位上的数字不同
其平方数的每个数位不含原数字的任何组成数位
以下程序实现了这一功能请你补全以下空白处内容
#include iostream
using namespace std;int main()
{int num[10], flag;for (long long i 123456; i 987654; i){long long a i;long long b i * i;memset(num, 0, sizeof(num));flag 1;while (a){_________________;}if (flag){while (b){if (num[b % 10]){flag 0;break;}b / 10;}if (flag)cout i endl;}}return 0;
}
提示
0的平方为0
1的平方为1
5的平方为5
6的平方为6
以上这4个数字都不能作为原数字的最后一位可以在最后一位排除
且第一位不能为0
#include iostream
#include cstdio
#include cstring
#include algorithm
#include unordered_map#define x first
#define y secondusing namespace std;typedef pairint, int PII;int main()
{int n;cin n;unordered_mapint, PII ans;for(int c 0; c * c n; c )//枚举C和Dfor(int d c; d * d c * c n; d ){int t c * c d * d; //存下来这两个数的平方和if(ans.count(t) 0) ans[t] {c, d};}for(int a 0; a * a n; a )for(int b a; b * b a * a n; b ){int t n - a * a - b * b;//看A和B的平方和还和目标差多少看看之前存的有没有这个数if(ans.count(t) ! 0){printf(%d %d %d %d\n, a, b, ans[t].x, ans[t].y);return 0;}}return 0;
} 问题解决的中心思想是 通过数组num[10], 初始化后全0状态a的每位取数后置非0考虑重复然后再后面b取位时看a[X]的非零状态如果取到是非零那就是重复了如果是零那就是之前没有置表示不重复flag直到B取尽后才能保证true.才证明这个数字符合要求。
所以上述代码穷尽法做num[a%10]运算就行了没有必要考虑位数值是0情况当然考虑0156就是条件规避场景更细致些。
题目合理利用数值置位方式表示是否取到过这个做法不错 *四平方和定理*
四平方和定理又称为拉格朗日定理 每个正整数都可以表示为至多 4 个正整数的平方和。 如果把 0 包括进去就正好可以表示为 4 个数的平方和。
比如 502021222 712121222
对于一个给定的正整数可能存在多种平方和的表示法。 要求你对 4 个数排序 0≤a≤b≤c≤d 并对所有的可能表示法按 a,b,c,d 为联合主键升序排列最后输出第一个表示法。
输入格式 输入一个正整数 N。
输出格式 输出4个非负整数按从小到大排序中间用空格分开。
数据范围 0N5∗106
输入样例
5输出样例
0 0 1 2题解 首先三重循环枚举a,b,c最后确定出来dO(N3)的复杂度大概率通过不了
这时候就用空间来换取时间 1首先我们先枚举C和D将所有组合的平方和进行一个记录 2然后枚举A和B算出来跟输入的数字差了几然后看之前存放的有没有这一项 3找到这一个然后进行输出 这里又要求到了按字典序排序的问题首先我们的A和B的枚举方法肯定是没有问题的一定是AB的那么看C和DC和D用的哈希表存放也是在枚举的时候确定了一个字典序的如果这个数字存在了在找到相同数字的时候是不会进行更新操作的所以字典序也一定是成立的。代码如下
#include iostream
#include cstdio
#include cstring
#include algorithm
#include unordered_map#define x first
#define y secondusing namespace std;typedef pairint, int PII;int main()
{int n;cin n;unordered_mapint, PII ans;for(int c 0; c * c n; c )//枚举C和Dfor(int d c; d * d c * c n; d ){int t c * c d * d; //存下来这两个数的平方和if(ans.count(t) 0) ans[t] {c, d};}for(int a 0; a * a n; a )for(int b a; b * b a * a n; b ){int t n - a * a - b * b;//看A和B的平方和还和目标差多少看看之前存的有没有这个数if(ans.count(t) ! 0){printf(%d %d %d %d\n, a, b, ans[t].x, ans[t].y);return 0;}}return 0;
}
*大数乘法*
对于32位字长的机器大约超过20亿用int类型就无法表示了我们可以选择int64类型但无论怎样扩展固定的整数类型总是有表达的极限如果对超级大整数进行精确运算呢一个简单的办法是仅仅使用现有类型但是把大整数的运算化解为若干小整数的运算即所谓“分块法”。 上图表示了分块乘法的原理。可以把大数分成多段此处为2段小数然后用小数的多次运算组合表示一个大数。可以根据int的承载能力规定小块的大小比如要把int分成2段则小块可取10000为上限值。注意小块在进行纵向累加后需要进行进位校正。
请从以下四个选项中选择正确答案填补在空白处使得代码能运行后能产生正确的结果。
提示
十进制数的进位问题
#include bits/stdc.h
using namespace std;void bigmul(int x, int y, int r[])
{int base 10000;int x2 x / base;int x1 x % base;int y2 y / base;int y1 y % base;int n1 x1 * y1;int n2 x1 * y2;int n3 x2 * y1;int n4 x2 * y2;r[3] n1 % base;r[2] n1 / base n2 % base n3 % base;r[1] __________________;r[0] n4 / base;r[1] r[2] / base;r[2] r[2] % base;r[0] r[1] / base;r[1] r[1] % base;
}int main(int argc, char *argv[])
{int x[] {0, 0, 0, 0};bigmul(87654321, 12345678, x);printf(%d%d%d%d\n, x[0], x[1], x[2], x[3]);return 0;
}
