浪在ACM集训队寒假集训第二场补题题解

接昨天的题解,这次是后四个当时没做出来的题的补题。


C - Leha and Function(CodeForces841C)

Leha like all kinds of strange things. Recently he liked the function F(n, k). Consider all possible k-element subsets of the set [1, 2, …, n]. For subset find minimal element in it. F(n, k) — mathematical expectation of the minimal element among all k-element subsets.

But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays A and B, each consists of m integers. For all i, j such that 1 ≤ i, j ≤ m the condition Ai ≥ Bj holds. Help Leha rearrange the numbers in the array A so that the sum Σ(i=1 to m)F(A’i,Bi) is maximally possible, where A’ is already rearranged array.

Input

First line of input data contains single integer m (1 ≤ m ≤ 2·105) — length of arrays A and B.

Next line contains m integers a1, a2, …, am (1 ≤ ai ≤ 109) — array A.

Next line contains m integers b1, b2, …, bm (1 ≤ bi ≤ 109) — array B.

Output
Output m integers a’1, a’2, …, a’m — array A’ which is permutation of the array A.

Examples

Input
5
7 3 5 3 4
2 1 3 2 3
Output
4 7 3 5 3

Input
7
4 6 5 8 8 2 6
2 1 2 2 1 1 2
Output
2 6 4 5 8 8 6

感谢lsr大佬的博客为补题提供思路援助:https://kangyupl.oschina.io/2019/01/20/cf841c/

又是一个被题目描述吓倒的题。。。上来就整什么数学期望这种玄乎的东西,但是如果读到后面就会发现其实。。。后边更难。。

题目上来先介绍了一个函数F(n,k),代表从一个有着1,2,3…n这些元素的集合里面抽一个长度为k的子集,完事每个子集求一下最小值,最后得到全部最小值的平均值。

等等,这不是数学期望吗?对啊(便乘百度百科),在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。它反映随机变量平均取值的大小。

既然反映的是随机变量(这里自然就是指每个k大小子集的最小值)的平均值,那需要算出来吗?其实并不用,这里只是用到这个规律。题目给你了两个元素个数相同的集合A和B,要求重新排列A中的元素,让F(Ai,Bi)的总和为最大值。

要让F取得最大值,就要考虑两个参数的取值问题。但是有两个参数,怎么控制呢?令其中一个先不动,我们分析另一个。假设现在n固定,k变化,n是一个元素是1,2,3,4…n的集合,k是取出子集的大小。模拟一下吧,如果n是123,k是2,那么所有可能的子集就是12,13,23,最小值分别是1,1,2,如果k是1,那么所有可能的子集就是1,2,3,最小值分别是1,2,3,看到最小值的平均值变大了。再模拟几组数据,发现依然符合这个规律。直观的感受就是当k变大时比较小的数字会变多,最小值的平均自然就拉下来了。

显然,k不变时n越大结果越大,因为总会有更大的最小值参入运算。

ok,满足简单的单调性,那么要让结果最大化怎么办呢?显然是n最大,k最小。那么自然想到反序和,也就是贪心的一种。

所以对应关系就明确了。A的第一大对应B的第一小,A的第二大对应B的第二小……这样只需要写出算法来找出这个重新排列的A就好了。

写法上基本参照了lsr的思路,感觉比较通俗易懂。仅仅对b数组做简单处理,记录一下每个位置的编号,然后对a升序排序,b降序排序(其实反过来也行,我就是反过来写的)由于每个值都绑定了一个编号,这样在输出的时候就可以“对号入座”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cmath>
#include <algorithm>
#define maxn 2333333
using namespace std;
struct Num {
int val;
int id;
bool operator<(const Num &rhs)const {
return val < rhs.val;
}
};
Num b[maxn];
int a[maxn];
int ans[maxn];
int m;

bool cmp(const int &a, const int &b) {
return a > b;
}

int main() {
ios::sync_with_stdio(false);
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i].val;
b[i].id = i;
}
sort(a + 1, a + m + 1, cmp);
sort(b + 1, b + m + 1);
for (int i = 1; i <= m; i++) {
ans[b[i].id] = a[i];
}
for (int i = 1; i <= m; i++)
cout << ans[i] << " ";
system("pause");
return 0;
}

