难度分类（同一难度下按字典序上升）
- 入门: J
- 简单: G, E, D
- 中等: I, B, k
- 困难: F, A
J-解题思路
按照题意模拟即可
J-代码实现
for _ in range(int(input())):
print(int(int(input()) ** 0.5))
G-解题思路
dp入门题跳台阶小改
G-代码实现
MOD = int(1e9 + 7)
dp = [0] * int(1e6 + 10)
dp[1] = 1
dp[2] = 2
dp[3] = 4
n = int(input())
for i in range(4, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD
print(dp[n])
E-解题思路
欧拉筛预处理后，按照题目模拟即可
E-代码实现
#include <bits/stdc++.h>
const int N = 5e5 + 10;
std::vector<int> primes;
std::unordered_set<int> prime_set;
bool f[N];
void euler(int n) {
for (int i = 2; i <= n; i++) {
if (!f[i]) {
primes.push_back(i);
prime_set.insert(i);
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
f[i * primes[j]] = true;
if (i % primes[j] == 0) {
break;
}
}
}
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
euler(N - 1);
int t;
std::cin >> t;
while (t--) {
int x, flag = 0;
std::cin >> x;
for (int i = 0; i < primes.size() && primes[i] < x; i++) {
for (int j = i; j < primes.size() && primes[i] + primes[j] < x; j++) {
int p3 = x - primes[i] - primes[j];
if (prime_set.count(p3)) {
std::cout << primes[i] << " " << primes[j] << " " << p3 << "\n";
flag = 1;
break;
}
}
if (flag) {
break;
}
}
if (!flag) {
std::cout << -1 << "\n";
}
}
}
D-解题思路
区间修改单点查询，树状数组或线段树都可以解决
D-代码实现
#include <bits/stdc++.h>
const int N = 2e5 + 10;
using i64 = long long;
i64 a[N], td[N], tid[N];
int n, q;
int lowbit(int x) {
return x & -x;
}
void update(int k, int x) {
for (int i = k; i <= n; i += lowbit(i)) {
td[i] += x;
tid[i] += (i64) k * x;
}
}
i64 getsum(int k) {
i64 res = 0;
for (int i = k; i > 0; i -= lowbit(i)) {
res += (k + 1) * td[i] - tid[i];
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
update(i, a[i]);
update(i + 1, -a[i]);
}
std::cin >> q;
while (q--) {
int op;
std::cin >> op;
if (op == 1) {
int l, r, v;
std::cin >> l >> r >>v;
update(l, v);
update(r + 1, -v);
} else {
int x;
std::cin >> x;
std::cout << getsum(x) - getsum(x - 1) << "\n";
}
}
}
I-解题思路
二分这个a最后对答案+1即可
I-代码实现
n = int(input())
c = list(map(int, input().split()))
l, r = min(c), max(c)
ans = float('inf')
while l <= r:
mid = (l + r) // 2
L = sum(abs(i - mid) for i in c)
R = sum(abs(i - (mid + 1)) for i in c)
ans = min(ans, L, R)
if L < R:
r = mid - 1
else:
l = mid + 1
print(ans + 1)
B-解题思路
思维题，先算必定操作的数后对于剩下的值XJB操作取最小即可
B-代码实现
n = int(input())
a = sorted(list(map(int, input().split())))
l, r = map(int, input().split())
t1 = t2 = t4 = t3 = 0 # t1必定加 t2必定减 t3波动加 t4波动减
for i in range(n):
if a[i] < l:
t1 += l - a[i]
t3 += r - l
elif a[i] > r:
t2 += a[i] - r
t4 += r - l
if l <= a[i] <= r:
t4 += a[i] - l
t3 += r - a[i]
# print(t1, t2, t3, t4)
ans = min(t1, t2)
t1 -= ans
t2 -= ans
if t1:
if t4 >= t1:
print(ans + t1)
else:
print(-1)
elif t2:
if t3 >= t2:
print(ans + t2)
else:
print(-1)
else:
print(ans)
K-解题思路
kruscal实现最小生成树的途中取s和t联通之前最大的边权就是答案
K-代码实现
#include <bits/stdc++.h>
using i64 = long long;
struct DSU {
std::vector<int> fa, rank, siz;
int cnt;
DSU(int n) : fa(n + 1), rank(n + 1), siz(n + 1, 1), cnt(n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
}
int find(int x) {
if (fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void merge(int x, int y) {
int X = find(x), Y = find(y);
if (X != Y) {
siz[X] += siz[Y];
if (rank[X] >= rank[Y]) {
fa[Y] = X;
rank[X] += (int) (rank[X] == rank[Y]);
} else {
fa[X] = Y;
}
cnt--;
}
}
int size() {
return cnt;
}
int count(int x) {
return siz[find(x)];
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
i64 n, m;
std::cin >> n >> m;
DSU dsu(n);
std::vector<std::array<i64, 3>> g(m);
for (int i = 0; i < m; i++) {
i64 u, v, w;
std::cin >> u >> v >> w;
g[i] = {w, u, v};
}
int s, t;
std::cin >> s >> t;
std::sort(g.begin(), g.end());
i64 ans = -1;
for (auto [w, u, v] : g) {
if (dsu.find(u) != dsu.find(v)) {
dsu.merge(u, v);
ans = w;
}
if (dsu.find(s) == dsu.find(t)) {
break;
}
}
std::cout << ans;
}
F-解题思路
正向建边反向建边跑两次dij即可
F-代码实现
#include <bits/stdc++.h>
const int inf = INT_MAX;
std::vector<std::vector<std::pair<int, int>>> g1;
void dijkstra(int s, std::vector<int>& dist) {
int n = g1.size();
dist.assign(n, inf);
dist[s] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) {
continue;
}
for (auto edge : g1[u]) {
auto [v, w] = edge;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, m;
std::cin >> n >> m;
g1.assign(n + 1, std::vector<std::pair<int, int>>());
std::vector<int> from(n + 1), to(n + 1);
for (int i = 0; i < m; i++) {
int u, v, w;
std::cin >> u >> v >> w;
g1[u].emplace_back(v, w);
}
dijkstra(1, from);
std::vector<std::vector<std::pair<int, int>>> g2(n + 1);
for (int u = 1; u <= n; u++) {
for (auto edge : g1[u]) {
auto [v, w] = edge;
g2[v].emplace_back(u, w);
}
}
g1 = g2;
dijkstra(1, to);
int ans = 0;
for (int i = 2; i <= n; i++) {
if (from[i] < inf && to[i] < inf) {
ans += from[i] + to[i];
}
}
std::cout << ans;
}
A-解题思路
打表找规律
A-代码实现
for i in range(int(input())):
y, m, d = map(int,input().split())
if (m + d) % 2 == 0 or ((m == 9 or m == 11) and d == 30):
print('YES')
else:
print('NO')