Codeforces Round 922 (Div. 2）
A - Brick Wall
贪心的去想水平的越多越好，k随意改，那么可以构造出没有垂直的，那么计算水平的有几块就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
void solve()
{
int n, m;
cin >> n >> m;
cout << n * (m / 2) << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
B - Minimize Inversions
任意次数的交换， 交换出现两种情况，i，j 位置在a数组是逆序对，b不是，那么交换完之后，在a数组不是逆序对了，但是b数组会是，因为是排列，不存在元素相等，不影响答案。因为是排列，不存在元素相等。第二种情况即为a中为逆序对，b中也为逆序对，交换完，逆序对减少
所以直接结构体排序即可，就把a升序排，b跟着排就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e6 + 10;
struct node
{
int a, b;
} s1[N];
bool cmp(node a, node b)
{
return a.a < b.a;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> s1[i].a;
for (int i = 1; i <= n; i++)
cin >> s1[i].b;
sort(s1 + 1, s1 + 1 + n, cmp);
for (int i = 1; i <= n; i++)
cout << s1[i].a << " ";
cout << endl;
for (int i = 1; i <= n; i++)
cout << s1[i].b << " ";
cout << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
C - XOR-distance
异或操作，位运算优先考虑拆位!
考虑贪心的做法，就是a和b在同一位置上如果相同，那么x在这一位置上取0/1都不影响的。
那么考虑a和b不同的情况，我们假定a大于b ， 那么想从高位到低位，a和b不同的第一次出现的位置。
分成两种情况1. r<2^i，就是我们改不了这一位，那么非常简单，我们后面能改的地方就都改成和这一位相反即可。
- r>=2^i 就是我们能改,我们不改，但是把后面能改的改成相反的。由于高位能改，自然后面低位都能改。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e6 + 10;
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
void solve()
{
int a, b, r;
cin >> a >> b >> r;
if (a < b)
swap(a, b);
int a1 = a, b1 = b;
int flag = 0;
for (int i = 62; i >= 0; i--)
{
int x = qpow(2LL, i);
// if (i == 2)
// {
// cerr << (((a >> i) & 1) == 1) << " " << (((b >> i) & 1) == 0) << " " << cnt << " " << abs(cnt - 2 * x) << " " << r << " " << cnt << endl;
// cerr << x << endl;
// }
if (((a >> i) & 1LL) == 1 && ((b >> i) & 1LL) == 0 && !flag)
{
flag = 1;
continue;
}
if (((a >> i) & 1LL) == 0 && ((b >> i) & 1LL) == 1 && !flag)
{
flag = -1;
continue;
}
if (((a >> i) & 1LL) == 0 && ((b >> i) & 1LL) == 1 && flag == -1 && r >= x)
{
a1 += x;
b1 -= x;
r -= x;
// if (i == 2)
// cerr << 2 << endl;
}
if (((a >> i) & 1LL) == 1 && ((b >> i) & 1LL) == 0 && flag == 1 && r >= x)
{
a1 -= x;
b1 += x;
r -= x;
// if (i == 2)
// cerr << 2 << endl;
}
// cerr << a1 << " " << b1 << " " << r << " " << flag << " " << i << endl;
}
cout << abs(a1 - b1) << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
D - Blocking Elements
最大值最小，考虑二分答案，check比较难想
贪心不正确，用dp。
dp[i]的含义为，前i位的情况均符合答案，并且i点作为分割点，那么我们创建一个n+1这个点，且这个点a[n+1]=0,用于check dp[n+1]和mid的关系，因为n这个点我们不确定是否作为分割点，而a[n+1]=0,对每一段的值无影响，且可以从前面合法的情况中转移
所以，
dp[i]=min(dp[k]~dp[i-1])+a[i];k为可转移的最左的下标
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e6 + 10;
int n;
int a[N];
int dp[N];
int s[N];
bool check(int mid)
{
int l = 0;
set<pair<int, int>> st;
//用set来维护当前可以转移的最优解，其实是可以用单调队列转移的，但是set能过
for (int i = 0; i <= n + 1; i++)
{
if (st.size() == 0)
dp[i] = a[i], st.insert({dp[i], i});
else
{
while (s[i - 1] - s[l] > mid && l <= i - 1)
{
st.erase({dp[l], l});
l++;
}
int x = (*st.begin()).first;
dp[i] = x + a[i];
st.insert({dp[i], i});
}
// cerr << st.size() << " " << (*st.begin()).first << endl;
}
// cerr << endl;
// for (int i = 1; i <= n + 1; i++)
// {
// cerr << dp[i] << " ";
// }
if (dp[n + 1] > mid)
return false;
else
return true;
}
void solve()
{
cin >> n;
a[n + 1] = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
int l = 1, r = 1e15;
// cerr << check(7) << endl;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
r = mid - 1;
else
l = mid + 1;
}
cout << l << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}