【CF】Day115——杂题 (构造 | 区间DP | 思维 + 贪心 | 图论 + 博弈论 | 构造 + 位运算 | 贪心 + 构造 | 计数DP)

B1. Exact Neighbours (Easy)

题目：

思路：

构造

题目意思很简单，就是让你分配位置，使得所有的女巫都能找到一个距离自己 a[i] 的房子

注意到题目数据 a[i] 必定为偶数，因此我们将女巫分在对角线即可，然后根据 a[i] 判断往前还是往后即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
int n;
int a[200005];
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}yes;for (int i = 1; i <= n; i++){cout << i << " " << i << endl;}for (int i = 1; i <= n; i++){int add = a[i] / 2;if(i + add <= n){cout << i + add << " ";}else{cout << i - add << " ";}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--){solve();}return 0;
}

C. Minimizing the Sum

题目：

思路：

区间DP

首先这一题我们看到操作很少，不妨考虑 DP

我们定义 dp[i][j] 表示处理 前 i 个元素用了 j 次操作的得到的最小和

那么如何转移呢？

我们可以想到我们能使用 k 次操作让 k + 1 个连续的数变得一样，所以我们可以靠这个转移

我们提前预处理 p[i][j] 表示 i ~ i+j 用了 j 次操作后的最小和，那么转移就是

具体解释看代码 

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
int a[300005];
//预处理 i ~ i + j 的最小值总和
int p[300005][11];
//前 i 个元素且 用了 j 次操作的最小值
int dp[300005][11];
void solve()
{int n, k;cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];//初始化一次不用，即本身p[i][0] = a[i];}//预处理 i ~ i + j 的最小值for (int i = 1; i <= k; i++){for (int j = 1; j + i <= n; j++){//比较新的值和原来的值，如果值更小就替换p[j][i] = min(p[j][i - 1], a[j + i]);}}//预处理 i ~ i +  j 的区间最小和for (int i = 1; i <= k; i++){for (int j = 1; j + i <= n; j++){p[j][i] *= (i + 1);//最小值乘上次数}}for (int i = 1; i <= n; i++){//一次都不处理，那么直接加dp[i][0] = dp[i - 1][0] + a[i];//枚举处理次数for (int j = 1; j <= k; j++){//选择最优，即用一次然后继承 j - 1 的状态，或者不用，那么就继承 i -1 的状态然后加上当前的值dp[i][j] = min(dp[i - 1][j] + a[i], dp[i][j - 1]);//往前跳几个点for (int h = 0; h < i && h <= j; h++){//往前跳 h 个，则次数要变为 j - h，且是 i - h ~ i 这段区间使用操作dp[i][j] = min(dp[i][j], dp[i - h - 1][j - h] + p[i - h][h]);}}}cout << dp[n][k] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D. Shop Game

题目：

思路：

贪心 + 模拟

显然这一题让我们贪心，但是如何贪呢？

注意到鲍勃一定会拿走 k 个物品，所以爱丽丝只要拿走的物品少于 k 个，那么就一定亏损，所以还不如不拿，因此爱丽丝要不就拿多余 k 个物品，要不就拿 0 个物品，接下来分类讨论

对于鲍勃，他一定会拿走前 k 大个 b，因为这利于爱丽丝，为了让爱丽丝利润少，那么一定会拿走这些，而剩下的绝对会交钱

对于爱丽丝，由于前 k 大个 b 一定会被拿走，那么爱丽丝就要让这些被拿走的 b 对于的 a 尽可能少，这样才能亏得钱少，因此爱丽丝会选择 k 个大 b 且 a 小的商品，然后对于之后的商品如果有利润就选

