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;
else
a += 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;
}