算法可运行①"/>
OJ算法可运行①
OJ算法题共10个篇幅,不定期在篇幅里增加题目(篇幅不增加)。
个人水平有限,如有错误和可以改进的地方,非常期待批评指正,谢谢!
题目描述
计算a+b
输入
第一个数为数据组数n,接下来n行,每行2个整数a, b(保证a, b, a+b在int范围内)
输出
对于每组数据,输出一行,为 a+b 的值
输入样例
2
1 2
2 3
输出样例
3
5
#include <stdio.h>
int main()
{int n;int a,b;scanf("%d", &n);while(n--){scanf("%d%d",&a, &b);printf("%d\n",(a+b));}/* // 或用如下for循环代替while循环int i;for(i=0; i<n; i++){scanf("%d%d",&a, &b);printf("%d\n",(a+b));}*/return 0;
}
题目描述
求两个整数的余数。
输入
两个正整数n, m。
输出
输出一个整数,为n除以m的余数。
输入样例
12 5
输出样例
2
#include<stdio.h>
int main(){int a,b;//scanf("%d",&n);// for(int i=0;i<n;i++){scanf("%d%d",&a,&b);printf("%d",(a%b));// }return 0;
}
题目描述
BlueFly是一个壕,
他有一大堆的挖掘机,通过挖掘机发家致富。
他不仅是厨师,
还是黑客,
还是高级技师,
拥有十八般武艺。。。
BlueFly是个壕,他有一个妹妹叫FlySnow。(脑洞不要太大。。)
BlueFly每天都要给他的妹妹发糖吃,第一天他给他妹妹发了n个糖,以后每天发的糖的数量比前一天多m个。 请问k天以后BlueFly总共发了多少块糖。(假定FlySnow都能吃完这些糖 233)
输入
输入多组数据。
每组数据只有一行,是三个正整数,分别为n,m,k,保证每个数都在int范围内。
输出
输出这k+1天中FlySnow总共吃了多少糖,保证输出结果在int范围内。
输入样例
1 1 2
1 2 2
输出样例
6
9
样例解释
第一天吃糖数量为1,每天比前一天多吃一块,2天后吃糖数量为1+2*1=3块。总共吃糖的个数就是1+2+3=6。总共吃了3天,而不是2天。
输入提示
用while(scanf("%d%d%d",&a,&b,&c) != EOF)来进行多组输入的控制,输入结束的标志是EOF。
#include<stdio.h>
int main(){int n,m,k;while(~(scanf("%d%d%d",&n,&m,&k))){int sum;sum=n;int two;two=sum;for(int i=0;i<k;i++){two=two+m;sum=sum+two;}printf("%d\n",sum);}return 0;
}
OJ算法题共20个篇幅,不定期在篇幅里增加题目(篇幅不增加)。
个人水平有限,如有错误和可以改进的地方,非常期待批评指正,谢谢!
题目描述
给你一非降序数列,以及一组查询,查询某一特定元素是否存在于数列之中,如果存在,则输出该元素首次出现的位置,否则输出"error"。
输入
多组测试数据。 对于每组数据,第一行为两个整数n,m(1<=n,m<=250000),表示数列中有n个元素以及m次查询。 第二行包含n个正整数,用空格分隔,表示有序数列。 接下来m行,每行一个整数,表示每次查询的元素。
输出
输出m行,每行输出内容见题目描述及样例
输入样例
5 3
1 2 3 4 5
3
5
7
输出样例
3
5
error
Hint
注意是下界二分查找
#include<stdio.h>
int main(){int n,m,num;while(~scanf("%d%d",&n,&m)){int a[n];for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=0;i<m;i++){scanf("%d",&num);int j=0;for(j;j<n;j++){if(num==a[j]){printf("%d\n",j+1);break;}}if(j==n) printf("error\n");}}return 0;
}
我们用O和X分别表示现物和搏筋兜牌。
假设有3次舍牌,我们可以很容易地枚举出所有排列方式:OOO, OOX, OXO, XOO, XOX,我们把每一个这样的一个序列叫做一种舍牌方式。
为了方便讨论,我们给出如下定义:
F(n) = n次舍牌中不同的舍牌方式数
比如上面的例子中,F(3) = 5。
我们来尝试推导具有普适性的公式:
假设F(n-2)种舍牌方式中,有m次以现物结束(类似于OXOXXX……O),F(n-2) - m次以搏筋兜牌结束(类似于OXOXXX……X)。
对于类似OXOXXX……O的舍牌方式,下一次舍牌既可以是O也可以是X,所以下一次有2*m中舍牌方式;对于类似OXOXXX……X的舍牌方式,下一次只能是O,所以下一次舍牌有F(n-2) - m种方式。
我们把两种舍牌方式数相加,就得到:
F(n-1) = 2*m + F(n-2) - m = F(n-2) + m
同理,由上面的推理结论,F(n-1)中有F(n-2)次以O结束,m次以X结束,所以:
F(n) = 2*F(n-2) + m = (F(n-2) + m) + F(n-2) = F(n-1) + F(n-2)
而这就是斐波那契数列的递推公式。
Part 2 取模运算的处理技巧
题目中要对其进行取模处理。这里需要补充一个结论:
斐波那契数列对某个整数取模的结果构成循环数列
这个结论的证明很繁琐,故不在此列出,可以去这篇博文下查看:
由于时间和空间有限,不可能使用递归方法对于每一个输入值进行求解。故进行预处理操作,把一个周期内的斐波那契数取模后的结果存入数组。对于之后的每一次查询,只需要用循环周期对其进行取模操作,然后根据余数直接读取数组里保存的值。
#include <iostream>
#define INF 0xFFFFFF
using namespace std;
int remainders[100000];//取余后的斐波那契数列,仅保存一个周期的数
int T = 2;//循环节void calFibonacciRemainders()
{remainders[0] = 1;remainders[1] = 2;while (1){remainders[T] = (remainders[T - 1] + remainders[T - 2]) % 100007;if (remainders[T] == remainders[1]){T--;break;}T++;}
}int main()
{calFibonacciRemainders();int n;while (cin >> n){n %= T;if (n == 0)n = T;cout << remainders[n] << endl;}
}
题目描述
jhljx又决定来出题了,上次上机以后有人说他是黑心学长,,噗。。。
肿么可以这样。。
松辰学妹对jhljx说不要不要丧心病狂。。jhljx说我给你出一道题,你要是答对了,你就赢了。。
松辰学妹说这还不简单啊。。
于是jhljx给了松辰学妹一个长度为n的数列A1,A2,A3……An。他说你能找出这个序列中a[i]-a[j]的最大值吗(保证i<j)?
松辰学妹说用数组啊。。jhljx说,没学数组,不准用。。用了你就跪了。。 松辰学妹说好吧。。这可怎么办呢?
输入
输入多组数据。
每组数据两行,第一行是一个正整数n(2<=n<=1000000)。第二行是n个数,每个数之间用空格隔开。保证这些数在int范围内。
输出
输出满足条件的最大值。
输入样例
2
100 20
输出样例
80
Hint
这道题尽量不要用数组,因为没有学。不用数组完全可以做。
PS:这道题没有去刻意卡内存。。
#include<cstdio>
#include<iostream>
using namespace std;
int main(){int n,i;long long a0,a1,maxV,maxGap,last,ai;while((scanf("%d",&n)) != EOF){cin >> a0 >> a1;maxGap = a0 - a1;maxV = a0;last = a1;for(i = 2;i < n;i++){cin >> ai;if(last > maxV)maxV = last;if(maxV - ai > maxGap)maxGap = maxV - ai;last = ai;}cout << maxGap << endl;}
}
上一篇
下一篇
更多推荐
OJ算法可运行①
发布评论