Codeforces 1513D - GCD and MST(設計解題)

Codeforces
字數統計： 2.1k   |   閱讀時間≈ 8分鐘

題目大意

Nastia 有一個數列，但我們並不知道數列裡面的數值，我們現在必須知道這些數值是甚麼，其中我們得知數列裡面的數值，是 1 ~ 數列長度。

我們可以像 Nastia 進行詢問，但 Nastia 不接受普通的詢問方式，她接受的詢問方式如下

  • \(t=1 : max(min(x,p_i), min(x+1, p_j)) \)
  • \(t=2 : mim(max(x,p_i), max(x+1, p_j)) \)
  • 其中 \(t\) 為我們選擇哪種查詢公式，\(p_i,p_j\) 則是數列的 index 當下數值，\(x\) 則是我們任意給的值，但 \(x\) 必須是數列中的數字。
  • \(t=1\) or \(t=2, 1 \leq i,j \leq n, i != j, 1 \leq x \leq n-1\)，一定要符合這些條件。

我們可以對 Nastia 最多查詢 \( \frac{3*n}{2} + 30 \)，必須在這些次數前確認出所有的數列。

如果已經確定數列，那輸出格式為 ! a b c，其中 a,b,c 為數列的數字， index 從 1 開始。

題目連結

重點觀念

  • 理解交互式解題
  • 找出 \(t=1, t=2\) 公式，在甚麼情況下可以省略裡面一些邏輯式
  • 如何確定數列中的每個數值

分析

我們可以對這題進行分析。
稍微看看這兩個公式

  • \(t=1 : max(min(x,p_i), min(x+1, p_j)) \)
  • \(t=2 : min(max(x,p_i), max(x+1, p_j)) \)

公式分析一下

  • \(t=1 : max(min(x,p_i), min(x+1, p_j)) \)
    當 \(x\) 設為無限大時，那我們可以簡化為 \(max(p_i,p_j) \)
  • \(t=2 : min(max(x,p_i), max(x+1, p_j)) \)
    當 \(x\) 設為無限小時，那我們可以簡化為 \(min(p_i,p_j) \)

我們沒有辦法設定為無限小或無限大，那該怎麼辦呢？

  • 那我們可以設為數列的最大數值與最小數值，分別式 \(n,1\)。
  • 現在我們知道可以將公式化簡了，但我沒有辦法知道 index \(i,j\) 要放哪些數值
    很簡單，我們只要將 \(min(p_i,p_j) \)，將 \(p_j\) 放最大，那 \(p_i\) 就是我們要的數值。
    另外一個公式亦同。
  • 我們以 我們只要將 \(min(p_i,p_j) \)，將 \(p_j\) 放最大，那 \(p_i\) 就是我們要的數值。 來進行探討
  • 將 \(p_j\) 放最大，那我們要先找出數列中的最大值
    由於題目的查詢方式不可以讓我們的 \(x\) 放最大，因此就用數列最大值。

那我們進行分析，如何找出數列中最大值

  • 根據上面的公式，我們有提到，當 \(x\) 設為無限小時，那我們可以簡化為 \(min(p_i,p_j) \)，因此我們要找到的是此公式中的最大值。
  • 因此公式就是 \(t=1 : max(min(n,p_i), min(n+1, p_j)) = n \)，n 是數列最大值，我們把 x 設為 n
    理論上現在我們可以知道數列最大值是在 \(i,j\) 這兩個位置，但我要怎麼寫呢？
  • 不斷循序漸進，也就是 \(i =i, j = i+1\)，for 迴圈一次進行 i,j
  • 我已經知道最大的數值在 \(i,j\) 位置，那我要怎麼確定她在 i 還是 j 呢？
  • 似乎不太能夠確定呢…

那我們再稍微簡化一下，我們鎖定 j 的位置一定是題目最大值的位置。

  • 因此公式就是 \(t=1 : max(min(n-1,p_i), min(n, p_j)) = n\)，n 是數列最大值，我們把 x 設為 n
  • 這樣 \(min(n, p_j) \) 一定是題目最大值。
  • 但現在有個問題，那如果依照迴圈去寫假如數列 index i 才是最大值，那該怎麼辦
    • 我們可以知道一件事情，\(min(n-1,p_i)\)，最大的數值為 \(n-1\)
    • 如果 \(p_i = n\)，那 \(min(n, p_j) < n \)
    • 因此只要我們 \(t=1 : max(min(n-1,p_i), min(n, p_j)) = n-1\)，我們就讓 \(i,j\) 位置互換
  • 紀錄最大的數值位置

