链接: https://ac.nowcoder.com/acm/contest/66307#question
\(\\\)
An A-SOUL Ellien Fan F
指定每一位的进制,求 \(A+B\) 的值,直接模拟即可,复杂度 \(O(max(n, \ m))\),\(n,m\)为字符串的长度。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
void solve() {
string base;
cin >> base;
string A, B;
cin >> A >> B;
deque<char> a, b;
for (int i = 0; i < A.size(); i++) {
a.push_back(A[i]);
}
for (int i = 0; i < B.size(); i++) {
b.push_back(B[i]);
}
while (a.size() < base.size()) {
a.push_front('0');
}
while (b.size() < base.size()) {
b.push_front('0');
}
deque<int> ans;
int S = 0;
for (int i = b.size() - 1; i >= 0; i--) {
int cur = a[i - b.size() + a.size()] - '0' + b[i] - '0' + S;
int B = base[i - b.size() + base.size()] - '0';
B = B ? B : 10;
ans.push_front(cur % B);
S = cur / B;
}
for (int i = a.size() - b.size() - 1; i >= 0; i--) {
int cur = a[i] - '0' + S;
int B = base[i] - '0';
B = B ? B : 10;
ans.push_front(cur % B);
S = cur / B;
}
assert(S < 10);
if (S) {
ans.push_front(S);
}
while (ans.size() && !ans[0]) {
ans.pop_front();
}
if (!ans.size()) {
cout << 0 << endl;
return;
}
for (auto c: ans) {
cout << c;
}
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
B 打牌
贪心,降序排序后,每次选择收益最大的一项,复杂度 \(O(n \ logn)\)。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
void solve() {
cin >> n;
multiset<i64> p, q;
for (int i = 0; i < n; i++) {
cin >> k;
if (k & 1) {
p.insert(k);
} else {
q.insert(k);
}
}
i64 x = 0, y = 0;
int check = 1;
while (p.size() || q.size()) {
if (check) {
if (p.size() && q.size()) {
if (*p.rbegin() <= *q.rbegin()) {
x += *q.rbegin();
q.extract(*q.rbegin());
} else {
p.extract(*p.rbegin());
}
} else if (p.size()) {
p.extract(*p.rbegin());
} else {
x += *q.rbegin();
q.extract(*q.rbegin());
}
} else {
if (p.size() && q.size()) {
if (*p.rbegin() >= *q.rbegin()) {
y += *p.rbegin();
p.extract(*p.rbegin());
} else {
q.extract(*q.rbegin());
}
} else if (p.size()) {
y += *p.rbegin();
p.extract(*p.rbegin());
} else {
q.extract(*q.rbegin());
}
}
check ^= 1;
}
if (x > y) {
cout << "T" << endl;
} else if (x < y) {
cout << "X" << endl;
} else {
cout << "Tie" << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
C BJS and HT
暴力哈希,逆天卡常题。双模和动态都不行,必须单模+静态模,复杂度 \(O(max(N*strlen^2, \ 1e8))\)。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
constexpr i64 mod = 998244353, P = 131;
template<const long long N>
struct StringHash {
using i64 = long long;
array<i64, N> a;
array<i64, N> Phs;
StringHash() {
init(N - 1);
}
void work(const char *s) {
i64 n = strlen(s);
for (int i = 0; i < n; ++i) {
Phs[i + 1] = (Phs[i] * P + s[i]) % mod;
}
}
i64 PreHash(int l, int r) {
if (l > r) {
return -1;
}
i64 res = (Phs[r] - Phs[l - 1] * a[r - l + 1] % mod + mod) % mod;
return res;
};
void init(int n) {
a[0] = 1;
for (int i = 0; i < n; ++i) {
a[i + 1] = a[i] * P % mod;
}
}
};
constexpr int N = 5e5 + 5;
char b[N], h[N];
StringHash<N> p, q;
void solve() {
cin >> n;
int ans = 0;
auto check = [&](i64 x, i64 y) -> bool {
if (x == -1 || y == -1) {
return true;
}
return x == y;
};
while (n--) {
cin >> b >> h >> k;
if (strlen(b) != strlen(h) || k > strlen(b)) {
continue;
}
p.work(b);
q.work(h);
for (int i = 0; i < strlen(b) - k + 1; i++) {
if (b[i] != h[0]) {
continue;
}
if (!check(p.PreHash(i + 1, i + k), q.PreHash(1, k))) {
continue;
}
if (!check(p.PreHash(1, i), q.PreHash(k + 1, k + i))) {
continue;
}
if (!check(p.PreHash(i + k + 1, strlen(b)), q.PreHash(i + k + 1, strlen(h)))) {
continue;
}
ans++;
break;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
D F爱玩炉石传说
判断若干个给定的数能够构成一个 \([1,\ ranges::max\{a\}]\) 的排列,用 \(map\) 枚举。复杂度 \(O(n \ logn)\)。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
void solve() {
cin >> n;
vector<int> p(n);
map<int, bool> mp;
int mx = -1;
for (int i = 0; i < n; i++) {
cin >> p[i];
mx = max(mx, p[i]);
mp[p[i]] = true;
}
for (int i = 1; i < mx; i++) {
if (mp.find(i) == mp.end()) {
cout << "Nevermind, just use the Twisting Nether." << endl;
return;
}
}
cout << "This is a textbook-like blasphemy!" << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
E A+B Problem
非常浪费时间的高精度浮点数模拟,复杂度 \(O(max(n, \ m))\),\(n,m\)为字符串的长度。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
void solve() {
string a, b;
while (cin >> a >> b && a != "-1") {
int p = -1, q = -1;
for (int i = 0; i < a.size(); i++) {
if (a[i] == '.') {
p = i;
break;
}
}
for (int i = 0; i < b.size(); i++) {
if (b[i] == '.') {
q = i;
break;
}
}
if (p != -1 && q != -1) {
deque<int> in, on;
int l = a.size() - p - 1, r = b.size() - q - 1;
if (l < r) {
swap(a, b);
swap(l, r);
swap(p, q);
}
for (int i = a.size() - 1; i > a.size() - l + r - 1; i--) {
on.push_front(a[i] - '0');
}
int S = 0;
for (int i = a.size() - l + r - 1; i > p; i--) {
int j = b.size() + i - a.size() + l - r;
int cur = a[i] - '0' + b[j] - '0' + S;
on.push_front(cur % 10);
S = cur / 10;
}
if (p < q) {
swap(a, b);
swap(p, q);
}
for (int i = p - 1; i > p - 1 - q; i--) {
int j = q - 1 + i - p + 1;
int cur = a[i] - '0' + b[j] - '0' + S;
in.push_front(cur % 10);
S = cur / 10;
}
for (int i = p - 1 - q; i >= 0; i--) {
int cur = a[i] - '0' + S;
in.push_front(cur % 10);
S = cur / 10;
}
if (S) {
in.push_front(S);
}
for (auto c: in) {
cout << c;
}
int mx = 0;
for (auto c: on) {
mx = max(mx, c);
}
if (!on.size() || !mx) {
cout << endl;
continue;
}
deque<int> on2;
for (int i = on.size() - 1; i >= 0; i--) {
if (on[i]) {
for (int j = i; j >= 0; j--) {
on2.push_front(on[j]);
}
break;
}
}
cout << ".";
for (auto c: on2) {
cout << c;
}
cout << endl;
} else if (q != -1) {
deque<int> in, on;
for (int i = q + 1; i < b.size(); i++) {
on.push_back(b[i] - '0');
}
int mx = 0;
for (auto c: on) {
mx = max(mx, c);
}
while (b.size() > q) {
b.pop_back();
}
if (a.size() < b.size()) {
swap(a, b);
}
int S = 0;
for (int i = b.size() - 1; i >= 0; i--) {
int j = a.size() + i - b.size();
int cur = a[j] - '0' + b[i] - '0' + S;
in.push_front(cur % 10);
S = cur / 10;
}
for (int i = a.size() - b.size() - 1; i >= 0; i--) {
int cur = a[i] - '0' + S;
in.push_front(cur % 10);
S = cur / 10;
}
if (S) {
in.push_front(S);
}
for (auto c: in) {
cout << c;
}
if (!on.size() || !mx) {
cout << endl;
continue;
}
deque<int> on2;
for (int i = on.size() - 1; i >= 0; i--) {
if (on[i]) {
for (int j = i; j >= 0; j--) {
on2.push_front(on[j]);
}
break;
}
}
cout << ".";
for (auto c: on2) {
cout << c;
}
cout << endl;
} else if (p != -1) {
deque<int> in, on;
for (int i = p + 1; i < a.size(); i++) {
on.push_back(a[i] - '0');
}
int mx = 0;
for (auto c: on) {
mx = max(mx, c);
}
while (a.size() > p) {
a.pop_back();
}
if (a.size() < b.size()) {
swap(a, b);
}
int S = 0;
for (int i = b.size() - 1; i >= 0; i--) {
int j = a.size() + i - b.size();
int cur = a[j] - '0' + b[i] - '0' + S;
in.push_front(cur % 10);
S = cur / 10;
}
for (int i = a.size() - b.size() - 1; i >= 0; i--) {
int cur = a[i] - '0' + S;
in.push_front(cur % 10);
S = cur / 10;
}
if (S) {
in.push_front(S);
}
for (auto c: in) {
cout << c;
}
if (!on.size() || !mx) {
cout << endl;
continue;
}
deque<int> on2;
for (int i = on.size() - 1; i >= 0; i--) {
if (on[i]) {
for (int j = i; j >= 0; j--) {
on2.push_front(on[j]);
}
break;
}
}
cout << ".";
for (auto c: on2) {
cout << c;
}
cout << endl;
} else {
deque<int> in;
if (a.size() < b.size()) {
swap(a, b);
}
int S = 0;
for (int i = b.size() - 1; i >= 0; i--) {
int j = a.size() + i - b.size();
int cur = a[j] - '0' + b[i] - '0' + S;
in.push_front(cur % 10);
S = cur / 10;
}
for (int i = a.size() - b.size() - 1; i >= 0; i--) {
int cur = a[i] - '0' + S;
in.push_front(cur % 10);
S = cur / 10;
}
if (S) {
in.push_front(S);
}
for (auto c: in) {
cout << c;
}
cout << endl;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
F 懒虫读诗
树形 \(dp\),原题为无根树,会形成森林,做起来比较困难,考虑新增一个结点权值为 \(0\) 的零结点作为树的根,可视为有根树中每个结点最多有一个父亲结点。
考虑 \(dp(i, \ j, \ k)\) 表示在以 \(i\) 为根的子树中,遍历了 \(u\) 个结点,选择了 \(k\) 个结点的最优解,并设以 \(x\) 为根的子树的大小为 \(size_x\),任一点 \(y\) 的儿子结点个数 \(s_y\),其状态转移过程是不难的,
\[dp(i, \ j, \ k)=max_{u<size_v} \ dp(i, \ j - 1, \ k - u) + dp(i, \ s_v, \ u) \]不过开三维空间会爆内存,需要滚动数组来省略掉第二维。时间复杂度不确定,应该是 \(O(nm)\)。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
void solve() {
cin >> m >> n;
vector<vector<int>> adj(m + 1);
vector<int> p(m + 1);
int x, y;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
adj[x].emplace_back(i);
p[i] = y;
}
vector<vector<int>> dp(m + 1, vector<int> (m + 1, 0));
auto dfs = [&](auto &&self, int u, int cur) -> void {
if (!cur) {
return;
}
for (auto c: adj[u]) {
for (int i = 0; i < cur; i++) {
dp[c][i] = dp[u][i] + p[c];
}
self(self, c, cur - 1);
for (int i = 1; i <= cur; i++) {
dp[u][i] = max(dp[u][i], dp[c][i - 1]);
}
}
};
dfs(dfs, 0, n);
cout << dp[0][n] << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
G A Hard Calculation Problem
签到,复杂度 \(O(T)\)。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
void solve() {
cin >> n;
cout << 2016 + n << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
H 水果蛋糕
题面有点绕,建议编故事别跑题了。简单说就是把一个矩形分成若干个三角形或者梯形或者矩形,求第几个图形内的给定点的数量最多。
这题也是卡常卡的很死,射线法判断 \(InPolygon\) 寄了,为什么 \(O(4m \ logn)\) 寄了,感觉完全够用啊。
改成矢量叉积之后对了,常数变成射线法的 \(\frac{1}{4}\),变成 \(O(m \ logn)\)。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
typedef struct Point {
i64 x, y;
Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
};
void solve() {
i64 x, y;
cin >> n >> m >> x >> y;
Point p[n + 2][2];
p[0][0].x = 0, p[0][0].y = 0;
p[0][1].x = 0, p[0][1].y = y;
p[n + 1][0].x = x, p[n + 1][0].y = 0;
p[n + 1][1].x = x, p[n + 1][1].y = y;
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
p[i][0].x = p[i - 1][0].x + l, p[i][0].y = p[i - 1][0].y;
p[i][1].x = p[i - 1][1].x + r, p[i][1].y = p[i - 1][1].y;
}
vector<i64> L(n + 1), R(n + 1);
L[0] = 0, R[0] = max(p[1][0].x, p[1][1].x);
for (int i = 1; i <= n; i++) {
L[i] = min(p[i][0].x, p[i][1].x);
R[i] = max(p[i][0].x, p[i][1].x);
}
vector<int> cnt(n + 2);
vector<i64> S(n + 2);
for (int i = 1; i <= n + 1; i++) {
S[i] = p[i][0].x - p[i - 1][0].x + p[i][1].x - p[i - 1][1].x;
}
for (int i = 0; i < m; i++) {
i64 u, v;
cin >> u >> v;
auto prod = [&](i64 a, i64 b, i64 c, i64 d) -> i64 {
return a * d - b * c;
};
auto calc = [&](Point p[2]) -> i64 {
return prod(p[1].x - p[0].x, -y, u - p[0].x, v - y);
};
auto get = [&]() -> int {
int l = 1, r = n + 1;
while (l < r) {
int mid = l + r >> 1;
if (calc(p[mid]) > 0) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
};
int idx = get();
cnt[idx]++;
}
int cur = 0, ans = 0;
i64 area = 0;
for (int i = 0; i <= n + 1; i++) {
if (cnt[i] > cur || (cnt[i] == cur && S[i] > area)) {
cur = cnt[i];
area = S[i];
ans = i;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
I Digital Logic and Bit Operation
给定 \(n, m\),在区间 \([n,m]\) 内找两个数,使其或运算后结果最大。分类讨论一下,分为 \(n\) 和 \(m\) 的二进制位数相等和不相等两种情况。
容易发现,当二进制位数不相等时,答案为 \(2^{bitwidth(m)}-1\)。否则,从高逐位枚举,找到异或为 \(1\) 的位置,之后全部置 \(1\) 即可。复杂度 \(O(logm)\) 或 \(O(log^2m)\)。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
void solve() {
cin >> n >> m;
if (n == m) {
cout << n << endl;
return;
}
auto u = (n > 1LL && (n & (n - 1) == 0) ? __lg(n) : __lg(n) + 1);
u = n ? u : 1;
auto v = (m > 1LL && (m & (m - 1) == 0) ? __lg(m) : __lg(m) + 1);
v = v ? v : 1;
i64 ans = 0;
if (u != v || !(n * m)) {
ans += (1LL << v) - 1;
cout << ans << endl;
return;
}
for (int i = u - 1; i >= 0; i--) {
if (n & (1LL << i) && m & (1LL << i)) {
ans += 1LL << i;
} else if (n & (1LL << i) || m & (1LL << i)) {
ans += 1LL << i;
for (int j = i - 1; j >= 0; j--) {
ans += 1LL << j;
}
break;
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
J 蛋糕惨案
欧拉筛之后枚举一下就可以了。复杂度 \(O(nlog(\frac{n}{lnn})+nlogn)\),可以用 \(minp\) 和桶排序做到 \(O(n)\),不过无所谓,而且内存可能会爆。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
vector<int> Sieve(int n) {
vector<int> minp;
minp.assign(n + 1, 0);
vector<int> res;
for(int i = 2; i <= n; i++) {
if(!minp[i]) {
minp[i] = i;
res.emplace_back(i);
}
for(auto p: res) {
if(i * p > n) {
break;
}
minp[i * p] = p;
if(p == minp[i]) {
break;
}
}
}
return res;
}
auto primes = Sieve(10000000);
void solve() {
cin >> n;
int kk;
vector<int> ans;
for (int i = 0; i < n; i++) {
cin >> kk;
int q = lower_bound(primes.begin(), primes.end(), kk) - primes.begin();
if (q != primes.size() && primes[q] == kk) {
ans.emplace_back(kk);
}
}
sort(ans.begin(), ans.end());
if (!ans.size()) {
cout << 0 << endl << -1 << endl;
return;
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " \n"[i == ans.size() - 1];
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
K Equation
求给定函数的最值,套个模拟退火就过了,看了下题解是求导二分,不是很懂。复杂度为常数。
点击查看代码
import math
import random
t = int(input())
for i in range(0, t):
n = int(input());
def aimFunction(x):
y = 6 * (x ** 7) + 8 * (x ** 6) + 7 * (x ** 3) + 5 * (x ** 2) - n * x
return y
start = 0
end = 100
X = random.uniform(start,end)
Y = aimFunction(X)
T = 100000000000
rate = 0.9974
while T > 1:
x = random.uniform(start,end)
y = aimFunction(x)
if y < Y:
Y = y
X = x
else:
p = math.exp((Y - y) / T)
q = random.random();
if p > q:
Y = y
X = x
T *= rate
print(round(Y, 4))
\(\\\)
L 树上宝藏
因为边的数量很少,直接暴力 \(dfs\),复杂度不会算。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
void solve() {
cin >> n >> m;
vector<i64> p(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
vector<vector<int>> adj;
adj.assign(n + 1, {});
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
adj[x].emplace_back(y);
adj[y].emplace_back(x);
}
for (int i = 0; i < m; i++) {
int x, y;
i64 z;
cin >> x >> y >> z;
bool check = false;
auto dfs = [&](auto &&self, int u, int bef) -> void {
p[u] += z;
if (u == y) {
check = true;
return;
}
for (auto c: adj[u]) {
if (c == bef) {
continue;
}
if (check) {
return;
}
self(self, c, u);
}
if (check) {
return;
}
p[u] -= z;
};
dfs(dfs, x, -1);
}
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
i64 ans = 0, cur = 0;
bool check = false;
auto dfs = [&](auto &&self, int u, int bef) -> void {
if (u == y) {
cur += p[u];
ans = cur;
return;
}
cur += p[u];
for (auto c: adj[u]) {
if (c == bef) {
continue;
}
self(self, c, u);
}
cur -= p[u];
};
dfs(dfs, x, -1);
cout << ans << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
M Rescue Hostage
这个题的测试数据有问题,\(assert\) 之后会发现存在无 \(F\) 或者无 \(X\) 的数据。做法是从 \(F\) 点和 \(X\) 点开始各做一次 \(bfs\),然后暴力枚举所有的 \(H\) 求最小的和。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
struct g {
int x, y;
g (int x_, int y_): x(x_), y(y_) {}
};
void solve() {
cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
static const int M = 250;
int dis[M][M][2];
memset(dis, 0, sizeof dis);
vector<vector<int>> dir{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
auto check = [&](int x, int y) -> bool {
if (x < 0 || y < 0 || x > n - 1 || y > m - 1) {
return false;
}
return true;
};
int sx = 0, sy = 0, ux = 0, uy = 0;
auto bfs = [&](int x, int y, int P) -> void {
queue<g> q;
g st(x, y);
q.push(st);
while (!q.empty()) {
auto c = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
g nxt(c.x + dir[i][0], c.y + dir[i][1]);
if (!check(nxt.x, nxt.y)) {
continue;
}
if (dis[nxt.x][nxt.y][P]) {
continue;
}
if (s[nxt.x][nxt.y] == '#') {
continue;
}
dis[nxt.x][nxt.y][P] = dis[c.x][c.y][P] + 1;
q.push(nxt);
}
}
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == 'F') {
sx = i, sy = j;
}
if (s[i][j] == 'X') {
ux = i, uy = j;
}
}
}
int ans = 10010;
bfs(sx, sy, 0);
bfs(ux, uy, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == 'H' && dis[i][j][0] && dis[i][j][1]) {
// assert(dis[i][j][0] && dis[i][j][1]);
ans = min(ans, dis[i][j][0] + dis[i][j][1]);
}
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
\(\\\)
N 嘉然的问题
签到,复杂度 \(O(strlen^2)\)。
点击查看代码
#pragma GCC optimize("unroll-loops, Ofast")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 Mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;
void init() {}
template<const long long N>
struct StringHash {
using i64 = long long;
using PII = std::pair<i64, i64>;
const i64 mod1 = 1e9 + 97, mod2 = 998244853, p1 = 131, p2 = 233;
std::array<i64, N> a1, a2;
std::array<i64, N> Phs1, Phs2;
std::array<i64, N> Shs1, Shs2;
StringHash() {
init(N - 1);
}
StringHash(const std::string& S) {
init(N - 1);
work(S);
}
void work(const std::string& s) {
i64 n = s.size();
assert(n + 1 <= N);
for (int i = 0; i < n; ++i) {
i64 t = n - i - 1;
Phs1[i + 1] = ((i64)Phs1[i] * p1 + s[i]) % mod1;
Phs2[i + 1] = ((i64)Phs2[i] * p2 + s[i]) % mod2;
Shs1[t + 1] = ((i64)Shs1[t + 2] * p1 + s[t]) % mod1;
Shs2[t + 1] = ((i64)Shs2[t + 2] * p2 + s[t]) % mod2;
}
}
PII PreHash(i64 l, i64 r) {
assert(l <= r);
i64 P1 = (Phs1[r] - (i64)Phs1[l - 1] * a1[r - l + 1] % mod1 + mod1) % mod1;
i64 P2 = (Phs2[r] - (i64)Phs2[l - 1] * a2[r - l + 1] % mod2 + mod2) % mod2;
return PII(P1, P2);
};
PII SufHash(i64 l, i64 r) {
assert(l <= r);
i64 S1 = (Shs1[l] - (i64)Shs1[r + 1] * a1[r - l + 1] % mod1 + mod1) % mod1;
i64 S2 = (Shs2[l] - (i64)Shs2[r + 1] * a2[r - l + 1] % mod2 + mod2) % mod2;
return PII(S1, S2);
}
bool isPlalindrome(i64 l, i64 r) {
auto [P1, P2] = PreHash(l, r);
auto [S1, S2] = SufHash(l, r);
return P1 == S1 && P2 == S2;
}
void init(i64 n) {
a1[0] = a2[0] = 1;
for (int i = 0; i < n; ++i) {
a1[i + 1] = (i64)a1[i] * p1 % mod1;
a2[i + 1] = (i64)a2[i] * p2 % mod2;
}
}
};
constexpr int N = 1500;
StringHash<N> S;
void solve() {
string s;
getline(cin, s);
vector<pair<string, int>> ans;
S.work(s);
for (int i = 1; i <= s.size(); i++) {
for (int j = i + 1; j <= s.size(); j++) {
if (S.isPlalindrome(i, j)) {
ans.emplace_back(s.substr(i - 1, j - i + 1), i);
}
}
}
sort(ans.begin(), ans.end(), [](pair<string, int> x, pair<string, int> y) {
if (x.first.size() < y.first.size()) {
return true;
}
if (x.first.size() > y.first.size()) {
return false;
}
return x.second < y.second;
});
for (auto [x, y]: ans) {
cout << x << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}