A. Tricky Sum
居然没有一眼秒掉。。自闭了
1 到 n 的和很好算，小于等于 n 的所有 2 的幂次之和也很好算，把后面那个东西减两次就做完了。
一遍 AC。
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --> 0) {
int n; cin >> n;
lli ans = (1ll * n) * 1ll * (n + 1); ans >>= 1;
for (int i = 0; i <= 30; ++i) {
if ((1 << i) <= n) ans -= (1 << (i + 1));
} cout << ans << endl;
}
return 0;
}
B. Queries on a String
直接模拟即可。循环写起来可能有些不便，拿 deque 暴力模拟也能过。
一遍 AC。
const int MAXN = 10000 + 10;
int m;
char ss[MAXN];
char tt[MAXN];
void Process(int l, int r, int k) {
std::deque<char> s;
for (int i = l; i <= r; ++i) {
s.push_back(ss[i]);
}
for (int i = 1; i <= k; ++i) {
s.push_front(s.back());
s.pop_back();
}
for (int i = l; i <= r; ++i) {
ss[i] = s.front(); s.pop_front();
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> (ss + 1); cin >> m;
rep (i, 1, m) {
int l, r, k; cin >> l >> r >> k;
k %= (r - l + 1);
Process(l, r, k);
}
cout << ss + 1 << endl;
return 0;
}
C. Nearest Vectors
使用 atan2 函数计算方位角，按照方位角排序后相邻的计算一下角度，更新答案即可。
#错误警示：调了一场没调出来，后来发现调用 abs(x) 而不是 std::abs(x) 居然会重载成 int abs(int x)。
const int MAXN = 100000 + 10;
struct T {
long double x; int id; T() {x = id = 0;};
bool operator < (const T &th) const {
return x < th.x;
}
} ts[MAXN];
int n;
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
scanf("%d", &n);
rep (i, 1, n) {
int x, y; scanf("%d %d", &x, &y); ts[i].id = i;
ts[i].x = atan2((long double) y, (long double) x);
} std::sort(ts + 1, ts + 1 + n);
ts[++n] = ts[1];
long double ang = 1e15;
long double pi = acos((long double) -1);
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= n - 1; ++i) {
long double relangle = std::abs(ts[i + 1].x - ts[i].x);
if (relangle > pi) relangle = pi * 2.0 - relangle;
if (relangle < ang) {
ang = relangle; ans1 = ts[i].id, ans2 = ts[i + 1].id;
}
} cout << ans1 << ' ' << ans2 << endl;
return 0;
}
D. Igor In the Museum
拿并查集维护联通块，联通块内的答案相同，然后 BFS 求答案即可。
一遍 AC。
#错误警示：搜索的时候一定不要忘了记录是否访问过。
const int MAXN = 1000 + 10;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n, m, k;
char ss[MAXN][MAXN];
int ans[MAXN * MAXN];
bool vis[MAXN][MAXN];
struct DSU {
int fa[MAXN * MAXN];
int Find(int x) {
return !fa[x] ? x : fa[x] = Find(fa[x]);
}
void Merge(int x, int y) {
x = Find(x); y = Find(y);
if (x != y) fa[x] = y;
}
} dsu;
int gid(int x, int y) {
return (x - 1) * m + y;
}
struct ND { int x, y; };
int search(int x, int y) {
std::queue<ND> q;
q.push({x, y});
int ans = 0;
while (!q.empty()) {
int ux = q.front().x, uy = q.front().y; q.pop();
if (vis[ux][uy]) continue;
vis[ux][uy] = true;
for (int dr = 0; dr <= 3; ++dr) {
int nx = ux + dx[dr], ny = uy + dy[dr];
if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
// std::cerr << nx << '-' << ny << endl;
if (ss[nx][ny] == '*') ++ans;
else q.push({nx, ny});
}
} return ans;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
rep (i, 1, n) {
cin >> (ss[i] + 1);
rep (j, 1, m) {
if (ss[i][j] == '.') rep (dr, 0, 3) {
int nx = i + dx[dr], ny = j + dy[dr];
if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
if (ss[nx][ny] == '.') {
dsu.Merge(gid(i, j), gid(nx, ny));
}
}
}
}
for (int i = 1; i <= k; ++i) {
int fx, fy; cin >> fx >> fy;
int ansid = dsu.Find(gid(fx, fy));
if (!ans[ansid]) ans[ansid] = search(fx, fy);
cout << ans[ansid] << endl;
}
return 0;
}
或者你甚至可以不用并查集维护连通性，先扫一遍矩阵，遇到点的时候就做一遍 dfs 求出每个点属于哪个联通块和答案，最后 (O(1)) 输出，写起来更舒服一些。
一遍 AC。
const int MAXN = 1000 + 10;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int n, m, k;
char ss[MAXN][MAXN];
int bel[MAXN][MAXN], cnt, aans[MAXN * MAXN];
int ans = 0;
void dfs(int x, int y, int bl) {
if (bel[x][y]) return;
bel[x][y] = bl;
for (int dr = 0; dr < 4; ++dr) {
int nx = x + dx[dr], ny = y + dy[dr];
if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
if (ss[nx][ny] == '*') ++ans;
else dfs(nx, ny, bl);
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
rep (i, 1, n) {
cin >> (ss[i] + 1);
}
rep (i, 1, n) {
rep (j, 1, m) {
if (ss[i][j] == '.') {
++cnt; ans = 0; dfs(i, j, cnt);
aans[cnt] = ans;
}
}
}
rep (i, 1, k) {
int x, y; cin >> x >> y; cout << aans[bel[x][y]] << endl;
}
return 0;
}
E. Chocolate Bar
记忆化搜索。设 f[i][j][k] 表示现在我有一个 (i imes j) 的巧克力块，要从中选取大小为 (k) 的最小花费。
转移直接枚举在哪一行 / 列下刀，以及从这一块中要拿走的大小。
看似时间复杂度是 (O(Tnmk)) 的，但实际上记忆化数组可以复用，并不需要每组数据都清空。
#错误警示：好好处理边界条件，想想 0 到底能不能取到。
const int MAXN = 30 + 10;
const int MAXK = 50 + 10;
lli dp[MAXN][MAXN][MAXK];
lli search(int a, int b, int c) {
if (c == 0) return 0;
if (c == a * b) return 0;
if (dp[a][b][c] != -1) return dp[a][b][c];
dp[a][b][c] = (1ll << 60);
for (int x = 1; x < a; ++x) {
for (int p = 0; p <= c; ++p) {
dp[a][b][c] = std::min(dp[a][b][c], search(a - x, b, p) + search(x, b, c - p) + 1ll * b * b);
}
}
for (int x = 1; x < b; ++x) {
for (int p = 0; p <= c; ++p) {
dp[a][b][c] = std::min(dp[a][b][c], search(a, b - x, p) + search(a, x, c - p) + 1ll * a * a);
}
}
return dp[a][b][c];
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T;
memset(dp, -1, sizeof dp);
while (T --> 0) {
int n, m, k; cin >> n >> m >> k;
cout << search(n, m, k) << endl;
}
return 0;
}
F
计算几何……