Problem	Status	Tags
A - A Hero Named Magnus	🎈	💧
B - A Plus B Problem	💀	平衡树
C - AC Automaton	💀
D - Assume is All You Need	🎈	构造
E - Buy and Delete	💀	最短路 | 最小环
F - Illuminations 2	💀
G - Occupy the Cities	🎈	模拟
H - Popcount Words	💀
I - PTSD	🎈	贪心
J - Suffix Automaton	💀
K - Tax	💀	搜索
L - Wiring Engineering	💀

---

A - A Hero Named Magnus

• 简单签到，答案为 $2 x - 1$ 。

---

B - A Plus B Problem

Solution

$C_i = ( A_i + B_i + [A_j + B_j \ge 10] \bmod 10 )$，
其中 $j$ 为 $i$ 往低第一个满足 $A_j + B_j \operatorname{ne} 9$ 的位。

如果 $i$ 位是否进位的状态改变，那么往高到第一个满足 $A_j + B_j \operatorname{ne} 9$ 的位 $j$ 都会改变。

那么我们只需要维护所有满足 $A_i + B_i \operatorname{ne} 9$ 的位 $i$ 就可很快解决问题。

考场上计划维护实际结果中连续的 0 与 9 的区间，但是细节过多，写挂了。😰

Code

const int MAX_N = 1000005;

int a[2][MAX_N];
set<int> st;
int n, q;

void get_num(int *a) {
    static char s[MAX_N];
    scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i) a[i] = s[i] - '0';
}

int main() {

    scanf("%d%d", &n, &q);
    get_num(a[0]), get_num(a[1]);
    
    for (int i = 1; i <= n; ++i)
        if (a[0][i] + a[1][i] != 9)
            st.insert(i);
    st.insert(0);
    st.insert(n + 1);
    
    for (int k, i, v, j, cnt; q; --q) {
    
        scanf("%d%d%d", &k, &i, &v); --k;
    
        j = *st.upper_bound(i);
        bool low_carry = (j <= n and a[0][j] + a[1][j] >= 10);
        
        if (a[k][i] == v) cnt = 0; else {
            cnt = 2;
            bool old_carry = (a[0][i] + a[1][i] + low_carry >= 10);
            bool new_carry = (a[k ^ 1][i] + v + low_carry >= 10);
            if (old_carry != new_carry) {
                j = *--st.lower_bound(i);
                cnt += (j ? i - j : i - 1);
            }
            if (a[0][i] + a[1][i] == 9) st.insert(i);
            if (a[k ^ 1][i] + v == 9) st.erase(i);
            a[k][i] = v;
        }
    
        printf("%d %d\n", (a[0][i] + a[1][i] + low_carry) % 10, cnt);
    
    }
    
    return 0;

}

---

C - AC Automaton

---

D - Assume is All You Need

Solution

可以发现较大的元素位置越靠前是越有利于我们的行动的。在一个元素交换到目标位置的过程中，不断地将该元素和区间内最大的元素进行交换，可以保证较大的元素尽量靠前，不会损失解。

Code

typedef pair<int, int> pii; 

const int MAX_N = 2025, MAX_K = 2041215;

int pos_a[MAX_N], pos_b[MAX_N];
int a[MAX_N], b[MAX_N];
pii ans[MAX_K];

int main() {
	int T, n;
	scanf("%d", &T);
	while (T--) {
		
		scanf("%d", &n);
		for (int i = 1, x; i <= n; ++i) scanf("%d", &x), pos_a[x] = i;
		for (int i = 1, x; i <= n; ++i) scanf("%d", &x), pos_b[x] = i;
		
		int cnt = 0; bool unsolvable = 0;
		
		for (int i = n; i; --i) {
			int &st = pos_a[i], ed = pos_b[i];
			for (int j = i - 1; j; --j) {
				if (pos_a[j] > st and pos_a[j] <= ed) {
					ans[++cnt] = pii(st, pos_a[j]);
					swap(st, pos_a[j]);
				}
			}
			if (st != ed) { unsolvable = 1; break; }
		}
		
		if (unsolvable) puts("-1");
		else {
			printf("%d\n", cnt);
			for (int i = 1; i <= cnt; ++i)
				printf("%d %d\n", ans[i].first, ans[i].second);
		}
	
	}
	return 0;
}

