H-index
题目大意
计算学术H指数。如果一个人有x篇论文各自被引用至少x次，那么最大可能的x即为它的H指数。
思路
优化求h指数过程，最初intuitive solution只想到了二分查找合适的x，而求解x的过程并没有优化。实际很简单：通过树状数组维护大于x的总数。
代码
#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题目，但需要一些数据预处理：
-
把每个格子所处的正反斜线标号，使得每条斜线上的格子编号一致，如下图所示，对于n=3的情况，有此编号：
排序示例 - 由上图不难看出，每个格子都是正反斜线的焦点，故用数组G维护其相交线的编号及焦点是否为黑色。
- DFS每个焦点，决定是否翻当前这个斜线的牌。由于一定有解，且整个DFS的策略只与是否翻第一个牌有关，故我们用cnt数组记录 所到交点的翻/不翻的次数，两者交换即为另一种情况（即是否翻第一个牌）。
代码
#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的情况是否存在，即为题解。
代码
#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;
}
