H-index
題目大意
計(jì)算學(xué)術(shù)H指數(shù)咖祭。如果一個(gè)人有x篇論文各自被引用至少x次，那么最大可能的x即為它的H指數(shù)呕屎。
思路
優(yōu)化求h指數(shù)過(guò)程，最初intuitive solution只想到了二分查找合適的x，而求解x的過(guò)程并沒(méi)有優(yōu)化。實(shí)際很簡(jiǎn)單：通過(guò)樹(shù)狀數(shù)組維護(hù)大于x的總數(shù)。
代碼
#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
題目大意
翻牌游戲，每次翻一個(gè)斜線晌砾，求最少經(jīng)過(guò)多少步可以把棋盤(pán)里的格子翻為黑色。
思路
感覺(jué)這道題比較難烦磁，一道DFS題目养匈，但需要一些數(shù)據(jù)預(yù)處理：
-
把每個(gè)格子所處的正反斜線標(biāo)號(hào)哼勇，使得每條斜線上的格子編號(hào)一致，如下圖所示呕乎，對(duì)于n=3的情況积担，有此編號(hào)：
排序示例 - 由上圖不難看出，每個(gè)格子都是正反斜線的焦點(diǎn)猬仁，故用數(shù)組G維護(hù)其相交線的編號(hào)及焦點(diǎn)是否為黑色帝璧。
- DFS每個(gè)焦點(diǎn)，決定是否翻當(dāng)前這個(gè)斜線的牌湿刽。由于一定有解的烁，且整個(gè)DFS的策略只與是否翻第一個(gè)牌有關(guān)，故我們用cnt數(shù)組記錄 所到交點(diǎn)的翻/不翻的次數(shù)诈闺，兩者交換即為另一種情況（即是否翻第一個(gè)牌）渴庆。
代碼
#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
題目大意
給你若干個(gè)0~9的數(shù)字，每個(gè)數(shù)字?jǐn)?shù)量為 Ai, i∈[0,9]买雾。讓你排列這些數(shù)字，使其按a+b-c+d-e+...這樣的加減交替得出的最終解為11的倍數(shù)杨帽。
思路
這道題相對(duì)第二題簡(jiǎn)單些漓穿，可以通過(guò)dp解決，但需要滾動(dòng)數(shù)組降維注盈。
dp[type][j][k]代表對(duì)于當(dāng)前數(shù)字i晃危，對(duì)j個(gè)執(zhí)行加法、對(duì)A[i]-j個(gè)執(zhí)行減法時(shí)老客，是否存在mod 11后結(jié)果為k的情況僚饭。
由于最終會(huì)有 總數(shù)/2 個(gè)執(zhí)行加法的，故dp[type][sum/2][0]即為劃分一半的數(shù)執(zhí)行加法胧砰、另一半執(zhí)行減法后鳍鸵，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;
}
