【算法课OJ】上机复习
蓬生麻中，不扶自直。
考试计划
考试时间：11月7日 14:00 - 15:40
考试地点：计-17机房
使用OS：等级考试（有Code::Blocks环境）
策略：使用头文件#include<bits/stdc++.h>，准确比时间重要（据说错1次扣1分，而且错误产生罚时，拉低Rank，得不偿失）。
作业二
问题 B: 排列问题
直接调库，没啥意义，应该不会考。
题目描述
输入一个可能含有重复字符的字符串，打印出该字符串中所有字符的全排列。
输入
单组测试数据，输入数据是一个长度不超过10个字符的字符串，以逗号结尾。
输出
打印出该字符串中所有字符的全排列。以字典序顺序输出，用空格分隔。
样例输入
abc,
样例输出
abc acb bac bca cab cba
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
char str[15];
scanf("%s",str);
int len = strlen(str)-1;
str[len] = '\0';
sort(str,str+len);
printf("%s",str);
while(next_permutation(str,str+len))
printf(" %s",str);
printf("\n");
return 0;
}
注意点
善于调用库函数，避免重复造轮子。注意next_permutation()的用法。
问题 C: 快速幂
快速幂模板，也没啥意义，应该不考。
题目描述
输入
多组测试样例，最多50组。每组测试样例给定一个整数x(1<=x<=25000)
输出
对每个样例，输出一行，代表f(x)对100000007取余的结果。
样例输入
3
4
5
样例输出
33
289
3414
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e8 + 7;
ll f[55];
ll poww(ll x,ll n)
{
ll ans = 1;
while(n)
{
if(n & 1) ans = ans*x%mod;
x = x*x%mod;
n >>= 1;
}
return ans;
}
int main()
{
f[1] = 1;
for(int i = 2; i < 55; i++)
f[i] = (f[i-1]+poww(ll(i),ll(i)))%mod;
int n;
while(~scanf("%d",&n))
printf("%lld\n",f[n]+1);
return 0;
}
注意点
记住快速幂的写法。
问题 E: 沙子的质量
题目描述
设有N堆沙子排成一排，其编号为1，2，3，…，N（N< =300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为1 3 5 2我们可以先合并1、2堆，代价为4，得到4 5 2又合并1，2堆，代价为9，得到9 2，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。
输入
第一行一个数N表示沙子的堆数N。 第二行N个数，表示每堆沙子的质量。 a[i]< =1000。
输出
合并的最小代价。
样例输入
4
1 3 5 2
样例输出
22
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 305;
int dp[maxn][maxn];
int sum[maxn];
int main()
{
int n,a[maxn];
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
dp[i][i] = 0;
sum[i] = sum[i-1]+a[i];
}
for(int r = 2; r <= n; r++)
{
for(int i = 1; i <= n-r+1; i++)
{
int j = i+r-1;
dp[i][j] = dp[i+1][j]+sum[j]-sum[i-1];
for(int k = i; k < j; k++)
{
int t = dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
dp[i][j] = min(dp[i][j],t);
}
}
}
printf("%d\n",dp[1][n]);
return 0;
}
注意点
这题和矩阵连乘很像，注意使用一个数组sum[i]保存前缀和，减少计算量。
问题 F: 最长公共子序列
题目描述
一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad” ,顺次选1，3，5个字符就构成子串” cad” ,现给定两个字符串，求它们的最长共公子串。
输入
第一行两个字符串用空格分开。两个串的长度均小于2000 。
输出
最长子串的长度。
样例输入
abccd aecd
样例输出
3
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2005;
int dp[maxn][maxn];
int m[maxn][maxn];
int main()
{
char x[maxn],y[maxn];
scanf("%s %s",x,y);
int lx = strlen(x),ly = strlen(y);
for(int i = 1; i <= lx; i++)
{
for(int j = 1; j <= ly; j++)
{
if(x[i-1] == y[j-1])
{
dp[i][j] = dp[i-1][j-1]+1;
m[i][j] = 1;
}
else if(dp[i-1][j] >= dp[i][j-1])
{
dp[i][j] = dp[i-1][j];
m[i][j] = 2;
}
else
{
dp[i][j] = dp[i][j-1];
m[i][j] = 3;
}
}
}
printf("%d\n",dp[lx][ly]);
return 0;
}
代码（求出最优解）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2005;
int dp[maxn][maxn];
int m[maxn][maxn];
char x[maxn],y[maxn];
void lcs(int xx,int yy)
{
if(!xx || !yy) return;
if(m[xx][yy] == 1)
{
lcs(xx-1,yy-1);
printf("%c",x[xx-1]);
}
else if(m[xx][yy] == 2)
{
lcs(xx-1,yy);
}
else
{
lcs(xx,yy-1);
}
}
int main()
{
scanf("%s %s",x,y);
int lx = strlen(x),ly = strlen(y);
for(int i = 1; i <= lx; i++)
{
for(int j = 1; j <= ly; j++)
{
if(x[i-1] == y[j-1])
{
dp[i][j] = dp[i-1][j-1]+1;
m[i][j] = 1;
}
else if(dp[i-1][j] >= dp[i][j-1])
{
dp[i][j] = dp[i-1][j];
m[i][j] = 2;
}
else
{
dp[i][j] = dp[i][j-1];
m[i][j] = 3;
}
}
}
printf("%d\n",dp[lx][ly]);
lcs(lx,ly);
printf("\n");
return 0;
}
注意点
考试如果出了应该只要求最优值，不要求最优解。
写一写以防万一。
作业三
问题 B: 求数组的最长递减子序列
题目描述
给定一个整数序列，输出它的最长递减（注意不是“不递增”）子序列。
输入
输入包括两行，第一行包括一个正整数N（N<=1000），表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数，整数范围区间为[-30000,30000]。
输出
输入包括两行，第一行包括一个正整数N（N<=1000），表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数，整数范围区间为[-30000,30000]。
样例输入
8
9 4 3 2 5 4 3 2
样例输出
9 5 4 3 2
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
int dp[maxn];
int pre[maxn];
int main()
{
int n,a[maxn],ans[maxn],maxx = 1,maxp = 1;
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
scanf("%d",&a[i]);
dp[i] = 1;
pre[i] = -1;
for(int j = 0; j < i; j++)
{
if(a[i] < a[j] && dp[j]+1 > dp[i])
{
dp[i] = dp[j]+1;
pre[i] = j;
}
}
if(dp[i] > maxx)
{
maxx = dp[i];
maxp = i;
}
}
int cnt = 0;
while(true)
{
ans[cnt++] = a[maxp];
if(pre[maxp] == -1) break;
maxp = pre[maxp];
}
reverse(ans,ans+cnt);
for(int i = 0; i < cnt; i++)
{
printf("%d%c",ans[i]," \n"[i == cnt-1]);
}
return 0;
}
注意点
写起来比较麻烦，掌握的不够熟练。
问题 C: 矩形滑雪场
题目描述
zcb喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。 例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。
输入
第1行:两个数字r，c(1 ≤ r, c ≤ 100)，表示矩阵的行列。第2..r+1行:每行c个数，表示这个矩阵。
输出
仅一行:输出1个整数，表示可以滑行的最大长度。
样例输入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
25
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
int dp[maxn];
struct node
{
int x,y,h;
bool operator < (const node& c) const
{
return h > c.h;
}
}a[maxn];
bool check(int i,int j)
{
if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y) == 1) return true;
return false;
}
int main()
{
int r,c;
scanf("%d %d",&r,&c);
int n = 0;
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
node tmp;
tmp.x = i;
tmp.y = j;
scanf("%d",&tmp.h);
a[n++] = tmp;
}
}
sort(a,a+n);
int ans = 0;
for(int i = 0; i < n; i++)
{
dp[i] = 1;
for(int j = 0; j < i; j++)
{
if(check(i,j) && a[i].h < a[j].h)
dp[i] = max(dp[i],dp[j]+1);
}
ans = max(ans,dp[i]);
}
printf("%d\n",ans);
return 0;
}
问题 D: Homework
题目描述
临近开学了，大家都忙着收拾行李准 备返校，但 I_Love_C 却不为此担心!因为他的心思全在暑假作业上：目前为止还未开动。
暑假作业是很多张试卷，我们这些从试卷里爬出来的人都知道，卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少，但又因为选择题题目都普遍很长。如果有 55 张试卷，其中 44 张是选择题，最后一张是填空题，很明显做最后一张所花的时间要比前 44 张长很多。但如果你只做了选择题，虽然工作量很少，但表面上看起来也已经做了4/5的作业了。
I_Love_C决定就用这样的方法来蒙混过关，他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值（按上面的原理，选择题越多价值当然就越高咯）。
现在就请你帮他安排一下，用他仅剩的一点时间来做最有价值的作业。
输入
测试数据包括多组。每组测试数据以两个整数 M,N(1<M<20,1<N<10000)开头，分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 M 行，每行包括两个整数 T,V(1<T<N,1<V<10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值，输入以 0 0 结束。
输出
对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点 22 位
提示：float 的精度可能不够，你应该使用 double 类型。
样例输入
4 20
4 10
5 22
10 3
1 2
0 0
样例输出
37.00
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
struct node
{
double w,v;
bool operator < (const node &c) const
{
return v/w > c.v/c.w;
}
}a[maxn];
int main()
{
int m;
double n;
while(~scanf("%d %lf",&m,&n))
{
for(int i = 0; i < m; i++)
scanf("%lf %lf",&a[i].w,&a[i].v);
sort(a,a+m);
double ans = 0.0;
for(int i = 0; i < m; i++)
{
if(n >= a[i].w)
{
n -= a[i].w;
ans += a[i].v;
}
else
{
ans += a[i].v/a[i].w*n;
break;
}
}
printf("%.2lf\n",ans);
}
return 0;
}
注意点
w[i]、v[i]、n为double类型处理起来更方便。
问题 E: 区间包含问题
题目描述
已知 n 个左闭右开区间 [a,b)，对其进行 m 次询问，求区间[l,r]最多可以包含 n 个区间中的多少个区间，并且被包含的所有区间都不相交。
输入
输入包含多组测试数据，对于每组测试数据：
第一行包含两个整数 n ,m (1≤n≤100000,1≤m≤100) 。
接下来 n 行每行包含两个整数 a ,b (0≤a
接下来 m 行每行包含两个整数 l ,r (0≤l
输出
对于每组测试数据，输出 m 行，每行包含一个整数。
样例输入
4 3
1 3
2 4
1 4
1 2
1 2
1 3
1 4
样例输出
1
1
2
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
struct node
{
int l,r;
bool operator < (const node& c) const
{
return r < c.r;
}
}a[maxn];
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
for(int i = 0; i < n; i++)
{
scanf("%d %d",&a[i].l,&a[i].r);
}
sort(a,a+n);
for(int cas = 0; cas < m; cas++)
{
int x,y;
scanf("%d %d",&x,&y);
int j = 0;
int ans = 0;
for(int i = 0; i < n; i++)
{
if(a[i].l >= x)
{
if(a[i].r <= y)
{
ans++;
x = a[i].r;
}
else break;
}
}
printf("%d\n",ans);
}
}
return 0;
}
注意点
一道坑爹题，鬼知道排序考虑结束时间相等的时候按开始时间排为什么会错。
实验一
问题 B: 内部收益率
题目描述
输入
输出
对于每组数据，输出仅一行，即项目的IRR，四舍五入保留小数点后两位。
样例输入
1
-1 2
2
-8 6 9
0
样例输出
1.00
0.50
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 15;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int t,cf[maxn];
int main()
{
while(~scanf("%d",&t) && t)
{
for(int i = 0; i <= t; i++)
scanf("%d",&cf[i]);
double l = -1,r = inf;
while(r-l > eps)
{
double m = (l+r)/2;
double sum = 0;
for(int i = 0; i <= t; i++)
{
sum += cf[i]*pow(1+m,t-i);
}
if(sum < 0) r = m;
else l = m;
}
printf("%.2lf\n",l);
}
return 0;
}
问题 D: 奶牛的聚会
题目描述
农历新年马上就要到了，奶牛们计划举办一次聚会庆祝新年的到来。但是，奶牛们并不喜欢走太远的路，这会给他们的聚会带来消极情绪，当一头奶牛的消极指数为Wi，他参加聚会所需行走的距离为Si，那么他就会给聚会带来Si3*Wi的消极情绪。所有奶牛所在位置都在一条直线上，已知所有奶牛的坐标和消极指数，求如何确定聚会地点，使得所有奶牛给聚会带来的消极情绪之和最小，输出消极情绪之和的最小值。
输入
第一行包含一个整数 Ca(Ca<=20) ，表示有 Ca 组测试数据。
对于每组测试数据：第一行包含一个整数n(1<=n<=50000) ，表示奶牛的数量。接下来 n 行每行包含两个浮点数Xi和Wi (-106<=Xi<=106, 0
输出
对于每组测试数据，输出 “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
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int t,n;
double x[maxn],w[maxn];
double l,r;
double fun(double m)
{
double sum = 0;
for(int i = 0; i < n; i++)
{
double d = x[i]-m;
if(d < 0) d = -d;
sum += d*d*d*w[i];
}
return sum;
}
int main()
{
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)
{
double m1 = l+(r-l)/3;
double m2 = r-(r-l)/3;
if(fun(m1) > fun(m2)) l = m1;
else r = m2;
}
printf("Case #%d: %lld\n",cas,ll(fun(l)+0.5));
}
return 0;
}
实验二
问题 A: 最长公共子序列
题目描述
给你一个序列X和另一个序列Z，当Z中的所有元素都在X中存在，并且在X中的下标顺序是严格递增的，那么就把Z叫做X的子序列。
例如：Z=
现给你两个序列X和Y，请问它们的最长公共子序列的长度是多少？
输入
输入包含多组测试数据。每组输入占一行，为两个字符串，由若干个空格分隔。每个字符串的长度不超过100。
输出
对于每组输入，输出两个字符串的最长公共子序列的长度。
样例输入
abcfbc abfcab
programming contest
abcd mnp
样例输出
4
2
0
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int c[maxn][maxn];
int main()
{
char x[maxn],y[maxn];
while(~scanf("%s %s",x,y))
{
int lx = strlen(x);
int ly = strlen(y);
for(int i = 0; i <= lx; i++) c[i][0] = 0;
for(int i = 0; i <= ly; i++) c[0][i] = 0;
for(int i = 1; i <= lx; i++)
{
for(int j = 1; j <= ly; j++)
{
if(x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1]+1;
}
else
{
c[i][j] = max(c[i-1][j],c[i][j-1]);
}
}
}
printf("%d\n",c[lx][ly]);
}
return 0;
}
问题 B: 汽水瓶
题目描述
有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？
输入
输入文件最多包含10组测试数据，每个数据占一行，仅包含一个正整数n(1≤n≤100)，表示小张手上的空汽水瓶数。n=0表示输入结束，你的程序不应当处理这一行。
输出
对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出 0
样例输入
3
10
81
0
样例输出
1
5
40
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int f(int emp)
{
if(emp < 2) return 0;
if(emp == 2) return 1;
return emp/3+f(emp/3 + emp%3);
}
int main()
{
int n;
while(~scanf("%d",&n) && n)
{
printf("%d\n",f(n));
}
return 0;
}
实验三
问题 B: 节食的限制
题目描述
Bessie像她的诸多姊妹一样，因为从Farmer John的草地吃了太多美味的草而长出了太多的赘肉。所以FJ将她置于一个及其严格的节食计划之中。她每天不能吃多过H(5<=H<=45000)公斤的干草。Bessie只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了。她有一个完整的N(1<=n<=50)捆可以给她当作晚餐的干草的清单。她自然想要尽量吃到更多的干草。很自然地，每捆干草只能被吃一次（即使在列表中相同的重量可能出现2次，但是这表示的是两捆干草，其中每捆干草最多只能被吃掉一次）。给定一个列表表示每捆干草的重量Si(1<=Si<=H) ,求Bessie不超过节食的限制的前提下可以吃掉多少干草（注意一旦她开始吃一捆干草就会把那一捆干草全部吃完）。
输入
第一行：两个由空格隔开的整数：H和N，第2到N+1行：第i +1行是一个单独的整数，表示第i捆干草的重量Si。
输出
一个单独的整数表示Bessie在限制范围内最多可以吃多少公斤的干草。
样例输入
56 4
15
19
20
21
样例输出
56
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;
const int maxc = 45005;
int c,n,w[maxn],m[maxn][maxc];
int main()
{
scanf("%d %d",&c,&n);
for(int i = 1; i <= n; i++)
scanf("%d",&w[i]);
for(int i = 0; i <= c; i++) m[0][i] = 0;
for(int i = 0; i <= n; i++) m[i][0] = 0;
for(int i = 1; i <= n; i++)
{
int jMax = min(c,w[i]);
for(int j = 1; j < jMax; j++) m[i][j] = m[i-1][j];
for(int j = jMax; j <= c; j++) m[i][j] = max(m[i-1][j],m[i-1][j-w[i]]+w[i]);
}
printf("%d\n",m[n][c]);
return 0;
}
注意点
j <= c不要写成j <= c（血的教训QAQ）。
问题 C: 汽车费用
题目描述
一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。没有一辆车子行驶超过10公里，一个顾客打算行驶n公里(1<=n<100)，它可以通过无限次的换车来完成旅程。最后要求费用最少。
输入
第一行十个整数分别表示行走1到10公里的费用(<=500)。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。第二行一个整数n表示，旅客的总路程数。
输出
仅一个整数表示最少费用。
样例输入
12 21 31 40 49 58 69 79 90 101
15
样例输出
147
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
int main()
{
int dp[maxn],n;
for(int i = 1; i <= 10; i++) scanf("%d",&dp[i]);
scanf("%d",&n);
for(int i = 11; i <= n; i++) dp[i] = inf;
for(int i = 2; i <= n; i++)
{
for(int j = 1; j < n; j++)
{
dp[i] = min(dp[i],dp[j]+dp[i-j]);
}
}
printf("%d\n",dp[n]);
return 0;
}
问题 D: 法师康的工人
题目描述
三个法师康的工人每天早上6点到工厂开始到三条产品生产线上组装桔子手机。第一个工人在200时刻开始（从6点开始计时，以秒作为单位）在生产线上开始生产，一直到1000时刻。第二个工人，在700时刻开始，在1100时刻结束。第三个工人从1500时刻工作到2100时刻。期间最长至少有一个工人在生产线上工作的连续时间为900秒（从200时刻到1100时刻），而最长的无人生产的连续时间（从生产开始到生产结束）为400时刻（1100时刻到1500时刻）。
你的任务是用一个程序衡量N个工人在N条产品线上的工作时间列表（1≤N≤5000，以秒为单位）。
·最长的至少有一个工人在工作的时间段
·最长的无人工作的时间段（从有人工作开始计）
输入
输入第1行为一个整数N，第2-N+1行每行包括两个均小于1000000的非负整数数据，表示其中一个工人的生产开始时间与结束时间。
输出
输出为一行，用空格分隔开两个我们所求的数。
样例输入
3
200 1000
700 1100
1500 2100
样例输出
900 400
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5005;
const int inf = 0x3f3f3f3f;
struct node
{
int b,e;
bool operator < (const node &c) const
{
return b < c.b;
}
}a[maxn];
int main()
{
int n,ans1,ans2;
scanf("%d",&n);
for(int i = 0; i < n; i++)
scanf("%d %d",&a[i].b,&a[i].e);
sort(a,a+n);
ans1 = a[0].e-a[0].b;
ans2 = 0;
int j = 0;
for(int i = 1; i < n; i++)
{
if(a[i].b < a[j].e)
{
a[j].e = max(a[i].e,a[j].e);
ans1 = max(ans1,a[j].e-a[j].b);
}
else
{
ans2 = max(ans2,a[i].b-a[j].e);
j = i;
}
}
printf("%d %d\n",ans1,ans2);
return 0;
}
问题 E: 配对元素
题目描述
给出2个序列A={a[1]，a[2]，…，a[n]}，B={b[1]，b[2]，…，b[n]}，从A、B中各选出n个元素进行一一配对（可以不按照原来在序列中的顺序），并使得所有配对元素差的绝对值之和最大。
输入
输入的第1行为1个整数n 第2行包含n个整数，题目中的A序列。 第3行包含n个整数，题目中的B序列。
输出
一个数，最大配对。
3与6配对，2与7配对，5与4配对，6与1配对，绝对值之差和为14 对于10%的数据，有n≤20； 对于30%的数据，有n≤100； 对于50%的数据，有n≤1000； 对于100%的数据，有n≤10000；a[i]，b[i]≤1000。
样例输入
4
2 5 6 3
1 4 6 7
样例输出
14
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
int main()
{
int n,a[maxn],b[maxn],sum = 0;
scanf("%d",&n);
for(int i = 0; i < n; i++) scanf("%d",&a[i]);
for(int i = 0; i < n; i++) scanf("%d",&b[i]);
sort(a,a+n);sort(b,b+n);reverse(b,b+n);
for(int i = 0; i < n; i++) sum += abs(a[i]-b[i]);
printf("%d\n",sum);
return 0;
}
实验四
问题 A: 判断日期是否符合格式
题目描述
我们知道一年有12个月，每个月最多有31天，年有平年和闰年之分，本题目要求如果输入一个日期，程序需要判断用户输入的日期是否正确。
提示：测试输入的三个数字中，年份是正数，月份和日期有可能是负数，程序需要对这两个数为负数的情况进行判断。
输入
多组测试用例，对每组测试用例：
用户输入是三个数字，分别表示年，月和日。 例如 2007 10 21 ，表示2007年10月21日，这个输入经过判断是正确的。又例如输入 1993 11 38 ，这个输入经过判断是错误的，因为日期不能超过31天。
输出
程序的输出分为两种，1或者0。1表示输入正确，0表示输入错误。
样例输入
2011 21 10
样例输出
0
代码
#include<bits/stdc++.h>
using namespace std;
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isLeap(int y)
{
if(y%400 == 0) return true;
if(y%4 == 0 && y%100) return true;
return false;
}
int main()
{
int y,m,d;
while(~scanf("%d %d %d",&y,&m,&d))
{
if(m < 0 || m > 12 || d < 0)
{
puts("0");
continue;
}
int dd = days[m];
if(isLeap(y) && m == 2) dd++;
if(d <= dd) puts("1");
else puts("0");
}
return 0;
}
问题 B: 哈夫曼编码
题目描述
给定一只含有小写字母的字符串；输出其哈夫曼编码的长度
输入
第一行一个整数T，代表样例的个数，接下来T行，每行一个字符串，0<T<=2000,字符串长度0<L<=1500.
输出
对于每个字符串，输出其哈夫曼编码长度
样例输入
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq
样例输出
10
51
115
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+5;
struct cmp
{
bool operator()(int a,int b)
{
return a > b;
}
};
int main()
{
int t;char str[maxn];
scanf("%d",&t);
while(t--)
{
int a[26];
memset(a,0,sizeof(a));
priority_queue<int,vector<int>,cmp> pq;
scanf("%s",str);
int len = strlen(str);
for(int i = 0; i < len; i++) a[int(str[i]-'a')]++;
for(int i = 0; i < 26; i++) if(a[i]) pq.push(a[i]);
int ans = 0;
while(pq.size() > 1)
{
int a = pq.top();
pq.pop();
int b = pq.top();
pq.pop();
pq.push(a+b);
ans += a+b;
}
printf("%d\n",ans);
}
return 0;
}
问题 E: 部分和问题
题目描述
给定n个整数，判断是否可以从中选择若干数字，使得他们的和恰好为k。
输入
多组测试用例。
对于每组测试用例，第一行一个正整数n，第二行n个整数，第三行一个整数k。
1≤N≤20，输入整数及k均小于1e8。
输出
若可以使得和为k，输出”Yes”,否则”No”。
样例输入
4
1 2 4 7
13
样例输出
Yes
代码
递归&分治
斐波那契数列
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int mod = 1e9+7;
ll f[maxn] = {1,1};
int main()
{
int n;
for(int i = 2; i < maxn; i++)
f[i] = (f[i-1]+f[i-2])%mod;
while(~scanf("%d",&n))
printf("%lld\n",f[n]);
return 0;
}
求阶乘
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int mod = 1e9+7;
ll f[maxn] = {1,1};
int main()
{
int n;
for(int i = 2; i < maxn; i++)
f[i] = (f[i-1]*ll(i))%mod;
while(~scanf("%d",&n))
printf("%lld\n",f[n]);
return 0;
}
求排列的逆序数
题目描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。
对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。
现给定1,2,…,n的一个排列，求它的逆序数。
输入
第一行是一个整数n，表示该排列有n个数（n <= 100000)。
第二行是n个不同的正整数，之间以空格隔开，表示该排列。
输出
输出该排列的逆序数。
样例输入
6
2 6 3 4 5 1
样例输出
8
提示
- 利用二分归并排序算法（分治）；
- 注意结果可能超过int的范围，需要用long long存储。
代码
//ans为逆序对数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int ans;
void Merge(int a[],int l,int m,int r,int tmp[])
{
int i = l,j = m+1,k = 0;
while(i <= m && j <= r)
{
if(a[i] < a[j]) tmp[k++] = a[i++];
else
{
tmp[k++] = a[j++];
ans += m-i+1;
}
}
while(i <= m) tmp[k++] = a[i++];
while(j <= r) tmp[k++] = a[j++];
for(i = 0; i < k; i++)
{
a[l+i] = tmp[i];
}
}
void mergesort(int a[],int l,int r,int tmp[])
{
if(l < r)
{
int m = l+(r-l)/2;
mergesort(a,l,m,tmp);
mergesort(a,m+1,r,tmp);
Merge(a,l,m,r,tmp);
}
}
void MergeSort(int a[],int n)
{
int *tmp = new int[n];
mergesort(a,0,n-1,tmp);
}
int main()
{
int n,a[maxn];
scanf("%d",&n);
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);
ans = 0;
MergeSort(a,n);
printf("%d\n",ans);
// for(int i = 0; i < n; i++)
// printf("%d%c",a[i]," \n"[i == n-1]);
return 0;
}
动态规划
开餐馆
题目描述
北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, … mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。
输入
标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ，表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行,
第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000).
第2行:n 个地点的位置m1 , m2, … mn ( 1000000 > mi > 0 且为整数,升序排列)
第3行:n 个地点的餐馆利润p1 , p2, … pn ( 1000 > pi > 0 且为整数)
输出
对于每组测试数据可能的最大利润
样例输入
2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30
样例输出
40
30
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 5;
int main()
{
int t,n,k,m[maxn],p[maxn],dp[maxn];
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&k);
for(int i = 0; i < n; i++) scanf("%d",&m[i]);
for(int i = 0; i < n; i++) scanf("%d",&p[i]);
for(int i = 0; i < n; i++)
{
dp[i] = p[i];
for(int j = 0; j < i; j++)
{
if(m[i]-m[j] > k)
dp[i] = max(dp[i],dp[j]+p[i]);
}
}
printf("%d\n",dp[n-1]);
}
return 0;
}
电路布线
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
int n,c[maxn],dp[maxn][maxn],Net[maxn];
void MNS()
{
for(int j = 0; j < c[1]; j++) dp[0][j] = 0;
for(int j = c[1]; j <= n; j++) dp[0][j] = 1;
for(int i = 2; i < n; i++)
{
for(int j = 0; j < c[i]; j++) dp[i][j] = dp[i-1][j];
for(int j = c[i]; j <= n; j++) dp[i][j] = max(dp[i-1][j],dp[i-1][c[i]-1]+1);
}
dp[n][n] = max(dp[n-1][n],dp[n-1][c[n]-1]+1);
}
void BackTracking()
{
int j = n,m = dp[n][n]-1;
for(int i = n; i > 1; i--)
{
if(dp[i][j] != dp[i-1][j])
{
Net[m--] = i;
j = c[i]-1;
}
}
if(j >= c[1]) Net[m--] = 1;
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%d",&c[i]);
MNS();
printf("%d\n",dp[n][n]);
BackTracking();
for(int i = 0; i < dp[n][n]; i++)
{
printf("(%d,%d)\n",Net[i],c[Net[i]]);
}
return 0;
}
/*
10
8 7 4 2 5 1 9 3 10 6
*/
贪心
最优装载
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
struct node
{
int num,w,xi;
bool operator < (const node &c) const {return w < c.w;}
}a[maxn];
bool cmp(node a,node b) {return a.num < b.num;}
int main()
{
int n,c;
scanf("%d %d",&n,&c);
for(int i = 1; i <= n; i++)
{
a[i-1].num = i;
a[i-1].xi = 0;
scanf("%d",&a[i-1].w);
}
sort(a,a+n);
int ans = 0;
for(int i = 0; i < n && c >= a[i].w; i++)
{
c -= a[i].w;
a[i].xi = 1;
ans++;
}
printf("%d\n",ans);
sort(a,a+n,cmp);
for(int i = 0; i < n; i++)
printf("%d%c",a[i].xi," \n"[i == n-1]);
return 0;
}
/*
5 30
15 8 5 7 9 10
*/
最大字段和
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
int main()
{
int n,ans = 0,a[maxn],b[maxn]={0};
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
if(b[i-1] > 0) b[i] = b[i-1]+a[i];
else b[i] = a[i];
ans = max(ans,b[i]);
}
printf("%d\n",ans);
return 0;
}
/*
6
-2 11 -4 13 -5 -2
*/
矩阵连乘
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
int dp[maxn][maxn],m[maxn][maxn],lb[maxn],rb[maxn];
void MatrixChain(int p[],int n)
{
for(int i = 1; i <= n; i++) dp[i][i] = 0;
for(int r = 2; r <= n; r++)
{
for(int i = 1; i <= n-r+1; i++)
{
int j = i+r-1;
dp[i][j] = dp[i+1][j]+p[i-1]*p[i]*p[j];
m[i][j] = i;
for(int k = i+1; k < j; k++)
{
int t = dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
if(t < dp[i][j])
{
dp[i][j] = t;
m[i][j] = k;
}
}
}
}
}
void add(int l,int r)
{
if(r-l < 1) return;
lb[l]++;
rb[r]++;
add(l,m[l][r]);
add(m[l][r]+1,r);
}
int main()
{
int n,p[maxn];
scanf("%d",&n);
for(int i = 0; i <= n; i++)
scanf("%d",&p[i]);
MatrixChain(p,n);
printf("%d\n",dp[1][n]);
add(1,n);
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < lb[i]; j++) printf("(");
printf("A%d",i);
for(int j = 0; j < rb[i]; j++) printf(")");
}
printf("\n");
return 0;
}
/*
6
30 35 15 5 10 20 25
*/
回溯
马走日
问题描述
马在中国象棋以日字形规则移动。
请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。
输入
第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 10, n < 10)
输出
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。
样例输
1
5 4 0 0
样例输出
32
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
int n,m,ans;
int dir[8][2] = {1,2, 1,-2, -1,2, -1,-2, 2,1, 2,-1, -2,1, -2,-1};
bool visited[maxn][maxn];
bool check(int x,int y)
{
if(x >= 0 && x < n && y >= 0 && y < m) return true;
return false;
}
void dfs(int x,int y,int d)
{
if(!check(x,y) || visited[x][y]) return;
if(d == n*m)
{
ans++;
return;
}
visited[x][y] = true;
for(int i = 0; i < 8; i++)
{
int xx = x+dir[i][0];
int yy = y+dir[i][1];
dfs(xx,yy,d+1);
}
visited[x][y] = false;
}
int main()
{
int t,x,y;
scanf("%d",&t);
while(t--)
{
memset(visited,0,sizeof(visited));
scanf("%d %d %d %d",&n,&m,&x,&y);
ans = 0;
dfs(x,y,1);
printf("%d\n",ans);
}
return 0;
}
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/11/02/algorithm-experiment-review/