Rank 445/3193. AC 6/13.
A. 清楚姐姐学信息论
题意
给定 \(a\) 进制和 \(b\) 进制，用该进制下的一定数量的号码牌表示数字。输出用哪个进制可以用 \(a \times b\) 张号码牌表示更多的数。
思路
显然，我们只需比较 \(a ^ b\) 和 \(b ^ a\) 的大小，但我们无需模拟计算，因为只有 \(2,3\) 组合的时候，\(2 < 3,2 ^ 3 < 3 ^ 2\)，其余情况均为 \(a < b , a ^ b > b ^ a\)。所以对该情况特判即可。
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt(), b = scanner.nextInt();
if ((a == 2 && b == 3) || (a == 3 && b == 2)) System.out.println(3);
else System.out.println(Math.min(a, b));
}
}淦，还有特判，被坑了
B. 清楚姐姐学构造
题意
给定数组 \(c\) 和质数 \(m\)，构造两个数组 \(a,b\)，满足下面的同余方程组：
\(\left\{\begin{aligned} a_i \equiv a_{N-i-1} \pmod m \\ b_i \equiv -b_{N-i-1} \pmod m \\ c_i \equiv a_i+b_i \pmod m \end{aligned} \right.\)
若可构造，输出 \(YES\) 以及一种构造，否则输出 \(NO\)。
一句话题意
在模系下构造两个数列，一个满足奇函数性质，另一个满足偶函数性质，两个数列的和为任意给定数列。
思路
考虑到对称性，我们不妨设 \(a_i=a_{N-i-1}=x,b_i=m-b_{N-i-1}=y\)。
那么，\(a_i+b_i=x+y,a_{N-i-1}+b_{N-i-1}=x+m-y\)。
代入第三个式子，我们可以得到 \(x+y \equiv c_i \pmod m,x-y \equiv c_{N-i-1} \pmod m\)。
两式相加，\(2x \equiv c_i+c_{N-i-1} \pmod m\)，即 \(x=\frac{c_i+c_{N-i-1}+km}{2},k \in Z\)。
因而，我们只需判断分子的奇偶性，然后即可计算出 \(x\)。
同理可得 \(y\)。
若数组的长度为奇数，那么将会多出来一项 \(N/2\)，观察可得 \(a_i=c_i+km,b_i=0,k \in Z\) 符合题意。
遍历输出即可。
时间复杂度：\(O(\frac{n}{2})\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
#define int long long
int a[N], b[N], c[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i=0;i<n;i++) cin >> c[i];
for(int i=0;i<n/2;i++){
int k1 = c[i] + c[n - i - 1], k2 = c[i] - c[n - i - 1], x, y;
if(k1 % 2 == 0){
if(m == 2) {
x = m + k1;
y = m + k2;
}
else {
x = m * 2L + k1;
y = m * 2L + k2;
}
}else{
if(m == 2){
cout << "NO\n";
return 0;
}else {
x = m + k1;
y = m + k2;
}
}
x /= 2;
y /= 2;
a[i] = a[n - i - 1] = x;
b[i] = y;
b[n - i - 1] = m - y;
}
if(n % 2 == 1) {
a[n / 2] = c[n / 2];
b[n / 2] = 0;
}
cout << "YES\n";
for(int i=0;i<n;i++) cout << a[i] << ' ';
cout << '\n';
for(int i=0;i<n;i++) cout << b[i] << ' ';
}不会有人暴力吧（（
C. 清楚姐姐学01背包(Easy Version)
题意
给定 \(n\) 个物品以及总容量 \(m\)，第 \(i\) 个物品的体积为 \(w_i\)，价值为 \(v_i\)。任选若干个物品放入背包，满足物品总体积小于容量 \(m\)，运用 \(01\) 背包求出最大价值 \(Val_{\max}\)。
现在，枚举每个物品，将该物品去除后，得到最大价值 \(Val'_i\)，若\(Val'_i<Val_{\max}\)，那么该物品必选，输出 \(0\)；否则输出 \(x\)，满足该物品加上价值 \(x\) 后该物品必选。
\(N,M\) 均不超过 \(100\)。
思路
鉴于本题数据量很小，我们可以直接按照题面进行暴力模拟，对每个物品去掉后的情况进行 \(01\) 背包，若非必选，那么再以去掉该物品后的容量为总容量跑一遍 \(01\) 背包，将结果与 \(Val_{\max}\) 做差 \(+1\) 即可得到答案。
时间复杂度：\(O(nnm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110, inf = 0x3f3f3f3f;
#define int long long
int n, m;
int w[N], v[N], dp[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> w[i] >> v[i];
}
for (int i = 1; i <= n; i++)
for (int l = m; l >= w[i]; l--) {
dp[l] = max(dp[l], dp[l - w[i]] + v[i]);
}
int maxx = dp[m];
for(int i=1;i<=n;i++){
memset(dp, 0, sizeof dp);
for (int p = 1; p <= n; p++) {
int cw = p == i ? 0 : w[p], cv = p == i ? 0 : v[p];
for (int l = m; l >= cw; l--) {
dp[l] = max(dp[l], dp[l - cw] + cv);
}
}
if(maxx > dp[m]) cout << 0 << '\n';
else{
memset(dp, 0, sizeof dp);
for (int p = 1; p <= n; p++) {
int cw = p == i ? 0 : w[p], cv = p == i ? 0 : v[p];
for (int l = m - w[i]; l >= cw; l--) {
dp[l] = max(dp[l], dp[l - cw] + cv);
}
}
cout << maxx - dp[m - w[i]] - v[i] + 1 << '\n';
}
}
}令人感慨
D. 清楚姐姐学01背包(Hard Version)
题意
同 \(C\) 题，但 \(N,M\) 不超过 \(5000\)。
思路
暴力解决不了问题了。
我们回到 \(01\) 背包的二维实现：枚举所有物品，以及所有可能的最大容量，取 该状态的价值 和 前一个状态加上当前物品的价值 的最大值。
那么，我们自然可以发现，只要将 \(C\) 题的代码改成二维背包，那么至少最后一个 \(for\) 循环是不必要的，因为对于前 \(i-1\) 个物品，以 \(m-w[i]\) 为最大容量的 \(dp\) 值 我们已经 在前面 以 \(O(n^2)\) 的复杂度 推得了。
那么 \(i\) 后面物品的怎么办？从上面的分析我们可以知道，任意小于 \(m\) 的背包容量对应的答案均可通过 \(O(n^2)\) 的“预处理”得到，那么我们不妨从后往前跑一遍 \(01\) 背包，于是乎，对于第一维为 \(n-i\) 的 \(dp\) 数组，我们只需枚举容量即可。
更具体地
- 从前往后跑一遍 \(01\) 背包，得到二维数组 \(dpz\)；再从后往前跑一遍 \(01\) 背包，得到二维数组 \(dpf\)；
- 枚举每一个物品：维护对于 \(dpz\) 的 \(i\) 前一位的状态下容量的前缀最大值数组 \(mxz\)，对于 \(dpf\) 的 \(i\) 后一位的状态下容量的后缀最大值数组 \(mxf\)。然后，遍历前 \(i-1\) 个的最大容量 \(j\)，剩余的分给去掉前 \(i\) 个物品后剩下物品的最大容量，那么，\(mxz[j]+mxf[m-j]\) 的最大值即为 去掉 \(i\) 后的最大价值 \(Val'_i\)。
- 综合步骤 \(2\) 和暴力做法的最后一个 \(for\) 循环，我们只需将 前 \(i-1\) 个物品，第 \(i\) 个物品，剩下的物品 抽象为三个物品，然后利用 \(01\) 背包的第二层循环计算出必须将 \(i\) 选中的最大值 \(Val'_p\)。
- 输出 \(\max(0,Val'_i-Val'_p+1)\) 即可。
时间复杂度：\(O(nm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
#define int long long
int n, m;
int w[N], v[N], dpz[N][N], dpf[N][N], mxz[N], mxf[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++) {
dpz[i][j] = dpz[i - 1][j];
dpf[i][j] = dpf[i - 1][j];
if (j >= w[i]) dpz[i][j] = max(dpz[i][j], dpz[i - 1][j - w[i]] + v[i]);
if (j >= w[n - i + 1]) dpf[i][j] = max(dpf[i][j], dpf[i - 1][j - w[n - i + 1]] + v[n - i + 1]);
}
for (int i = 1; i <= n; i++) {
memset(mxz, 0, sizeof mxz);
memset(mxf, 0, sizeof mxf);
for (int j = 1; j <= m; j++) {
mxz[j] = max(mxz[j - 1], dpz[i - 1][j]);
mxf[j] = max(mxf[j - 1], dpf[n - i][j]);
}
int vi = 0, vp = 0;
for (int j = 0; j <= m; j++) {
vi = max(vi, mxz[j] + mxf[m - j]);
if (m - j >= w[i])
vp = max(vp, max(mxz[j] + mxf[m - j - w[i]] + v[i],
mxf[j] + mxz[m - j - w[i]] + v[i]));
}
cout << max(0ll, vi - vp + 1) << '\n';
}
}居然有点想出来了，毕竟背包就是贪心嘛
E. 清楚姐姐打怪升级
题意
给定 \(N\) 只怪物，第 \(i\) 只怪物的生命值上限为 \(h_i\)，生命恢复速度为 \(v_i\)。主角的攻击间隔为 \(t\)，攻击力为 \(a\)。
对于每个怪物，每个时刻初，恢复 \(v_i\) 点生命值，直至上限 \(h_i\)。
在 \(1+k \times t\) 时刻末，主角挑选一只怪物，扣除 \(a\) 点生命值，若剩余生命值为非正数，则判定怪物死亡。
输出在哪个时刻末可杀死所有怪物。若永远无法杀死则输出 \(-1\)。
思路
贪心。
我们采取将一只怪物杀死再去杀另一只的做法，使每只需要杀死的怪物能恢复的生命值最小。
显然，在下次攻击前，怪物能恢复 \(v_i \times t\) 点血量，如果恢复的血量大于主角攻击力 \(a\)，那么直接输出 \(-1\)。
否则：
- 如果一击秒杀，时刻 \(+1\)；
- 否则，在每次砍怪物之后，有效扣血为 \(a - v \times t\)，将其与第一次剩余的血量 \(h-a\) 进行除法运算即可。注意需要特判可能出现的一次砍完的情况。
因最后一只怪物的计算会多出一个单位等待时间，所以我们将其减去。
时间复杂度：\(O(n)\)
对应AC代码
import java.math.*;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong(), t = scanner.nextLong(), a = scanner.nextLong();
long tick = 0;
for(int i=0;i<n;i++){
long h = scanner.nextLong(), v = scanner.nextLong();
if(h <= a) {
tick ++;
continue;
}
if(v * t >= a){
System.out.println(-1);
return;
}else {
if ((h - a) % (a - v * t) == 0) tick += ((h - a) / (a - v * t) + 1);
else tick += ((h - a) / (a - v * t) + 2);
}
}
System.out.println((tick - 1) * t + 1);
}
}模拟+贪心呐
F. 清楚姐姐学树状数组
题意
构建一个 \(2^k\) 的树状数组对应的二叉树，二叉树的中序遍历为节点编号，如下图：
给定 \(q\) 个查询，输出询问的节点在前、中、后序遍历中分别是第几个。
思路
\(Dfs\)。
我们从 \(2^k\) 开始向下遍历，根据树状数组的特性，我们可以知道下一个需要遍历的点的值：
若向左，\(nxt=now-\frac{lowbit(now)}{2}\)；若向右，\(nxt=now+\frac{lowbit(now)}{2}\)。
接着，我们先来看前序遍历的规律：对于下一个节点，若向左子树移动，那么前序遍历的值会 \(+1\)，否则会 \(+lowbit(now)\)。
而对于后序遍历，类似于前序：对于下一个节点，若向右子树移动，那么后序遍历的值会 \(-1\)，否则会 \(-lowbit(now)\)。
特别地，在后续遍历中，从 \(2^k\) 移动到 \(2^{k-1}\) 时，后序遍历只相差 \(1\)，特判即可。
注： 当然，我们也可以用递推的方式，初始化数组后按照找对称点的方式解题。
时间复杂度：\(O(q \log_2x)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int ans, maxx, x;
int lb(int x){
return x & (-x);
}
void dfs(int now, bool inc) {
if (now == x) return;
if (now > x) {
if (inc) ans++;
else ans -= (now == maxx ? 1 : lb(now));
dfs(now - lb(now) / 2ll, inc);
} else {
if (inc) ans += lb(now);
else ans--;
dfs(now + lb(now) / 2ll, inc);
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int k, q;
cin >> k >> q;
maxx = (1ll << k);
while(q --){
cin >> x;
ans = 1;
dfs(maxx, true);
cout << ans << ' ' << x << ' ';
ans = maxx;
dfs(maxx, false);
cout << ans << '\n';
}
}你说你这个蠢人怎么连找规律都找不出来呢.jpg
G. 清楚姐姐逛街(Easy Version)
题意
给定一个迷宫，终点按照固定方式移动，以题给字符确定方向。给定多个查询，包括一个起点，输出从起点开始到可变终点的最短路。
思路
考虑到查询数量很少，我们采用暴力的做法：
- 从起点开始 \(Bfs\)，确定能到达的每个点的最短路径长度。
- 模拟终点移动，若遍历到的点存在路径长度小于等于当前终点移动的长度，那么输出答案。
时间复杂度：\(O(nmq)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 810;
#define int long long
char mp[N][N];
int dis[N][N], dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m, xs, ys, Q;
cin >> n >> m >> xs >> ys >> Q;
for(int i=0;i<n;i++) cin >> mp[i];
memset(dis, 0x3f, sizeof dis);
queue<pair<int, int>> q;
q.emplace(xs, ys);
dis[xs][ys] = 0;
while(!q.empty()){
auto t = q.front();
q.pop();
int px = t.first, py = t.second;
for(int i=0;i<4;i++){
int x = px + dx[i], y = py + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m && mp[x][y] != '#' && dis[x][y] > dis[px][py] + 1) {
dis[x][y] = dis[px][py] + 1;
q.emplace(x, y);
}
}
}
while(Q --){
int x, y, ans, step = 1;
cin >> x >> y;
while(true){
char cur = mp[x][y];
if(cur == 'L' && mp[x][y - 1] != '#') y --;
else if(cur == 'R' && mp[x][y + 1] != '#') y ++;
else if(cur == 'U' && mp[x - 1][y] != '#') x --;
else if(cur == 'D' && mp[x + 1][y] != '#') x ++;
else {
if(dis[x][y] == -1) {
ans = -1;
break;
}
}
if(dis[x][y] <= step) {
ans = step;
break;
}
step ++;
}
cout << ans << '\n';
}
}为啥BFS要这么写才对捏
H. 清楚姐姐逛街(Hard Version)
待补充，倍增+二分答案
I. 清楚姐姐采蘑菇
待补充，莫队+单调性
J. 清楚姐姐学排序
题意
给定数组 \(a\) 的 \(M\) 对元素大小关系，求顺序确定的位置和该位置的元素。
即对于位置 \(k\)，若确定位置在第 \(i\) 位，那么 \(b_k=i\)，否则 \(b_k=-1\)。输出顺序数组 \(b\)。
思路
显然，如果对于一个数，有 \(a\) 个数小于它，\(b\) 个数大于它，那么如果满足 \(a+b+1=n\)，该数的位置就一定唯一确定。
因此，我们直接枚举每个点即可。因为可能存在包含关系 \(a<b,b<c,a<c\)，所以我们需要 \(Dfs\)。
时间复杂度：\(O(nm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
#define int long long
vector<int> e[N][2];
int res[N], vis[N];
int dfs(int x, int t){
if(vis[x]) return -1;
vis[x] = true;
int ans = 0;
for(int each : e[x][t]){
ans += dfs(each, t) + 1;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i=0;i<m;i++){
int x, y;
cin >> x >> y;
e[x][0].emplace_back(y);
e[y][1].emplace_back(x);
}
memset(res, -1, sizeof res);
for(int i=1;i<=n;i++){
memset(vis, 0, sizeof vis);
int cntl = dfs(i, 1);
vis[i] = false;
int cntr = dfs(i, 0);
if(cntl + cntr == n - 1) res[cntl + 1] = i;
}
for(int i=1;i<=n;i++) cout << res[i] << ' ';
cout << '\n';
}不该不做这题...
K. 清楚姐姐玩翻翻乐
待补充
L. 清楚姐姐的三角形I
题意
对于 \(\Delta ABC\)，顶点对应的边分别为 \(l_a, l_b, l_c\)。记 \(V_A=l_b+l_c,V_B=l_a+l_c,V_C=l_a+l_b\)，给定 \(V_A,V_B,V_C\)，输出 \(l_a,l_b,l_c\)。无解输出 \(NO\)。
思路
显然，\(l_a=\frac{V_B+V_C-V_A}{2},l_b=\frac{V_A+V_C-V_B}{2},l_c=\frac{V_A+V_B-V_C}{2}\)，那么我们只需判断两边之和大于第三边以及分子是否为偶数即可。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 500010, inf = 0x3f3f3f3f;
#define int long long
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t, va, vb, vc;
cin >> t;
while(t -- > 0){
cin >> va >> vb >> vc;
int la = vb + vc - va, lb = va + vc - vb, lc = va + vb - vc;
if(la % 2 == 1 || lb % 2 == 1 || lc % 2 == 1){
cout << "NO\n";
}else{
la /= 2;
lb /= 2;
lc /= 2;
if(la + lb > lc && la + lc > lb && lb + lc > la){
cout << "YES" << '\n' << la << ' ' << lb << ' ' << lc << '\n';
}else cout << "NO\n";
}
}
}怎么可以暴力呢
M. 清楚姐姐的三角形II
题意
给定数组长度 \(N\)，构造一个数组，满足相邻三个数不能构成三角形。
思路
\(1,1,2,1,1,2,1,1,2,1,...\) 输出即可
时间复杂度：\(O(n/3)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 500010, inf = 0x3f3f3f3f;
#define int long long
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for(int i=0;i<n/3;i++){
cout << "1 1 2 ";
}
if(n % 3 == 1) cout << "1";
if(n % 3 == 2) cout << "1 1";
}差点斐波那契（（