因此我们可以先将商品按照 b 降序排列，然后模拟即可，具体的，我们用一个优先队列来储存 a，同时预处理选前 k 个商品对应的结果，随后对 k + 1 个商品模拟即可，先加入新的 a，然后把 原来的最大值踢出即可，即枚举一下分界线，左边的是给鲍勃选的，右边是给爱丽丝选的

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
void solve()
{int n, k;cin >> n >> k;vector<pair<int, int>> goods(n);for (int i = 0; i < n; i++){cin >> goods[i].second;}for (int i = 0; i < n; i++){cin >> goods[i].first;}int ans = 0;sort(goods.begin(), goods.end(), greater<>());priority_queue<int> pq;for (int i = 0; i < n; i++){if (i < k){ans -= goods[i].second;pq.push(goods[i].second);}else{if (goods[i].first > goods[i].second)ans += goods[i].first - goods[i].second;}}int tans = ans;for (int i = k; i < n; i++){pq.push(goods[i].second);tans += pq.top();//把原来最叼的提踢了pq.pop();tans -= goods[i].second;//现在这个进去了那就得剪掉if (goods[i].first > goods[i].second)//如果之前还选了他，那么它的奉献也没了{tans -= goods[i].first - goods[i].second;}ans = max(tans, ans);}cout << max(0LL, ans) << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while (t--){solve();}return 0;
}

C2. Game on Tree (Medium)

题目：

思路：

图论 + 博弈论

本题中我们要分析必胜态与必败态，对于所有的叶子节点都是必败态，因为其无法继续行走了，那么对于其余节点，如果其子节点都是必胜态，那么其就是必败态，否则就是必胜态，因为我们能走到一个节点让对手进入必败态，否则无论怎么走对手都是必胜态

然后进行 dfs 即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "Ron\n"
#define no cout << "Hermione\n"void solve()
{int n,t;cin >> n >> t;vector<vector<int>> g(n+1);for (int i = 0; i < n-1; i++){int u,v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}auto dfs = [&](auto && self,int fa,int se)->int{int ans = 1;for(auto & son : g[se]){if(son == fa) continue;ans *= (1 - self(self,se,son));}return ans;};for (int i = 0; i < t; i++){int id;cin >> id;dfs(dfs,id,id) ? no : yes;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--){solve();}return 0;
}

B. Finding OR Sum

题目：

思路：

构造 + 位运算

题目大意就是给我们两次询问的机会，每次我们给出一个 n，然后题目返回 (n | x) + (n | y) 给我们

最后我们会得到一个 m，让我们输出 (m | x) + (m | y) 的结果

显然我们可以分两次得到 x y 的所有位，那么如何选呢？

不难想到可以分奇偶位置选，但是由于是 | 运算，因此我们最后的结果应该要减去 2*n 才是 x 的奇/偶 位的值 + y 奇/偶 位的值

那么现在关键点就在于如何求出 x y 的具体 奇/偶 位了

我们可以想到，既然是 奇/偶 位，那么显然就有一个进位关系，如果奇数位的值是 1，那么显然二者中必定有一个数这一位是 1，如果我们查询的是奇数位但是偶数位也有 1，那么说明二者在上一个位置均是 1，如下图

但是题目不要求我们求出具体的 x y，因此我们这里全分配给 x 即可，最后的结果是等价的 

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"int a = 0, b = 0;void init()
{for (int i = 29; i >= 0; i--){if (i & 1)b += 1LL << i;elsea += 1LL << i;}
}
int reply;
int x = 0, y = 0;
void getw(int f)
{for (int i = f; i < 30; i += 2){if (reply & (1 << i)){x += 1 << i;}if (reply & (1 << i + 1)){x += 1 << i;y += 1 << i;}}
}
int m = 0;
void solve()
{x = 0, y = 0;cout << a << endl;cin >> reply;reply -= 2 * a;getw(1LL);cout << b << endl;cin >> reply;reply -= 2 * b;getw(0LL);cout << "!" << endl;cin >> m;cout << ((m | x) + (m | y)) << endl;
}signed main()
{init();int t = 1;cin >> t;while (t--){solve();}return 0;
}

B. White Magic

题目：

思路：

贪心 + 构造

 简单构造，不难发现只要一个数列不含 0，那么其一定是符合要求的，所以答案的下届就是 n - zero，那么来探究答案上界

我们注意到如果一个数列含有 0，那么显然如果有两个以上的 0 是一定不符合要求的，因为某一时刻必定有 min = 0，mex > 0

但是有一个 0 是可能可以的，因此尝试构造把 0 塞入不含 0 的数列中进行构造，但是 0 可能有多个，难道要全部枚举吗？

显然不用，注意到如果一个 0 位于 i 是可行的，那么其位于 j 也是可行的 (j < i)，同时贪心的想，0越左，那么显然越早满足 min = 0, mex = 0 这个条件，显然也是更优的

因此我们只选最左边的 0 加入数列进行判断，如果可以那么答案就是 n - zero + 1

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
int a[200005];
void solve()
{int n;cin >> n;int zero = 0;for (int i = 0; i < n; i++){cin >> a[i];if(a[i] == 0){zero++;}}if(!zero){cout << n << endl;return;}vector<int> b;int flag = 1;for (int i = 0; i < n; i++){if(a[i] == 0 && flag){flag = 0;b.push_back(0);}else if(a[i] != 0){b.push_back(a[i]);}}flag = 1;int mex = 0;vector<int> MEX(b.size(),0);set<int> st;for (int i = b.size() - 1; i > 0; i--){st.insert(b[i]);while (st.count(mex)){mex++;}MEX[i] = mex;}int mi = b[0];for(int i = 0;i < b.size()-1;i++){mi = min(mi,b[i]);       if(mi < MEX[i+1]){flag = 0;break;}}cout << n - zero + flag << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while (t--){solve();}return 0;
}

F. Fix Flooded Floor

题目：

思路：

计数 DP

显然本题其实可以不用DP，直接观察即可，但是多学总是豪德

我们可以定义 dp[i][j] 为处理到第 i 个位置，且状态为 j 的方案数，j = 0 时为上下都填满，j = 1 时为上填下不填，j = 2 时为上不填下填

那么转移就很简单了，特别注意限制数量，因为本题不需要输出具体方案数

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
int dp[200005][3];
string mp[2];
void solve()
{int n;cin >> n;cin >> mp[0] >> mp[1];mp[0] = ' ' + mp[0];mp[1] = ' ' + mp[1];dp[0][0] = 1;for (int i = 1; i <= n; i++){dp[i][0] = dp[i][1] = dp[i][2] = 0;if (mp[0][i] == '.' && mp[1][i] == '.'){dp[i][0] = dp[i - 1][0];if (i > 1 && mp[0][i - 1] == '.' && mp[1][i - 1] == '.'){dp[i][0] += dp[i - 2][0];}dp[i][1] = dp[i - 1][2];dp[i][2] = dp[i - 1][1];}else if (mp[0][i] == '.' && mp[1][i] == '#'){dp[i][0] = dp[i - 1][2];dp[i][2] = dp[i - 1][0];}else if (mp[0][i] == '#' && mp[1][i] == '.'){dp[i][0] = dp[i - 1][1];dp[i][1] = dp[i - 1][0];}else if (mp[0][i] == '#' && mp[1][i] == '#'){dp[i][0] = dp[i - 1][0];}for (int j = 0; j <= 2; j++){dp[i][j] = min(dp[i][j], 2LL);}}if (dp[n][0] == 0){cout << "None\n";}else if (dp[n][0] == 1){cout << "Unique\n";}else{cout << "Multiple\n";}
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while (t--){solve();}return 0;
}