【算法课OJ】实验一
决定程序优雅的是人，而不是语言。
链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1108
密码：123654
问题 A: 判断字符串是否是手机号码
题目描述
手机号码是一串数字，长度为 11 位，并且第一位必须是 1，现在给出一个字符串，我们需要判断这个字符串是否符合手机格式。
输入
多组测试数据。每组数据输入一个字符串。
输出
若该字符串符合手机号码格式，输出 1，否则输出 0。
样例输入
12345612345
样例输出
1
题意
Water，输入一个字符串，判断字符串是不是一个手机号码。
思路
（可封装在一个返回 bool 的 check() 函数中）考虑三个方面：
- 是不是 11 位；
- 首位是不是为 “1”；
- 每位是不是数字。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
bool check(char str[])
{
if(strlen(str) != 11) return false;
if(str[0] != '1') return false;
for(int i = 0; i < 11; i++)
{
if(str[i] < '0' || str[i] > '9')
return false;
}
return true;
}
int main()
{
char str[999999];
while(~scanf("%s",str))
{
if(check(str)) puts("1");
else puts("0");
}
return 0;
}
问题 B: 内部收益率
题目描述
输入
输出
对于每组数据，输出仅一行，即项目的 IRR，四舍五入保留小数点后两位。
样例输入
1
-1 2
2
-8 6 9
0
样例输出
1.00
0.50
题意
如题目描述所示。
思路
题目两边等式同乘 $(1+IRR)^T$。则原题相当于求：$CF_0(1+IRR)^T+CF_1(1+IRR)^{T-1}+\cdots +CF_T=0$ 的解，则可使用二分法。
L 初始值取 -1.0，R 初始值取常规正无穷大（一般取 0x3F3F3F3F）。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int main()
{
int t;
double cf[13],l,r,m;
while(~scanf("%d",&t) && t)
{
for(int i = 0; i <= t; i++)
{
scanf("%lf",&cf[i]);
}
l = -1.00;
r = inf;
while(r-l > eps)
{
m = (l+r)/2;
double sum = 0.0;
for(int i = 0; i <= t; i++)
{
sum += cf[i]*pow(1+m,t-i);
}
if(sum > 0) l = m;
else r = m;
}
printf("%.2lf\n",l);
}
return 0;
}
问题 C: 跳台阶
题目描述
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
输入
多组测试样例。每组测试样例包含一个整数 n。
输出
每组测试样例输出一行，表示青蛙跳上 n 级台阶的跳法数量.
所得到的结果模 1000000007 。
样例输入
3
4
样例输出
3
5
题意
Water，Fibonacci 数列，先打个表（牺牲空间换取时间），最好用 long long。
思路
假设青蛙在第 n 级台阶，那么我们倒推一步。
因为它每次可以跳 1 级台阶或者 2 级台阶，所以它上一步只能在第 n-1 级或者第 n-2 级台阶，每次都要对 1e9 + 7 取余所以可写出递推式：f[n] = (f[n-1] + f[n-2]) % mod;。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long ll;
ll f[99999] = {1,1};
const int mod = 1e9 + 7;
int main()
{
int n;
for(int i = 2; i < 99999; i++)
{
f[i] = (f[i-1]+f[i-2])%mod;
}
while(~scanf("%d",&n))
{
printf("%lld\n",f[n]);
}
return 0;
}
问题 D: 奶牛的聚会
题目描述
农历新年马上就要到了，奶牛们计划举办一次聚会庆祝新年的到来。但是，奶牛们并不喜欢走太远的路，这会给他们的聚会带来消极情绪，当一头奶牛的消极指数为 $W_i$，他参加聚会所需行走的距离为 $S_i$，那么他就会给聚会带来 $S_i^3*W_i$ 的消极情绪。所有奶牛所在位置都在一条直线上，已知所有奶牛的坐标和消极指数，求如何确定聚会地点，使得所有奶牛给聚会带来的消极情绪之和最小，输出消极情绪之和的最小值。
输入
第一行包含一个整数 Ca (Ca <= 20) ，表示有 Ca 组测试数据。
对于每组测试数据：第一行包含一个整数 n (1 <= n <= 50000) ，表示奶牛的数量。接下来 n 行每行包含两个浮点数 $X_i$ 和 $W_i$ (-106 <= $X_i$ <=106, 0 < $W_i$ <15)。
输出
对于每组测试数据，输出 “Case #c: ans” ，其中c表示测试数据编号，ans 表示消极情绪之和的最小值，结果四舍五入为一个整数。
样例输入
1
5
0.9 2
1.4 4
3.1 1
6.2 1
8.3 2
样例输出
Case #1: 300
题意
如题目描述所示。
思路
这题和 B 题类似，不同的是 B 题是单调函数，而此题是先减后增的函数，取的点一定在最左边奶牛的家和最右边奶牛的家的中间，故我们设两个变量 L 和 R 存储最左边的点的坐标和最右边点的坐标。一开始我们可以把 L 设为正无穷大，R 设为负无穷大，然后边输入边更新 。原问题可看作一个先减后增的函数，我们的目标是求最小值。
三分：子问题规模缩小到原来的 2/3。
初始化：L 足够大，R 足够小。
在输入时L = min(L,x[i]); R = max(R,x[i]);更新L和R，使他们最后为区间的左界和右界。
m1 为 [L,R) 的 1/3 分位点，m2 为 [L,R) 的 2/3 分位点。
写一个计算取某点时的结果 double f()，每次比较 f(m1) 和 f(m2) ：
- 若
f(m1) > f(m2)，则最小值一定在[L+(R-L)/3,R)区域内，更新L = m1； - 否则，最小值一定在
[L,R-(R-L)/3)区域内，更新R = m2。
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
double x[50005],w[50005];
int t,n;
double f(double t)
{
double sum = 0.0;
for(int i = 0; i < n; i++)
{
double d = t-x[i];
if(d < 0) d = -d;
sum += d*d*d*w[i];
}
return sum;
}
int main()
{
double m1,m2,l,r;
scanf("%d",&t);
for(int cas = 1; cas <= t; cas++)
{
scanf("%d",&n);
l = inf;
r = -inf;
for(int i = 0; i < n; i++)
{
scanf("%lf %lf",&x[i],&w[i]);
l = min(l,x[i]);
r = max(r,x[i]);
}
while(r-l > eps)
{
m1 = l+(r-l)/3;
m2 = r-(r-l)/3;
if(f(m1) < f(m2)) r = m2;
else l = m1;
}
printf("Case #%d: %lld\n",cas,ll(f(l)+0.5));
}
return 0;
}
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/09/28/algorithm-experiment-1/