navystar

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

4.5万

yindujuxi

nothing_sybs

cyxbq

Fkrito
incra

Hasity

Warsaw

cannedfish
Ariesfun

navystar
29分钟前
//这里填你的代码^^#include <bits/stdc++.h>
using namespace std;
vector<int> p ,val;
inline void solve()
{
int n, m, res = 0;
cin >> n >> m;
p.resize(n + 1 , 0), val.resize(n + 1, 0);
for(int i = 0; i <= n;  i ++ ) p[i] = i;
function <int (int)> find = [&](int x){
if (p[x] == x) return p[x];
int root = find(p[x]);
val[x] += val[p[x]];
p[x] = root;
return p[x];
};
while (m -- )
{
int l, r, s;
cin >> l >> r >> s;
int px = find(l - 1), py = find(r);
if (px != py)
{
p[px] = py;
val[px] = s + val[r] - val[l - 1];
}
else
{
if (val[l - 1] - val[r] != s) res ++;
}
}
cout << res << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


navystar
6小时前
//这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
int p[N];
int n, m;
inline void solve()
{
cin >> n >> m;
for (int i = 0; i <= n; i ++ ) p[i] = i;
function <int (int)> find = [&](int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
};
for (int i = 0; i < m; i ++ )
{
int a, b;
cin >> a >> b;
if (find(a) != find(b)) p[find(a)] = find(b);
}
set<int> s;
for (int i = 1; i <= n; i ++ )
if (s.find(find(i)) == s.end()) s.insert(p[i]);
cout << s.size() << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
int t = 1;
cin >> t;
while (t -- ) solve();
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


navystar
6小时前

## 并查集

#### C++ 代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
int p[N];
int n, m;
inline void solve()
{
cin >> n >> m;
for (int i = 0; i <= n; i ++ ) p[i] = i;
function <int (int)> find = [&](int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
};
for (int i = 0; i < m; i ++ )
{
int a, b;
cin >> a >> b;
if (find(a) != find(b)) p[find(a)] = find(b);
}
set<int> s;
for (int i = 1; i <= n; i ++ )
if (s.find(find(i)) == s.end()) s.insert(p[i]);
cout << s.size() << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
int t = 1;
cin >> t;
while (t -- ) solve();
return 0;
}


navystar
6小时前
//这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
int p[N];
int n, m;
inline int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
inline void solve()
{
while(cin >> n >> m, n || m)
{
for (int i = 0; i < n; i ++ ) p[i] = i;
while (m -- )
{
int k, x, y;
cin >> k >> x;
for (int i = 2; i <= k; i ++ )
{
cin >> y;
p[find(x)] = find(y);
}
}
int cnt = find(0), res = 0;
for (int i = 0; i < n; i ++ )
if (find(i) == cnt)
res ++;
cout << res << endl;
}
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


navystar
6小时前

## 并查集

#### C++ 代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
int p[N];
int n, m;
inline int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
inline void solve()
{
while(cin >> n >> m, n || m)
{
for (int i = 0; i < n; i ++ ) p[i] = i;
while (m -- )
{
int k, x, y;
cin >> k >> x;
for (int i = 2; i <= k; i ++ )
{
cin >> y;
p[find(x)] = find(y);
}
}
int cnt = find(0), res = 0;
for (int i = 0; i < n; i ++ )
if (find(i) == cnt)
res ++;
cout << res << endl;
}
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}


//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int primes[N], cnt;
bool st[N];
int phi[N];
LL s[N];
inline void init(int x)
{
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[primes[j]] * phi[i];
}
}
for (int i = 1; i <= x; i ++ ) s[i] = s[i - 1] + phi[i];
}
inline void solve()
{
int n;
cin >> n;
init(n);
LL res = 0;
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
res += (2 * s[n / p] + 1);
}
cout << res << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


## 欧拉 + 枚举

#### C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int primes[N], cnt;
bool st[N];
int phi[N];
LL s[N];
inline void init(int x)
{
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[primes[j]] * phi[i];
}
}
for (int i = 1; i <= x; i ++ ) s[i] = s[i - 1] + phi[i];
}
inline void solve()
{
int n;
cin >> n;
init(n);
LL res = 0;
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
res += (2 * s[n / p] + 1);
}
cout << res << endl;
}
int main()
{
cin.tie(nullptr) -> sync_with_stdio(0);
solve();
return 0;
}


//这里填你的代码^^
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 200010, M = N * 2, INF = 0x3f3f3f3f;
int n;
int h[N], e[M], w[M], ne[M], idx;
int d[N], f[N], deg[N];
inline void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
inline int dfs_d(int u, int fa)
{
if (deg[u] == 1)
{
d[u] = INF;
return d[u];
}
d[u] = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
d[u] += min(w[i], dfs_d(j, u));
}
return d[u];
}
inline void dfs_f(int u, int fa)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
if (deg[j] == 1) f[j] = w[i] < (f[u] - w[i]) ? w[i] : (f[u] - w[i]);
else
{
int cntr = w[i] < d[j] ? w[i] : d[j];
int cntl = (f[u] - cntr) < w[i] ? (f[u] - cntr) : w[i];
f[j] = d[j] + cntl;
dfs_f(j, u);
}
}
}
inline void solve()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
memset(deg, 0, sizeof deg);
idx = 0;
for (int i = 0; i < n - 1; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
deg[a] ++, deg[b] ++;
}
int root = 1;
while (root <= n && deg[root] == 1) root ++;
if (root > n)
{
cout << w[0] << endl;
return;
}
dfs_d(root, -1);
f[root] = d[root];
dfs_f(root, -1);
int res = 0;
for (int i = 1; i <= n; i ++ )
if (res < f[i])
res = f[i];
cout << res << endl;
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t -- ) solve();
return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


240++题解 开心下😋

//这里填你的代码^^
class Solution {
public:
long long minimumCost(string s) {
long long res = 0;
int n = s.size();
for (int i = 0; i < n - 1; i ++ )
if (s[i] != s[i + 1])
res += min(i + 1, n - i - 1);
return res;
}
};

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