2019ICPC陜西省賽暨陜西邀請賽題解 BCDEF HIJKL

共111支隊伍，獲獎情況（大概）

銅牌66 —— 3? 296

銀牌33 —— 4 391

金牌 11 —— 6 808

題目難度（過題）L F E?B C??I J D K H?

Problem - L - Codeforces

思路：注意到答案是連乘，只要有0那全部為0，而 > 10的區間一定有0,10之內的模擬即可

// Code Start Here	int t;cin >> t;while(t--){int l , r;cin >> l >> r;if(r - l >= 10)cout << 0 << endl;else{int ans = 1;for(int i = l;i<=r;i++){int now = i;while(now){ans *= now % 10;ans %= md;now /= 10;}}cout << ans << endl;}}

Problem - F - Codeforces

思路：我們肯定想到最簡單的方法就是直接恰好一輪mod，然后判斷一下 x + y - z的值

提交，wa2

仔細來想一下，這個題有坑。

當k < x 或 z時，根本沒法到x , z這兩個時間，只會變成x % k和? z % k?

分類討論一下，看 k 和x , z的關系

提交? ?通過

//	code start hereint t;cin >> t;while(t--){int x , y , z;cin >> x >> y >> z;if(x + y == z)cout << z + 1 << endl;else if( x <= z && x + y > z){if(x + y - z > z)cout << x + y - z <<endl;else cout << -1 << endl;}else if(x > z && y > z)cout << x + y - z <<endl;else cout << -1 << endl;}

Problem - E - Codeforces

觀察到這個E要求求的是一個最大值的最小值，考慮二分的可行性。

我們注意到一選L一定是一個連續的區間，無論有多少個1，后面有多少個0，后面都要直接全選。

二分長度后貪心

// Code Start Here	int t;cin >> t;while(t--){int n , k;cin >> n >> k;string s;cin >> s;auto check = [&](int x)->bool{int now = 0;int i = n - 1;while(i >= 0){if(s[i] == '1')now ++ ,i -= x;else i--;}return k >= now;};if(s == string(n , '0'))cout << 0 << endl;else{int l = 1 , r = n;while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout << l << endl;}}return 0;

Problem - B - Codeforces

題意大概是一筆畫問題，考慮往歐拉路徑上靠。

根據歐拉路徑的定義：一個圖存在歐拉路徑的充要條件是，圖忽略方向后聯通。最多只能有一個起點和終點，其他節點入度= 出度。

我們把每個格子變成一個節點，然后根據箭頭建一條從當前格子指向另外一個格子的邊。比如如果 (i,j) 是 'u' 且 a[i][j] = 2，那么有一條邊：(i,j) → (i-2,j)

建圖后檢查一下是否存在歐拉路徑，然后判斷一次聯通即可

// Code Start Herevi dx(256), dy(256);dx['u'] = -1;dy['u'] = 0;dx['d'] = 1;dy['d'] = 0;dx['l'] = 0;dy['l'] = -1;dx['r'] = 0;dy['r'] = 1;int t;cin >> t;while (t--) {int n, m;cin >> n >> m;vector<str> a(n);vvi step(n, vi(m));for (int i = 0 ; i < n; i++)cin >> a[i];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> step[i][j];}}vi indeg(n * m, 0), outdeg(n * m, 0);vvi g(n * m);vb used(n * m, false);for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {// 看下一個在哪里int ni = i + dx[a[i][j]] * step[i][j];int nj = j + dy[a[i][j]] * step[i][j];int u = i * m + j;used[u] = true;if (ni >= 0 && ni < n && nj >= 0 && nj < m) {int v = ni * m + nj;indeg[v]++;outdeg[u]++;g[u].push_back(v);g[v].push_back(u);used[v] = true;}}}bool f = true;int st = 0, ed = 0;for (int i = 0; i < n * m; ++i) {if (used[i]) {if (outdeg[i] - indeg[i] == 1) st++;else if (indeg[i] - outdeg[i] == 1) ed++;else if (indeg[i] != outdeg[i]) {f = false;break;}}}if (!((st == 0 && ed == 0) || (st == 1 && ed == 1))) f = false;vb vis(n * m, false);auto dfs = [&](auto dfs, int u)->void{vis[u] = true;for (int v : g[u]) {if (!vis[v]) {dfs(dfs, v);}}};int l = -1;for (int i = 0; i < n * m; ++i) {if (used[i]) {l = i;break;}}dfs(dfs, l);for (int i = 0; i < n * m; ++i)if (used[i] && !vis[i]) {f = false;}if (f)cout << "Yes\n";else cout << "No\n";}return 0;