G - New Year and Domino(CodeForces611C)

They say “years are like dominoes, tumbling one after the other”. But would a year fit into a grid? I don’t think so.

Limak is a little polar bear who loves to play. He has recently got a rectangular grid with h rows and w columns. Each cell is a square, either empty (denoted by ‘.’) or forbidden (denoted by ‘#’). Rows are numbered 1 through h from top to bottom. Columns are numbered 1 through w from left to right.

Also, Limak has a single domino. He wants to put it somewhere in a grid. A domino will occupy exactly two adjacent cells, located either in one row or in one column. Both adjacent cells must be empty and must be inside a grid.

Limak needs more fun and thus he is going to consider some queries. In each query he chooses some rectangle and wonders, how many way are there to put a single domino inside of the chosen rectangle?

Input

The first line of the input contains two integers h and w (1 ≤ h, w ≤ 500) – the number of rows and the number of columns, respectively.

The next h lines describe a grid. Each line contains a string of the length w. Each character is either ‘.’ or ‘#’ — denoting an empty or forbidden cell, respectively.

The next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of queries.

Each of the next q lines contains four integers r1i, c1i, r2i, c2i (1 ≤ r1i ≤ r2i ≤ h, 1 ≤ c1i ≤ c2i ≤ w) — the i-th query. Numbers r1i and c1i denote the row and the column (respectively) of the upper left cell of the rectangle. Numbers r2i and c2i denote the row and the column (respectively) of the bottom right cell of the rectangle.

Output

Print q integers, i-th should be equal to the number of ways to put a single domino inside the i-th rectangle.

Examples

Input
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8
Output
4
0
10
15
Input
7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8
Output
53
89
120
23
0
2

Note

A red frame below corresponds to the first query of the first sample. A domino can be placed in 4 possible ways.

题目大意:给一个长宽给定的矩阵,里面的.代表空位,#代表不是空位,连续的两个横向或者竖向的空位可以放一个东西,有q次询问,每次询问问给定的区域能放多少个。

感谢lyj大佬的博客为补题提供思路援助:https://blog.csdn.net/weixin_43537190/article/details/86561402?tdsourcetag=s_pctim_aiomsg

简单的预处理+回答每个询问。状态是固定的,所以支持预处理答案。开两个辅助二维数组crosswiseAnswer和verticalAnswer分别记录水平方向所有可能的答案和垂直方向所有可能的答案。统计答案时分两步走,因为同一区域横向和竖向都有可能的答案,两者相加才是总答案。扫描时发现本区域有可行方案则将当前点的值置为1,然后去累加之前的答案,最后回答询问时控制一个坐标不变,另一个坐标用后减前就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cmath>
#include <algorithm>
#define maxn 2333
using namespace std;
int h, w;
char matrix[maxn][maxn];
int crosswiseAnswer[maxn][maxn];
int verticalAnswer[maxn][maxn];
int q;
int r1, c1, r2, c2;

int main() {
ios::sync_with_stdio(false);
cin >> h >> w;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> matrix[i][j];
if (matrix[i][j] == '.') {
if (matrix[i][j - 1] == '.')
crosswiseAnswer[i][j] = 1;
if (matrix[i - 1][j] == '.')
verticalAnswer[i][j] = 1;
}
crosswiseAnswer[i][j] += crosswiseAnswer[i][j - 1];
verticalAnswer[i][j] += verticalAnswer[i - 1][j];
}
}
cin >> q;
while (q--) {
cin >> r1 >> c1 >> r2 >> c2;
int ans = 0;
for (int i = r1; i <= r2; i++) {
ans += crosswiseAnswer[i][c2] - crosswiseAnswer[i][c1];
}
for (int j = c1; j <= c2; j++) {
ans += verticalAnswer[r2][j] - verticalAnswer[r1][j];
}
cout << ans << endl;
}
system("pause");
return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:浪在ACM集训队寒假集训第二场补题题解

文章作者:Shawn Zhou

发布时间:2019年01月21日 - 17:01

最后更新:2019年01月22日 - 16:01

原始链接:http://shawnzhou.xyz/2019/01/21/19-01-21-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%