题目链接点这里
CF1918A Brick Wall
void solve()
{
ll n, m;
cin >> n >> m;
cout << n * (m / 2) << endl;
}
CF1918B Minimize Inversions
注意到,当其中一个排列有序时,总的逆序对数量最少()
今天找个时间补上证明
对于任意一对 \(i,j\) 位置,其可能的逆序对总贡献度 \(c_{i,j}\) 为 \(0,1,2\) 。由于两个排列对应位置上的元素是绑定的,所以在任意操作后只可能会出现下面几种情况:
- 总贡献度 \(c_{i,j}\) 由 \(0\) 变成 \(2\)
- 总贡献度 \(c_{i,j}\) 由 \(1\) 变成 \(1\)
- 总贡献度 \(c_{i,j}\) 由 \(2\) 变成 \(0\)
那么令其中一个排列有序时,只会出现上面的第 2, 3 种情况(其中一个排列有序时 \(c_{i,j}\) 不会取到 \(2\) )。这样所有的 \(c_{i,j}\) 都取到了最小值,则此时答案最小。
void solve()
{
int n;
cin >> n;
vector<pii> arr(n);
for (int i = 0; i < n; ++i)
cin >> arr[i].fi;
for (int i = 0; i < n; ++i)
cin >> arr[i].se;
sort(all(arr));
for (int i = 0; i < n; ++i)
cout << arr[i].fi << " ";
cout << endl;
for (int i = 0; i < n; ++i)
cout << arr[i].se << " ";
cout << endl;
}
CF1918C XOR-distance
为减少讨论,先假设 a > b。
首先将 \(a\),\(b\) 拆位。然后根据异或的性质,当 \(x\) 的某一位取 \(1\) 时,会将原本的 \(0\) 和 \(1\) 翻转,而本题求的是差,所以只要考虑不同的位。于是贪心的从高位到低位考虑,找到第一个不同的位置 \(hdig\),若 \(r\) 可以取这一位为 \(1\),则可以分两种情况考虑:
- 翻转该位,则会使 \(a<b\),然后在后面的位置上通过翻转尽量让 \(a\) 贴近 \(b\)。
- 不翻转该位,则保留 \(a>b\),然后在后面的位置上通过翻转尽量让 \(b\) 贴近 \(a\)。
若 \(r\) 这一位取不到 \(1\),则只考虑上面的第二种情况。最后取其中的最小值作为答案。
void solve()
{
ll a, b, r;
cin >> a >> b >> r;
if (a == b || r == 0)
{
cout << abs(a - b) << endl;
return;
}
if (a <= b)
swap(a, b);
int hdig = -1;
for (int i = 62; i >= 0; --i)
{
if (((a >> i) & 1) != ((b >> i) & 1))
{
hdig = i;
break;
}
}
if (r >> hdig)
{
ll ans = 4e18;
// a > b
ll x = 0;
for (int i = hdig - 1; i >= 0; --i)
if (((a >> i) & 1) == 1 && ((b >> i) & 1) == 0)
if ((x ^ (1ll << i)) <= r)
x ^= 1ll << i;
ans = min(ans, abs((a ^ x) - (b ^ x)));
// a < b
x = 1ll << hdig;
for (int i = hdig - 1; i >= 0; --i)
if (((a >> i) & 1) == 0 && ((b >> i) & 1) == 1)
if ((x ^ (1ll << i)) <= r)
x ^= 1ll << i;
ans = min(ans, abs((a ^ x) - (b ^ x)));
cout << ans << endl;
}
else
{
// a > b
ll x = 0;
for (int i = __lg(r); i >= 0; --i)
if (((a >> i) & 1) == 1 && ((b >> i) & 1) == 0)
if ((x ^ (1ll << i)) <= r)
x ^= 1ll << i;
cout << abs((a ^ x) - (b ^ x)) << endl;
}
}
CF1918D Blocking Elements
这题用到了单调队列优化的 dp 和二分答案。
首先以题目要求的最小花费为 \(mid\) 进行二分。在 \(check\) 函数中,我们优先确保每一段的花费不超过 \(mid\),然后就要考虑如何选择分割点。
在 \(check\) 时直接贪心的选择分割点会 WA,所以我们用 dp 优化选择。定义 \(dp[i]\) 是仅考虑前 \(i\) 个位置,并且以第 \(i\) 个位置作为分割点的分割点花费之和。在求 \(dp\) 值时,先用双指针+前缀和快速确定一个 \(j\) 位置,使得 \(j\) 到 \(i-1\) 这段的花费不大于 \(mid\),即这些位置都是可以向 \(dp[i]\) 转移的位置。然后根据单调队列的性质,队首即是可转移的最小值。最后检查分割点的花费之和是否超过了 \(mid\),即 \(dp[n + 1]\) 是否大于 \(mid\)。
- dp 转移方程:\(dp[i]=\min \limits_{j \le x \le i-1}(dp[x]) + arr[i]\)
void solve()
{
int n;
cin >> n;
vector<ll> arr(n + 2), pre(n + 2);
for (int i = 1; i <= n; ++i)
cin >> arr[i], pre[i] = pre[i - 1] + arr[i];
ll l = 1, r = 1e14, mid, ans = 1;
function<bool(ll x)> check = [&](ll x)->bool
{
vector<ll> dp(n + 2);
deque<ll> dq;
dq.pb(0);
for (int i = 1, j = 0; i <= n + 1; ++i)
{
while (pre[i - 1] - pre[j] > x)
++j;
while (!dq.empty() && dq.front() < j)
dq.pop_front();
if (dq.empty())
return false;
dp[i] = dp[dq.front()] + arr[i];
while(!dq.empty() && dp[dq.back()] >= dp[i])
dq.pop_back();
dq.pb(i);
}
return dp[n + 1] <= x;
};
while (l <= r)
{
mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
cout << ans << endl;
}
标签:arr,int,ll,Codeforces,mid,Div.2,922,dp,dq
From: https://www.cnblogs.com/tllwtg/p/17998815/2024-01-31-CF_922