菜鸡求建议

第一题：n为奇数输出n个1，n为偶数输出n-1个0即可：#include <iostream>using namespace std;int main() {int t;cin >> t;while (t --) {int n;cin >> n;if (n & 1) {for (int i = 0; i < n; i ++) {cout << 1 << " ";}cout << '\n';} else {for (int i = 0; i < n - 1; i ++) {cout << 1 << " ";}cout << 0 << '\n';}}}第二题：如果你有n个长度相同的木棍，那么他们组成正m边形的组合是C(n，m)个，C是组合数，计下数就可以了。#include <bits/stdc++.h>using namespace std;#define int long longconst int p = 998244353;const int N = 5e3 + 10;int h[N], rh[N];int C(int n, int m) {if (n < m) return 0;return h[n] * rh[m] % p * rh[n - m] % p;}int qs(int a, int b) {int res = 1;while (b) {if (b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;}signed main() {h[0] = rh[0] = 1;for (int i = 1; i < N ; i ++) {h[i] = h[i - 1] * i % p;rh[i] = qs(h[i], p - 2);}int n;cin >> n;map<int, int> mp;for (int i = 0; i < n; i ++) {int x;cin >> x;mp[x] ++;}for (int i = 3; i <= n; i ++) {int res = 0;for (auto& it : mp) {res = (res + C(it.second, i)) % p;}cout << res << ' ';}}3，最小生成树模板题，注意处理一下正边#include <cmath># include <iostream>#include <queue>using namespace std;const int N = 1e5 + 10;int p[N];int find(int x) {if (x != p[x]) p[x] = find(p[x]);return p[x];}int main() {int n, m;cin >> n >> m;priority_queue<pair<int, pair<int, int>>> pq;for (int i = 1; i <= n; i ++) p[i] = i;for (int i = 1 ; i <= m; i ++) {int u, v, x;cin >> u >> v >> x;pq.push({x, {u, v}});}long long res = 0;while (pq.size() > 0) {auto t = pq.top();pq.pop();int u = t.second.first;int v = t.second.second;int x = t.first;if (x >= 0) {res += x;p[find(u)] = find(v);} else if (find(u) != find(v)) {res += x;p[find(u)] = find(v);}}cout << res << '\n';

1.算法：给定长度为n的序列A，你可以选择至多一个区间[L,R]（也可以不选），将该区间内的每个数加1，得到新序列B。目标是最大化 inv(A) - inv(B)（即尽可能减少逆序对数量）思路：选择区间 [L,R] 使得操作后，减少的逆序对（来自左侧大于区间内元素恰好1的数对）尽可能多，而新增的逆序对（来自区间内等于右侧元素的数对）尽可能少，从而最大化逆序对的净减少量。2.算法：给定一个长度为n的01串s和m个数字a₁到aₘ，判断能否从s中选出m个互不相交的连续子串（区间），使得每个子串恰好是对应数字aᵢ的二进制表示（无前导0，0用"0"表示）。思路：将每个数字aᵢ转化为二进制字符串（无前导0），然后尝试在s中为每个二进制串匹配一个出现位置，且所有匹配区间互不相交；可通过贪心策略（如优先选择最靠左的匹配）或动态规划（记录匹配状态和区间结束位置）来高效判断可行性。

北方华创机械有人收到了人工面的邮件嘛

0816 京东笔试答案第一题, 减少逆序对数量对于每个 ai, 找到 所有 aj = a[i] + 1 且 j < i 的 j, 则对于选择 j < L <= i 的 L 贡献 +1, 然后做一个前缀和取最大值即可代码```#include <iostream>#include <cstring>#include <algorithm>#include <vector>#include <unordered_map>using namespace std;void solve(){int n; cin >> n;vector<int> a(n + 10, 0), b(n + 10, 0), c(n + 10, 0);unordered_map<int, vector<int>> pos;for (int i = 1; i <= n; i ++){cin >> a[i];}for (int i = 1; i <= n; i ++){int v =a[i];int t = v + 1;if (pos.find(t) != pos.end()){for (int j : pos[t]){if (j < i){b[j + 1] ++;b[i + 1] --;}}}pos[v].push_back(i);}int ans = 0;int tmp = 0;for (int i = 1; i <= n; i ++){tmp += b[i];ans = max(ans, tmp);}cout << ans << endl;}int main(){int _ = 1;cin >> _;while (_ --){solve();}}```第二题, 跳水打分解法类似求区间最值, 维护每个长度为 m 的区间的最大值和最小值, 然后遍历过去即可算出答案。代码```#include <bits/stdc++.h>#define PII pair<long, long>#define x first#define y secondusing namespace std;int main(){int n, m;cin >> n >> m;priority_queue<PII> maxPq;priority_queue<PII, vector<PII>, greater<PII>> minPq;vector<long long> a(n + 10);double ans = 0;long long tmp = 0;for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 1; i <= m; i ++){maxPq.push({a[i], i});minPq.push({a[i], i});tmp += a[i];}long long minV = minPq.top().x;long long maxV = maxPq.top().x;ans = double(tmp - minV - maxV) / (m - 2);int ans2 = 1;int l = 1, r = m;while (r < n){// cout << ans << endl;tmp -= a[l]; l ++;r ++; tmp += a[r];minPq.push({a[l], l}); minPq.push({a[r], r});maxPq.push({a[l], l}); maxPq.push({a[r], r});while (minPq.top().y < l) minPq.pop();while (maxPq.top().y < l) maxPq.pop();if ((double(tmp - minPq.top().x - maxPq.top().x) / (m - 2)) > ans){ans = double(tmp - minPq.top().x - maxPq.top().x) / (m - 2);ans2 = l;}}cout << ans2 << endl;}```