金溪网站建设,做网站跳转,哪个网站可以做视频播放器,网站作用文章目录 CF 1918C XOR-distanceCF 1918D Blocking ElementsCF 1918E ace5 and Task Order CF 1918C XOR-distance
题目链接
这题出思路还挺快的#xff0c;就是考虑二进制每一位的贡献#xff0c;可惜写了个假的贪心
正确贪心是#xff0c;考虑两种情况#xff0c;第一… 文章目录 CF 1918C XOR-distanceCF 1918D Blocking ElementsCF 1918E ace5 and Task Order CF 1918C XOR-distance
题目链接
这题出思路还挺快的就是考虑二进制每一位的贡献可惜写了个假的贪心
正确贪心是考虑两种情况第一种情况是当处理结束时a ^ x比b ^ x大另一种情况是a ^ x比b ^ x小
当结束时前面比后面大遍历每一位中 a是1 b是0 的位置就要尽可能让 a 变成 0 b变成 1这样需要的代价是2的位数的次方可以减少的差值是两倍的次方
当结束时前面比后面小遍历每一位中 a是0 b是1 的位置就要尽可能让 a 变成 1 b变成 0这样需要的代价是2的位数的次方可以减少的差值是两倍的次方
有个需要注意的点是要单独处理一下ab第一个不同的数如果结束a大于b那第一个不同的数一定要是a为1 b为0如果不是就要调整成这样调整不了就不考虑这种情况a小于b也是类似的
下面是我很啰嗦的代码可以把后面类似的两部分写成一个函数
#include bits/stdc.husing namespace std;#define int long longtypedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 1000010;int cf[63];void init()
{cf[0] 1;for (int i 1; i 61; i ) cf[i] 2 * cf[i - 1];
}void solve()
{int a, b, r;cin a b r;if (a b) swap(a, b);int ans a - b;int res ans;vectorint aa, bb;if (a 0) aa.push_back(0);if (b 0) bb.push_back(0);int at a, bt b;while (at){aa.push_back(at 1);at 1;}while (bt){bb.push_back(bt 1);bt 1;}while (bb.size() aa.size()) bb.push_back(0);int i bb.size() - 1;int tmp r;bool flag false;while (i 0){if (!flag aa[i] ! bb[i]){flag true;if (aa[i] 0){if (cf[i] r) break;else{r - cf[i];ans - 2 * cf[i];res min(res, abs(ans));i -- ;continue;}}i -- ;continue;}if (r cf[i] || aa[i] bb[i]){i -- ;continue;}if (!flag aa[i] 0 cf[i] r) break;if (aa[i] 1 bb[i] 0 flag){r - cf[i];ans - cf[i] * 2;res min(abs(ans), res);}i -- ;}r tmp;i bb.size() - 1;ans b - a;flag false;while (i 0){if (!flag aa[i] ! bb[i]){flag true;if (aa[i] 1){if (cf[i] r) break;else{r - cf[i];ans - 2 * cf[i];res min(res, abs(ans));i -- ;continue;}}i -- ;continue; }if (r cf[i] || aa[i] bb[i]){i -- ;continue;}if (!flag aa[i] 0 cf[i] r) break;if (bb[i] 1 aa[i] 0 flag){r - cf[i];ans - cf[i] * 2;res min(abs(ans), res);}i -- ;}cout res \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);init();int t 1;cin t;while (t -- ){solve();}
}CF 1918D Blocking Elements
题目链接
这题只能想到二分了后面的单调队列没用过极大可能是用过没总结就忘记了
二分最终答案然后让区间和都满足条件去判断端点和是否满足条件
dp[i]表示以i为最后一个分割点最小的端点和是多少
j表示以i为最后一个端点它前面能取到的最大的端点序号值
用sum记录当前区间和每当区间和超过mid了就把最前面一个值删掉更新j
然后用单调队列维护以i为最后一个端点能取到的端点中端点和最小的序号所以转移方程为dp[i] dp[q.front()] a[i]
关于单调队列总结在这
#include bits/stdc.husing namespace std;#define int long longtypedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 1000010;void solve()
{int n;cin n;vectorint a(n 2);for (int i 1; i n; i ) cin a[i];auto check [](int mid){vectorint dp(n 2);dequeint q;int sum 0;int j 0;q.push_front(0);for (int i 1; i n 1; i ){while (sum mid) sum - a[ j];while (q.size() q.front() j) q.pop_front();if (!q.size()) return false;dp[i] dp[q.front()] a[i];while (q.size() dp[q.back()] dp[i]) q.pop_back();q.push_back(i);sum a[i];}return dp[n 1] mid;};int l 0, r 1e15;while (l r){int mid l r 1;if (check(mid)) r mid;else l mid 1;}cout r \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t -- ){solve();}
}CF 1918E ace5 and Task Order
题目链接
这题还是挺妙的
目标是给数组排序还有个用于比较的元素 x通过这个想到题目的交互可能是利用快排的思想小于x的丢到左边大于丢到右边然后左右两边再递归排序
数据已经有序的时候快排会退化到 O ( n 2 ) O(n^2) O(n2)所以做之前先打乱顺序
#include bits/stdc.husing namespace std;#define int long longvoid solve()
{mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());int n;cin n;vectorint pos(n); // 存储值i的位置for (int i 0; i n; i ) pos[i] i;shuffle(pos.begin(), pos.end(), rnd);auto ask [](int x){cout ? x 1 endl;char nn;cin nn;return nn;};functionvoid(int, int) qsort [](int l, int r){if (l r) return;int mid pos[l r 1];while (ask(mid) ! ) ;vectorint a, b, c; // for (int i l; i r; i ){if (pos[i] mid) a.push_back(pos[i]);else{char t ask(pos[i]);ask(mid);if (t ) c.push_back(pos[i]);else b.push_back(pos[i]);}}copy(c.begin(), c.end(), pos.begin() l);copy(b.begin(), b.end(), pos.begin() c.size() l 1);pos[l c.size()] mid;qsort(l, l c.size() - 1);qsort(l c.size() 1, r);};qsort(0, n - 1);vectorint ans(n);for (int i 0; i n; i ) ans[pos[i]] i;cout !;for (int i 0; i n; i ) cout ans[i] 1;cout endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t -- ){solve();}
}