Problem - C - Codeforces

我們假設每一個子串都可以用來旋轉變成一個新字符串，所有子串都會帶來一個不同的結果，然后我們開始看不產生新串的重復情況：

純 '0' 子串不會變；純 '8' 子串不會變；‘6’ 與 ‘9’ 混搭會產生重復（如 “69” ? “96”）。

提交，wa。

思考，注意到并不是所有 '6' 和 '9' 混合子串都變成相同的東西。比如 '669' → '996' ≠ '669'。所以并不總是意味著重復，只是可能導致重復

// Code Start Here	int t;cin >> t;while(t--){string s;cin >> s;int a = 0 , b = 0 , c = 0 , d = 0;for(auto i :s){if(i == '0')a++;else if(i == '6')b++;else if(i == '8')c++;else d++;}int ans = 0;ans += (1 + sz(s)) * sz(s) / 2;ans -= (1 + a) * a / 2;ans -= (1 + c) * c / 2;ans -= 1 * b * d;if(b != sz(s) && d != sz(s))ans++;cout << ans << endl;}

Problem - I - Codeforces

題意：給定一棵無根樹，每條邊帶有一個小寫字母，問：有多少個節點可以作為根，使得這棵樹變成一個合法的字典樹

思路：一個 trie 合法需要滿足

1、每個節點表示一條從根到該節點的字符串路徑

2、所有節點代表的字符串必須是互不相同

3、字符串是沿著邊上的字符拼接得到的

換句話說：從根出發，不能走出兩條完全相同的路徑。

我們可以逐個節點檢查它連出的邊，主要分為以下幾種情況：

首先是不合法的情況：

1：某個節點連出三條或更多相同字符的邊，肯定構成沖突，無解

2：某個節點連出兩種不同的字符，各重復兩次，例如 a a b b，無解

其次觀察合法情況：

當一個節點u 恰好有兩條邊使用了相同字符，例如 a a，如果這兩條邊通向的節點 x,y 都存在，那么，路徑從根出發到 x?和 y在字符上就會重復。因此必須讓根節點選在某個區域，避免讓 x?和 y?出現在同一路徑上

以下引出本題核心判斷：

1：根節點位置的分類討論

我們選定任意一個根進行 DFS（只是為了編號），然后設：?

in[u]: u 的 DFS 進入時間（序號）
siz[u]: u 的子樹大小

?情況 1：in[u] < in[x], in[y]，說明 u 是 x 和 y 的祖先，根只能選在 x 的子樹或 y 的子樹中，其余地方都不能選，標記為非法區間

情況 2：in[x] < in[u] < in[y]，說明 x 是 u 的祖先，y 是 u 的子樹，根只能選在 y 的子樹中或在 u 的子樹外部

因此，我們需要將這些非法的區間進行標記，最終統計哪些節點未被標記，他們就是合法根

子樹大小可以用dfn解決，打非法區間標記可以使用線段樹

