模擬競賽 II 題解

題目大意

有兩個序列 \(a\)、\(b\)
從起點開始，你要走 \(n\) 步
第 \(i\) 步會直線移動 \((a_i,b_i)\) 的距離
把它們重新排列，滿足你走的路線不自交

如果 \(a_i\) 總和或 \(b_i\) 總和不是 0 就無解

Subtask 1

\(n=3\)

如果你隨便弄出 3 個向量
如果這 3 個向量拼不出三角形
唯一的可能就是它們互相平行
否則，這 3 個向量可以以任意順序排列

枚舉所有 \(a\) 的排列
檢查每個向量 \((a_i,b_i)\) 是否平行

Subtask 2

\(n \leq 6\)

枚舉 \(a\) 的排列和 \(b\) 的排列的搭配
然後檢查能不能當答案

\(O(n! \times n! \times n^2)\)

Subtask 3

\(\forall 1 \leq i < n,\ b_i=1\)

如果把 \(a\) 由小到大排序
那麼前 \(n-1\) 步會走出一個下凸包的形狀
最後一步會直接走回原點
所以這樣走出來的一定是一個凸多邊形

\(O(n \log n)\)

Subtask 4

在 Subtask 1 中
我們用「是不是全部平行」來判斷能不能當解

事實上，只要有 \(n\) 個向量
至少有一對不平行
那就可以用它們做出一個合法路線

在 Subtask 3 中我們做出了一個凸多邊形

只要把這 \(n\) 個向量極角排序就可以得到凸多邊形了

剩下的問題就是怎麼找這 \(n\) 個向量

配出 \(n\) 個全部平行的向量的方法數
遠低於總方案數

random 會是好的

可不可以不要 random？

官解作法：
把 \(a\) 按絕對值由小到大排序
\(b\) 按絕對值由大到小排序

對於 \(|a_i| < |a_j|\)
肯定有 \(\frac{|a_i|}{|b_i|} \neq \frac{|a_j|}{|b_j|}\)
因為 \(|b_i| \geq |b_j|\)
得出 \(\left\lvert\frac{a_i}{b_i}\right\rvert \neq \left\lvert\frac{a_j}{b_j}\right\rvert\)

至於 \(|a_i| = |a_j|\)
因為 \(a_i\) 皆相異，這最多只有兩個而已
而 \(n \geq 3\) 所以肯定有解

\(O(n \log n)\)

一些會錯的解：

• 照輸入順序原封不動輸出
• 純 random 輸出
• 把 \(a\)、\(b\) 由小排到大湊向量
• 把 \(a\) 由小排到大、\(b\) 由大排到小湊向量

為什麼 \(n\) 那麼小？

因為我不會寫 checker

#include <bits/stdc++.h>
 
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
 
using namespace std;
 
typedef long long ll;
 
using pll = pair<ll, ll>;
 
int main(){
    StarBurstStream
 
    int n;
    cin >> n;
 
    vector<ll> a(n), b(n);
    ll asum = 0, bsum = 0;
    for(int i = 0; i < n; i++) cin >> a[i], asum += a[i];
    for(int i = 0; i < n; i++) cin >> b[i], bsum += b[i];
 
    if(asum != 0 || bsum != 0){
        cout << "No\n";
        return 0;
    }
 
    sort(iter(a), [](ll a, ll b){ return abs(a) < abs(b); });
    sort(iter(b), [](ll a, ll b){ return abs(a) > abs(b); });
    vector<pll> v(n);
    for(int i = 0; i < n; i++) v[i] = mp(a[i], b[i]);
 
    auto comp = [](pll a, pll b){
        return atan2(a.S, a.F) < atan2(b.S, b.F);
    };
 
    sort(iter(v), comp);
 
    cout << "Yes\n";
    for(int i = 0; i < n; i++){
        cout << v[i].F << " " << v[i].S << "\n";
    }
 
    return 0;
}

題目大意

給一張圖
令 \(s\) 到節點 \(i\) 走 \(k\) 步的最短距離是 \(d(i,k)\)
對於每個 \(i\) 求 \(\min \{ d(i,k) \times k \}\)