---

E - Buy and Delete

竟死于不知道 DAG 中的 A —— Acyclic 这个词。🐶 英语，早该学学了。

Solution

当边集为空时答案为 0，边集无环时答案为 1，边集有环时答案位 2 。

理解一：第一遍删除树边和横叉边，第二遍删除返祖边。
理解二：可以一遍删除满足 $u < v$ 的边 $(u,\ v)$，然后删除满足 $u > v$ 的边。

问题转换为求最小边与最小环。跑 $n$ 遍单源最短路即可。

Code

typedef pair<int, int> pii;

const int MAX_N = 2005, MAX_M = 5005;

struct edge {
	int v, w, nxt;
	edge(int v = 0, int w = 0, int nxt = 0)
	: v(v), w(w), nxt(nxt) {}
} e[MAX_M];

int dist[MAX_N][MAX_N];
int head[MAX_N], tot;
int n, m, c;

void lnk(int u, int v, int w) {
	e[++tot] = edge(v, w, head[u]);
	head[u] = tot;
}

void dij(int s) {
	priority_queue<pii> pq;
	
	int *d = dist[s];
	
	pq.push(pii(d[s] = 0, s));
	while (!pq.empty()) {
		pii top = pq.top(); pq.pop();
		int u = top.second;
		if (d[u] < -top.first) continue;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v, w = e[i].w, t = d[u] + w;
			if (d[v] > t) 
				pq.push(pii(-(d[v] = t), v));
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &c);
	for (int i = 1, u, v, w; i <= m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		lnk(u, v, w);
	}
	int ans = 0;
	memset(dist, 0x3f, sizeof(dist));
	for (int s = 1; s <= n; ++s) dij(s);
	for (int u = 1; u < n; ++u)
	for (int v = u + 1; v <= n; ++v) {
		if (dist[u][v] <= c or dist[v][u] <= c) ans = 1;
		if (dist[u][v] + dist[v][u] <= c) {
			ans = 2;
			goto output_part;
		} 
	}
	output_part:
		printf("%d\n", ans);
	return 0;
}

---

F - Illuminations 2

---

G - Occupy the Cities

Solution

处理出连续的 1 区间之间的距离。并划分 1 区间的属性：单数或者复数。单数的区间一轮只能往左右一个方向扩展，而复数的区间可以同时往两个方向扩展。特殊处理第一轮，之后的所有区间都是复数区间，可以简单计算。

Code

const int MAX_N = 1000005;

bool sg[MAX_N];
char s[MAX_N];
int d[MAX_N];
int n;

void chkmx(int &a, const int& b) { if (a < b) a = b; }

int main() {
	int T;
	scanf("%d",&T);
	while (T--) {
		
		scanf("%d%s", &n, s + 1);
		int m = 0, r = 0; bool g = 0;
		
		for (int l = 1; l <= n; ++l) if (s[l] == '1') {
			
			g |= (d[++m] = l - r - 1);
			
			for(r = l; r < n and s[r + 1] == '1'; ++r);
			sg[m] = (l == r);
			
			l = r;
			
		}
		
		g |= (d[m + 1] = n - r);
		
		if (!g) puts("0"); else {
			
			d[1] = (d[1] << 1) - 1;
			d[m + 1] = (d[m + 1] << 1) - 1;
			for (int i = 1; i <= m; ++i) {
				if (!sg[i]) --d[i], --d[i + 1];
				else (d[i] >= d[i + 1]) ? --d[i] : --d[i + 1];
			}
			
			int ans = 0;
			for (int i = 1; i <= m; ++i) chkmx(ans, (d[i] + 1) >> 1);
			chkmx(ans, (d[m + 1] + 1) >> 1);
			printf("%d\n", ans + 1);
			
		}
		
	}
	return 0;
}

---

H - Popcount Words

---

I - PTSD

Solution