template<class Info, class Tag>
struct LazySegmentTree {int n;vector<Info> info;vector<Tag> tag;LazySegmentTree(const vector<Info>& init) {n = init.size() - 1;info.assign(4 * n, Info());tag.assign(4 * n, Tag());function<void(int, int, int)> build = [&](int p, int l, int r) {if (l == r) {info[p] = init[l];return;}int m = (l + r) / 2;build(p * 2, l, m);build(p * 2 + 1, m + 1, r);pull(p);};build(1, 1, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void apply(int p, const Tag &v) {info[p].apply(v);tag[p].apply(v);}void push(int p) {apply(2 * p, tag[p]);apply(2 * p + 1, tag[p]);tag[p] = Tag();}void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {if (r < x || l > y) return;if (x <= l && r <= y) {apply(p, v);return;}push(p);int m = (l + r) / 2;rangeApply(p * 2, l, m, x, y, v);rangeApply(p * 2 + 1, m + 1, r, x, y, v);pull(p);}void rangeApply(int l, int r, const Tag &v) {if (l > r) return;rangeApply(1, 1, n, l, r, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (r < x || l > y) return Info();if (x <= l && r <= y) return info[p];push(p);int m = (l + r) / 2;return rangeQuery(p * 2, l, m, x, y) + rangeQuery(p * 2 + 1, m + 1, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 1, n, l, r);}
};struct Tag {ll x;Tag(ll x = 0) : x(x) {}void apply(const Tag &t) { x += t.x; }
};struct Info {ll x, l, r;Info(ll x = 0, ll l = 0, ll r = 0) : x(x), l(l), r(r) {}void apply(const Tag &t) {x += t.x * (r - l + 1);}
};Info operator+(const Info &a, const Info &b) {return Info(a.x + b.x, a.l, b.r);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {int n;cin >> n;vector<vector<pair<int, char>>> g(n + 1);for (int i = 1; i < n; ++i) {int u, v; char c;cin >> u >> v >> c;g[u].emplace_back(v, c);g[v].emplace_back(u, c);}bool f = false;for (int u = 1; u <= n; ++u) {map<char, int> cnt;for (auto [v, c] : g[u]) cnt[c]++;int tw = 0;for (auto [_, k] : cnt) {if (k >= 3) f = true;if (k == 2) ++tw;}if (tw >= 2) f = true;}if (f) {cout << 0 << endl;continue;}vector<int> dfn(n + 1), siz(n + 1);int timer = 0;function<void(int, int)> dfs = [&](int u, int p) {dfn[u] = ++timer;siz[u] = 1;for (auto &[v, c] : g[u]) {if (v != p) {dfs(v, u);siz[u] += siz[v];}}};dfs(1, 0);vector<Info> init(n + 1);for (int u = 1; u <= n; ++u) {init[dfn[u]] = Info(0, dfn[u], dfn[u]);}LazySegmentTree<Info, Tag> seg(init);for (int u = 1; u <= n; ++u) {unordered_map<char, int> mp;for (auto &[v, c] : g[u]) {if (!mp.count(c)) mp[c] = v;else {int f1 = mp[c], f2 = v;if (dfn[f1] > dfn[f2]) swap(f1, f2);if (dfn[f1] > dfn[u] && dfn[f2] > dfn[u]) {seg.rangeApply(1, dfn[f1] - 1, Tag(1));seg.rangeApply(dfn[f1] + siz[f1], dfn[f2] - 1, Tag(1));seg.rangeApply(dfn[f2] + siz[f2], n, Tag(1));}else if (dfn[f1] > dfn[u] && dfn[u] > dfn[f2]) {seg.rangeApply(dfn[u], dfn[f1] - 1, Tag(1));seg.rangeApply(dfn[f1] + siz[f1], dfn[u] + siz[u] - 1, Tag(1));}else if (dfn[f2] > dfn[u] && dfn[u] > dfn[f1]) {seg.rangeApply(dfn[u], dfn[f2] - 1, Tag(1));seg.rangeApply(dfn[f2] + siz[f2], dfn[u] + siz[u] - 1, Tag(1));}break;}}}int ans = 0;for (int u = 1; u <= n; ++u) {if (seg.rangeQuery(dfn[u], dfn[u]).x == 0) ++ans;}cout << ans << endl;}return 0;
}

Problem - J - Codeforces

題意：給定多個區間，從這些區間里面選數使得and和最大

思路：我們從高位往第0位嘗試是否可以填1

記錄每個區間目前構造的前綴 v，即當前已經選的高位部分,假設我們嘗試在第 p 位填 1，那么我們希望每個區間都能選擇一個數，其第 p 位為 1。也就是說，當前候選區間必須和 $v_i + 2^p , v_i +2 ^ p +1 - 1$ 有交集，如果所有區間都滿足這個條件，那我們就將所有 v_i+= 2^p，把第 p 位設為 1。否則，說明這位只能是 0，此時我們判斷：

哪些區間這一位只能填 0；
哪些區間這一位必須填 1（因為否則無法滿足區間條件）
哪些區間這一位不影響答案，隨意填

// Code Start Here	int t;cin >> t;while(t--){int n;cin >> n;vpii ranges(n);for(auto &[l , r] : ranges)cin >> l >> r;vi v(n , 0);int ans = 0;for(int bit = 30 ; bit >=0 ;bit--){bool f = true;for(int i = 0;i<n;i++){int l = ranges[i].first;int r = ranges[i].second;int lo = v[i] + (1 << bit);int hi = v[i] + (1 << (bit + 1)) - 1;if(hi < l || lo > r){f = false;break;}}if(f){ans |= (1 << bit);for(int i = 0;i<n;i++)v[i] += (1 << bit);}else{for(int i = 0;i<n;i++){int l = ranges[i].first;int r = ranges[i].second;int lo = v[i] + (1 << bit);int hi = v[i] + (1 << (bit + 1)) - 1;if(hi < l || lo > r){continue;}int x = v[i] + (1 << bit) - 1;if(x < l)v[i] += (1 << bit);}}}cout << ans <<endl;}

Problem - D - Codeforces

題意：此題中我們定義兩個點之間的最短距離是曼哈頓距離。

寶寶從A 走向商場C，速度為a。夢幻從B 開車，也要到C，速度為b>a。夢幻可以中途接上寶寶，兩人一起前往C。找出寶寶到達C 的最短時間

思路：我們考慮兩種策略：

1：寶寶獨自走到商場

2：夢幻網格接上寶寶，一起前往商場

比較這兩種方式誰用時更少。

假設你是 Dream，想要中途接寶寶。如果你在接他前繞了太遠路，就白費了；那么最好的情況是找一個中轉點 D接上。所以讓 D 滿足兩個條件：

1：D 必須位于A 和B 組成的最小矩形R 中，不繞路

2：D 離C 盡可能近，接上之后離目標也近

共有三種情況：

寶寶自己走到 C
Dream先到 D，然后自己去商場（不接人）
Dream先到 D，然后追上寶寶一起去商場

其中后者用追擊問題計算，模擬題。

// Code Start Here	int t;cin >> t;while(t--){int a, b, xa, ya, xb, yb, xc, yc;cin >> a >> b >> xa >> ya >> xb >> yb >> xc >> yc;auto Manhattan = [&](int xa, int ya, int xb, int yb, int v)->double{return (abs(xb - xa) + abs(yb - ya)) * 1.0 / v;};double ans = Manhattan(xa, ya, xc, yc, a);int l = min(xa, xb), r = max(xa, xb);int d = min(ya, yb), u = max(ya, yb);int xd = max(l, min(r, xc));int yd = max(d, min(u, yc));double ta = Manhattan(xa, ya, xd, yd, a);double tb = Manhattan(xb, yb, xd, yd, b);if (ta < tb) {ans = min(ans, Manhattan(xb, yb, xc, yc, b));} else {double t = Manhattan(xa, ya, xb, yb, a + b);double dis = abs(xc - xa) + abs(yc - ya) - a * t;ans = min(ans, t + dis / b);}cout << point(6) << ans << '\n';}

Problem - K - Codeforces

題意：

有一個無向圖，每個點有若干只怪物。每個點最多能被怪物隨機封鎖 d[i] 條出邊。給定若干出口點，問從點 1 出發，在最壞情況下是否能逃離，并輸出最短路徑長度。

思路：

最壞情況意味著：從每個點出發時，最短的 d[i] 條邊都無法使用。我們可以使用一種反向 Dijkstra + 堵塞次數判定的策略

我們不從點 1 出發，而從所有出口點出發，向其他點做 Dijkstra。

這樣做的好處是：從出口到其他點的最短距離 = 從其他點到出口在圖中路徑反向后的最短距離。即最終得到的 dis[x] 實際上表示的是最壞情況下從點 x 到任意一個出口的最短路徑長度。

核心問題是如何用 d[x] 模擬最壞情況的怪物堵路。每個點 x 有 d[x] 條邊可能會被堵住。為了模擬最壞情況下，我們允許每個點被訪問多次。前 d[x] 次訪問全部忽略，相當于被怪物堵）。第 d[x] + 1 次訪問才確定該點的最終 dis 值，認為這條路徑不是被封鎖的，因此可以走。即：

1：每次訪問 u，都減少一個封路的怪物。

2：如果還有怪物封路，這次路徑作廢。

3：否則，說明已經沒有怪物，我們可以更新 dis[u]

// Code Start Hereint t;cin >> t;while (t--) {int n, m, k;cin >> n >> m >> k;vector<int> d(n + 2, 0), dis(n + 2, -1);vector<int> exits(k);vector<vpii> g(n + 1, vector<pair<int,int>>());for (int i = 0; i < k; ++i) cin >> exits[i];for (int i = 1; i <= n; i++)cin >> d[i];for (auto i : exits) d[i] = 0;for(int i = 1;i<=m;i++){int u , v , w;cin >> u >> v >>w;g[u].emplace_back(v , w);g[v].emplace_back(u , w);}priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;for(auto i : exits)pq.emplace(0 , i);while (!pq.empty()) {auto [dd, u] = pq.top(); pq.pop();if (dis[u] != -1) continue;if (--d[u] >= 0) continue;dis[u] = dd;for (auto [v, w] : g[u]) {if (dis[v] == -1) {pq.emplace(dis[u] + w, v);}}}cout << dis[1] <<endl;}

Problem - H - Codeforces

題意：有 n 個學生編號為 1 到 n，每個學生最多參加一個配對。要求構造一個數組：

配對 (a, b) 滿足：gcd(a, b) > 1。每個學生最多參與一次；盡可能多地構造配對；輸出這個構造的數組。

思路：

我們優先保證大質數能使用其倍數構造；如果從小到大，可能被更小的質數先配走 i*2，造成損失；所以大質數優先。

其次收集所有 p 的倍數中未使用的數進行配對，處理奇數個的情況：加入 i * 2。i * 2 是 i 的倍數；在從大到小的順序下，i * 2 此時尚未被使用（否則跳過）；加入后，保證 vec.size() 為偶數。然后兩兩配對，?標記使用。剩下的偶數做補充配對

// Code Start Here	constexpr int N = 1e6+10;vector<bool> f(N,false);auto sieve = [&]()-> void {for (int i = 2; i * i < N; i++) {if (!f[i]) {for (int j = i * 2; j < N; j += i){f[j] = true;}}}};sieve();int t;cin >> t;while(t--){int n;cin >> n;vector<pair<int,int>> ans;vector<bool> vis(n + 10, false);if (n <= 3) {cout << 0 << endl;continue;}for (int i = n; i > 2; i--) {if (!f[i] && i * 2 <= n) {if(vis[i*2])continue;vector<int> vec = {i};for (int j = i * 3; j <= n; j += i) if (!vis[j]) vec.push_back(j);if (vec.size() % 2 == 1) vec.push_back(i * 2);for (size_t j = 1; j < vec.size(); j += 2) {vis[vec[j - 1]] = vis[vec[j]] = true;ans.emplace_back(vec[j - 1], vec[j]);}}}vector<int> res;for (int i = 2; i <= n; i += 2) 	if (!vis[i]) res.push_back(i);for (int i = 1; i < sz(res); i += 2) 	ans.emplace_back(res[i - 1], res[i]);cout << ans.size();for (auto [a, b] : ans) {cout << " " << a << " " << b;}cout << endl;}