Subtask 1,2,3,4

暴力走所有可能路徑

• Subtask 1：最多 \(O(n!)\) 條路徑
• Subtask 2：圖是鏈狀，只有 \(O(n)\) 條路徑
• Subtask 3：圖是樹，只有 \(O(n)\) 條路徑
• Subtask 4：圖是環，只有 \(O(n)\) 條路徑

Subtask 5,6

把每個節點都複製 \(n\) 份
如果本來有一條邊是 \((u,v)\)
那就對所有 \(1 \leq i < n\)
蓋一條邊是 \(u\) 的第 \(i\) 個點到 \(v\) 的第 \(i+1\) 個點（有向）
還有 \(v\) 的第 \(i\) 到 \(u\) 的第 \(i+1\)
這樣走到某個節點的第 \(i\) 個點的路徑長度一定是 \(i-1\)
\(n^2\) 個點、\(2nm\) 個邊做最短路徑

\(O((n^2+m) \log n)\)

Subtask 7

\(dp[i][j]=\) 走 \(i\) 步到 \(j\) 的最短路

\[dp[i][j]=\min_{(k,j) \in E} \{ dp[i-1][k] + dis(k,j) \}\]

\(O(n(n+m))\) DP

#include <bits/stdc++.h>
 
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define eb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
 
using namespace std;
 
typedef long long ll;
 
using pll = pair<ll, ll>;
 
