A B 都是垃圾题,不说了。
C. The Labyrinth
和之前做过的某道题相似,用 DFS 确定一下每个位置属于哪个联通块,然后确定一下每个 *
周围有哪几个联通块,去重可以直接 std::set
实现。
const int MAXN = 1000 + 10;
int n, m;
int gid(int x, int y) { return m * (x - 1) + y; }
int bel[MAXN][MAXN], siz[MAXN * MAXN], belcnt;
char mat[MAXN][MAXN];
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int sz;
void dfs(int ux, int uy, int bl) {
if (bel[ux][uy]) return;
++sz;
bel[ux][uy] = bl;
for (int dr = 0; dr < 4; ++dr) {
int nx = ux + dx[dr], ny = uy + dy[dr];
if (nx < 1 || ny < 1 || nx > n || ny > m || mat[nx][ny] == '*') continue;
dfs(nx, ny, bl);
}
}
int main() {
scanf("%d %d", &n, &m);
rep (i, 1, n) scanf("%s", mat[i] + 1);
rep (i, 1, n) {
rep (j, 1, m) {
if (mat[i][j] != '.') continue;
sz = 0;
if (!bel[i][j]) { dfs(i, j, ++belcnt); siz[belcnt] = sz; }
}
}
rep (i, 1, n) {
rep (j, 1, m) {
if (mat[i][j] == '.') { printf("."); continue; }
int base_bel = 0;
std::set<int> bels;
for (int dr = 0; dr < 4; ++dr) {
int nx = i + dx[dr], ny = j + dy[dr];
if (nx < 1 || ny < 1 || nx > n || ny > m || mat[nx][ny] == '*') continue;
bels.insert(bel[nx][ny]);
}
int ans = 1;
for (auto b : bels) ans += siz[b];
printf("%d", ans % 10);
}
puts("");
}
return 0;
}
D. Longest k-Good Segment
可以双指针,也可以二分查找。
const int MAXN = 5e5 + 10;
int n, k;
int aa[MAXN];
int nums[MAXN * 2], cnt;
void Add(int x) {
if (nums[aa[x]] == 0) ++cnt;
++nums[aa[x]];
}
void Del(int x) {
if (nums[aa[x]] == 1) --cnt;
--nums[aa[x]];
}
int main() {
n = read(); k = read();
rep (i, 1, n) {
aa[i] = read();
}
int l = 1, r = 0, tl = 0, tr = -1;
while (r < n) {
while (r <= n && cnt <= k) Add(++r);
Del(r--);
if (tr - tl + 1 < r - l + 1) {
tr = r; tl = l;
}
Del(l++);
}
printf("%d %d\n", tl, tr);
return 0;
}
const int MAXN = 5e5 + 10;
int n, k;
int aa[MAXN];
int nums[MAXN * 2], cnt;
void Add(int x) {
if (nums[aa[x]] == 0) ++cnt;
++nums[aa[x]];
}
void Del(int x) {
if (nums[aa[x]] == 1) --cnt;
--nums[aa[x]];
}
int tl = 0, tr = 0;
bool check(int mid) {
tl = 0, tr = 0;
memset(nums, 0, sizeof nums); cnt = 0;
for (int i = 1; i <= mid - 1; ++i) Add(i);
for (int l = 1; l + mid - 1 <= n; ++l) {
int r = l + mid - 1;
Add(r);
if (cnt <= k) {
tl = l, tr = r;
return true;
}
Del(l);
}
return false;
}
int main() {
n = read(); k = read();
rep (i, 1, n) {
aa[i] = read();
}
int l = 1, r = n, ans = 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
check(ans);
printf("%d %d\n", tl, tr);
return 0;
}
E. Sum of Remainders
\(\sum (n - \lfloor\frac{n}{i}\rfloor)i\)
然后数论分块。
const lli HA = 1e9 + 7;
lli n, m;
lli ans;
lli fastpow(lli a, lli b, lli p) {
lli r = 1; while (b) { if (b & 1) r = r * a % p; a = a * a % p; b >>= 1; } return r;
}
int main() {
lli inv2 = fastpow(2, HA - 2, HA);
n = readll(); m = readll();
ans = n % HA * (m % HA) % HA;
for (lli l = 1, r = 0; l <= std::min(n, m); l = r + 1) {
r = std::min(m, n / (n / l));
ans = (ans - ((n / l) % HA) * ((l + r) % HA) % HA * ((r - l + 1) % HA) % HA * inv2 % HA + HA) % HA;
}
printf("%lld\n", ans);
return 0;
}