牛客 周赛111 20251008

牛客 周赛111 20251009

https://ac.nowcoder.com/acm/contest/117763

A：
题目大意：

void solve(){int a, b, c;cin >> a >> b >> c;if (b != a + 1 || c != b + 1) cout << "No";else cout << "Yes";
}

签到

B：

题目大意：

void solve(){int n;cin >> n;int mn = 1e9, pos = 0;for (int i = 1; i <= n; i ++){int x;cin >> x;if (mn > x){mn = x;pos = i;}}cout << pos << ' ';int mx = 0;for (int i = 1; i <= n; i ++){int x;cin >> x;if (mx < x){mx = x;pos = i;}}cout << pos;
}

转换方程，当 \(a_x\) 是 \(a\) 数组中最小的元素，\(b_y\) 是 \(b\) 数组中最大的元素时两式相减有最大值

C：
题目大意：

void solve(){LL n, k, x;cin >> n >> k >> x;vector<int> a(2 * x);vector<int> b;if (k == 0){for (int i = 1; i <= n; i ++){int t;cin >> t;cout << t << ' ';}return;}for (int i = 0; i < n; i ++){int t;cin >> t;if (i < x)a[i + x] = a[i] = t;elseb.push_back(t);}int st = (((x - k) % x) + x) % x;for (int i = st; i < st + x; i ++) cout << a[i] << ' ';for (auto i : b) cout << i << ' ';}

每次都令第 \(x\) 张牌放到顶部，那么前 \(x\) 张牌的顺序会形成一个循环

做 \(k\) 次操作相当于把前 \(x\) 张牌循环右移 \(k\) 次，那么最终的位置的偏移量就是 \(k \% x\)

D：
题目大意：

void solve(){int n;cin >> n;vector<int> a(n);for (auto &x : a) cin >> x;vector<int> b(n);for (int i = 0; i < n; i ++){b[i] = to_string(a[i]).size() & 1;a[i] %= 11;}vector<vector<int>> dp(2, vector<int>(11, 0));LL ans = 0;for (int i = 0; i < n; i ++){ans += dp[1][a[i]] + dp[0][(11 - a[i]) % 11];if (b[i]) ans += dp[1][a[i]] + dp[0][a[i]];else ans += dp[0][(11 - a[i]) % 11] + dp[1][(11 - a[i]) % 11];dp[b[i]][a[i]] ++;}	cout << ans;
}

根据题意，定义 \(c = a\times 10^{\lvert b\rvert} + b\) ，（\({\lvert b\rvert}\) 表示 \(b\) 的位数）判断 \(c\) 是否为 \(11\) 的倍数

又因为在模 $11 $ 的意义下 \(10 \equiv -1\) ，所以 \(c = (-1)^{\lvert b\ \rvert} a+ b\)

定义 \(dp_{i,j}\) 表示在当前枚举的数之前有多少个数位奇偶性为 \(i\) 且 余数为 \(j\) 的数，枚举每一个数，分类讨论它作为 \(a,b\) 的情况

如果这个数是 \(a\) ，那么答案累加上它之前 奇偶性为 \(1\) 且 余数为 \(a\%11\) 的数 和 奇偶性为 \(0\) 且 余数为 \((11- a)\%11\) 的数

\[(-1)^1a+b \equiv 0(\mathrm{mod}\ 11) \to b\equiv a(\mathrm{mod}\ 11)\\ (-1)^0a+b \equiv 0(\mathrm{mod}\ 11) \to b \equiv 11 - a (\mathrm{mod}\ 11)\\ \]

如果这个数作为 \(b\) 位数为奇数时，答案累加上它之前所有余数为 \(a\%11\) 的数

\[(-1)^1a + b\equiv 0(\mathrm{mod}\ 11) \to a \equiv b(\mathrm{mod}\ 11) \]

如果这个数作为 \(b\) 位数为偶数时，答案累加上它之前所有余数为 \((11- a)\%11\) 的数

\[(-1)^0a + b\equiv 0(\mathrm{mod}\ 11) \to a \equiv 11-b(\mathrm{mod}\ 11) \]

E：
题目大意：

void solve(){LL n, k;cin >> n >> k;LL sum = 0;for (int i = 1; i <= n; i ++) sum += i;sum += n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++) a[i] = i;for (int i = n - 2; i >= 1; i --){if (sum - k >= i){swap(a[i], a[i + 1]);sum -= i;} }if (sum != k){cout << -1;return;}for (int i = 1; i <= n; i ++) cout << a[i] << ' ';
}

考虑先构造出一个 \(L(a) +R(a)\) 最大的排列，显然有一种方式是直接按照顺序排列，这样的 \(L(a) + R(a) = \sum\limits_{i = 1}^ni + n\)

可以发现，从后往前如果交换任意两个相邻的数 \(a_i,a_{i + 1}(i + 1 < n)\) 那么 \(L(a)+R(a)\) 就会减少 \(a_i\) 的贡献

例如 \(1,2,3,4,5\) ，从后往前交换 \(3,4\) 会变成 \(1,2,4,3,5\) ，\(L(a) = 1+2+4+5,R(a)=5\)

像这样的构造，下标可以从 \(n-1\) 枚举到 \(1\) ，记最大的 \(L(a)+R(a) = sum\) ，当 \(sum-k\ge a_i\) 时，就令 $a_{i} $ 和 \(a_{i + 1}\) 交换

直到最后，如果 \(sum\) 还是不等于 \(k\) 说明这样的构造方式不存在，因为最小的 \(sum\) 的情况就是令两个极大的数在排列左右两端

F：
题目大意：

void solve(){int n, k;cin >> n >> k;if (k >= n ||  k < (n + 1) / 2){cout << -1;return;}int m = n - k;int st = 1;for (int i = 1; i < m; i ++){cout << st + 1 << ' ' << st << ' ';st += 2;} int ed = st;st ++;while (st <= n){cout << st << ' ';st ++;}cout << ed;
}

依然是一个经典的结论构造，对于一个序列 \(1,2,3,4,5\) 它的环指的是把这些数依次向左或向右循环移动，例如 \(2,3,4,5,1\) 和 \(4,5,1,2,3\) 对于这样的形成的任意两个序列 \(a,b\) 通过交换任意两个元素的操作使得 \(a\) 变为 \(b\) 的操作次数为 \(n-1\) ，即环元素个数减去 \(1\)

题意需要构造一个排列，使得数组变为升序的最小操作次数为 \(k\)

可以将排列分割为 \(m\) 个独立的环 \(cir\)，那么总操作次数就是 \(\sum\limits_{i=1}^m\lvert cir_i \rvert-m = n-m=k\) ，求出 \(m = n -k\)

又因为要求每个 \(a_i\ne i\) ，所以每个划分的环的大小至少为 \(1\)

一种构造方式是前 \(k-1\) 个环都是形如 \(\{i + 1,i\}\) ，最后一个环的大小为 \(n-2\times(k - 1)\)