navystar

https://git.acwing.com/navy.star

4.5万

nothing_sybs

cyxbq

Fkrito

incra

Hasity

Warsaw

cannedfish
Ariesfun

hyyyds
mpsi

navystar
3小时前

## 购买两块巧克力

#### C++ 代码

class Solution {
public:
int buyChoco(vector<int>& prices, int money) {
sort(prices.begin(), prices.end());
int cnt = prices[0] + prices[1];
if (cnt > money) return money;
else return money - cnt;
}
};

## 字符串中的额外字符

#### C++ 代码

class Solution {
public:
int minExtraChar(string s, vector<string>& dictionary) {
int n = s.size();
vector<int> f(n + 1, 0);
unordered_set<string> st;
for (auto d : dictionary) st.insert(d);
for (int i = 1; i <= n; i ++ )
{
f[i] = f[i - 1] + 1;
for (int j = 1; j <= i; j ++ )
{
string tmp = s.substr(j - 1, i - j + 1);
if (st.count(tmp)) f[i] = min(f[i], f[j - 1]);
}
}
return f[n];
}
};

## 一个小组的最大实力值

f[i][0] = max({f[i - 1][0], f[i][0] * nums[i - 1], f[i][1] * nums[i - 1], nums[i]);
f[i][1] = min({f[i - 1][1], f[i][0] * nums[i - 1], f[i][1] * nums[i - 1], nums[i]);

#### C++ 代码

class Solution {
public:
long long maxStrength(vector<int>& nums) {
int n = nums.size();
long long f[n + 1][2];
f[1][0] = nums[0]; //最大
f[1][1] = nums[0]; //最小
for (int i = 2; i <= n; i ++ )
{
f[i][0] = max(f[i - 1][0],
max(f[i - 1][0] * nums[i - 1],
max(f[i - 1][1] * nums[i - 1], 1LL * nums[i - 1])));

f[i][1] = min(f[i - 1][1],
min(f[i - 1][0] * nums[i - 1],
min(f[i - 1][1] * nums[i - 1], 1LL * nums[i - 1])));
}
return f[n][0];
}
};

## 最大公约数遍历

#### C++ 代码

class Solution {
public:
bool canTraverseAllPairs(vector<int>& nums) {
unordered_map<int,int> mp;
int n = nums.size(), res = 0;
if (n == 1) return true;
vector<int> p(n + 1, 0), f(n + 1, 0);
function<int (int)> find = [&](int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
};
for (int i = 0; i < n; i ++ ) p[i] = i, f[i] = 1;
for (int i = 0; i < n; i ++ )
{
for (int j = 2; j <= nums[i] / j; j ++ )
{
if (nums[i] % j == 0)
{
if (mp.count(j))
{
int a = find(i), b = find(mp[j]);
if (a != b)
{
f[b] += f[a];
p[a] = b;
if (res < f[b]) res = f[b];
}
}
else mp[j] = find(i);
while (nums[i] % j == 0) nums[i] /= j;
}
}
if (nums[i] > 1)
{
if (mp.count(nums[i]))
{
int a = find(i), b = find(mp[nums[i]]);
if (a != b)
{
f[b] += f[a];
p[a] = b;
if (res < f[b]) res = f[b];
}
}
else mp[nums[i]] = find(i);
}
}
return res == n;
}
};

navystar
15小时前
//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, k;
char g[N][N], s[N][N];
int len;
inline int power (int a,int b) {
int ans = 1;
while (b--) ans *= a;
return ans;
}
inline void dfs(int x, int y, int num, int dep, int type)
{
if (type == 1)
{
for (int i = x; i <= x + num - 1; i ++ )
for (int j = y; j <= y + num - 1; j ++ )
s[i][j] = '*';
return;
}
if (dep == 1)
{
for (int i = x; i <= x + num - 1; i ++ )
for (int j = y; j <= y + num - 1; j ++ )
s[i][j] = g[i - x][j - y];
return;
}
int cnt = num / n;
for (int i = x; i <= x + num - 1; i += cnt )
for (int j = y; j <= y + num - 1; j += cnt )
dfs(i, j, cnt, dep - 1, g[(i - x) / cnt][(j - y) / cnt] == '*');
}
inline void solve()
{
cin >> n >> k;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
cin >> g[i][j];
len = power(n, k);
dfs(1, 1, len, k, 0);
for (int i = 1; i <= len; i ++ )
for (int j = 1; j <= len; j ++ )
cout << s[i][j] << ((j == len) ? "\n" : "");
}
int main()
{
solve();
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

navystar
17小时前

## 暴力枚举

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N], b[N];
inline void solve()
{
int n, res = 0;
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i < n; i ++ ) b[i] = a[i + 1] - a[i];
for (int i = 1; i < n; i ++ )
if (b[i] * b[i + 1] < 0 && i + 1 < n)
res ++;
cout << res << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}

navystar
17小时前

## 暴力枚举

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5050;
int a[N], b[N], res[N];
inline void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ )
{
memset(b, 0, sizeof b);
int maxv = 0, cnt = 0;
for (int j = i; j <= n; j ++ )
{
b[a[j]] ++;
int t = b[a[j]];
if (t > maxv || t == maxv && cnt > a[j])
maxv = t, cnt = a[j];
res[cnt] ++;
}
}
for (int i = 1; i <= n; i ++ ) cout << res[i] << " ";
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 320;
int h[N], e[N], ne[N], w[N], idx;
int n, m, f[N][N];
inline void dfs(int u)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
for (int k = m; k >= 0; k -- )
for (int s = 1; s <= k; s ++ )
if (f[u][k] < f[u][k - s] + f[j][s])
f[u][k] = f[u][k - s] + f[j][s];
}
for (int i = m; i >= 1; i -- )
f[u][i]  = f[u][i - 1] + w[u];
}
inline void solve()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
int a, b;
cin >> a >> b;
e[idx] = i, ne[idx] = h[a], h[a] = idx ++;
w[i] = b;
}
m ++;
dfs(0);
cout << f[0][m] << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

