硬币
多少有些人类智慧了。。。。。
题解写的还行。
具体就是每次把当前这一位代表的质数 \(i\) 向后每隔 \(i\) 个数除上 \(i\)。
这一位肯定是一个质数，因为若是合数则前面一定会被除上质数。
Kaiserredux
#include <bits/stdc++.h>
long long num[1100000];
long long answer[1100000];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("coins.in", "r", stdin);
freopen("coins.out", "w", stdout);
for (long long i = 1; i <= 1e6; ++ i) {
answer[i] = num[i] = 1ll * i * i + 1ll;
}
for (long long i = 1; i <= 1000000; ++ i) {
if (num[i] == 1)
continue;
long long x = num[i];
for (long long j = i; j <= 1000000; j += x) {
answer[j] = std::min(answer[j], x);
while (num[j] % x == 0)
num[j] /= x;
}
}
long long Q, N;
std::cin >> Q;
while (Q --) {
std::cin >> N;
if (answer[N] == N * N + 1ll)
std::cout << -1 << '\n';
else
std::cout << answer[N] << ' ' << (N * N + 1) / answer[N] << '\n';
}
return 0;
}
猜数
逆天单调队列优化dp + 大眼观察法。
根本不会证QAQ。
56 Road
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
int N;
long long sum[52100], dp[4000][4000];
class Monotonic_Queue {
public:
int l, r;
std::pair<int, long long> value[52100];
Monotonic_Queue() {
l = 1, r = 0;
}
void pop_from_range(int rRange) {
while (l <= r && value[l].first > rRange)
l ++;
}
void emplace(long long val, int pos) {
while (l <= r && value[r].second > val)
r --;
value[++ r] = std::make_pair(pos, val);
}
long long front() {
return value[l].second;
}
int front_first() {
return value[l].first;
}
void clear() {
l = 1, r = 0;
}
}queue;
int to[51000];
int Len(int l, int r) {
return r - l + 1;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("guess.in", "r", stdin);
freopen("guess.out", "w", stdout);
int S = 3750;
std::cin >> N;
for (int r = S + 110; r >= 1; -- r)
for (int l = 2; l <= S; ++ l)
dp[r][l] = 1e18;
for (int i = 1; i <= N; ++ i)
to[i] = i % 3800, sum[i] = 1e18;
sum[1] = 0;
long long answer = 0;
for (int r = 2; r <= N; ++ r) {
int mid = r;
queue.clear();
for (int l = r - 1; r - l + 1 <= std::min(r, S); -- l) {
queue.emplace(dp[to[r]][Len(l + 1, r)] + l, l);
while (mid > l && dp[to[mid - 1]][Len(l, mid - 1)] >= dp[to[r]][Len(mid + 1, r)]) {
mid --;
queue.pop_from_range(mid);
}
dp[to[r]][Len(l, r)] = std::min(queue.front(), dp[to[mid]][Len(l, mid)] + mid + 1);
sum[r] = std::min(sum[r], std::max(sum[l - 1], dp[to[r]][Len(l + 1, r)]) + l);
}
answer += sum[r];
}
std::cout << answer << '\n';
return 0;
}
P3403 跳楼机
同余最短路板子题。
我们先设 \(f_i\) 表示我们只用操作 \(2,3\) 使得 \(f_i \% x = i\)，并且让 \(f_i\) 最小。每次将 \(i\) 连向 \((i+y)\%x\) 和 \((i+z)\%x\)，边权分别为 \(y\) 和 \(z\)。然后跑最短路就行了。
燃烧的世界
#include <bits/stdc++.h>
typedef long long ll;
class Point {
public:
ll val, poi;
bool operator <(const Point &b) const {
return val > b.val;
}
Point(ll _val, ll _poi) {
val = _val;
poi = _poi;
}
};
int cnt, head[110000], next[210000], to[210000];
ll value[210000];
void AddEdge(int u, int v, ll val) {
++ cnt;
next[cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
value[cnt] = val;
}
ll f[110000];
bool visit[110000];
ll H, X, Y, Z;
void Dijkstra(int begin) {
memset(visit, 0, sizeof(visit));
for (int i = 0; i < X; ++ i)
f[i] = 2e18;
f[1] = 1;
std::priority_queue<Point> queue;
queue.emplace(f[1], 1);
while (queue.size()) {
int now = queue.top().poi;
queue.pop();
if (visit[now])
continue;
visit[now] = true;
for (int i = head[now]; i; i = next[i]) {
if (f[to[i]] > f[now] + value[i]) {
f[to[i]] = f[now] + value[i];
queue.emplace(f[to[i]], to[i]);
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> H >> X >> Y >> Z;
if (X == 1 || Y == 1 || Z == 1) {
std::cout << H << '\n';
return 0;
}
if (X > Y)
std::swap(X, Y);
if (X > Z)
std::swap(X, Z);
for (int i = 0; i < X; ++ i) {
AddEdge(i, (i + Y) % X, Y);
AddEdge(i, (i + Z) % X, Z);
}
Dijkstra(1);
ll answer = 0;
for (int i = 0; i < X; ++ i) {
if (f[i] > H)
continue;
answer += (H - f[i]) / X + 1;
}
std::cout << answer << '\n';
return 0;
}