A. GCD vs LCM

inline void solve() {
    int n;
    cin >> n;
    if ((n - 2) / 2 == n - 2 - (n - 2) / 2) cout << 1 << ' ' << n - 3 << ' ' << 1 << ' ' << 1 << endl;
    else cout << (n - 2) / 2 << ' ' << n - 2 - (n - 2) / 2 << ' ' << 1 << ' ' << 1 << endl;
}

int main() {
    //freopen("../input.txt" , "r" , stdin);
    int T;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

分情况讨论一下： 当n为偶数的时候c = 1 , d = 1 , lcm(c , d) = 1 , 这个时候gcd(a , b) = 1,即只需要构造出
a,b互质即可即a = 1 , b = n - 3
当n为奇数的时候同理。

B. Array Cloning Technique

inline void solve() {
    int n;
    cin >> n;
    map<int , int> mp;
    for (int i = 0 ; i < n ; i ++ ) {
        int x;
        cin >> x;
        mp[x] ++ ;
    }
    int maxv = 0;
    for (auto [_ , cnt] : mp) maxv = max(maxv , cnt);
    int cnt = 0 , cur_x = maxv , copy = 0;
    while (cur_x < n) {
        if (copy == 0) {
            cnt ++ ;
            copy = cur_x;
        }
        else {
            cnt ++ ;
            copy -- ;
            cur_x ++ ;
        }
    }
    cout << cnt << endl;
}

int main() {
    //freopen("../input.txt" , "r" , stdin);
    int T;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

贪心的想一下要使操作步数最少，那么选出现次数最多的一个数进行操作就可以了，模拟一下就可以了。

C. Tree Infection

bool check(int mid , vector<int> &cnt) {
    if (cnt.size() > mid) return 0;
    int need = 0;
    for (int i = 0 ; i < cnt.size() ; i ++ ) {
        need ++ ;
        need += max(0 , cnt[i] - (mid - i));
    }
    return need <= mid;
}

inline void solve() {
    int n;
    cin >> n;
    map<int , int> mp;
    vector<int> cnt;
    mp[0] = 1;
    for (int i = 0 ; i < n ; i ++ ) {
        int x;
        cin >> x;
        mp[x] ++ ;
    }
    for (auto [_ , cnt] : mp) cnt.push_back(cnt);
    sort(cnt.begin() , cnt.end() , greater<int>());
    int l = 1 , r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid , cnt)) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
}

int main() {
    //freopen("../input.txt" , "r" , stdin);
    int T;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

同样也是贪心，二分下一答案 ，要使感染时间最短，那么把每一层的节点都感染一个然后手动的把剩下的感染就可以了
如果二分的时间小于需要的时间或者小于层数（即每一层感染一个都做不到那么这个方案一定不可能成功）返回false否则
返回true。

D. GCD Guess

int query(int x , int y) {
    cout << "? " << x << ' ' << y << endl;
    int res;
    cin >> res;
    return res; 
}

inline void solve() {
    int ans = 0;
    for (int i = 1 ; i <= 30 ; i ++ ) {
        int res = query((1 << i - 1) - ans , (1 << i) + (1 << i - 1) - ans);
        if (res != (1 << i - 1)) ans += (1 << i - 1);
    } 
    cout << "! " << ans << endl;
}

交互式题目，从每一位考虑。

E. MinimizOR

不会做先放着。