# Codeforces 1076A - Minimizing the String

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1076/problem/A

## 实现

https://pasteme.cn/2739

#include <bits/stdc++.h>
const int maxn = int(2e5) + 7;
char str[maxn];
int n, ans = -1;
int main() {
scanf("%d %s", &n, str + 1);
for (int i = 1; i <= n && ans == -1; i++) if (str[i] > str[i + 1]) ans = i;
for (int i = 1; i <= n; i++) if (i != ans) printf("%c", str[i]);
return 0;
}

# Codeforces 1076B - Divisor Subtraction

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1076/problem/B

## 题意

1. 如果 $n = 0$ 结束程序
2. 找到 $n$ 的最小质因数 $d$
3. $n = n - d$ ，然后回到步骤 $1$

## 实现

https://pasteme.cn/2740

#include <bits/stdc++.h>
const int maxn = int(1e5) + 7;
long long n;
bool prime[maxn];
bool isprime(long long x) {
for (long long i = 2; i * i <= x; i++) if (x % i == 0) return false;
return true;
}
int main() {
#ifdef AC
freopen("../in", "r", stdin);
#endif
memset(prime, true, sizeof(prime));
for (int i = 2; i < maxn; i++) {
if (!prime[i]) continue;
for (int j = i + i; j < maxn; j += i) prime[j] = false;
}
scanf("%lld", &n);
long long ans = n;
if (ans & 1) {
if (isprime(ans)) return 0 * puts("1");
for (int i = 3; i <= ans; i++) {
if (ans % i == 0 && prime[i]) {
ans -= i;
break;
}
}
}
printf("%lld\n", ans / 2 + (n & 1));
return 0;
}

# Codeforces 1076C - Meme Problem

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1076/problem/C

## 思路

$$\begin{cases}a + b = d\\a \ \cdot \ b = d\end{cases}$$

$$\Rightarrow a \cdot (d - a) = d$$

$$\Rightarrow a ^ 2 - d \cdot a + d = 0$$

## 实现

https://pasteme.cn/2741

#include <bits/stdc++.h>
std::vector<double> solve(double a, double b, double c) {
std::vector<double> ret;
double delta = b * b - a * c * 4;
if (delta < 0) return ret;
delta = sqrt(delta);
double x[2] = {(-b - delta) / 2 / a, (-b + delta) / 2 / a};
for (double i : x) if (i > 0) ret.push_back(i);
return ret;
}
int solve(std::vector<double> ans, int d) {
for (auto i : ans) if (fabs((d - i) * i - d) < 1e-9) return printf("Y %.9lf %.9lf\n", i, d - i);
return 0 * puts("N");
}
int main() {
int t, d;
for (std::cin >> t; t; t--) {
std::cin >> d;
if (d != 0) solve(solve(1, -d, d), d);
else puts("Y 0.000000000 0.000000000");
}
return 0;
}
/*
* a + b = d
* a * b = d
* b = d - a
* a * (d - a) = d
* a * d - a * a = d
* a * a - d * a + d = 0
*/


# Codeforces 1076D - Edge Deletion - 思维

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1076/problem/D

## 实现

https://pasteme.cn/2742

#include <bits/stdc++.h>
const int maxn = int(3e5) + 7;
typedef long long ll;
std::pair<int, int> pre[maxn];
std::vector<std::pair<int, int>> tree[maxn];
std::vector<int> ans;
struct { int next, v, cost, index; } edge[maxn << 1];
struct Graph {
void addedge(int u, int v, int cost, int index) {
edge[cnt] = {head[u], v, cost, index};
}
} graph;
int n, m, k, cnt;
namespace Dijkstra {
ll dist[maxn];
bool vis[maxn];
struct Node {
int u;
ll dist;
Node(int u, ll dist):u(u), dist(dist) {}
bool operator < (const Node &tmp) const {
return dist > tmp.dist;
}
};
void run() {
std::priority_queue<Node> que;
que.emplace(1, 0);
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
while (!que.empty()) {
int u = que.top().u;
que.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = graph.head[u]; ~i; i = edge[i].next) {
int v = edge[i].v, cost = edge[i].cost, index = edge[i].index;
if (dist[v] > dist[u] + cost) {
dist[v] = dist[u] + cost;
que.emplace(v, dist[v]);
pre[v] = std::make_pair(u, index);
}
}
}
}
}
void dfs(int u) {
for (auto it : tree[u]) {
if (cnt++ < k) {
ans.push_back(it.second);
dfs(it.first);
}
}
}
int main() {
#ifdef AC
freopen("../in", "r", stdin);
#endif
std::cin >> n >> m >> k;
for (int i = 1, u, v, cost; i <= m; i++) {
std::cin >> u >> v >> cost;
}
Dijkstra::run();
for (int i = 2; i <= n; i++) tree[pre[i].first].emplace_back(i, pre[i].second);
dfs(1);
std::cout << ans.size() << std::endl;
for (auto i : ans) std::cout << i << ' ';
return 0;
}


# Codeforces 1076E - Vasya and a Tree - 树状数组

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1076/problem/E

## 实现

https://pasteme.cn/2743

#include <bits/stdc++.h>
const int maxn = int(3e5) + 7;
typedef long long ll;
int n, m, max_dep, dep[maxn];
std::vector<int> edge[maxn];
std::vector<std::pair<int, int>> query[maxn];
struct Bit {
ll data[maxn];
void add(int pos, int val) {
while (pos <= n) data[pos] += val, pos += pos & -pos;
}
ll query(int pos) {
ll ret = 0;
while (pos) ret += data[pos], pos -= pos & -pos;
return ret;
}
} bit;
void dfs(int u, int pre) {
max_dep = std::max(dep[u] = dep[pre] + 1, max_dep);
for (int v : edge[u]) if (v != pre) dfs(v, u);
}
ll ans[maxn];
void solve(int u, int pre) {
for (auto pair : query[u]) {
}
ans[u] = bit.query(dep[u]);
for (int v : edge[u]) if (v != pre) solve(v, u);
for (auto pair : query[u]) {
}
}
int main() {
#ifdef AC
freopen("../in", "r", stdin);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 1, u, v; i < n; i++) {
std::cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1, 1);
std::cin >> m;
for (int i = 1, u, d, x; i <= m; i++) {
std::cin >> u >> d >> x;
query[u].emplace_back(std::min(dep[u] + d, max_dep), x);
}
solve(1, 1);
for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], i == n ? '\n' : ' ');
return 0;
}

Responses