## 分组背包的树形结构

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 320;
int h[N], e[N], ne[N], w[N], idx;
int n, m, f[N][N];
inline void dfs(int u)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
for (int k = m; k >= 0; k -- )
for (int s = 1; s <= k; s ++ )
if (f[u][k] < f[u][k - s] + f[j][s])
f[u][k] = f[u][k - s] + f[j][s];
}
for (int i = m; i >= 1; i -- )
f[u][i]  = f[u][i - 1] + w[u];
}
inline void solve()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
int a, b;
cin >> a >> b;
e[idx] = i, ne[idx] = h[a], h[a] = idx ++;
w[i] = b;
}
m ++;
dfs(0);
cout << f[0][m] << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}

//这里填你的代码^^
#include <iostream>
#define endl '\n'
using namespace std;
const int N = 1001;
int primes[N], cnt;
int phi[N], a[N], res[N];
bool st[N];
inline void get(int x)
{
phi[1] = 1;
for (int i = 2; i <= x; i ++ )
{
if (!st[i])
{
primes[cnt ++] = i;
phi[i] = i - 1;
}
for (int j = 0; primes[j] * i <= x; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0)
{
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
phi[primes[j] * i] = phi[i] * phi[primes[j]];
}
}
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
int t = 1, maxv = 0;
cin >> t;
for (int i = 1; i <= t; i ++ )
{
cin >> a[i];
if (maxv < a[i]) maxv = a[i];
}
get(maxv);
res[0] = 1;
for (int i = 1; i <= maxv; i ++ ) res[i] = res[i - 1] + (phi[i] << 1);
for (int i = 1; i <= t; i ++ )
cout << i << " " << a[i] << " " << res[a[i]] << endl;
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

## 欧拉函数

#### C++ 代码

#include <iostream>
#define endl '\n'
using namespace std;
const int N = 1001;
int primes[N], cnt;
int phi[N], a[N], res[N];
bool st[N];
inline void get(int x)
{
phi[1] = 1;
for (int i = 2; i <= x; i ++ )
{
if (!st[i])
{
primes[cnt ++] = i;
phi[i] = i - 1;
}
for (int j = 0; primes[j] * i <= x; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0)
{
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
phi[primes[j] * i] = phi[i] * phi[primes[j]];
}
}
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
int t = 1, maxv = 0;
cin >> t;
for (int i = 1; i <= t; i ++ )
{
cin >> a[i];
if (maxv < a[i]) maxv = a[i];
}
get(maxv);
res[0] = 1;
for (int i = 1; i <= maxv; i ++ ) res[i] = res[i - 1] + (phi[i] << 1);
for (int i = 1; i <= t; i ++ )
cout << i << " " << a[i] << " " << res[a[i]] << endl;
return 0;
}

//这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
int h[N], e[N], ne[N], w[N], idx;
bool father[N];
int f[N][2];
inline void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
inline void dfs(int u)
{
f[u][1] = w[u];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
int cnt = f[j][0] > f[j][1] ? f[j][0] : f[j][1];
f[u][0] += cnt;
f[u][1] += f[j][0];
}
}
inline void solve()
{
int n;
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i < n; i ++ )
{
int l, k;
cin >> l >> k;
father[l] = true;
}
int root = 1;
while (father[root]) root ++;
dfs(root);
int cnt = f[root][0] > f[root][1] ? f[root][0] : f[root][1];
cout << cnt << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

## 树形状态转移

f[i][0] 可以由f[s][1], f[s][0]推出

#### C++ 代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
int h[N], e[N], ne[N], w[N], idx;
bool father[N];
int f[N][2];
inline void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
inline void dfs(int u)
{
f[u][1] = w[u];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
int cnt = f[j][0] > f[j][1] ? f[j][0] : f[j][1];
f[u][0] += cnt;
f[u][1] += f[j][0];
}
}
inline void solve()
{
int n;
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i < n; i ++ )
{
int l, k;
cin >> l >> k;
father[l] = true;