基本情况
C又不是正解，A甚至还加一，以后要考虑好再交。
C. Constructing Tests
为了更好的代码实现而非手算出解来推式子
式子都推出来了。
\(n^2 - {\left\lfloor\frac{n}{m}\right\rfloor}^2 = x\)
myCode
不知道怎么直接解，就写了一个 \(\operatorname{O}(n\log n)\) 的枚举 \(m\) 然后对 \(n\) 二分的写法。
constexpr int N(1E9 + 1);
void solve() {
#define tests
int x;
std::cin >> x;
if (x == 0) {
std::cout << "1 1\n";
return ;
}
for (int m = 1; m * m <= x * 10; m++) {
i64 lo(m), hi(N);
auto check = [&](auto& o) -> bool {
return o * o - (o / m) * (o / m) < x;
};
i64 n(0);
while (lo <= hi) {
i64 mid(lo + hi >> 1);
if (check(mid)) {
lo = mid + 1;
}
else {
hi = mid - 1;
n = mid;
}
}
if (n * n - (n / m) * (n / m) == x) {
std::cout << n << ' ' << m << '\n';
return ;
}
}
error;
}
STD
我疑惑的点在于如果按照求根公式那一套来解，代码很难实现，而且还要考虑下取整。
实际上可以暴力一点，先因式分解一下（为了方便代码实现服务）
\[(n + {\left \lfloor \frac{n}{m} \right \rfloor})(n - {\left \lfloor \frac{n}{m} \right \rfloor}) = x \]\(x_1 = (n + {\left \lfloor \frac{n}{m} \right \rfloor})\)
\(x_2 = (n - {\left \lfloor \frac{n}{m} \right \rfloor})\)
然后直接 \(\operatorname{O}(\sqrt x)\) 枚举 \(x1, x2\)。
然后通过 \(x_1, x_2\)，解出 \(n, m\)（暂时不用管向下取整等等）
最后再回代验证，就确保了正确性。
void solve() {
#define tests
int x;
std::cin >> x;
if (x == 0) {
std::cout << "1 1\n";
return ;
}
for (int i = 1; i * i < x; i++) if (x % i == 0) {
int x_1(x / i), x_2(i);
int n(x_1 + x_2 / 2), m((x_1 + x_2) / (x_1 - x_2));
if (n * n - (n / m) * (n / m) == x) {//回代验证
std::cout << n << ' ' << m << '\n';
return ;
}
}
error ;
return ;
}
D. Buy a Ticket
建图技巧：虚点
化点权为边权
暴力的想法是对每一个点跑单源最短路，肯定超时。
考虑优化，因为每条路径最后一定会加上 \(a_j\)，也就是终点的点权，我们直接建立一个虚点，对所有城市连边，其边权就是每个城市的点权。
然后直接从虚点出发跑一次单源最短路，自然就得到了所有点的最短路径（从终点到起点的）。
struct Node {
i64 v;
i64 w;
};
struct State{
i64 u, d;
bool operator < (const State &s) const {
return d > s.d;
}
};
int n, m;
std::vector<std::vector<Node>> adj;
std::vector<i64> dis;
void dijkstra(int S){
std::priority_queue<State> heap;
dis.assign(n + 1, LONG_LONG_MAX);
heap.push({S, 0});
dis[S] = 0;
while(not heap.empty()){
auto[u, d](heap.top());
heap.pop();
if (d > dis[u]) continue;
for (auto&[v, w] : adj[u]) {
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
heap.push({v, dis[v]});
}
}
}
}
void solve() {
std::cin >> n >> m;
adj.assign(n + 1, std::vector<Node>());
for (i64 i = 0, u, v, w; i < m; i++) {
std::cin >> u >> v >> w;
adj[u].push_back({v, w * 2});
adj[v].push_back({u, w * 2});
}
for (int i = 1; i <= n; i++) {
i64 w;
std::cin >> w;
adj[0].push_back({i, w});
}
dijkstra(0);
for (int i = 1; i <= n; i++) {
std::cout << dis[i] << ' ';
}
std::cout << '\n';
}