傳送門

I

注意 ：題目是要讓 \(1\) 都在右邊

K

通過(guò)手動(dòng)模擬就可以發(fā)現(xiàn)規(guī)律， \(fppf\) 循環(huán)

B

貪心，位運(yùn)算

按位枚舉最小的最大值，哪一位必須要放1

這體現(xiàn)在如果這位后面全是 \(1\) 的時(shí)候，\(n\) 個(gè)數(shù)的總和開始首次小于目前的 \(sum\) ，就說(shuō)明 當(dāng)前位必須放 \(1\)

• 在枚舉當(dāng)前位的前一位時(shí)，發(fā)現(xiàn)此時(shí)的和 \(>\) 或 \(= sum\) ，那么在前一位放 \(1\) ，結(jié)果肯定會(huì)大于 \(sum\) ，不符合要求

• 枚舉當(dāng)前位的時(shí)候，此時(shí)和 \(< sum\)，則在這一位放 \(1\)，結(jié)果會(huì) \(<\) 或 \(= sum\) ，只要不是 大于，就可以在這一位后面繼續(xù)放 \(1\) ，讓最后的結(jié)果為 \(sum\) 。由于枚舉每一位都是 必放不可 才會(huì)放 \(1\) ，所以這樣的最大值是最小的

注意：由于最后數(shù)組中的數(shù)可能并不是完全相同，所以并不是當(dāng)前位上的 \(1\) 在每一個(gè)數(shù)中都存在，所以要看當(dāng)前的 \(sum\) 最多需要多少個(gè) 此位上的 \(1\)

void solve()
{
    int n, sum = 0, u = 0; cin >> n;
    for(int i = 0; i < n; i++) {int q; cin >> q; sum += q;}
    for(int i = 31; i >= 0; i--) {
    	if(((1ll << i) - 1) * n < sum) u += (1ll << i), sum -= (1ll << i) * min(n, sum / (1ll << i));
    }
    cout << u;
}

F

二分

每次從 左下角 \(or\) 右上角 開始判斷當(dāng)前 \(mid\) 是否滿足條件

  -- 原因：
  1.左上角開始的話，下面和右邊都比當(dāng)前大，不方便判斷個(gè)數(shù) 
  2.右上角開始的話，左邊比它小，下邊比它大，方便轉(zhuǎn)移
  3.左下角同理右上角，右下角同理左上角

由于要求 從大到小 第 \(k\) 大的數(shù) -- 轉(zhuǎn)換一下 \(k = n * n - k + 1\) 從小到大第 \(k\) 小的數(shù)

以左下角為例 (第 \(k\) 小的數(shù)稱為 \(mid\))

• 若當(dāng)前返回 \(0\)，說(shuō)明比 \(mid\) 小，由于性質(zhì)，所以這一列從這一行開始都比 \(mid\) 小，\(cnt += i\)，轉(zhuǎn)移到右邊一列，比當(dāng)前大的地方繼續(xù)判斷

• 若當(dāng)前返回 \(1\)，說(shuō)明不比 \(mid\) 小，那么就轉(zhuǎn)移到這一列的上一行，比它的的地方繼續(xù)判斷

只統(tǒng)計(jì)比它小的即可，再用 最后的結(jié)果 和 \(k\) 的比較 作為 二分 的 \(check\)

int ask(int x, int y, int z){
    cout << "? " << x << ' ' << y << ' ' << z << '\n';
    cout.flush();
    int ans; cin >> ans;
    return ans;
}

void solve()
{
    int n, k; cin >> n >> k;
    k = n * n - k + 1; //正數(shù)的順序
    auto check = [&](int x) {
    	int cnt = 0, i = n, j = 1;
    	while(i >= 1 && j <= n) {
    		if(ask(i, j, x) == 1) j++, cnt += i;
    		else i--;
    	}
    	return (cnt >= k ? true : false);
    };
    int l = 1, r = n * n;
    while(l <= r) {
    	int mid = l + r >> 1;
    	if(check(mid)) r = mid - 1;
    	else l = mid + 1;
    }
    cout << "! " << l << '\n';
}

D

分成四種情況

\(① 一直向右\)

\(② 一直向左\)

\(③ 先向左再向右 （最優(yōu)解法只會(huì)折返一次）\)

\(④ 先向右再向左\)

上面兩種都可以直接用 前綴和 求出

