Welsh_Powell

34.7万

ACwisher

zyq198
IDETI
zhangzhengyan1

luoxiaen

anonymous233
xzx_123
AC不了怎么办
humenglong

Welsh_Powell
7小时前

Welsh_Powell
15小时前
#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;
}


Welsh_Powell
17小时前

### 算法

##### (数位 dp)

$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{的整数个数}$

#### 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;
}


Welsh_Powell
19小时前
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)$

$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;
}


### 算法分析

#### 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)


### 算法

#### 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;
}
};