2025 江蘇省大學生程序設計大賽 & 2025 廣東省大學生程序設計競賽題解
目錄
比較難繃的一場比賽吧……大部分題目給我的感覺就是……代碼量巨大，寫之前比較費腦子但是寫的時候無腦的
題解給的難度排名比較奇怪：
\[D < F < J < G < H < A < I < K < C < B < E < L
\]
但是就我個人感覺而言，\(B\) 其實比大部分題目都要簡單很多？
接下來是題解和代碼，都寫完了而且有些題真的很坐牢（
Problem A. 矩陣游戲
唯一一個寫破防了的題目（
不是因為這道題具體有多難，而是這道題有點毒瘤。（把 long long 炸了的神仙題目?。。?/p>
我們發現 \(m\) 的取值非常的小，于是顯然想到這道題的復雜度最后可能與 \(2 ^ m\) 相關。
不難想到：
枚舉列反轉情況 \(t\) 與枚舉每一個行原始狀態狀態 \(u\)，可以得出異或后的行狀態 \(s\)，并將所有行狀態為 \(s\) 的行存入到一個 vector \(v\) 里面。此時對于一個行狀態為 \(s\) 的行 \(v_i\)，我們可以很輕易的算出是否反轉此行的貢獻。記不反轉為 \(w_1\)，反轉為 \(w_2\)
例如對于第 \(i\) 且行狀態 \(s\)，顯然：
\[令 W = \sum_{i = 1}^{m} j[s_j=1] \\
w_1 = A * i * popcnt(s) + B * W \\
w_2 = A * i * (m - popcnt(s)) + B * (\frac{m * (m + 1)}{2} - W)
\]
容易發現隨著 \(i\) 的增長，\(w_1\) 和 \(w_2\) 的變化都是單調的，而且增速都是恒定的，也就是貢獻隨著行數增大都是單調變化的。
如此我們可以輕易發現：至多出現一個分界點 \(i\) 使得 \(v_i\) 之前的行不反轉更優，之后的行反轉更優（可能是反過來說，無所謂了）
我們可以通過二分獲得這個分界點 \(i\)，之后的做法就很顯然了。
不過這題會炸 long long，所以在算答案的時候要用 __int128，還不能無腦用因為可能會 TLE……
題解和具體的代碼實現可能有點出入，將就著看吧。
代碼：
#include <iostream>
#include <vector>
#define int long long
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 1e6 + 100;
using big = __int128;
int n, m, A, B;
std::vector<int> v[kMaxN];
std::vector<int> suf[kMaxN];
int popcnt[kMaxN];
int sucker[kMaxN]; // 不要管這個奇怪的數組名
int toi(const std::string& str) {
int ans = 0;
for (int i = 0; i < str.size(); i++) {
ans = (str[str.size() - i - 1] - '0') + (ans << 1);
}
return ans;
}
int suck(int s) {
int ans = 0;
for (int i = 0; i < m; i++) {
ans += ((s >> i) & 1) * B * (i + 1);
}
return ans;
}
int pop(int x) {
int cnt = 0;
while (x) {
cnt += x & 1;
x >>= 1;
}
return cnt;
}
// v1 = suck(i) + i * popcnt * A
// v2 = ((m + 1) * m / 2) * B + m * B * i - v1
// 顯然 v1 和 v2 都是單調的
int v1(int i, int s) {
return sucker[s] + i * popcnt[s] * A;
}
int v2(int i, int s) {
return ((m + 1) * m / 2) * B - sucker[s] + i * (m - popcnt[s]) * A;
}
big v1sum(int i, int s, int s2) {
if (i < 0) return 0;
return (big)sucker[s] * (i + 1) + popcnt[s] * A * suf[s2][i];
}
big v2sum(int i, int s, int s2) {
if (i < 0) return 0;
return (big)(((m + 1) * m / 2) * B - sucker[s]) * (i + 1) + suf[s2][i] * (m - popcnt[s]) * A;
}
void upans(big& ans, int mid, int s, int s2) {
if (mid < 0) return;
ans = std::max(ans, v1sum(mid, s, s2) + v2sum(v[s2].size() - 1, s, s2) - v2sum(mid, s, s2));
ans = std::max(ans, v2sum(mid, s, s2) + v1sum(v[s2].size() - 1, s, s2) - v1sum(mid, s, s2));
}
void print(big s) {
if (s < 10) {
cout << (int)s;
return;
}
print(s / 10);
cout << (int)(s % 10);
}
signed main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
cin >> n >> m >> A >> B;
for (int i = 1; i <= n; i++) {
std::string str;
cin >> str;
v[toi(str)].push_back(i);
int s = toi(str);
popcnt[s] = pop(s);
sucker[s] = suck(s);
}
for (int s = 0; s < (1 << m); s++) {
popcnt[s] = pop(s);
sucker[s] = suck(s);
suf[s] = v[s];
for (int i = 1; i < suf[s].size(); i++) {
suf[s][i] += suf[s][i - 1];
}
}
big ans = -1e18, sum, tmp;
for (int s1 = 0; s1 < (1 << m); s1++) {
sum = 0;
for (int s2 = 0; s2 < (1 << m); s2++) {
int s = s1 ^ s2;
auto& v = ::v[s2];
if (v.empty()) continue;
// 拋棄大腦的寫法，別學
tmp = std::max(v1sum(v.size() - 1, s, s2), v2sum(v.size() - 1, s, s2));
int l = 0, r = v.size() - 1, t = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (v1(v[mid], s) - v2(v[mid], s) >= 0) {
l = mid + 1;
t = mid;
} else {
r = mid - 1;
}
}
upans(tmp, t, s, s2);
l = 0, r = v.size() - 1, t = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (v1(v[mid], s) - v2(v[mid], s) >= 0) {
r = mid - 1;
t = mid;
} else {
l = mid + 1;
}
}
upans(tmp, t, s, s2);
l = 0, r = v.size() - 1, t = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (v1(v[mid], s) - v2(v[mid], s) <= 0) {
t = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
upans(tmp, t, s, s2);
l = 0, r = v.size() - 1, t = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (v1(v[mid], s) - v2(v[mid], s) <= 0) {
r = mid - 1;
t = mid;
} else {
l = mid + 1;
}
}
upans(tmp, t, s, s2);
sum += tmp;
}
if (s1 == 0) ans = sum;
ans = std::max(ans, sum);
}
print(ans);
// cout << ans << endl;
return 0;
}
Problem B. 整數生成器
一道有意思的線性代數？線性基？題目。
我不認為這道題太難，但是考場上只有五個隊寫出來這道題還是挺疑惑的。
首先我們要明確一個事實：加法和異或其實沒有那么大區別，他們構成的線性空間本質上甚至一樣，二者的性質和定理可以相互使用，所以我們最后可以直接高斯消元求解。我不太清楚怎么描述這個數學現象，同構？還是什么。
首先維護一個線性基，然后將所有數字插入到這組線性基中。很顯然題目給出的另外兩個運算 \(and\) 和 \(or\) 是可能構造出線性無關的向量的，于是我們直接隨機兩個數然后 \(and\) \(or\) 直接插進去。由生日悖論可以得知這樣做其實問題不大。
不過題解給出了更優秀的做法：把線性基中已有的數進行與或操作，正確性不會證（
由于線性基的大小不可能超過 \(32\)，所以兩種位運算的操作次數也不可能超過 \(32\)。題目給出的 \(70\) 上限其實是很難達到的。
最后我們對于這組線性基直接用它來高斯消元來獲取題目中要求的 \(x\)。而且線性基的大小不可能超過 \(32\)，不過線性基應該要額外保存好原始的數字，因為最后輸出答案的時候要給出原始數。
代碼：
#include <iostream>
#include <random>
#include <vector>
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 1e6 + 100;
class BASE {
int val[32];
int id[32];
public:
std::vector<int> v;
bool insert(int x, int t) {
for (int i = 31; i >= 0; i--) {
if ((x >> i) & 1) {
if (val[i]) {
x ^= val[i];
} else {
val[i] = x;
v.push_back(t);
id[i] = t;
return true;
}
}
}
return false;
}
} sour;
int matrix[34][34];
int a[kMaxN];
int n, x;
std::vector<std::tuple<int, int, int>> ans;
void calc() {
int m = sour.v.size();
for (int j = 0; j < m; j++) {
for (int i = 31; i >= 0; i--) {
matrix[i][j] = (a[sour.v[j]] >> i) & 1;
}
}
for (int i = 31; i >= 0; i--) {
matrix[i][32] = (x >> i) & 1;
}
for (int i = 0; i <= 31; i++) {
if (matrix[i][i] != 1) {
bool flag = false;
for (int j = i + 1; j <= 31 && !flag; j++) {
if (matrix[j][i] == 1) {
for (int k = 0; k < 34; k++) std::swap(matrix[i][k], matrix[j][k]);
flag = true;
}
}
}
if (matrix[i][i] != 1) continue;
for (int j = 0; j <= 31; j++) {
if (i == j) continue;
if (matrix[j][i]) {
for (int k = 0; k < 34; k++) {
matrix[j][k] ^= matrix[i][k];
}
}
}
}
std::vector<int> anslist;
for (int i = 0; i <= 31; i++) {
// 方程的秩不一致，說明無解
if (matrix[i][i] == 0 && matrix[i][32] != 0) {
return cout << -1 << endl, void();
}
if (matrix[i][32]) {
anslist.push_back(sour.v[i]);
}
}
if (anslist.size() == 1) {
goto end;
}
ans.push_back(std::make_tuple(1, anslist[0], anslist[1]));
// cout << 0 << ' ' << anslist[0] << ' ' << anslist[1] << endl;
n++;
a[n] = ::a[anslist[0]] ^ ::a[anslist[1]];
for (int i = 2; i < anslist.size(); i++) {
ans.push_back(std::make_tuple(1, n, anslist[i]));
// cout << 0 << ' ' << n << ' ' << anslist[i] << endl;
n++;
a[n] = ::a[n - 1] ^ ::a[anslist[i]];
}
end:
cout << ans.size() << endl;
for (auto[a, b, c] : ans) {
cout << a << ' ' << ::a[b] << ' ' << ::a[c] << endl;
}
}
std::random_device seed;
std::mt19937_64 e(seed());
int rand(int l, int r) {
std::uniform_int_distribution<int> rd(l, r);
return rd(e);
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
cin >> n >> x;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt += sour.insert(a[i], i);
}
if (x == 0) {
cout << 1 << endl;
cout << 1 << ' ' << a[1] << ' ' << a[1] << endl;
return 0;
}
for (int i = 1; i <= 1e5 && cnt < 40; i++) {
int x, y;
do {
x = rand(1, n), y = rand(1, n);
} while (x == y);
if (cnt < 40 && sour.insert(a[x] & a[y], n + 1)) {
n++;
a[n] = a[x] & a[y];
ans.push_back(std::make_tuple(2, x, y));
cnt++;
}
if (cnt < 40 && sour.insert(a[x] | a[y], n + 1)) {
n++;
a[n] = a[x] | a[y];
ans.push_back(std::make_tuple(0, x, y));
cnt++;
}
}
// cout << "AFTER INSERT" << endl;
// for (auto i : sour.v) {
// cout << i << ' ';
// }
// cout << endl;
calc();
return 0;
}
不過這份代碼事實上可以被 hack，但是官方數據居然沒有叉掉我……
Problem C. 切牌
算是把我的智商摁在地上錘的聰明題。好玩。
官方題解寫的很好我就放這里了：
首先注意到答案一定不會超過 \(n\), 因為如果目標序列前 \(k\) 個數是屬于某種切分方式中每一堆的第一個數，那么切分和排列方案是唯一的。
假設我們已經確定了前 \(k\) 個數是某一堆的第一個數，那么對于后面的 \(n ? k\) 個數，每個數 \(x\) 一定與 \(x ? 1\) 在同一堆，且 \(x ? 1\) 在目標序列的位置 \(p_x?1\) 在 \(x\) 的位置 \(p_x\) 左邊，我們把 \((p_x?1, p_x)\) 看成區間，是否合法的充要條件是 \(p_x?1 < p_x\) 且這些區間沒有包含關系，證明如下：
必要性：如果有包含關系，假設 \(p_{x-1} < p_{y-1} < p_y < p_x\)，那么因為 \(p_{x-1} < p_{y-1}\)，\(x\) 所在堆要在 \(y\) 前面；又由于 \(p_y < p_x\)，\(x\) 所在的堆要在 \(y\) 后面，產生矛盾。
充分性：因為知道前 \(k\) 個數，可以直接推出切分關系。由于沒有區間包含，我們可以根據前 \(k\) 個數得到一個堆之間的順序，直接按這個排列即可。
通過這個，我們可以推出一個結論：如果前 \(k\) 個數對應的切分是合法的，那么前 \(k + 1\) 個數的切分也是合法的，因為我們只是減少了區間數量，不會帶來新的區間矛盾。于是，每次詢問就變成了去找最大的不滿足條件的 \(k\)。
記原序列為 \(a_i\)，我們維護每個位置 \(x\) 是否滿足 \(p_{a_x - 1} < x\) 以及對應的區間 \((p_{a_x - 1},\, x)\) 是否被右邊一個位置的區間 \((p_{a_{x+1} - 1},\, x + 1)\) 包含。因為如果 \((p_{a_x - 1},\, x)\) 被某個區間包含，要么是 \((p_{a_{x+1} - 1},\, x + 1)\)，要么 \((p_{a_{x+1} - 1},\, x + 1)\) 也被這個區間包含，即會在比 \(x\) 更右邊的某個位置 \(y\) 產生矛盾。而我們的詢問是找最右邊會產生矛盾的位置，因此一定會找到該 \(y\)。
維護某個位置是否合法可以在 \(O(1)\) 時間內完成。每次交換會影響 \(O(1)\) 個位置。查詢最右邊矛盾的位置可以用線段樹實現?？傮w復雜度為\(O(n \log n)\)
其實也可以用樹狀數組實現其實（
代碼：
#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 1e6 + 100;
int n, q;
int a[kMaxN];
int p[kMaxN];
bool bad[kMaxN];
class SegmentTree {
struct node {
int val;
node* son[2];
int l, r;
} a[kMaxN], *root;
int tot = 0;
void pushup(node *p) {
p->val = std::max(p->son[0]->val, p->son[1]->val);
// p->val = p->son[0]->val | p->son[1]->val;
}
void build(node *p, int l, int r) {
p->val = 0, p->l = l, p->r = r;
if (l == r) return;
int mid = (l + r) >> 1;
p->son[0] = a + (tot++);
p->son[1] = a + (tot++);
build(p->son[0], l, mid);
build(p->son[1], mid + 1, r);
}
void upd(node *p, int x, int v) {
if (p->l > x || p->r < x) exit(-1);
if (p->l == p->r) return p->val = v, void();
if (p->son[0]->r >= x) upd(p->son[0], x, v);
if (p->son[1]->l <= x) upd(p->son[1], x, v);
pushup(p);
}
public:
int query() {
return root->val;
}
void build() {
root = a + (tot++);
build(root, 1, n);
}
void upd(int p, int v) {
if (p < 1) return;
if (p > n) return;
// cout << "UPD " << p << ' ' << v << endl;
upd(root, p, v);
pushup(root);
}
} tree;
int checkbad(int i) {
if (i <= 0) return 0;
if (i > n) return 0;
if (a[i] == 1) return 1;
if (p[a[i] - 1] > i) return 1;
if (i < n) {
if (p[a[i + 1] - 1] <= p[a[i] - 1]) return 1;
}
return 0;
}
void run() {
// bad 表示在i之前進行分割是錯誤的
for (int i = 0; i <= n; i++) bad[i] = false;
for (int i = 1; i <= n; i++) {
if (a[i] == 1) {
bad[i] = true;
}
if (p[a[i] - 1] > i) bad[i] = true;
if (i < n) {
if (p[a[i + 1] - 1] <= p[a[i] - 1]) bad[i] = true;
}
}
bad[1] = true;
int ans = 1;
for (int i = n; i >= 1; i--) {
if (bad[i]) break;
ans++;
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[a[i]] = i;
}
tree.build();
auto upd = [&](int x) {
tree.upd(x, checkbad(x) * x);
};
for (int i = 1; i <= n; i++) {
upd(i);
}
cout << n - tree.query() + 1 << endl;
while (q--) {
int x, y;
cin >> x >> y;
std::swap(a[x], a[y]);
// 不是很想仔細去考慮會影響哪些位置了，直接這樣拋棄大腦去寫了
p[a[x]] = x;
p[a[y]] = y;
upd(x);
upd(y);
upd(x - 1);
upd(y - 1);
upd(x + 1);
upd(y + 1);
upd(p[a[x] + 1]);
upd(p[a[y] + 1]);
upd(p[a[x] - 1]);
upd(p[a[y] - 1]);
upd(p[a[x] + 1] - 1);
upd(p[a[y] + 1] - 1);
upd(p[a[x] - 1] - 1);
upd(p[a[y] - 1] - 1);
upd(p[a[x] + 1] + 1);
upd(p[a[y] + 1] + 1);
upd(p[a[x] - 1] + 1);
upd(p[a[y] - 1] + 1);
cout << n - tree.query() + 1 << endl;
}
return 0;
}
Problem D. 生成魔咒
?。窟@題真的需要講嗎？
代碼：
#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
void solve() {
long long n;
cin >> n;
long long t = 0;
long long ans = 0;
while (n) {
ans += (1ll << t) * (n % 10);
n /= 10;
t++;
}
cout << ans << endl;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Problem E. 網格染色
考場上 0 人通過的細節貪心題。當然其實不是最難的那道就是嘍……
但是似認為這道題難度其實低于 B。
我們的染色操作只能減少聯通塊數量。 而且任何可以連接兩個以上聯通塊的情況一定可以被分割成若干次連接兩個聯通塊的方法，所以我們接下來只需要考慮連接兩個聯通塊的操作。
有效的染色的操作主要有兩種：
* * 1 0 0 0 1 * * * * 1 1 1 1 1 * *
* * * * * * * * * -> * * * * * * * * *
數字相同的在同一列，顯然兩個數可以直接連起來
另外一種情況：不在同一列或者被其他數字擋掉
* * 1 0 0 * * *
* * * 0 0 1 * *
* * 1 0 0 * 1 * *
* * * 0 0 0 0 * *
* * * 0 0 * 1 * *
* * 1 0 0 0 0 * *
當然，我們需要注意一個很特別的情況：
* 2 0 1 1 1 *
* * 0 0 0 0 2
這種情況下填 1 是沒有任何收益的。所以我們選擇填數的時候，這個數一定要保證已經出現在兩個聯通塊中，同時填完了之后刷新一下所屬聯通塊就好。
復雜度顯然 \(O(n)\)，但是我太懶了用了 set 所以復雜度比較玄學。
代碼：
#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <unordered_map>
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 1e6 + 100;
int n;
int a[3][kMaxN];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dfntot = 0;
int dfn[3][kMaxN];
int fa[kMaxN];
int init(int x, int y) {
return (x - 1) * n + 10 + y;
}
// 維護所屬聯通快
void update(int x, int y, int t) {
std::queue<std::pair<int, int>> q;
auto record = [&](int tx, int ty) {
if (tx < 1 || tx > 2 || ty < 1 || ty > n) return;
if (a[tx][ty] != a[x][y]) return;
if (dfn[tx][ty] == t) return;
dfn[tx][ty] = t;
q.push({tx, ty});
};
record(x, y);
while (!q.empty()) {
auto[x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
record(x + dx[i], y + dy[i]);
}
}
}
void flush(std::vector<std::pair<int, int>>& v, int col, int mergeto = -1) {
for (auto [x, y] : v) {
a[x][y] = col;
if (mergeto != -1) {
dfn[x][y] = mergeto;
}
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
cin >> n;
for (int i = 1; i < kMaxN; i++) fa[i] = i;
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= 2; i++) {
int lastcol = -1;
for (int j = 1; j <= n; j++) {
if (lastcol && a[i][j] == lastcol && a[i][j - 1] == 0) {
for (int k = j - 1; k >= 1 && a[i][k] == 0; k--) {
a[i][k] = lastcol;
}
}
if (a[i][j]) lastcol = a[i][j];
}
}
for (int j = 1; j <= n; j++) {
if (a[1][j] && dfn[1][j] == 0) {
update(1, j, ++dfntot);
}
if (a[2][j] && dfn[2][j] == 0) {
update(2, j, ++dfntot);
}
}
int lastcol = 0;
std::vector<std::pair<int, int>> zeroblock;
std::set<int> inset;
std::unordered_map<int, int> setcnt;
auto record = [&](int x, int y) {
if (x < 1 || x > 2 || y < 1 || y > n) return;
if (a[x][y] == 0) return;
if (inset.count(dfn[x][y])) return;
inset.insert(dfn[x][y]);
setcnt[a[x][y]]++;
};
auto check = [&](int x, int y) {
if (x < 1 || x > 2 || y < 1 || y > n) return false;
if (a[x][y] == 0) return false;
return setcnt[a[x][y]] >= 2;
};
for (int j = 1; j <= n; j++) {
if (zeroblock.size()) {
// 如果不聯通
if ((a[1][j] + a[1][j - 1]) && (a[2][j] + a[2][j - 1])) {
if (a[1][j] && a[1][j - 1] == 0) flush(zeroblock, a[1][j], dfn[1][j]);
else if (a[2][j] && a[2][j - 1] == 0) flush(zeroblock, a[2][j], dfn[2][j]);
else exit(-1);
inset.clear();
setcnt.clear();
zeroblock.clear();
}
}
if (a[1][j]) lastcol = a[1][j];
if (a[2][j]) lastcol = a[2][j];
if (a[1][j] == 0) zeroblock.push_back({1, j});
if (a[2][j] == 0) zeroblock.push_back({2, j});
for (int i = 1; i <= 2 && zeroblock.size(); i++) {
if (a[i][j] != 0) continue;
for (int k = 0; k < 4 && zeroblock.size(); k++) {
record(i + dx[k], j + dy[k]);
if (check(i + dx[k], j + dy[k])) {
flush(zeroblock, a[i + dx[k]][j + dy[k]], dfn[i + dx[k]][j + dy[k]]);
inset.clear();
setcnt.clear();
zeroblock.clear();
}
}
}
}
if (zeroblock.size()) {
if (lastcol == 0) lastcol = 1;
flush(zeroblock, lastcol);
zeroblock.clear();
}
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << ' ';
}
cout << endl;
}
return 0;
}
Problem F. 排名預測
也是非常簡單的一道題，算是讓小白明白 XCPC 的罰時計算機制了。
不過要注意一點：如果一個題沒有通過，那么這個題是不算罰時的。注意到這一點就可以去貪心了。
#include <iostream>
#include <algorithm>
#include <vector>
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
void solve() {
int n, a, b, s;
cin >> n >> a >> b;
std::vector<int> cnt(128, 0);
std::vector<bool> pass(128, 0);
std::vector<int> pro;
cin >> s;
int A = 0, B = 0;
int tot = 0;
for (int i = 1; i <= s; i++) {
int t;
char ch;
std::string status;
cin >> t >> ch >> status;
if (pass[ch]) continue;
if (status == "ac" || status == "pd") {
pass[ch] = true;
if (status == "pd") {
pro.push_back(t + 20 * cnt[ch]);
} else {
A++;
B += t + 20 * cnt[ch];
}
} else {
cnt[ch]++;
}
}
if (A > a || (A == a && B < b)) {
return cout << 0 << endl, void();
}
std::sort(pro.begin(), pro.end());
for (int i = 0; i < pro.size(); i++) {
B += pro[i], A++;
if (A > a || (A == a && B < b)) {
return cout << i + 1 << endl, void();
}
}
cout << -1 << endl;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Problem G. 貨幣系統
有趣的計數題，要是想到正確做法還是不難的。
先給 \(A_n\) 排序，記 \(cnt_i\) 為 \(f(x, n) = i\) 的數量，然后我們先預處理出小于 \(A_n\) 情況下所有數字的 \(f(x, n)\) 并且統計到 \(cnt_i\) 里面。
接下來我們需要想辦法統計所有大于 \(A_n\) 的數字。當然這顯然是荒誕的，TLE 會給你來上一巴掌。
我們可以發現對于任何大于 \(A_n\) 的數字，它一定要墊若干張 \(A_n\) 然后變成 \(1\) 到\(A_n\) 中的某一個數。不難想到對于任意 \(f(x, n) = 1\)，\(x + A_n\) 可以為 \(cnt_2\) 產生貢獻，\(x + 2 A_n\) 可以為 \(cnt_3\) 產生貢獻……以此類推
于是對 \(cnt_i\) 取個前綴和一切都結束了（
代碼：
#include <cassert>
#include <iostream>
#include <algorithm>
#define int long long
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 2e6 + 100;
int n, m;
int ans[kMaxN];
int a[kMaxN];
int able[kMaxN], sum = 0;
int cnt[kMaxN];
int query(int x) {
if (x > a[n]) {
return query(x % a[n]) + x / a[n];
}
if (ans[x] != -1) return ans[x];
return ans[x] = (query(x % a[able[x]]) + x / a[able[x]]);
}
void solve() {
int x;
cin >> x;
if (x >= a[n]) {
cout << cnt[a[n]] << ' ';
} else {
cout << cnt[x] << ' ';
}
}
signed main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < kMaxN; i++) ans[i] = -1;
ans[0] = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
std::sort(a + 1, a + 1 + n);
int j = 1;
for (int i = 1; i <= 1e6; i++) {
while (j != n && a[j + 1] <= i) j++;
able[i] = j;
}
for (int i = 1; i <= a[n]; i++) {
cnt[query(i)]++;
}
for (int i = 1; i <= a[n]; i++) {
cnt[i] += cnt[i - 1];
}
while (m--) {
solve();
}
return 0;
}
Problem H. 松散子序列
非常經典的一道題啊，就是從本質不同子序列的轉移上面動一下手腳就結束了。我感覺官方題解給的狀態轉移方程其實有問題，不過我的狀態設計和他不太一樣……
直接看代碼吧，沒什么好講的。大部分設計其實可以參考本質不同子序列的寫法。
代碼：
#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 1e6 + 100;
const int MOD = 998244353;
int inc(int a, int b) {
return (a + b) >= MOD ? a + b - MOD : a + b;
}
int dec(int a, int b) {
return (a - b) < 0 ? a - b + MOD : a - b;
}
int mul(int a, int b) {
return (1ll * a * b) % MOD;
}
int dp[kMaxN][128];
void solve() {
int n, k;
std::string str;
cin >> n >> k >> str;
str = '#' + str;
for (int i = 0; i <= n; i++) {
for (int j = 'a'; j <= 'z'; j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
int sum = 1;
for (int j = 'a'; j <= 'z'; j++) {
int l = (i - k - 1);
if (l < 0) l = 0;
sum = inc(sum, dp[l][j]);
}
for (int j = 'a'; j <= 'z'; j++) {
if (j == str[i]) {
dp[i][j] = inc(dp[i][j], sum);
continue;
}
dp[i][j] = inc(dp[i][j], dp[i - 1][j]);
}
}
int ans = 0;
for (int j = 'a'; j <= 'z'; j++) {
ans = inc(ans, dp[n][j]);
}
cout << ans << endl;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Problem I. 隊伍取名
一個不是太難的冗斥。
通過枚舉 \(id\) 來考慮被組成的人，接下來我們只需要去尋找兩個人，使得這兩個人和 \(id\) 名字中某兩個數相同即可。
我們可以輕易統計出名字位置上 \((1, 3)\) 相同、 \((2, 3)\) 相同、 \((1, 2)\) 相同的人數，并且冗斥出來只有 \(1\)、\(2\)、\(3\) 相同的人數。于是就可以計算出答案了。
代碼實現比較暴力，冗斥也是手動冗斥（
代碼：
#include <iostream>
#include <cassert>
#include <unordered_map>
#define int long long
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 1e6 + 100;
int n;
int name[kMaxN][4];
int tot = 0;
int cnt[4][kMaxN];
std::unordered_map<int, int> cnt1[kMaxN];
std::unordered_map<int, int> cnt2[kMaxN];
std::unordered_map<int, int> cnt3[kMaxN];
int dp[kMaxN][8];
int calc(int v) {
return (v - 1) * v / 2;
}
signed main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++) {
cin >> name[i][j];
cnt[j][name[i][j]]++;
}
// 不可能有人同時在 cnt1 和 cnt2 中有計數，除了他自己
cnt1[name[i][1]][name[i][2]]++;
cnt2[name[i][1]][name[i][3]]++;
cnt3[name[i][2]][name[i][3]]++;
}
// for each i, find a (j, k) st the have two same val to i
int ans = 0;
for (int i = 1; i <= n; i++) {
dp[i][1] = cnt[1][name[i][1]] - 1;
dp[i][2] = cnt[2][name[i][2]] - 1;
dp[i][4] = cnt[3][name[i][3]] - 1;
dp[i][3] = cnt1[name[i][1]][name[i][2]] - 1;
dp[i][5] = cnt2[name[i][1]][name[i][3]] - 1;
dp[i][6] = cnt3[name[i][2]][name[i][3]] - 1;
dp[i][1] -= dp[i][3] + dp[i][5];
dp[i][2] -= dp[i][3] + dp[i][6];
dp[i][4] -= dp[i][5] + dp[i][6];
for (int k = 1; k <= 6; k++) {
for (int j = k + 1; j <= 6; j++) {
ans += dp[i][j] * dp[i][k];
}
}
ans += calc(dp[i][3]) + calc(dp[i][5]) + calc(dp[i][6]);
}
cout << ans << endl;
return 0;
}
Problem J. 解謎比賽
官方題解說這道題是拓撲排序，但是我并沒有從題目中看到保證 DAG 的信息……我怎么感覺其實是 dijkstra 的變形？
對于強制刷新器有兩種處理辦法：
-
直接設定其入隊的時間
-
設置一個虛擬節點，然后將貢獻調整為 \(\infty\)
我們對于任何一個點，維護一個 heap （或者是優先隊列，隨便了）用來存放最早提供貢獻的 \(k\) 個時間點，當 \(k \geq a_i\) 時就可以將 \(i\) 入隊了。具體實現看代碼。
代碼：
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <set>
#define int long long
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 2e6 + 10;
std::vector<std::pair<int, int>> go[kMaxN];
struct type {
int t, id;
bool operator < (const type& p) const {
if (t == p.t) return id < p.id;
return t < p.t;
}
};
bool used[kMaxN];
int n, m, k;
std::set<type> s;
int ubtime[kMaxN];
int a[kMaxN], power[kMaxN];
std::priority_queue<int> q[kMaxN];
void record(int t, int id) {
if (used[id]) return;
if (t > ubtime[id]) return;
s.erase({ubtime[id], id});
ubtime[id] = t;
s.insert({t, id});
}
int vtot = 0;
void dijkstra() {
while (!s.empty()) {
auto[t, id] = *s.begin();
s.erase(s.begin());
if (used[id]) continue;
used[id] = true;
for (auto[v, w] : go[id]) {
if (a[v] == 0) {
record(ubtime[id] + w, v);
continue;
}
if (q[v].size() >= a[v]) q[v].pop();
q[v].push(ubtime[id] + w);
if (q[v].size() >= a[v]) {
record(q[v].top(), v);
}
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
cin >> n >> m >> k;
memset(ubtime, 0x3f, sizeof(ubtime));
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 0) {
record(0, i);
}
}
vtot = n + 10;
for (int i = 1; i <= k; i++) {
int t, s, id;
cin >> t >> s;
for (int i = 1; i <= s; i++) {
cin >> id;
record(t, id);
}
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
go[u].push_back({v, w});
}
dijkstra();
for (int i = 1; i <= n; i++) {
if (used[i] == false) ubtime[i] = -1;
cout << ubtime[i] << ' ';
}
return 0;
}
Problem K. 打字機
其實不是太難的一個字符串題目……只是我覺得我像個傻子。
這道題其實是有 \(O(n)\) 的妙妙做法的，大概思路就是用 \(Manacher\) 處理掉回文的問題，然后跑一遍 \(z函數\)。我沒有仔細想這個方向所以用 \(hash\) 跑了一個 \(O(n \log n)\) 的做法，最后統計答案的時候寫的也不是很優雅。
我們將題目進一步抽象：
找到一個字符串形如 \(T = (aLb), |L| \geq 0\)，使得 \((aLbL^R)^{\infty}\) 的一個前綴是 \(S\)。
當然有特殊情況就是 \(|T| = 1\) 的情況，這里要特殊處理一下。我當時就是因為沒有特殊處理卡死了好久 QAQ。
容易發現一個正確的 \(T\) 是可以為若干個連續的前綴 \(S'\) 提供貢獻的，這對應一個區間。
容易發現最小循環周期不是 \(T\) 而是 \(aLbL^R\)，我們可以通過倍增 + 二分來得到區間右端點。
當然這里還需要特殊考慮一種情況：\(S\) 的長度不允許你跑完一個完整的周期 \(aLbL^R\)，這里也要特殊處理一下。
代碼，當時調試的時候以為自己哈希沖突了所以寫了個雙哈希：
#include <cassert>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
#define int long long
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 1e6 + 100;
int n;
std::string str;
template<int MOD>
class hasher {
int hash_[kMaxN];
int revhash_[kMaxN];
int inc(int x, int y) { return (x + y) >= MOD ? x + y - MOD : x + y; }
int dec(int x, int y) { return (x - y) < 0 ? x - y + MOD : x - y; }
int mul(int x, int y) { return (1ll * x * y) % MOD; }
int powch[kMaxN];
int invch[kMaxN];
int pow(int x, int p) {
int ans = 1;
while (p) {
if (p & 1) ans = mul(ans, x);
p >>= 1, x = mul(x, x);
}
return ans;
}
public:
int kk[kMaxN];
int hash(int l, int r) {
assert(l <= r);
return dec(hash_[r], mul(hash_[l - 1], powch[r - l + 1]));
}
int revhash(int l, int r) { return dec(revhash_[l], mul(revhash_[r + 1], powch[r - l + 1])); }
void init(const std::string& str) {
hash_[0] = revhash_[n + 1] = 0;
for (int i = 1; i <= n; i++) {
hash_[i] = inc(mul(hash_[i - 1], powch[1]), str[i]);
}
for (int i = n; i >= 1; i--) {
revhash_[i] = inc(mul(revhash_[i + 1], powch[1]), str[i]);
}
}
hasher() {
powch[0] = invch[0] = 1;
powch[1] = 128, invch[1] = pow(128, MOD - 2);
for (int i = 2; i < kMaxN; i++) {
powch[i] = mul(powch[i - 1], powch[1]);
invch[i] = mul(invch[i - 1], invch[1]);
}
}
void upkk(int mid) {
kk[0] = hash(1, mid);
for (int i = 1; i <= 20; i++) {
if ((1ll << i) * mid > kMaxN) break;
kk[i] = inc(kk[i - 1], mul(kk[i - 1], powch[(1 << (i - 1)) * mid]));
}
}
};
hasher<998244353> hash1;
hasher<(int)(1e9 + 7)> hash2;
int kk[30];
int kk2[30];
int cnt[kMaxN];
std::vector<int> begin[kMaxN];
std::vector<int> end[kMaxN];
void run(int mid) {
if (mid == n) return;
if (mid % 2) return;
if (mid != 2) {
int mid2 = mid >> 1;
if (hash1.hash(2, mid2) != hash1.revhash(mid2 + 2, mid)) return;
if (hash2.hash(2, mid2) != hash2.revhash(mid2 + 2, mid)) return;
}
hash1.upkk(mid);
hash2.upkk(mid);
int lastp = mid;
for (int i = 20; i >= 0; i--) {
long long nextp = (lastp + 1ll * mid * (1 << i));
if (nextp > n) continue;
if (hash1.kk[i] == hash1.hash(lastp + 1, nextp) &&
hash2.kk[i] == hash2.hash(lastp + 1, nextp)) {
lastp = nextp;
}
}
int l = 1, r = mid, able = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (lastp + mid <= n &&
hash1.hash(lastp + 1, lastp + mid) == hash1.hash(1, mid) &&
hash2.hash(lastp + 1, lastp + mid) == hash2.hash(1, mid)) {
l = mid + 1;
able = mid;
} else {
r = mid - 1;
}
}
lastp += able;
cnt[mid / 2 + 1]++;
end[lastp].push_back(mid / 2 + 1);
}
void runtwo(int t) {
int Llen = t - 2;
int l = 1, r = Llen, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (t + mid <= n &&
hash1.revhash(t - mid, t - 1) == hash1.hash(t + 1, t + mid) &&
hash2.revhash(t - mid, t - 1) == hash2.hash(t + 1, t + mid)) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
if (ans != 0) {
cnt[t]++;
end[t + ans].push_back(t);
}
}
bool bfcheck(const std::string& str, const std::string& sub) {
int v = 1, p = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] != sub[p]) return false;
if (p + v >= sub.size() || p + v < 0) v *= -1;
p += v;
if (sub.size() == 1) p = 0;
}
return true;
}
std::set<int> s;
void solve() {
s.clear();
cin >> str;
n = str.size(); str = '#' + str + '#';
bool flag = true;
for (int i = 2; i <= n && flag; i++) {
flag &= str[i] == str[i - 1];
}
if (flag) {
int ans = 0;
for (int i = 1; i <= n; i++) {
ans ^= 1 * i;
}
return cout << ans << endl, void();
}
hash1.init(str);
hash2.init(str);
for (int i = 2; i <= n; i++) {
run(i);
}
for (int i = 2; i < n; i++) {
runtwo(i);
}
cnt[1]++;
for (int i = 2; i <= n; i++) {
if (str[i] != str[i - 1]) {
end[i - 1].push_back(1);
break;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (cnt[i]) s.insert(i);
// if (caninsert[i]) s.insert(i);
int tmp;
if (s.empty()) {
tmp = i;
ans ^= i * i;
} else {
tmp = *s.begin();
ans ^= i * (*s.begin());
}
for (auto v : end[i]) {
cnt[v]--;
if (cnt[v] == 0) s.erase(v);
}
end[i].clear();
}
for (int i = 1; i <= n; i++) cnt[i] = 0;
cout << ans << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Problem L. 路線選擇
嗯……雖然作為一個插頭 DP 看上去真的很嚇人好不好……但是寫完了感覺這個插頭 DP 其實還是挺板的一道題。
考慮狀態設計：由于我們是從上到下開始遍歷，所以同時只會存儲橫向至多 \(4\) 個點的狀態。對于每一個點一共有兩個狀態需要處理：已經經過的路徑度奇偶性和所屬聯通塊?？梢园l現這個狀態其實非常小，于是直接壓縮進一個數內，其數量大概也就是 \(2 * (m + 1)^m\)，事實上非常小。
至于狀態轉移，一共有六種情況，這里可以看代碼里的注釋。
代碼：
// 非常hard的一道題，考場上能寫出來的那隊真的是神仙，甚至還是一遍過
#include <iostream>
#include <ctime>
#include <cstring>
#include <algorithm>
#include <vector>
using std::cin;
using std::cout;
using std::cerr;
const char endl = '\n';
const int kMaxN = 1e6 + 100;
template <class type>
void upmin(type& a, const type& b) { a = std::min(a, b); }
template <class type>
void upmax(type& a, const type& b) { a = std::max(a, b); }
struct path {
int v;
std::vector<double> pos;
// 0 不走
// 1 走一次
// 2 來回
// 3 左邊走到最右邊但不到點/上面走到最下面但不到點
// 4 右邊走到最左邊但不到點/下面走到最上面但不到點
// 5 兩個點同時走但是在中間一個地方回頭
double val[6];
void init() {
double c = 1.0 / v;
val[1] = c, val[2] = c * 2;
if (pos.empty()) return;
std::sort(pos.begin(), pos.end());
val[0] = 1e18;
val[3] = 2 * pos.back() * c;
val[4] = 2 * (1 - pos.front()) * c;
pos.push_back(1);
val[5] = 1e18;
for (int i = 0; i < pos.size(); i++) {
upmin(val[5], (i ? pos[i - 1] * 2 * c : 0) + ((1 - pos[i]) * 2 * c));
}
}
};
path pathR[70][10], pathC[70][10];
// 狀態構造：每個端點出度的奇偶性+所屬于的聯通塊，然后把所有點的信息壓縮到一個數字內。不難證明數量不超過 10^m (上限)
double dp[2][10010];
bool has[1145][1145];
int n, m, k;
bool isInt(double x) {
return x == (int)x;
}
std::pair<int, int> nextState_[10010][10][7][7];
bool vis[10010][10][7][7];
int total = 1;
int cnt[6], bel[6], deg[6];
void clear() {
memset(cnt, 0, sizeof(cnt));
memset(bel, 0, sizeof(bel));
memset(deg, 0, sizeof(deg));
}
// 考慮從(u, p)轉移到的下一個狀態，同時走法是(i, j)，i考慮列走法，j考慮行走法
// 兩個值代表不經過和經過
const std::pair<int, int>& nextState(int u, int p, int i, int j) {
if (vis[u][p][i][j]) return nextState_[u][p][i][j];
auto& state = nextState_[u][p][i][j];
vis[u][p][i][j] = true;
clear();
// cnt = std::vector<int>(5, 0);
// bel = std::vector<int>(m + 1, 0);
// deg = std::vector<int>(m + 1, 0);
int now = u;
for (int t = m - 1; t >= 0; t--) {
int tmp = now % (2 * (m + 1));
now /= 2 * (m + 1);
deg[t] = tmp / (m + 1);
bel[t] = tmp % (m + 1);
cnt[bel[t]]++;
}
if ((deg[p] ^ (i == 1)) ||
(bel[p] == 0 && i != 0 && i != 4) ||
(bel[p] && cnt[bel[p]] == 1 && (i != 1 && i != 2)) ||
(p && bel[p - 1] == 0 && j != 0 && j != 4) ||
(j && p == 0)) {
return state;
}
int BEL = bel[p];
deg[p] = bel[p] = 0;
if ((i == 0 || i == 3) && (j == 0 || j == 3)) {
int nxt = 0;
for (int t = 0; t < m; t++) {
nxt *= 2 * (m + 1);
nxt += deg[t] * (m + 1) + bel[t];
}
state.first = nxt;
} else {
if (i == 1 || i == 2) {
deg[p] ^= i == 1;
bel[p] = BEL;
}
if (j == 1 || j == 2) {
deg[p] ^= j == 1;
deg[p - 1] ^= j == 1;
int nxt = bel[p - 1];
if (bel[p]) {
for (int t = 0; t < m; t++) {
if (bel[t] == BEL) bel[t] = nxt;
}
} else {
bel[p] = nxt;
}
}
}
for (auto& i : cnt) i = 0;
for (int i = 0; i < m; i++) {
cnt[bel[i]]++;
}
if (bel[p] == 0) {
for (int i = 1; i <= m; i++) {
if (cnt[i] == 0) {
bel[p] = i;
break;
}
}
}
int nxt = 0;
for (int i = 0; i < m; i++) {
nxt *= 2 * (m + 1);
nxt += deg[i] * (m + 1) + bel[i];
}
state.second = nxt;
return state;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
cin >> pathR[i][j].v;
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
cin >> pathC[i][j].v;
}
}
for (int i = 1; i <= k; i++) {
double x, y;
cin >> x >> y;
int ix = (int)x, iy = (int)y;
if (!isInt(x)) {
pathC[ix][iy].pos.push_back(x - ix);
} else if (!isInt(y)) {
pathR[ix][iy].pos.push_back(y - iy);
} else {
has[ix][iy] = true;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
pathC[i][j].init(), pathR[i][j].init();
}
}
for (int i = 1; i <= m; i++) {
total *= (m + 1) * 2;
}
for (int i = 0; i < 10000; i++) {
dp[0][i] = 1e18;
}
int begin = m + 1 + 1;
for (int i = 1; i < m; i++) begin *= 2 * (m + 1);
dp[0][begin] = 0;
int now = 0, lst = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 && j == 0) continue;
now ^= 1, lst ^= 1;
for (int t = 0; t < total; t++) {
dp[now][t] = 1e18;
}
for (int u = 0; u < total; u++) {
if (dp[lst][u] >= 1e18) continue;
for (int x = 0; x <= 5; x++) {
if (i == 0 && x != 0) continue;
for (int y = 0; y <= 5; y++) {
if (j == 0 && y != 0) continue;
const auto&[s1, s2] = nextState(u, j, x, y);
if (has[i][j] == false && s1 != -1) {
upmin(dp[now][s1], dp[lst][u] +
(j == 0 ? 0 : pathR[i][j - 1].val[y]) +
(i == 0 ? 0 : pathC[i - 1][j].val[x]));
}
if (s2 != -1) {
upmin(dp[now][s2], dp[lst][u] +
(j == 0 ? 0 : pathR[i][j - 1].val[y]) +
(i == 0 ? 0 : pathC[i - 1][j].val[x]));
}
}
}
}
}
}
double ans = 1e18;
for (int u = 0; u < total; u++) {
clear();
{
int now = u;
for (int t = m - 1; t >= 0; t--) {
int tmp = now % (2 * (m + 1));
now /= 2 * (m + 1);
deg[t] = tmp / (m + 1);
bel[t] = tmp % (m + 1);
cnt[bel[t]]++;
}
}
bool flag = true;
flag &= bel[m - 1] != 0;
flag &= deg[m - 1] == 1;
flag &= cnt[0] + cnt[bel[m - 1]] == m;
for (int i = 0; i + 1 < m; i++) flag &= deg[i] == 0;
if (flag) upmin(ans, dp[now][u]);
}
printf("%.9lf", ans);
// cout << ans << endl;
return 0;
}
浙公網安備 33010602011771號