現在我們有了最大的數值位置，求出其他位置數值

  • 可以用 \(t=2 : min(max(x,p_i), max(x+1, p_j)) \) 反推
  • 現在我們定義 \(p_m\) 表示最大的數值位置
  • \(t=2 : min(max(x,p_i), max(x+1, p_m)) \)
    • \(max(x+1, p_m) > p_i \)
    • 因此我們只要把 x 設到最小即可。
    • 數列中最小值是 0。
  • 因此我們只要對每一個 index 進行一次查詢就能推出答案！

注意：不可以在查詢時出現 \(? 2 p_i p_m 1 \)，其中 \(p_i == p_m\)，題目有說明 i 不可以等於 j，如果你這樣做則 codeforces 則會輸出 WA: wrong answer Indices should be distinct (test case 1)

稍微檢查下查詢次數會不會大於 \( \frac{3*n}{2} + 30 \)

  • 找出數列最大值 index 進行查詢次數 \(n/2+1\)
  • 每一個數值與數列最大值進行 \(t=2\)查詢次數 \(n-1\)
  • 因此最多的查詢次數只會有 \( \frac{3*n}{2} \)

參考連結

C. Nastia and a Hidden Permutation by JophieQu

心得

其實我之前並沒有寫過交互式解題，因此對這種流程非常不熟，是我的朋友們告訴我交互式解題我們應該要注重的是 input，而非 output，我原本在這邊思考了很久都一直鬼打牆…。腦袋不給力阿QQ。

後來再看 JophieQu 大大的詳解時，我一直寫錯…，我忘記 \(n-1 = max(min(n-1,p_i), min(n, p_j))) 的現象，因此要進行確認，然後再將 \(i,j\) 位置顛倒，為甚麼會忘記呢？因為我那時候認為我這樣比較好寫。可是是錯的阿

然後我還忘記題目的說明，題目有說明 不可以在查詢時出現 \(? t i j x \)，其中 \(i != j\)，對！我有看到。
但是我把每個 index 都帶入 \(t=2\) 去推出數列的數值，卻一直得到 WA，我就一直用紙筆去推敲，就是得不出這樣會錯的結果，後來再重新看一遍題目才知道，…，\(p_m\) 也是數列中的一個 index，如果直接用 for 迴圈去跑每一個 index，那其中會有一個 index 與 \(m\) 相同。

唉，還不夠聰明，腦袋還不夠好。還需要多多訓練自己的腦袋R。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 30000;
int T, a, n;
int num[MAXN];

int query(string cmd, int t, int i, int j, int x){ //用於查詢
    cout << cmd << " " << t << ' ' << i << ' ' << j << ' ' << x << '\n';
    int value;
    cin >> value;
    return value;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> T;
    while(T--){
        int max_index = 0, value; //max_index 為記錄最大值的 index
        // value 為 query function 回傳值

        cin >> n;
        for(int i = 1; i <= n; i+=2){ //找出最大的數值
            if(n & 1 && i == n){ //由於我是 i+=2，但有可能數列是奇數的情況，因此如果
                //數列是奇數，並且到現在還沒有找到最大值，那麼最後一個數值一定是最大值。
                max_index = n; //紀錄最大值 index
                num[n] = i; //並放入數列中
                break; //找到最大值跳出迴圈
            }
            value = query("?", 1, i, i+1, n-1); //進行查詢，查詢 i,j 內是否有數列最大值
            if(value == n){ //如果有，並且出現在 j 位置，j = i+1
                max_index = i+1; //紀錄最大值 index
                num[i+1] = n;  //並放入數列中
                break; //找到最大值跳出迴圈
            }
            if(value == n-1){ // p_i 有 7 or 8 的可能，我們在一次進行驗證
                value = query("?", 1, i+1, i, n-1); //將 i,j 相反後再 query 一次
                if(value == n){ //如果發現 i 真的是最大值
                    max_index = i;  //紀錄最大值 index
                    num[i] = n; //並放入數列中
                    break; //找到最大值跳出迴圈
                }
            }

        }

        //cout << "max_index " << max_index << '\n';
        for(int i = 1; i <= n; i++){ //找到最大值後，利用 t=2 公式找出每個數列的數值
            //由於 max_index 的值會在 i 裡面，題目的查詢有說明不可以用兩個 index 相同去查詢
            //因此我們要避免這種情況，才會寫這個 if 
            if(i == max_index) continue; 
            num[i] = query("?", 2, i, max_index, 1); //找出 i 數列的值
        }
        cout << "!"; //輸出答案
        for(int i = 1; i <= n; i++) cout << " " << num[i];
        cout << "\n";
    }

    return 0;
}

思考流程

透過紙筆與黑板而思考而成的片段，放在網路上供我紀念XD

  • 版權聲明： 本部落格所有文章除有特別聲明外，均採用 Apache License 2.0 許可協議。轉載請註明出處！
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: