2023杭電第七場補題報告1002 1004 1011 1013

1002 B. Random Nim Game (hdu.edu.cn)

思路

手推一下就可以發現其實除了一次必定結束的其他情況概論都是$\frac{1}{2}$

代碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve();
signed main(){cin.sync_with_stdio(0);cin.tie(0);int T = 1;cin >> T;while(T--){solve();}return 0;
}void solve(){int n;cin >> n;int cn1 = 0;for(int i = 0;i < n;i++){int x;cin >> x;if(x > 1)cn1++;}if(cn1 == 0){if(n & 1){cout << "1\n";}else{cout << "0\n";}}else{cout << "499122177\n";}
}

1004 D. Medians Strike Back (hdu.edu.cn)

思路

若答案是 B，則構造為 {1, 3, 1*,* 3*, . . . ,* 1*,* 3*,* 2*,* 2*,* 1*,* 3*, . . .* }，即 B 個 1 3 之后 2 2 構成一循環。**

代碼

#include <bits/stdc++.h>
#define re register
using namespace std;
inline int read()
{re int t = 0;re char v = getchar();while (v < '0')v = getchar();while (v >= '0')t = (t << 3) + (t << 1) + v - 48, v = getchar();return t;
}
int t, n, ans;
int main()
{t = read();while (t--){n = read();re int l = 1, r = n;while (l <= r){re int mid = l + r >> 1, tmp = n / (mid + mid + 2);re int s = tmp * 2 + max(0, n % (mid + mid + 2) - mid - mid);if (s <= mid)ans = mid, r = mid - 1;elsel = mid + 1;}printf("%d\n", ans);}
}

1011 K. Three Operations (hdu.edu.cn)

思路

思考一下就會發現，直接選擇收斂速度最快的進行，然后再在不選擇最后兩種情況的時候直接把當前數字加到結果中加速模擬。

代碼

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define sc secondusing namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int, int> PII;
int n;
int a[N];void solve() {int x, y;cin >> n >> x >> y;int res = 0;while (n != 0) {int x1 = n - 1, x2 = (n + x) / 2, x3 = sqrt(1.0 * (n + y));if(x2 >= n && x3 >= n){res += n;break;}if (x1 == min({x1, x2, x3}))n = x1;else if (x2 == min({x1, x2, x3}))n = x2;elsen = x3;res++;}cout << res << "\n";
}signed main() {IOS;int t = 1;cin >> t;for (int i = 1; i <= t; i++) {solve();}
}

1013 M. Minimal and Maximal XOR Sum (hdu.edu.cn)

思路

任選一個長度為 k 的區間，將其翻轉，然后可以再利用 f(k) = k(k 2 ?1) 次交換相鄰兩個數的操作再將這個區間翻轉回去，相當于什么操作都沒有做，而卻多了一個權值為 k 的操作和 f(k) 個權值為 2 的操作，所以：

? 如果 k ≡ 0 (mod 4) 或 k ≡ 1 (mod 4)，則我們可以任何時候將答案（權值異或和）異或 k；

? 如果 k ≡ 0 (mod 4) 或 k ≡ 1 (mod 4)，則我們可以任何時候將答案異或 k ⊕ 2。

代碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {char c = getchar();int x = 0, s = 1;while (c < '0' || c > '9') {if (c == '-') s = -1;c = getchar();}  //是符號while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}  //是數字return x * s;
}void solve();
signed main() {int T;T = read();while (T--) {solve();}return 0;
}
class FenwickTree {private:vector<int> tree;int n;public:FenwickTree(int size) {n = size;tree.resize(n + 1, 0);}// 單點更新：將索引i位置上的值增加valvoid update(int i, int val) {i++;  // 樹狀數組的索引從1開始，所以將i加1while (i <= n) {tree[i] += val;i += lowbit(i);}}// 區間查詢：計算前綴和，返回索引i位置的前綴和int query(int i) {i++;  // 樹狀數組的索引從1開始，所以將i加1int sum = 0;while (i > 0) {sum += tree[i];i -= lowbit(i);}return sum;}// 區間查詢：計算區間[i, j]的和int query(int i, int j) { return query(j) - query(i - 1); }private:int lowbit(int x) { return x & -x; }
};
void solve() {int n;n = read();vector<int> a(n + 1);for (int i = 1; i <= n; i++) {a[i] = read();}if (n == 1) {cout << "0 1\n";return;}FenwickTree t(n + 1);int cnt = 0;for (int i = 1; i <= n; i++) {cnt += t.query(a[i], n);t.update(a[i], 1);}// cout << cnt << "\n";int ans1 = 0, ans2 = 0;if (cnt & 1) {ans1 = 2;int c = log2(n) + 1;ans2 = (1 << c) - 1;} else {ans1 = 0;int c = log2(n) + 1;ans2 = (1 << c) - 1;ans2 -= 2;}cout << ans1 << " " << ans2 << "\n";
}