C. Against the Difference
題目：
思路：
簡單DP
不難發現我們貪心是沒法貪的，因此考慮DP
我們令 dp[i] 為 前 i 個元素能構造出的最長整齊子序列的長度，不難發現一個很簡單的轉移，即直接繼承 dp[i] = dp[i-1]，那么現在考慮增加奉獻的情況
對于 a[i]，如果我們此時要選擇增加奉獻，那么就要從前 a[i] 個位置轉移，且這 a[i] 個位置 j 的 a[j] 都是 a[i]
所以考慮儲存 a[i] 的位置，如果 pos[a[i]].size() >= a[i]，那么說明此時可以轉移，貪心的想，我們肯定是越后轉移越好，所以我們直接從前 a[i] 個位置轉移即可，此時增加的奉獻就是 a[i]
具體實現看代碼?
代碼：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());void solve()
{int n, x;cin >> n;vector<int> dp(n + 1, 0);vector<vector<int>> pos(n + 1);for (int i = 1; i <= n; i++){cin >> x;dp[i] = dp[i - 1];pos[x].push_back(i);if (pos[x].size() >= x)dp[i] = max(dp[i], dp[pos[x][pos[x].size() - x] - 1] + x);}cout << dp[n] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while (t--){solve();}return 0;
}D. For the Champion
題目：
思路：
經典距離
我們不難發現，絕對值很麻煩，所以我們應該考慮刪除絕對值的影響
同時我們還能發現，如果 k 很小，這其實不利于我們尋找，因為會有很多的節點干擾我們
所以我們考慮一個很大的坐標，如 (∞，∞)，這樣的話我們肯定能確定是哪個點的結果
考慮十步內得出，我們不妨考慮兩個極端：?P1 (∞，∞)，P2 (∞，-∞)
我們假設求出的答案是 ask，原始坐標是 (x, y)
①.對于 P1，我們不難寫出對應式子
其中 x/y_m 代表移動的距離，x/y_i 代表距離最短時對應的點，那么拆開就有（這里直接化簡）
其中兩個 x/y_m 都是 ∞ 均為已知量，那么為了讓 ask 最小，我們的 x_i + y_i 肯定是最大的，所以預處理即可
②.對于 P2，我們同理可寫出
但是由于此時 y-y_m?小于 y_i，因此考慮變號，則有
化簡得
同理為了讓 ask 最小，我們就要讓 y_i - x_i 最小，所以也是預處理出來
我們將上面兩個式子優化一下，則有
由于 res1 和 res2 我們可以求出來，那么也就能求出 x,y 的坐標
具體的，由于我們無法一次直接移動 ∞ 長度，那我們就移動一個很長的距離即可，由于 k <= 1e9，所以我們考慮移動四次?1e9，其中兩次 R 來達到 x 軸無限遠，兩次 D 來達到 y 軸無限遠，這樣就能得到一個 res 了
而對于另一個 res，我們直接四次 U 即可，因為 x 軸無限遠了，所以只需要考慮 y 軸，所以先兩次抵消向下無限遠，然后向上即可，這樣另一個 res 也解決了
綜上，我們只使用了 8 次即可完成問題
代碼：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());void solve()
{int n;cin >> n;int mx = -1e18, mi = 1e18;for (int i = 0; i < n; i++){int x, y;cin >> x >> y;mi = min(mi, y - x);mx = max(mx, x + y);}int ask;cout << "? R 1000000000" << endl;cin >> ask;cout << "? R 1000000000" << endl;cin >> ask;cout << "? D 1000000000" << endl;cin >> ask;cout << "? D 1000000000" << endl;cin >> ask;int res1 = ask - 4000000000LL - mi;cout << "? U 1000000000" << endl;cin >> ask;cout << "? U 1000000000" << endl;cin >> ask;cout << "? U 1000000000" << endl;cin >> ask;cout << "? U 1000000000" << endl;cin >> ask;int res2 = ask - 4000000000LL + mx;cout << "! " << (res1 + res2) / 2 << " " << (res2 - res1) /2 << endl;
}signed main()
{int t = 1;cin >> t;while (t--){solve();}return 0;
}
