第一题 中位数
【题目描述】
给出1～n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
【输入格式】
第一行为两个正整数n和b，第二行为1～n的排列。
【输出格式】
输出一个整数，即中位数为b的连续子序列个数。
【样例输入】
| 样例输入1 | 样例输入2 | 样例输入3 |
| 5 4 1 2 3 4 5 |
6 3 1 2 4 5 6 3 |
7 4 5 7 2 4 3 1 6 |
【样例输出】
| 样例输出1 | 样例输出2 | 样例输出3 |
| 2 | 1 | 4 |
【数据范围】
n<=100000。
【分析】
假设b左面有x1个比b大，y1个比b小。b右面有x2个比b打，y2个比b小。那么有x1 + x2 = y1 + y2。移项有，x1 – y1 = – (x2 – y2)。我们先统计b左面每个位置计算出的每个x - y的差值各出现了多少次，然后统计b右面的每个位置计算出的-(x – y)的差值各出现了多少次。由乘法原理将对应的相乘。
第二题 打砖块
【题目描述】
在一个凹槽中放置n层砖块，最上面的一层有n块砖，从上到下每层依次减少一块砖，每块砖都有一个分值，敲掉这块砖就能得到相应的分值，如下图所示。
如果你要敲掉第i层的第j块砖的话，若i=1，你可以直接敲掉它；若i>1，则你必须先敲掉i-1层的第j和第j+1快砖。
你现在可以敲掉最多m块砖，求得分最多能有多少。
【输入格式】
输入文件的第一行为两个正整数n和m；接下来n行，描述这n层砖块上的分值a[i][j]，满足0≤a[i][j] ≤100.
【输出格式】
输出文件仅一行为一个正整数，表示被敲掉砖块的最大价值总和。
【样例输入】
4 5
2 2 3 4
8 2 7
2 3
49
【样例输出】
19
【数据范围】
对于20%的数据，满足1≤n≤10,1≤m≤30;
对于100%的数据，满足1≤n≤50,1≤m≤500。
【分析】
首先按照正常的思想，我们会想到以行划分阶段。但是他是有后效性的。于是我们尝试用列划分阶段。
对于上图橘黄色的点。如果取了他，那么粉色的点都会被取走。设f[i][j][k]表示当前是第i列，共取走j个，其中k个在第i列。f[i][j][k] = max(f[i – 1][j – k][p]) + s[i][k]。其中k – 1 <= p < i（即图中有棕色点的范围），s[i][k]表示第i列最上面k个数的和。
结果为所有f[i][m][k]中最大的。
第三题 序列合并
【题目描述】
有两个长度为N的序列A和B，在A和B中各任取一个数相加可以得到N^2个和，求这N^2个和中最小的N个。
【输入格式】
第一行输入一个正整数N；第二行N个整数Ai 且Ai≤10^9；第三行N个整数Bi，且Bi≤10^9。
【输出格式】
输出仅一行，包含n个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
【样例输入】
5
1 3 2 4 5
6 3 4 1 7
【样例输出】
2 3 4 4 5
【分析】
首先将两个数列排序。第一步固定b中选的数是b[1]，和a中所有的数相加，得出n个数，放入小根堆中。
每次从中取出最小的。将他所选的b[i]下表加1，即变成b[i + 1]。然后放回堆中。
第四题 最小密度路径
【题目描述】
给出了一张有N个点M条边的加权有向无环图，接下来有Q个询问，每个询问包括2个结点X和Y，要求算出从X到Y的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）
【输入格式】
第一行包括2个整数N和M。
第2到第M+1行，每行三个数字A、B、W，表示从A到B有一条权值为W的有向边。
第M+2行只有一个整数Q。
接下来的Q行，每行有两个整数X和Y，表示一个询问。
【输出格式】
对于每个询问输出一行，表示该询问的最小密度路径的密度（保留3位小数），如果不存在从X到Y的一条路径，则输出“OMG！”
【样例输入】
3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3
【样例输入】
5.000
5.500
【数据范围】
对于60%的数据，有1≤N≤10；1≤M≤100,1≤W≤1000,1≤Q≤1000；
对于100%的数据，有1≤N≤50；1≤M≤1000,1≤W≤100000,1≤Q≤100000。
【分析】
f[i][j][k]表示从i到j走k条边做能达到的最小值。然后floyd求解。o(n^4)。
给出的数据有误，存在环。
代码
第一题
#include <stdio.h>
#define MAXN 100010
#define pz 150000
int n,b;
int a[MAXN],f[3 * MAXN],g[3 * MAXN];
int main() {
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
scanf("%d%d",&n,&b);
for (int i = 1;i <= n;++i)
scanf("%d",&a[i]);
int wh,sum,ans;
for (int i = 1;i <= n;++i)
if (a[i] == b) {
wh = i;
break;
}
sum = 0;
++g[pz];
++f[pz];
for (int i = wh - 1;i >0;--i) {
if (a[i] > b)
++sum;
else
--sum;
++f[sum + pz];
}
sum = 0;
for (int i = wh + 1;i <= n;++i) {
if (a[i] < b)
++sum;
else
--sum;
++g[sum + pz];
}
ans = 0;
for (int i = -n;i <= n;++i)
ans += f[i + pz] * g[i + pz];
printf("%d\n",ans);
return 0;
}
第二题
#include <stdio.h>
#include <string.h>
#include <iostream>
#define MAXN 60
#define MAXM 510
using namespace std;
int f[MAXN][MAXM][MAXM],a[MAXN][MAXN],s[MAXN][MAXN];
int n,m,ans;
int main() {
freopen("brike.in","r",stdin);
freopen("brike.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n - i + 1;++j)
scanf("%d",&a[i][j]);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= i;++j)
s[i][j] = s[i][j - 1] + a[j][n - i + 1];
memset(f,255,sizeof(f));
for (int i = 0;i <= n;++i)
f[i][0][0] = 0;
for (int i = 1;i <= n;++i)
f[i][1][1] = a[1][n - i + 1];
for (int i = 1;i <= n;++i)
for (int k = 0;k <= i;++k)
for (int j = k;j <= m;++j)
for (int p = k - 1;p < i;++p)
if ((p >= 0) && (f[i - 1][j - k][p] != -1)) {
f[i][j][k] = max(f[i][j][k],f[i - 1][j - k][p] + s[i][k]);
if ((j == m) && (f[i][j][k] > ans))
ans = f[i][j][k];
}
printf("%d\n",ans);
return 0;
}
第三题
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define MAXN 100010
using namespace std;
struct ss {
int pa,pb,t;
} h[MAXN];
int tot,n,ans;
int a[MAXN],b[MAXN];
int cmp(const void *a,const void *b) {
int c = *(int *)a,d = *(int *)b;
return c - d;
}
void down(int x ) {
int p,q;
p = x;
q = x * 2;
while (q <= tot) {
if ((q + 1 <= tot) && (h[q + 1].t < h[q].t))
++q;
if (h[q].t > h[p].t)
return;
swap(h[q],h[p]);
p = q;
q = p * 2;
}
}
int main() {
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d",&n);
for (int i = 1;i <= n;++i)
scanf("%d",&a[i]);
for (int j = 1;j <= n;++j)
scanf("%d",&b[j]);
qsort(a + 1,n,sizeof(int),cmp);
qsort(b + 1,n,sizeof(int),cmp);
for (int i = 1;i <= n;++i) {
h[i].pa = i;
h[i].pb = 1;
h[i].t = a[i] + b[1];
}
tot = n;
for (int i = tot;i > 0;--i)
down(i);
for (int i = 1;i <= n;++i) {
ans = h[1].t;
printf("%d ",ans);
++h[1].pb;
h[1].t = a[h[1].pa] + b[h[1].pb];
down(1);
}
return 0;
}
第四题
#include <stdio.h>
#define MAXINT 10000010
int n,m,x,y,z,tot;
double f[51][51][501],dis[51][51];
int main() {
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j)
for (int k = 0;k <= n;++k)
f[i][j][k] = MAXINT;
for (int i = 1;i <= m;++i) {
scanf("%d%d%d",&x,&y,&z);
if (z < f[x][y][1])
f[x][y][1] = z;
}
for (int p = 2;p <= n;++p)
for (int k = 1;k <= n;++k)
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j)
if (f[i][k][p - 1] + f[k][j][1] < f[i][j][p])
f[i][j][p] = f[i][k][p - 1] +f[k][j][1];
scanf("%d",&tot);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j)
dis[i][j] = MAXINT;
for (int i = 1;i <= n;++i)
for (int j = 1;j <= n;++j)
for (int k = 1;k <= n;++k)
if (f[i][j][k] < MAXINT)
if (f[i][j][k] / k < dis[i][j])
dis[i][j] = f[i][j][k] / k;
for (int i = 1;i <= tot;++i) {
scanf("%d%d",&x,&y);
if (dis[x][y] < MAXINT)
printf("%.3lf\n",dis[x][y]);
else
printf("OMG!\n");
}
return 0;
}
后记
今天的题目写的很悲剧。因为身体感觉很差吧。放假调整一下，下午去买点感冒药。太冷了。
第二题打出了数组观察结果交题的时候忘记删掉了。第四题没有判断动归数组是否有解就直接去计算dis。两百分消失。