求最大值，于是优先给值大的元素组队。从后往前贪心求解即可。

Code

typedef long long ll;

const int MAX_N = 1000005;

char s[MAX_N];
int n;

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%s", &n, s + 1);
		ll ans=0;
		for (int i = n, g = 0; i; --i) {
			if (s[i] == '1' and g) --g, ans += i;
			else ++g;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

---

J - Suffix Automaton

Solution

考虑依据字符串的长度离线处理。求固定长度本质不同子串的个数，以及查询第 k 大。

考虑使用后缀数组：

• $suf_i$ 可以贡献长度为 $j$ 的子串，其中 $j \in [height_{i} + 1,\ len_{i}]$ 。
• 利用差分容易算出各个长度本质不同子串的个数。
• 接下来使用平衡树维护当前长度合法的子串，并查询所在子串在 $sa$ 中最早出现的位置。
• 由于需要找到子串在原串中最早出现的位置：
  以当前位置为基础二分，对区间内 $height$ 的最小值限制，求 $sa$ 的最小值。
  为 RMQ 问题，使用 Sparse Table 维护。

Code

typedef pair<int, int> pii;
typedef long long ll;

const int MAX_N = 1000005, MAX_LOGN = 21, MAX_Q = 1000005, MAX_T = 3000005;

pii ans[MAX_Q];
char s[MAX_N];
int n, m, Q;
ll d[MAX_N];

struct OptData {
	bool typ; int id, l, k;
	OptData(bool typ = 0, int id = 0, int l = 0, int k = 0)
	: typ(typ), id(id), l(l), k(k) {}
} q[MAX_T];

namespace SA {
	
	int sa[MAX_N], rk[MAX_N], ht[MAX_N];
	int bkt[MAX_N], t[MAX_N];
	
	void RadSort() {
		for (int i = 1; i <= m; ++i) bkt[i] = 0;
		for (int i = 1; i <= n; ++i) ++bkt[rk[i]];
		for (int i = 2; i <= m; ++i) bkt[i] += bkt[i - 1];
		for (int i = n; i; --i) sa[bkt[rk[t[i]]]--] = t[i];
	}
	
	inline bool eq(int i, int j, int k) {
		return (t[i] == t[j] and (i + k <= n) == (j + k <= n) and t[i + k] == t[j + k]);
	}
	
	void SufSort() {
		m = 26;
		for (int i = 1; i <= n; ++i) rk[i] = s[i] - 'a' + 1, t[i] = i;
		RadSort();
		for (int k = 1, p = 0; p < n; k <<= 1) {
			p = 0;
			for (int i = n - k + 1; i <= n; ++i) t[++p] = i;
			for (int i = 1; i <= n; ++i) if (sa[i] > k) t[++p] = sa[i] - k; 	
			RadSort();
			swap(rk, t);
			rk[sa[1]] = p = 1;
			for (int i = 2; i <= n; ++i) rk[sa[i]] = eq(sa[i], sa[i - 1], k) ? p : ++p;
			m = p;
		}
	}
	
	void GetHt() {
		for (int i = 1, k = 0; i <= n; ++i) {
			if (k) --k;
			for (int j = sa[rk[i] - 1]; s[i + k] == s[j + k]; ++k);
			ht[rk[i]] = k;
		}
	}
	
} using namespace SA;

namespace ST {

	int mnht[MAX_N][MAX_LOGN];
	int mnsa[MAX_N][MAX_LOGN];
	int l2[MAX_N];
	
	void Init() {
		for (int i = 2; i <= n; ++i) l2[i] = l2[i >> 1] + 1;
		for (int i = 1; i <= n; ++i) mnht[i][0] = ht[i], mnsa[i][0]= sa[i];
		for (int j = 1; j <= l2[n]; ++j)
		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
			mnht[i][j] = min(mnht[i][j - 1], mnht[i + (1 << (j - 1))][j - 1]);
			mnsa[i][j] = min(mnsa[i][j - 1], mnsa[i + (1 << (j - 1))][j - 1]);
		}
	}
	
	int qry(int a[][MAX_LOGN], int l, int r) {
		int k = l2[r - l + 1];
		return min(a[l][k], a[r - (1 << k) + 1][k]);
	}

} using namespace ST;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Set;
Set rbt;

