_Crush

$\color{blue}{AcWing小学}$

6490

acmdyh
Eureka_7
Ungoliant

gwj12345

1668120228

tangmmmy

leimingze

21KINGDMG

_Crush
1天前
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int p[N], a[N], d[N];

int main ()
{
function<int(int)> f = [&](int x) {
return x == p[x] ? x : p[x] = f(p[x]);
};
auto mg = [&](int x, int y) {
x = f(x); y = f(y);
p[x] = y;
};

int n; cin >> n;
iota(p + 1, p + n + 1, 1);

for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) cin >> d[i];

for (int i = 1; i <= n; i ++ )
{
if (i - d[i] >= 1) mg(i-d[i], i);
if (i + d[i] <= n) mg(i+d[i], i);
}
for (int i = 1; i <= n; i ++ )
{
if (f(a[i]) != f(i)) return cout << "NO\n", 0;
}
cout << "YES\n";
return 0;
}


_Crush
1天前
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N], c[N]; // c(i) 表示以i为因子的所有数字的数量

int main ()
{
int n; cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i], ++ c[a[i]];
for (int i = 1; i < N; i ++ ) // 枚举所有因子
for (int j = i + i; j < N; j += i)
c[i] += c[j];
int ret = 1;
for (int i = 2; i < N; i ++ ) ret = max(ret, c[i]);
cout << ret << endl;
return 0;
}


_Crush
1天前
#include <bits/stdc++.h>
using namespace std;

int main ()
{
string s; cin >> s;
int q1 = 0, a = 0, q2 = 0;
for (int i = 0; i < s.size(); i ++ )
{
if (s[i] == 'A') a += q1;
if (s[i] == 'Q') q2 += a, ++ q1;
}
cout << q2 << endl;
return 0;
}


_Crush
3天前

# Edu 118(Div.2)

## A. Long Comparison

### 分析

1. 位数相同：根据位数判断。
2. 位数不同：把 $x$ 和 $y$ 的后导 $0$ 去掉，再比较 $x, y$ 。

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;

void solve ()
{
string a; int p; cin >> a >> p;
string b; int p2; cin >> b >> p2;
if (a.size() + p != b.size() + p2)
{
if (a.size() + p > b.size() + p2) cout << '>' << endl;
else cout << '<' << endl;
}
else
{
while(a[a.size() - 1] == '0') p ++ , a = a.substr(0, a.size() - 1);
while(b[b.size() - 1] == '0') p2 ++, b = b.substr(0, b.size() - 1);
if (a == b) cout << '=' << endl;
else if (a > b) cout << '>' << endl;
else cout << '<' << endl;
}
}

signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}


## B. Absent Remainder

### 题意

1. $x != y$ 。
2. $x \in a, y \in a$ 。
3. $x \ \ mod \ \ y \notin a$ 。

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
using namespace std;
const int N = 200010;

int a[N];

void solve ()
{
int n; cin >> n;
rep(i, 1, n) cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 0, p = 2; i < n / 2; i ++, p ++ )
cout << a[p] << ' ' << a[1] << endl;
}

signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}


## C. Poisoned Dagger

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;

int d[N]; // 间隔，n-1个
int n, h;

bool check (int mid)
{
int m = 0;
for (int i = 1; i < n; i ++ )
m += min(d[i], mid);
m += mid;
return m >= h;
}

void solve ()
{
cin >> n >> h;
int last; cin >> last;
for (int i = 1; i < n; i ++ )
{
int x; cin >> x;
d[i] = x - last;
last = x;
}
int l = 1, r = 1e18 + 10;
while(l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
}

signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}


## D. MEX Sequences

### 分析

1. $mex = x-1, max = x$ 。
2. $mex = x-1, max = x-2$ 。
3. $mex = x+1, max = x+2$ 。
4. $mex = x + 1, max = x$ 。

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define int long long
using namespace std;

const int mod = 998244353;

/*
* dp1(i) 表示mex为i且最大值为i-1的方案数量
* dp2(i) 表示mex为i且最大值为i+1的方案数量
*/

void solve ()
{
int n, ret = 0; cin >> n;
map<int, int> dp1, dp2;
rep(i, 1, n)
{
int x; cin >> x;
dp2[x-1] = (dp2[x-1] * 2 + dp1[x-1] + (x == 1)) % mod;
dp2[x+1] = (dp2[x+1] * 2) % mod;
dp1[x+1] = (dp1[x+1] * 2 + dp1[x] + (x == 0)) % mod;
}
for (auto & [k, v] : dp1) ret = (ret + v) % mod;
for (auto & [k, v] : dp2) ret = (ret + v) % mod;
cout << ret << endl;
}

signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}


## E. Crazy Robot

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
using namespace std; using PII = pair<int, int>;
const int N = 1000010;

const int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
PII q[N];

void solve ()
{
int n, m, x, y; cin >> n >> m;
vector g(n, vector<char>(m));
rep(i, 0, n-1) rep(j, 0, m-1)
{
cin >> g[i][j];
if (g[i][j] == 'L') x = i, y = j;
}
int hh = 0, tt = -1;
// 把周围点加进来
for (int i = 0; i < 4; i ++ )
{
int dx = x + dr[i], dy = y + dc[i];
if (dx < 0 || dx >= n || dy < 0 || dy >= m || g[dx][dy] == '#') continue;
q[++ tt] = {dx, dy};
}
while(hh <= tt)
{
PII t = q[hh ++ ];
int x = t.first, y = t.second, cnt_free = 0;
for (int i = 0; i < 4; i ++ )
{
int dx = x + dr[i], dy = y + dc[i];
if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
if (g[dx][dy] == '.') cnt_free ++ ;
}
if (cnt_free > 1) continue;
g[x][y] = '+';
for (int i = 0; i < 4; i ++ )
{
int dx = x + dr[i], dy = y + dc[i];
if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
if (g[dx][dy] == '.') q[++ tt] = {dx, dy};
}
}
rep(i, 0, n-1)
{
rep(j, 0, m-1) cout << g[i][j];
cout << '\n';
}
}

signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; )
solve();
return 0;
}


_Crush
4天前
// Trie + Haffman Tree
#include <iostream>
#include <queue>
#include <vector>
#define int long long

using namespace std;
using PLI = pair<long long, long long>; // 存储权值和深度

signed main ()
{
priority_queue<PLI, vector<PLI>, greater<PLI> > q;
long long n, k; cin >> n >> k;
for (int i = 1, x; i <= n && cin >> x; i ++ ) q.push({x, 0});
while(((int)q.size() - 1) % (k - 1)) q.push({0, 0}); // 满足k叉哈夫曼树性质
long long ret = 0;
// 构建haffman树
while(q.size() >= k)
{
long long t = 0; // 新结点权值
int dep = -1; // 新结点深度
// 找出k小权值构造一个结点
for (int i = 1; i <= k; i ++ )
{
PLI node = q.top(); q.pop();
t += node.first;
dep = max(dep, (int)node.second);
}
ret += t;
q.push({t, dep + 1});
}
cout << ret << endl << q.top().second << endl;
return 0;
}


_Crush
4天前
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
using PLI = pair<long long, int>;

const int N = 100010;

int n, k;
long long d[N];
int l[N], r[N];

void del (int idx)
{
// 把idx从链表中删除
r[l[idx]] = r[idx];
l[r[idx]] = l[idx];
}

int main ()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++ ) cin >> d[i];
for (int i = n; i >= 1; i -- ) d[i] -= d[i-1];
for (int i = 1; i <= n; i ++ )
{
// 把相对位置插入到双链表中
l[i] = i - 1;
r[i] = i + 1;
}
d[1] = d[n + 1] = 1e18;
set<PLI> S; // set找最小的贡献，这里的功能等价于二叉堆
for (int i = 1; i <= n; i ++ ) S.insert({d[i], i});
long long ret = 0;
for (int i = 1; i <= k; i ++ )
{
PLI t = *S.begin();
long long v = t.first;
// cout << v << endl;
int p = t.second, left = l[p], right = r[p];
del(left); del(right);
ret += v;
S.erase(t); S.erase({d[left], left}); S.erase({d[right], right});
d[p] = d[left] + d[right] - d[p];
S.insert({d[p], p});
}
cout << ret << endl;
return 0;
}


_Crush
6天前

# Deltix Round, Automn 2021

## A. Divide and Multiply

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define int long long
using namespace std;
const int N = 200010;

int a[N];

void solve ()
{
int n; cin >> n;
int ans = 0, cnt = 0;
rep(i, 1, n)
{
cin >> a[i];
while(a[i] % 2 == 0) ++ cnt, a[i] /= 2;
}
sort(a + 1, a + n + 1);
cout << accumulate(a+1, a+n, 0ll) + (1ll<<cnt) * a[n] << endl;
}

signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}


## B. William the Vigilant

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;

int n, q;
string s;

bool check (int p)
{
if (s[p] == 'a' && p + 2 < n && s.substr(p, 3) == "abc") return true;
if (s[p] == 'b' && p - 1 >= 0 && p + 1 < n && s.substr(p-1, 3) == "abc") return true;
if (s[p] == 'c' && p - 2 >= 0 && s.substr(p-2, 3) == "abc") return true;
return false;
}

