唉唉，今天狀況超級不對啊。整個就是撞牆卡在 Suffix Palindrome 完全寫不出來，然後到了快三個半鐘頭才想到 Lighting Rectangle 要怎麼寫，還錯了一次，真是奇慘無比。
Lighting Rectangle RECTLIT
解法
簡單來說就是分 Case 題：
- 在內部如果有四個點，那麼存在一種方式可以照亮所有區域。
- 如果角落有一個點，那麼一定可以照亮所有區域。
- 把邊分成上下、跟左右兩個部份。如果其中一個部份有兩個點，那可以照亮所有區域。
- 如果邊上有一個點、而且內部有至少兩個點，那麼可以照亮所有區域。
- 如果邊上有兩個點、而且內部至少有一個點，那麼可以照亮所有區域。
- 除了以上情形外，其他情形都無法照亮所有區域。
參考程式碼
// by tmt514
#include <cstdio>
using namespace std;
void solve() {
int K, N;
scanf("%d%d", &K, &N);
int ncorner = 0;
int nsidex = 0;
int nsidey = 0;
int ninside = 0;
for(int i=0;i<K;i++) {
int x, y;
scanf("%d%d", &x, &y);
int sx = (x==0 || x==N-1);
int sy = (y==0 || y==N-1);
if(sx && sy) { ncorner++; }
else if(sx) { nsidex++; }
else if(sy) { nsidey++; }
else ninside++;
}
if (ncorner==0 && nsidex==1 && nsidey==1 && ninside==0) puts("no");
else
puts(4*ncorner + 2*nsidex + 2*nsidey + ninside >= 4? "yes": "no");
}
int main(void) {
int T;
scanf("%d", &T);
while(T--) solve();
return 0;
}
Suffix Palindromes SFXPAL
解法
這是一道很漂亮的 DP 題。假設 $f(n)$ 是答案，那麼每個字串的最後 $n-1$ 個字元都會被算入 $f(n-1)$。所以我們可以嘗試扣除掉加了一個字元以後會變成迴文的可能情形。而利用迴文的特性，我們可以證明在「加了一個字以後變成迴文」的當下，所有可能的迴文只能是來自 $f(\lceil n/2\rceil)$。所以，可以從 $f(1)=S$ 開始，依序計算 $f(n) = Sf(n-1) - f(\lceil n/2\rceil)$。
參考程式碼
// by tmt514
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
int main(void) {
LL N, S, M;
cin >> N >> S >> M;
vector<LL> dp(N+1);
dp[0] = 1;
dp[1] = S;
for (int i = 2; i <= N; i++) {
dp[i] = S*dp[i-1] - dp[(i+1)/2];
dp[i] = (dp[i]%M+M)%M;
}
cout << dp[N] << endl;
return 0;
}
Adi and the Tree ADITREE
解法
另一個乾淨的漂亮問題。這題的主要觀察點在於：最小的距離總和，恰好等於所有「子樹中有奇數個亮燈」節點的數量。所以我們只需要維護一個資料結構，使得每次更新兩個點後，順便更新節點的奇偶性就行了！
要怎麼動 態更新節點的奇偶性呢？我們可以利用樹鍊剖分，把一棵樹分成許多路徑，使得任何一個節點到樹根的路上至多只跨越 $O(\log N)$ 條路徑。我們在每一條路徑上面維護一個線段樹，因此總時間複雜度是 $O(N+M\log^2 N)$。
// by tmt514
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
struct SegNode {
int odd, even;
bool inverted;
};
class SegmentTree {
public:
vector<SegNode> seg;
void init(int x, int l, int r) {
if (l == r) seg[x] = (SegNode){0, 1, false};
else {
int m = (l+r)/2;
init(x*2, l, m);
init(x*2+1, m+1, r);
seg[x] = (SegNode){0, r-l+1, false};
}
}
void init(int n) {
seg.resize(4*n);
init(1, 1, n);
}
void push(int x, int l, int r) {
if (l == r) { seg[x].inverted = false; }
else if (seg[x].inverted) {
swap(seg[x*2].odd, seg[x*2].even);
swap(seg[x*2+1].odd, seg[x*2+1].even);
seg[x*2].inverted ^= 1;
seg[x*2+1].inverted ^= 1;
seg[x].inverted = false;
}
}
void pull(int x) {
seg[x].odd = seg[x*2].odd + seg[x*2+1].odd;
seg[x].even = seg[x*2].even + seg[x*2+1].even;
if (seg[x].inverted) swap(seg[x].odd, seg[x].even);
}
void toggle(int x, int l, int r, int target) {
if (r <= target) {
swap(seg[x].odd, seg[x].even);
seg[x].inverted ^= 1;
} else {
int m = (l+r)/2;
push(x, l, r);
toggle(x*2, l, m, target);
if (target > m) toggle(x*2+1, m+1, r, target);
pull(x);
}
}
int ask(int x, int l, int r, int target) {
if (r <= target) {
return seg[x].odd;
} else {
int m = (l+r)/2;
push(x, l, r);
return seg[x*2].odd + ask(x*2+1, m+1, r, target);
}
}
};
const int N = 250000;
vector<int> a[N];
int total_odd[N];
int parent[N];
int depth[N];
int child[N];
int segtree_idx[N];
int segtree_seq[N];
SegmentTree t[N];
int segtree_root[N];
void find_depth_dfs(int x, int p=-1) {
parent[x] = p;
depth[x] = 1;
for(auto y : a[x]) {
if (y != p) {
find_depth_dfs(y, x);
if(depth[y]+1 > depth[x]) {
depth[x] = depth[y]+1;
child[x] = y;
}
}
}
}
int all_segids = 0;
void build_segment_tree(int x, int segid=0, int d=1) {
segtree_idx[x] = segid;
segtree_seq[x] = d;
if (d == 1) {
segtree_root[segid] = x;
t[segid].init(depth[x]);
}
for (auto y : a[x]) {
if (y == parent[x]) continue;
if (y == child[x]) build_segment_tree(y, segid, d+1);
else {
all_segids++;
build_segment_tree(y, all_segids, 1);
}
}
}
// 找出修改狀態時會經過的每一條鍊，我們把每一條鍊的進入點蒐集起來。
void toggle(int x) {
vector<int> tree_ids;
int c = x;
while (c != -1) {
tree_ids.push_back(c);
c = parent[segtree_root[segtree_idx[c]]];
}
int delta = 0;
for (auto c : tree_ids) {
auto& tree = t[segtree_idx[c]];
delta -= tree.seg[1].odd;
tree.toggle(1, 1, depth[segtree_root[segtree_idx[c]]], segtree_seq[c]);
delta += tree.seg[1].odd;
total_odd[segtree_root[segtree_idx[c]]] += delta;
}
}
int main(void) {
int n, m;
// 處理第一部份的輸入：紀錄整棵樹的訊息。
scanf("%d", &n);
for(int i=0;i<n-1;i++) {
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
// 用 DFS 連結每個節點至高度最高的子節點。
find_depth_dfs(1);
// 對於每一條鍊，初始化一個相應大小的線段樹。
build_segment_tree(1);
// 處理第二部分輸入：對於一次輸入的兩個點 A, B，改變其燈號狀態。
scanf("%d", &m);
while(m--) {
int A, B;
scanf("%d%d", &A, &B);
toggle(A);
toggle(B);
printf("%d\n", total_odd[1]);
}
return 0;
}
其他推薦題解
Recover Square RECOVER
解法
感覺就是從角落用拼拼圖的方式一個一個把它拼起來。可能有點麻煩就是了...