OJ算法可运行①

算法可运行①"/>

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;}
}

上一篇

下一篇