KickStart 2019 Round H题解

H-index

题目链接

题目大意

计算学术H指数。如果一个人有x篇论文各自被引用至少x次,那么最大可能的x即为它的H指数。

思路

优化求h指数过程,最初intuitive solution只想到了二分查找合适的x,而求解x的过程并没有优化。实际很简单:通过树状数组维护大于x的总数。

代码

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
47
48
49
50
#include <vector>
#include <iostream>

using namespace std;

int N, M, tmp;
int MAXN = 1e5+10;
vector<int> a (MAXN+1);

void update(int data, int idx) {
while (idx <= MAXN) {
a[idx] += data;
idx += -idx & idx;
}
}

int query(int idx) {
int res = 0;
while (idx) {
res += a[idx];
idx -= -idx & idx;
}
return res;
}

int bisearch(int idx) {
int l = 0, r = MAXN-1;
while (l < r) {
int mid = l + (r-l) / 2, cnt = idx + 1 - query(mid-1);
if (cnt >= mid) l = mid + 1;
else r = mid;
}
return l-1;
}

int main(int argc, const char * argv[]) {
cin >> N;
for (int kase = 1; kase <= N; ++kase) {
cin >> M;
cout << "Case #" << kase << ":";
fill(begin(a), end(a), 0);
for (int i = 0; i < M; ++i) {
cin >> tmp;
update(1, tmp);
cout << " " << bisearch(i);
}
cout << endl;
}
return 0;
}

Diagonal Puzzle

题目链接

题目大意

翻牌游戏,每次翻一个斜线,求最少经过多少步可以把棋盘里的格子翻为黑色。

思路

感觉这道题比较难,一道DFS题目,但需要一些数据预处理:

  1. 把每个格子所处的正反斜线标号,使得每条斜线上的格子编号一致,如下图所示,对于n=3的情况,有此编号:
    排序示例
  2. 由上图不难看出,每个格子都是正反斜线的焦点,故用数组G维护其相交线的编号及焦点是否为黑色。
  3. DFS每个焦点,决定是否翻当前这个斜线的牌。由于一定有解,且整个DFS的策略只与是否翻第一个牌有关,故我们用cnt数组记录 所到交点的翻/不翻的次数,两者交换即为另一种情况(即是否翻第一个牌)。

代码

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
47
48
49
50
51
52
53
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int T, N;
const int MAXN = 500;
vector<string> mat (101, "");
vector<bool> vis (MAXN, false);
vector<vector<pair<int, bool>>> G (MAXN, vector<pair<int, bool>> ());
vector<int> cnt (2, 0); // 0: step for not change, 1: step for change

void dfs(int idx, bool changed) {
vis[idx] = true;
cnt[changed]++;
for (auto& pir: G[idx]) {
if (!vis[pir.first])
dfs(pir.first, pir.second ^ changed);
}
}

int main(int argc, const char * argv[]) {
cin >> T;
for (int kase = 1; kase <= T; ++kase) {
cin >> N;
for (int i = 0; i < N; ++i)
cin >> mat[i];

for_each(G.begin(), G.end(), [](auto& pirs) { pirs.clear(); });
fill(vis.begin(), vis.end(), false);

for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
int lidx = i + j, ridx = N + (N+i-1) + (N-j-1);
G[lidx].emplace_back(ridx, mat[i][j] == '.');
G[ridx].emplace_back(lidx, mat[i][j] == '.');
}
}

int pircnt = 2 * (2 * N - 1), res = 0;
for (int i = 0; i < pircnt; ++i) {
if (!vis[i]) {
cnt[0] = cnt[1] = 0;
dfs(i, false);
res += min(cnt[0], cnt[1]);
}
}
cout << "Case #" << kase << ": " << res << endl;
}

return 0;
}

Elevanagram

题目链接

题目大意

给你若干个0~9的数字,每个数字数量为 Ai, i∈[0,9]。让你排列这些数字,使其按a+b-c+d-e+…这样的加减交替得出的最终解为11的倍数。

思路

这道题相对第二题简单些,可以通过dp解决,但需要滚动数组降维。
dp[type][j][k]代表对于当前数字i,对j个执行加法、对A[i]-j个执行减法时,是否存在mod 11后结果为k的情况。
由于最终会有 总数/2 个执行加法的,故dp[type][sum/2][0]即为划分一半的数执行加法、另一半执行减法后,mod 11为0的情况是否存在,即为题解。

代码

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
47
48
49
50
51
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int T;
const int MAXN = 1000;
vector<int> A (10, 0);
vector<vector<vector<bool>>> dp;

int main(int argc, const char * argv[]) {

cin >> T;
for (int kase = 1; kase <= T; ++kase) {
cout << "Case #" << kase << ": ";

int tot = 0;
for (int i = 1; i <= 9; ++i) {
cin >> A[i];
// if large than 21/22, the overflow value is no need to be calculate
A[i] = min(A[i], 20 + (A[i] & 1));
tot += A[i];
}

dp = vector<vector<vector<bool>>> (2, vector<vector<bool>> (MAXN+10, vector<bool> (11, false)));
int type = 0;
dp[type][0][0] = true;
for (int i = 1; i <= 9; ++i) {
type = 1-type;

for (auto& subarr: dp[type])
fill(subarr.begin(), subarr.end(), false);

for (int lcnt = 0; lcnt <= A[i]; ++lcnt) {
for (int rcnt = 0; rcnt < MAXN-lcnt; ++rcnt) {
for (int premod = 0; premod <= 10; ++premod) {
int curmod = (premod + lcnt * i - (A[i]-lcnt) * i + 11) % 11;
while (curmod < 0) curmod += 11;
dp[type][lcnt + rcnt][curmod] = dp[1-type][rcnt][premod] || dp[type][lcnt + rcnt][curmod];
}
}
}
}

cout << (dp[type][tot >> 1][0] ? "YES" : "NO") << endl;;

}

return 0;
}