int main() {
	
	scanf("%s", s + 1); n = strlen(s + 1);
	SufSort(); GetHt(); Init();
	for (int i = 1; i <= n; ++i) ++d[ht[i] + 1], --d[n - sa[i] + 2];
	for (int i = 2; i <= n; ++i) d[i] += d[i - 1];
	for (int i = 2; i <= n; ++i) d[i] += d[i - 1];
	
	int opts = 0;
	
	scanf("%d", &Q);
	for (int i = 1, j; i <= Q; ++i) {
		ll k; scanf("%lld", &k);
		j = lower_bound(d + 1, d + n + 1, k) - d;
		q[++opts] = OptData(1, i, j, k - d[j - 1]);
	}
	
	for (int i = 1; i <= n; ++i) if (n - sa[i] + 1 > ht[i]) {
		q[++opts] = OptData(0, i, ht[i] + 1    , 0);
		q[++opts] = OptData(0, i, n - sa[i] + 2, 1);
	}
	
	sort(q + 1, q + opts + 1, [](OptData lhs, OptData rhs) {
		return lhs.l != rhs.l ? lhs.l < rhs.l : lhs.typ < rhs.typ;
	});
	
	for (int i = 1; i <= opts; ++i) {
		if (q[i].typ == 0) {
			if (q[i].k == 0) rbt.insert(q[i].id);
			else rbt.erase(q[i].id);
		} else {
			if (q[i].l > n) ans[q[i].id] = pii(-1, -1);
			else {
				int j = *rbt.find_by_order(q[i].k - 1);
				int l = j, r = n;
				while (l < r) {
					int mid = (l + r + 1) >> 1;
					if (qry(mnht, j + 1, mid) >= q[i].l) l = mid;
					else r = mid - 1;
				}
				j = qry(mnsa, j, r);
				ans[q[i].id] = pii(j, j + q[i].l - 1);
			}
		}
	}
	
	for (int i = 1; i <= Q; ++i) printf("%d %d\n", ans[i].first, ans[i].second);
	
	return 0;
}

---

K - Tax

题意为先满足最短路，再要求花费最小。审题挂掉。🙊

Solution

根据题意，直接在最短路的基础上进行搜索。

根据幂平均不等式，复杂度在每层点数都相同的分层图时最大，为 $O(\exp({n \cfrac{\ln x}{x}}))$ 。

求导最后可得在 $x = 3$ 时复杂度最大，可以通过题目。

Code

const int MAX_N = 55, MAX_M = 1235, MAX_2M = 2505;

struct edge {
	int v, c, nxt;
	edge(int v = 0, int c = 0, int nxt = 0)
	: v(v), c(c), nxt(nxt) {}
} e[MAX_2M];

int tax[MAX_M], cnt[MAX_M];
int d[MAX_N], cost[MAX_N];
int head[MAX_N], tot;
int n, m;

inline void lnk(int u, int v, int c) {
	e[++tot] = edge(v, c, head[u]);
	head[u] = tot;
}

void bfs(int s) {
	queue<int> q;
	d[s] = 1; q.push(s);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (!d[v]) { d[v] = d[u] + 1; q.push(v); }
		}
	}
}

void dfs(int u, int g = 0) {
	if (cost[u] > g) cost[u] = g;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v, c = e[i].c;
		if (d[v] != d[u] + 1) continue;
		++cnt[c];
		dfs(v, g + cnt[c] * tax[c]);
		--cnt[c];
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) scanf("%d", tax + i);
	for (int i = 1, u, v, c; i <= m; ++i) {
		scanf("%d%d%d", &u, &v, &c);
		lnk(u, v, c), lnk(v, u, c);
	}
	memset(cost, 0x3f, sizeof(cost));
	bfs(1);
	dfs(1);
	for (int i = 2; i <= n; ++i) printf("%d\n", cost[i]);
	return 0;
}

---

L - Wiring Engineering