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