Welsh_Powell

34.9万

_LRJ_

ACwisher

zyq198
IDETI
zhangzhengyan1

luoxiaen

anonymous233
xzx_123
AC不了怎么办
humenglong

Welsh_Powell
3小时前

### 算法

#### Python 代码

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = []
for x in a:
if x not in b:
ans.append(x)
for x in b:
if x not in a:
ans.append(x)
ans.sort()
print(*ans)


Welsh_Powell
3小时前
class Solution:
def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
res = min(k, numOnes)
k -= min(k, numOnes)
k -= min(k, numZeros)
res -= k
return res


Welsh_Powell
4小时前

### 算法

##### (模拟)

$\Rightarrow ans \cdot X < YZ \Rightarrow ans \cdot \leqslant YZ-1 \Rightarrow ans \leqslant \frac{YZ-1}{X}$

#### Python 代码

x, y, z = map(int, input().split())
print((y*z-1)//x)


Welsh_Powell
5小时前
class Solution:
def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
points.sort()
res = 0
for i in range(1, len(points)):
res = max(res, points[i][0]-points[i-1][0])
return res


Welsh_Powell
14小时前
#define rep(i, n) for (int i = 0; i < (n); ++i)
class Solution {
public:
// linear sieve
vector<int> ps, pf;
void sieve(int mx) {
pf.resize(mx + 1);
rep(i, mx + 1) pf[i] = i;
for (int i = 2; i <= mx; ++i) {
if (pf[i] == i) ps.push_back(i);
rep(j, ps.size()) {
int x = ps[j] * i;
if (x > mx) break;
pf[x] = ps[j];
}
}
}

bool primeSubOperation(vector<int>& nums) {
sieve(1000);
int pre = 0;
for (int x : nums) {
if (x <= pre) return false;
int mn = x;
for (int p : ps) {
if (x-p <= pre) break;
mn = x-p;
}
pre = mn;
}
return true;
}
};


Welsh_Powell
15小时前
using ll = long long;
class Solution {
public:
vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
int n = nums.size(), m = queries.size();
sort(nums.begin(), nums.end());
vector<int> ord(m);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](const int i, const int j) {
return queries[i] < queries[j];
});
int i = 0;
ll l = 0, r = reduce(nums.begin(), nums.end(), 0ll);
vector<ll> res(m);
for (const int qi : ord) {
for (; i < n and nums[i] < queries[qi]; ++i) {
l += nums[i];
r -= nums[i];
}
res[qi] = r-l-1ll*queries[qi]*(n-i-i);
}
return res;
}
};


Welsh_Powell
16小时前
class Solution {
public:
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
const int n = coins.size();
vector<set<int>> to(n);
for (auto e : edges) {
int a = e[0], b = e[1];
to[a].insert(b);
to[b].insert(a);
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (to[i].size() == 1 and !coins[i]) {
q.push(i);
}
}
vector<bool> used(n);
while (q.size()) {
int v = q.front(); q.pop();
used[v] = true;
int u = *to[v].begin();
to[u].erase(v);
to[v].clear();
if (to[u].size() == 1 and !coins[u]) q.push(u);
}
vector<int> dist(n, -1);
for (int i = 0; i < n; ++i) {
if (!used[i] and to[i].size() == 1) {
dist[i] = 0;
q.push(i);
}
}
while (q.size()) {
int v = q.front(); q.pop();
used[v] = true;
int u = *to[v].begin();
to[u].erase(v);
to[v].clear();
dist[u] = max(dist[u], dist[v]+1);
if (to[u].size() == 1 and dist[u] <= 1) q.push(u);
}
return 2*(max(static_cast<int>(count(used.begin(), used.end(), false)), 1) - 1);
}
};


### 算法分析

#### 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 ll = long long;

int main() {
int n;
cin >> n;

vector<int> p(n, -1);
rep(i, n-1) {
cin >> p[i+1];
p[i+1]--;
}

dsu uf(n);
vector<int> root(n);
rep(i, n) root[i] = i;
auto get = [&](int v) -> int& {
};
auto merge = [&](int a, int b) {
int r = min(get(a), get(b));
uf.merge(a, b);
get(a) = r;
};

int q;
cin >> q;
rep(qi, q) {
int type;
cin >> type;
if (type == 1) {
int u, v;
cin >> u >> v;
--u; --v;
while (!uf.same(u, v)) {
u = get(u);
merge(u, p[u]);
}
}
else {
int x;
cin >> x;
--x;
int ans = get(x)+1;
cout << ans << '\n';
}
}

return 0;
}


class Solution {
public:
string shortestCommonSupersequence(string s1, string s2) {
int n = s1.size(), m = s2.size();
vector dp(n+1, vector<int>(m+1));
for (int i = 0; i < n; ++i) {
dp[i][m] = n-i;
}
for (int i = 0; i < m; ++i) {
dp[n][i] = m-i;
}
for (int i = n-1; i >= 0; --i) {
for (int j = m-1; j >= 0; --j) {
if (s1[i] == s2[j]) {
dp[i][j] = dp[i+1][j+1]+1;
}
else {
dp[i][j] = min(dp[i+1][j], dp[i][j+1])+1;
}
}
}

string res;
int i = 0,  j = 0;
while (i < n and j < m) {
if (s1[i] == s2[j]) {
res += s1[i];
++i;
++j;
}
else if (dp[i+1][j] == dp[i][j]-1) {
res += s1[i];
++i;
}
else if (dp[i][j+1] == dp[i][j]-1) {
res += s2[j];
++j;
}
}
if (i < n) res += s1.substr(i);
else if (j < m) res += s2.substr(j);
return res;
}
};