先向左再向右

 可以上一個(gè)的狀態(tài)，也就是 dp2[i - 1][j - 1] 
 假設(shè)它先向左移，在此處再判斷 是繼續(xù)左移比較好 還是 開始右移
 而在 i - 1 處的狀態(tài)在上一輪已經(jīng)判斷過(guò)，就可以直接用了

先向右再向左

  同理
  但是要從右邊開始，因?yàn)橐^承右邊的狀態(tài)

void solve()
{
	int n, ans = 0; cin >> n;
	vector<int> a(n + 2);
	vector<vector<int>> dp1(n + 2, vector<int>(2 * n + 10)), dp2(n + 2, vector<int>(2 * n + 10));
	for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
	for(int i = 1; i <= n; i++) {
		//一直向右 or 先向左再向右
		for(int j = 1; j <= 2 * n; j++) dp1[i][j] = max(dp1[i - 1][j - 1], a[min(n, i + j)] - a[i - 1]);
	}
	for(int i = n; i >= 1; i--) {
		//一直向左 or 先向右再向左
		for(int j = 1; j <= 2 * n; j++) dp2[i][j] = max(dp2[i + 1][j - 1], a[i] - a[max(0ll, i - j - 1)]), dp1[i][j] = max(dp1[i][j], dp2[i][j]);
	}
	for(int i = 1; i <= n; i++) {
		int res = 0;
		for(int j = 1; j <= 2 * n; j++) res ^= dp1[i][j] * j;
		ans ^= (res + i);		
	}
	cout << ans;
}

M

相差為 \(1\) 的兩個(gè)數(shù) 相加 得到一個(gè)數(shù)，讓最后的 字典序最大

就是 奇數(shù) ? 偶數(shù) \(=\) 奇數(shù) 盡可能大，所以從 最大的偶數(shù) \(x\) 依次 尋找 ，先找 是否存在 \(x + 1\)，因?yàn)檫@樣 字典序最大；沒有則再找是否存在 \(x - 1\)；都沒有就說(shuō)明此 \(x\) 不能用

查找

\(① 本就存在\)

\(② 通過(guò)其它數(shù)經(jīng)過(guò)好幾次拼湊而得\)

所以要使用 遞歸 來(lái)判斷 \(x + 1\) 或者 \(x - 1\) 是否存在，對(duì)一個(gè)偶數(shù) \(x\) 進(jìn)行判斷時(shí)，在這個(gè)過(guò)程中 會(huì)刪去很多用來(lái)拼湊的數(shù)字 ，所以刪除的時(shí)候要記錄一下，最后 遞歸到底層還是無(wú)法拼湊就要復(fù)原 ，再給它加回去

vector<int> res;

void solve()
{
	int n; cin >> n;
	vector<int> a(n), b, ans;
	unordered_map<int, int> mp;
	for(int i = 0; i < n; i++) {
		cin >> a[i], mp[a[i]]++;
		if(a[i] % 2 == 0) b.emplace_back(a[i]);
	}
	auto get = [&](auto&& get, int x) -> int {
		if(mp[x] > 0) {mp[x]--, res.emplace_back(x); return 1;}
		if(x == 1 || x % 2 == 0) return 0; //1 和 偶數(shù) 不可能拼湊出來(lái)
		return get(get, x / 2) && get(get, x / 2 + 1ll); //繼續(xù)向下遞歸，看是否能拼湊出x
	};
	auto check = [&](auto&& check, int x) -> int {
		res.clear(); //清除上次操作的影響，記錄此次操作刪了什么數(shù)字
		if(get(get, x)) return 1;
		//不成立，將此次操作中刪的數(shù)都加回去
		for(auto& u : res) mp[u]++;
		return 0;
	};
	sort(b.rbegin(), b.rend());
	for(auto& u : b) {
		if(mp[u] <= 0) continue;
		mp[u]--, res.emplace_back(u);
		//要讓結(jié)果盡可能大，所以要先找 u + 1
		if(check(check, u + 1)) mp[u * 2 + 1ll]++; 
		else if(check(check, u - 1)) mp[u * 2 - 1ll]++;
		else mp[u]++;
	}
	for(auto& [q, w] : mp) {
		for(int i = 0; i < w; i++) ans.emplace_back(q);
	}
	sort(ans.rbegin(), ans.rend());
	cout << ans.size() << '\n';
	for(auto& u : ans) cout << u << ' ';
}