答案即 \(\max(0,n)\)
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
cout << max(0, n) << '\n';
return 0;
}
感觉比 E+F 难，类似于光的反射，入射角等于反射角，那么斜率的绝对值相同，直接计算即可
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using DB = double;
const int kMaxN = 2e5 + 5;
DB sx, sy, tx, ty, ans, d, l;
void pr(bool pr) {
cout << (pr ? "Yes" : "No") << '\n';
}
int main() {
cin >> sx >> sy >> tx >> ty;
if (sx > tx) {
swap(sx, tx), swap(sy, ty);
}
d = sy + ty, l = sy / d;
cout << fixed << setprecision(10) << sx + l * (tx - sx) << '\n';
return 0;
}
直接枚举走城市的顺序，判断即可
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 8 + 5;
LL n, t[kMaxN][kMaxN], ans, f[kMaxN], k;
bitset<kMaxN> vis;
void pr(bool pr) {
cout << (pr ? "Yes" : "No") << '\n';
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> t[i][j];
}
f[i] = i;
}
do {
if (f[n] == 1) {
LL cur = 1, cnt = 0;
for (int i = 1; i <= n; i++) {
cnt += t[cur][f[i]], cur = f[i];
}
ans += (cnt == k);
}
} while(next_permutation(f + 1, f + n + 1));
cout << ans << '\n';
return 0;
}
差分模板，懒得解释了
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 2e5 + 5;
LL n, w, a[kMaxN], b[kMaxN], c[kMaxN], ans, s[kMaxN];
void pr(bool pr) {
cout << (pr ? "Yes" : "No") << '\n';
}
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i];
s[a[i]] += c[i], s[b[i]] -= c[i];
}
for (int i = 1; i <= n; i++) {
s[i] += s[i - 1];
}
for (int i = 0; i <= 2e5; i++) {
if (s[i] > w) {
pr(0);
return 0;
}
}
pr(1);
return 0;
}
dp 板子，记录一下左边，上面，左上方从上一个 # 的前缀和即可
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 2e3 + 5;
const LL kP = 1e9 + 7;
LL n, m, a[kMaxN], ans, dp[kMaxN][kMaxN], l[kMaxN][kMaxN], u[kMaxN][kMaxN], e[kMaxN][kMaxN];
bool mp[kMaxN][kMaxN];
char ch;
void pr(bool pr) {
cout << (pr ? "Yes" : "No") << '\n';
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> ch, mp[i][j] = ch == '.';
}
}
dp[1][1] = l[1][1] = u[1][1] = e[1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!mp[i][j]) {
l[i][j] = u[i][j] = e[i][j] = 0;
continue;
}
l[i][j] = l[i][j - 1] + dp[i][j] % kP, u[i][j] = u[i - 1][j] + dp[i][j] % kP, e[i][j] = e[i - 1][j - 1] + dp[i][j] % kP;
if (i + 1 <= n) {
(dp[i + 1][j] += u[i][j]) %= kP;
}
if (j + 1 <= m) {
(dp[i][j + 1] += l[i][j]) %= kP;
}
if (i + 1 <= n && j + 1 <= m) {
(dp[i + 1][j + 1] += e[i][j]) %= kP;
}
}
}
cout << dp[n][m] << '\n';
return 0;
}
使用并查集 + map 直接暴力，加上启发式合并可以优化到 \(O(n\log n)\)
// BLuemoon_
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int kMaxN = 2e5 + 5;
LL n, q, a[kMaxN], ans, op, x, y, fa[kMaxN], sz[kMaxN];
unordered_map<int, int> mp[kMaxN];
int Find(int x) {
return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
void Merge(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) {
return;
}
if (sz[x] > sz[y]) {
swap(x, y);
}
fa[x] = y, sz[y] += sz[x];
for (auto [i, j] : mp[x]) {
mp[y][i] += j;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i], mp[i][a[i]]++, fa[i] = i, sz[i] = 1;
}
for (; q; q--) {
cin >> op >> x >> y;
if (op == 1) {
Merge(x, y);
} else {
cout << mp[Find(x)][y] << '\n';
}
}
return 0;
}