int main(){
    StarBurstStream
 
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<pll>> g(n + 1);
    for(int i = 0; i < m; i++){
        int u, v, p;
        cin >> u >> v >> p;
        g[u].eb(mp(v, p));
        g[v].eb(mp(u, p));
    }
 
    vector<ll> dp(n + 1, 1LL << 60);
    dp[s] = 0;
    vector<ll> ans(n + 1, 1LL << 60);
    ans[s] = 0;
    for(int i = 1; i <= n; i++){
        vector<ll> dp2(n + 1, 1LL << 60);
        for(int j = 1; j <= n; j++){
            for(auto e : g[j]){
                dp2[e.F] = min(dp2[e.F], dp[j] + e.S);
            }
        }
        dp = dp2;
        for(int j = 1; j <= n; j++){
            if(dp[j] < (1LL << 60)) ans[j] = min(ans[j], dp[j] * i);
        }
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << "\n";
 
    return 0;
}

題目大意

給你一個序列 \(c\)
有 \(q\) 筆詢問，每筆詢問給 \(l, r\)
求有幾個在 \([l,r]\) 裡的區間 \([L,R]\)
滿足 \([L,R]\) 裡的數字全距不超過 \(k\)

Subtask 1

\(k=10^6\)

所有區間的全距都不會超過 \(k\)

詢問是 \(l,r\)
令 \(len=r-l+1\)
答案是 \(\frac{len(len+1)}{2}\)

Subtask 2

\(n,q \leq 50\)

對每個詢問
枚舉 \(O(n^2)\) 個區間
暴力掃一遍計算全距

\(O(n^3q)\)

Subtask 3

\(n,q \leq 500\)

對每個詢問
枚舉區間的左端點
然後枚舉右端點的時候可以一邊算區間內的最大最小值

\(O(n^2q)\)

Subtask 4

\(n,q \leq 10^4\)

先找到以每個位置為右界時
區間的左界最遠可以到哪

對每個詢問，枚舉右界
可以知道能取的左界有幾個

\(O(nq)\)

Subtask 5,6

把詢問照右界排序
從左邊掃到右邊
計錄「每個位置當左界時，有幾個目前已經掃過的位置可以當右界」
令這個數字是 \(r(i)\)

如果目前掃到的這個位置是 \(i\)
它當右界時，最遠的左界在 \(l(i)\)
那麼就把 \(r(l(i)..i)\) 都加上 1

處理右界在目前位置的詢問
直接詢問 \(r(l..r)\) 的和即可

\(r(i)\) 維護可以用 BIT
\(l(i)\) 計算可以用單調隊列
或是二分搜配 Sparse Table 求最大最小值
複雜度是 \(O((n+q) \log n)\)

如果你在二分搜的時候是配線段樹
複雜度會是 \(O(n \log^2 n + q \log n)\)
可能 TLE，只能過 Subtask 5

#include <bits/stdc++.h>
 
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define eb(a) emplace_back(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
 
using namespace std;
 
typedef long long ll;
 
using pii = pair<int, int>;
 
int lowbit(int x){
    return x & -x;
}
 
struct BIT{
    vector<ll> bit;
    void modify(int x, ll v){
        for(; x < bit.size(); x += lowbit(x)){
            bit[x] += v;
        }
    }
    ll query(int x){
        ll ans = 0;
        for(; x > 0; x -= lowbit(x)){
            ans += bit[x];
        }
        return ans;
    }
};
 
struct SUMBIT{
    BIT bit1, bit2;
    void modify(int l, int r, ll v){
        if(l > r) return;
        bit1.modify(l, v);
        bit1.modify(r + 1, -v);
        bit2.modify(l, l * v);
        bit2.modify(r + 1, (r + 1) * (-v));
    }
    ll query(int x){
        return (x + 1) * bit1.query(x) - bit2.query(x);
    }
    ll query(int l, int r){
        return query(r) - query(l - 1);
    }
};
 
int main(){
    StarBurstStream
 
    int n, k;
    cin >> n >> k;
 
    SUMBIT bit;
    bit.bit1.bit.resize(n + 1);
    bit.bit2.bit.resize(n + 1);
 
    vector<int> h(n + 1);
    for(int i = 1; i <= n; i++) cin >> h[i];
 
    vector<vector<pii>> qry(n + 1);
    int q;
    cin >> q;
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        qry[r].eb(mp(l, i));
    }
 
    deque<int> mx, mn;
    vector<ll> ans(q);
    int lp = 1;
    for(int i = 1; i <= n; i++){
        while(!mx.empty() && h[mx.back()] <= h[i]) mx.pob;
        while(!mn.empty() && h[mn.back()] >= h[i]) mn.pob;
        mx.eb(i);
        mn.eb(i);
 
        while(h[mx.front()] - h[mn.front()] > k){
            lp++;
            while(mx.front() < lp) mx.pof;
            while(mn.front() < lp) mn.pof;
        }
 
        bit.modify(lp, i, 1);
 
        for(auto p : qry[i]){
            int id = p.S, l = p.F;
            ans[id] = bit.query(l, i);
        }
    }
 
    for(ll i : ans) cout << i << "\n";
 
    return 0;
}

告示牌

只有在空格出現時才能換行

告示牌 - Subtask 1

\(s\) 沒有空格
→ 不能換行
→ 答案為 \(|s|\)

2 / 100

告示牌 - Subtask 2

\(|s| \le 20\)
→ 枚舉換行的位置
→ 複雜度 \(O(2^{|s|} \times |s|)\)

9 / 100

告示牌 - Subtask 3

\(|s| \le 1000\)
→ 枚舉告示牌寬度
→ 找到最小的 \(w\) 能塞得下
→ 複雜度 \(O(|s|^2)\)

(9 + 16) / 100

告示牌 - Subtask 4

\(|s| \le 2 \times 10^5\)
→ 枚舉告示牌寬度
→ 對告示牌寬度二分搜
→ 找到最小的 \(w\) 能塞得下
→ 複雜度 \(O(|s|\log{|s|})\)

100 / 100

#include<bits/stdc++.h>
using namespace std;
 
int k;
vector<int> v;
 
bool chk(int w)
{
    int now = 0, cnt = 1;
    for (int i : v)
        if (now + i > w)
            now = i, cnt++;
        else
            now += i;
    return (cnt <= k);
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> k, cin.ignore(100, '\n');
 
    string s;
    getline(cin, s);
 
    int mx = 0, sum = s.size();
    v.clear();
    for (int i = 0; i < s.size(); i++)
    {
        int tl = 0;
        while (i < s.size() && s[i] != ' ')
            tl++, i++;
 
        if (i < s.size())
            tl++;
        v.push_back(tl), mx = max(mx, tl);
    }
 
    int l = mx - 1, r = sum;
    while (l + 1 != r)
    {
        int m = (l + r) / 2;
        if (chk(m))
            r = m;
        else
            l = m;
    }
    cout << r << '\n';
 
    return 0;
}

變色蠑螈 - Subtask 1

\(c_1 = c_2 = \ldots = c_n\)
→ 需要的魔法只會有 \(c_1\) 到 \(d_i\)
→ 答案是 \(d_i\) 的相異數字數量 (？

變色蠑螈 - Subtask 1

\(c_1 = c_2 = \ldots = c_n\)
→ 需要的魔法只會有 \(c_1\) 到 \(d_i\)
→ 答案是 \(d_i\) 的相異數字數量
→ 如果存在 \(c_1 = d_i\) 記得要減一

set 維護，總複雜度 \(O(n\log{n})\)

6 / 100

變色蠑螈 - Subtask 2

\(a_i,b_i \le 2\)
→ 只會需要 \(1\) 變成 \(2\) 的魔法
→ 如果存在 \(c_i \ne d_i\) 答案為 \(1\)；否則為 \(0\)

複雜度 \(O(n)\)

4 / 100

變色蠑螈

蠑螈顏色 → 點
魔法 → 邊
→ 判斷需要多少邊才能讓每組 \(c_i,d_i\) 連通

變色蠑螈 - Subtask 3

\(a_i,b_i \le 4\)
→ 魔法數量只有 \(C^4_2 = 6\) 種
→ 枚舉需要哪些魔法

9 / 100

變色蠑螈 - Subtask 4

\(n,c_i \le 1000\)
→ 每次 DFS 判斷目前的 \(c_i,d_i\) 是否已連通
→ 不連通就加邊

總複雜度 \(O(n^2)\)

17 / 100

變色蠑螈 - Subtask 5

\(c_i \le 2 \times 10^5\)
→ 每次 DFS 判斷目前的 \(c_i,d_i\) 是否已連通
→ 並查集判斷目前的 \(c_i,d_i\) 是否已連通
→ 不連通就加邊

總複雜度 \(O(n \times \alpha(n))\)

(17+31) / 100

變色蠑螈 - Subtask 6

顏色最多 \(2n\) 種
→ 先將顏色編號離散化
→ 剩下跟 Subtask 5 一樣

總複雜度 \(O(n \log{n} + n \times \alpha(n))\)

100 / 100

#include<bits/stdc++.h>
using namespace std; 
 
#define MP make_pair
#define F first
#define S second
 
vector<int> rt;
 
int fnd(int a)
{
    if (a == rt[a])
        return a;
    else
        return rt[a] = fnd(rt[a]);
}
 
void uni(int a, int b)
{
    int x = fnd(a), y = fnd(b);
    rt[x] = y;
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    vector<int> c(n), d(n), v;
    for (int &i : c)
        cin >> i, v.push_back(i);
    for (int &i : d)
        cin >> i, v.push_back(i);
    sort(v.begin(), v.end()), v.resize(unique(v.begin(), v.end()) - v.begin());
 
    rt.resize(v.size());
    for (int i = 0; i < rt.size(); i++)
        rt[i] = i;
 
    vector<int> nc(n), nd(n);
    for (int i = 0; i < n; i++)
        nc[i] = lower_bound(v.begin(), v.end(), c[i]) - v.begin();
    for (int i = 0; i < n; i++)
        nd[i] = lower_bound(v.begin(), v.end(), d[i]) - v.begin();
 
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; i++)
        if (fnd(nc[i]) != fnd(nd[i]))
            ans.push_back(MP(v[nc[i]], v[nd[i]])), uni(nc[i], nd[i]);
 
    cout << ans.size() << '\n';
    for (auto p : ans)
        cout << p.F << ' ' << p.S << '\n';
 
    return 0;
}