#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
const int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
int main() {
int n, m;
cin >> n >> m;
vector<string> s(n);
rep(i, n) cin >> s[i];
vector ans(n, string(m, '*'));
rep(i, n)rep(j, m) {
if (s[i][j] == '*') continue;
int x = 0;
rep(v, 8) {
int ni = i+di[v], nj = j+dj[v];
if (ni < 0 or ni >= n or nj < 0 or nj >= m) continue;
if (s[ni][nj] == '*') x++;
}
ans[i][j] = '0'+x;
}
rep(i, n) cout << ans[i] << '\n';
return 0;
}
活动打卡代码
AcWing 462. 扫雷游戏
算法
(数位 dp)
令 $g(x) = \sum\limits_{k=0}^x f(k)$，则有 $\sum\limits_{k=L}^R f(k) = g(R) - g(L-1)$
$
g(x) = \sum\limits_{k=0}^x\sum\limits_{i} [\text{从} ~k ~\text{的第} ~i ~\text{个字符开始包含} ~S] = \sum\limits_i \text{在} ~x ~\text{以内从第} ~i ~\text{个字符开始包含} ~S ~\text{的整数个数}
$
然后跑数位dp即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
ll g(string s, ll x) {
int n = s.size();
vector<int> a;
while (x) {
a.push_back(x%10);
x /= 10;
}
reverse(a.begin(), a.end());
int m = a.size();
ll res = 0;
rep(si, m-n+1) {
vector dp(2, vector<ll>(2));
dp[0][0] = 1;
rep(i, m) {
vector p(2, vector<ll>(2));
swap(dp, p);
rep(j, 2)rep(k, 2)rep(d, 10) {
if (si <= i and i < si+n) {
if (s[i-si]-'0' != d) continue;
if (k == 0 and d == 0) continue; // leading zero
}
int nj = j, nk = k;
if (j == 0) {
if (d < a[i]) nj = 1;
if (d > a[i]) continue;
}
if (d) nk = 1;
dp[nj][nk] += p[j][k];
}
}
res += dp[0][1]+dp[1][1];
}
return res;
}
void solve() {
string s;
ll l, r;
cin >> s >> l >> r;
ll ans = g(s, r) - g(s, l-1);
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}
活动打卡代码
LeetCode 1638. 统计只差一个字符的子串数目
class Solution {
public:
int countSubstrings(string s, string t) {
int n = s.size(), m = t.size();
vector dpl(n+1, vector<int>(m+1));
vector dpr(n+1, vector<int>(m+1));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
dpl[i+1][j+1] = s[i] == t[j] ? (dpl[i][j]+1) : 0;
}
}
for (int i = n-1; i >= 0; --i) {
for (int j = m-1; j >= 0; --j) {
dpr[i][j] = s[i] == t[j] ? (dpr[i+1][j+1]+1) : 0;
}
}
int res = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (s[i] != t[j]) {
res += (dpl[i][j]+1)*(dpr[i+1][j+1]+1);
}
}
}
return res;
}
};
算法
(期望、组合) $O(NM)$
其实这题实际上是组合问题，因为这里是等概率！
注意到第 $k$ 小的数为 $X$ $\Leftrightarrow$ $A_k$ 等于在满足 $\geqslant X$ 的数至少有 $k$ 个中最小的 $X$
而 $\geqslant X$ 的数至少有 $k$ 个 $\Leftrightarrow$ $< X$ 的个数不足 $k$ 个
可以考虑对所有的 $X$ 求出 $A_k \leqslant X$ 的概率是多少
$A_k \leqslant X$ 意味着不超过 $X$ 的数至少有 $k$ 个，所以我们求出在 $0$ 中至少有 $k’$ 个数不超过 $X$ 的概率即可！
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint998244353;
// combination mod prime
struct modinv {
int n; vector<mint> d;
modinv(): n(2), d({0,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
int n; vector<mint> d;
modfact(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*n), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
int n; vector<mint> d;
modfactinv(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*invs(n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
if (n < k || k < 0) return 0;
return facts(n)*ifacts(k)*ifacts(n-k);
}
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
int z = 0;
sort(a.rbegin(), a.rend());
while (a.size() and a.back() == 0) {
a.pop_back();
z++;
}
mint ans;
rep(x, m+1) {
int sm = 0;
for (int na : a) if (na <= x) sm++;
rep(i, z+1) {
if (sm+i < k) {
mint now = comb(z, i);
now *= mint(x).pow(i); // <= x 的贡献为 1，> x的贡献为 0
now *= mint(m-x).pow(z-i);
ans += now;
}
}
}
ans /= mint(m).pow(z);
cout << ans.val() << '\n';
return 0;
}
算法分析
对于幸福子串只需满足在区间中每个字符出现的次数都是偶数即可，因此，每个字符在区间左端开始的累加和的奇偶性在左右两端应该应该是一致的。每个字符的奇偶性可以用 1 bit 表示，所以可以用 int 表示
类似题： LC1371
Python 代码
from collections import Counter
ans, now = 0, 0
cnt = Counter()
cnt[now] += 1
for x in map(int, input()):
now ^= 1<<x
ans += cnt[now]
cnt[now] += 1
print(ans)
算法
(模拟)
答案为 $\sum \frac{\text{颜色为} ~i ~\text{的袜子个数}}{2}$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
map<int, int> mp;
rep(i, n) {
int a;
cin >> a;
mp[a]++;
}
int ans = 0;
for (auto [col, num] : mp) {
ans += num/2;
}
cout << ans << '\n';
return 0;
}
算法
(模拟)
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int r, c;
cin >> r >> c;
vector<string> b(r);
rep(i, r) cin >> b[i];
vector ex(r, vector<bool>(c));
rep(i, r)rep(j, c) {
if (isdigit(b[i][j])) {
int d = b[i][j]-'0';
rep(ni, r)rep(nj, c) {
if (abs(i-ni)+abs(j-nj) <= d) {
ex[ni][nj] = true;
}
}
}
}
vector<string> ans(r, string(c, '.'));
rep(i, r)rep(j, c) {
if (b[i][j] == '#' and !ex[i][j]) ans[i][j] = '#';
}
rep(i, r) cout << ans[i] << '\n';
return 0;
}
算法
(模拟)
Python 代码
n = int(input())
w = list(input().split())
words = ['and', 'not', 'that', 'the', 'you']
ok = False
for i in range(n):
for word in words:
if word == w[i]:
ok = True
print('Yes' if ok else 'No')
class Solution {
public:
int findLengthOfShortestSubarray(vector<int>& a) {
int n = a.size();
int j = n-1;
while (j and a[j-1] <= a[j]) --j;
if (j == 0) return 0;
int res = j;
for (int i = 0; i < n; ++i) {
while (j < n and a[j] < a[i]) ++j;
res = min(res, j-i-1);
if (i+1 < n and a[i] > a[i+1]) break;
}
return res;
}
};