void solve ()
{
int cnt = 0; cin >> n >> q;
cin >> s;
for (int i = 0; i < (int)s.size() - 2; i ++ )
if (s.substr(i, 3) == "abc") ++ cnt;
for (int i = 1; i <= q; i ++ )
{
int p; char chg; cin >> p >> chg;
p -- ;
if (check(p)) -- cnt;
s[p] = chg;
if (check(p)) ++ cnt;
cout << cnt << endl;
}
}

signed main ()
{
cout.tie(0)->sync_with_stdio(0);
// int _; for (cin >> _; _--; )
solve();
return 0;
}


## C. Complex Market Analysis

### 题意

$a_i, a_{i + e}, a_{i + 2 * e}, \ldots a_{i + k * e}$ 的乘积为质数。

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define int long long
using namespace std;
const int N = 200010, M = 1000020;

int prime[M], cnt;
bool st[M];

void get_prime(int n)
{
st[1] = true;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) prime[cnt ++ ] = i;
for (int j = 0; i * prime[j] <= n; j ++ )
{
st[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}

int f[N], g[N], a[N];

void solve ()
{
int n, e, ret = 0; cin >> n >> e;
rep(i, 1, n) f[i] = g[i] = 0;
rep(i, 1, n) cin >> a[i];
rep(i, 1, e) f[i] = (a[i] == 1);
rep(i, e + 1, n)
{
f[i] = (a[i] == 1);
if (a[i-e] == 1) f[i] += f[i-e];
}
per(i, n, n - e + 1) g[i] = (a[i] == 1);
per(i, n - e, 1)
{
g[i] = (a[i] == 1);
if (a[i+e] == 1) g[i] += g[i+e];
}
rep(i, 1, n) if (!st[a[i]]) ret = ret + f[i] * g[i] + f[i] + g[i];
cout << ret << endl;
}

signed main ()
{
get_prime(1000010);
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}


## D. Social Network

### Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i++)
using namespace std;
const int N = 200010;

int p[N], siz[N];

int f (int x) { return x == p[x] ? x : p[x] = f(p[x]); }

void solve ()
{
int n, d, base = 1; cin >> n >> d;
rep(i, 1, n) p[i] = i, siz[i] = 1;
rep(i, 1, d)
{
int x, y, ret = 0; cin >> x >> y;
x = f(x); y = f(y);
if (x == y) base ++ ;
else siz[y] += siz[x], p[x] = y;

priority_queue<int> q;
rep(j, 1, n) if (j == f(j)) q.push(siz[j]);
rep(j, 1, base) ret += q.top(), q.pop();
cout << ret - 1 << endl;
}
}

signed main ()
{
cout.tie(0)->sync_with_stdio(0);
// int _; for (cin >> _; _--; )
solve();
return 0;
}


_Crush
8天前
#include <iostream>
#include <cstring>
using namespace std;
// #define int long long
const int N = 210;

int f[N][30 * N + 10]; // f(i, j, k) 表示前i个数字选j个数字，且5的数量为k时2的数量，压缩第一维

signed main ()
{
int n, k; cin >> n >> k;
memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 1; i <= n; i ++ )
{
long long x; cin >> x;
int c2 = 0, c5 = 0;
while(x % 2 == 0) { ++ c2; x /= 2; }
while(x % 5 == 0) { ++ c5; x /= 5; }
// 体积为c5，价值为c2
for (int j = k; j >= 1; j -- ) // 选j个数字
for (int r = j * 26; r >= c5; r -- )
f[j][r] = max(f[j][r], f[j-1][r - c5] + c2);
}
int ans = 0;
for (int i = 0; i <= 25 * N; i ++ ) ans = max(ans, min(i, f[k][i]));
cout << ans << endl;
return 0;
}


_Crush
8天前

#include <iostream>
using namespace std;

typedef long long ll;

ll n, m, k;

bool check (ll x)
{
ll res = 0;
for (int i = 1; i <= n; i ++ )
res += min(m, x / i);
return res >= k;
}

int main ()
{
cin >> n >> m >> k;
ll l = 1, r = n * m;
while(l < r)
{
ll mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}


_Crush
8天前
#include <iostream>
#include <string>
using namespace std;

int main ()
{
int T; cin >> T; while( T -- )
{
int n, cur = 0; cin >> n;
string t = to_string(cur);
while(n -- )
{
t = t.substr(1);
if (t == "") ++ cur, t = to_string(cur);
}
cout << t[0] << endl;
}
return 0;
}