2022蓝桥杯A组部分个人题解

A - 裁纸刀

没啥好说的 $x\times y - 1 + 4$

B - 灭鼠先锋

直接爆索即可。先后手顺序没明白

#include <iostream>

using namespace std;

//--- 填入初始状况 ---
int board[2][4] = {
    {0, 1, 1, 0},
    {0, 0, 0, 0},
};

bool dfs(int now = 0) {
   bool ff = false;
   for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 4; j++) {
         if (board[i][j] == 0) {
            ff = true;
            board[i][j] = 1;
            int f = dfs(now ^ 1);
            board[i][j] = 0;
            if (!f) return true;
         }
      }
   }

   if (!ff) return true;

   for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 3; j++) {
         if (board[i][j] == 0 && board[i][j + 1] == 0) {
            board[i][j] = board[i][j + 1] = 1;
            int f = dfs(now ^ 1);
            board[i][j] = board[i][j + 1] = 0;
            if (!f) return true;
         }
      }
   }

   return false;
}

int main() {
   cout << !dfs() << '\n';
   return 0;
}

C - 求和

我们发现答案是 $\sum\limits_{i=1}^na_i \times\sum\limits_{j=i+1}^n a_j$ 那么添加一个前缀和即可

#include <iostream>

using namespace std;

long long S[200010];

int main() {
   int n;
   scanf("%d", &n);

   for (int i = 1; i <= n; i++) {
      scanf("%lld", &S[i]);
      S[i] += S[i - 1];
   }

   long long ans = 0;

   for (int i = 1; i <= n; i++) {
      ans += (S[i] - S[i - 1]) * (S[n] - S[i]);
   }

   cout << ans << '\n';

   return 0;
}

D - 选数异或

一个裸的莫队。不过我们需要特判 0 带来的答案。

#include <algorithm>
#include <iostream>

using namespace std;

int cnt[2000010];
int a[100010];
int n, m, x;
int prt;

struct Que {
   int l, r, id;
   bool operator<(const Que& B) const {
      if (l / prt == B.l / prt) return r < B.r;
      return l / prt < B.l / prt;
   };
} q[100010];

bool ans[100010];

void find() {
   int l = 0, r = 1000;
   while (l <= r) {
      int m = (l + r) >> 1;
      if (m * m >= n) {
         prt = m;
         r = m - 1;
      } else {
         l = m + 1;
      }
   }
}

int l = 1, r = 0;

int que = 0;

void add(int i) {
   if (cnt[a[i]]) que += cnt[a[i]];
   int numb = a[i] ^ x;
   cnt[numb]++;
}

void del(int i) {
   if (cnt[a[i]]) {
      if (x == 0)
         que -= cnt[a[i]] - 1;
      else
         que -= cnt[a[i]];
   }
   int numb = a[i] ^ x;
   cnt[numb]--;
}

int main() {
   scanf("%d%d%d", &n, &m, &x);
   // cin >> n >> m >> x;
   find();
   for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
   }
   for (int i = 0; i < m; i++) {
      scanf("%d%d", &q[i].l, &q[i].r);
      q[i].id = i;
   }
   sort(q, q + m);

   for (int i = 0; i < m; i++) {
      int ql = q[i].l;
      int qr = q[i].r;
      while (r < qr) add(++r);
      while (l > ql) add(--l);
      while (r > qr) del(r--);
      while (l < ql) del(l++);
      ans[ q[i].id] = que;
   }

   for (int i = 0; i < m; i++) {
      if (ans[i])
         puts("yes");
      else
         puts("no");
   }
}

还有别的做法,参考。编译时记得加参数 -std=c++17。

如果你写 st 的话可以参考下面的代码~~比线段树简洁一万倍~~。

int val[N]        // --> 表示最小的 R
int fval[N][20]   // --> ST 表。

for (int i = 1 ; i <= n ; i ++) fval[i][0] = val[N];

// 表示 区间 [i , i + 2^j - 1] 区间的最小值。

// func init();
void init() {
   for (int j = 0 ; j < 19 ; j ++) {
      for (int i = 0 ; i <= n ; i ++) {
         fval[i][j + 1] = min(fval[i][j] , fval[i + (1 << j)][j]);
      }
   }
}

// func querry(int l,int r);
int querry(int l,int r) {
   int res = 1e9;
   int now = l;
   for (int i = 19 ; i >= 0 ; i --) {
      int nxt = now + (1 << i);
      if(nxt - 1 <= r) {
         res = min(res , fval[now][i]);
         now = nxt;
      }
   }
   return res;
}

线段树就如下。

#include <iostream>
#include <vector>

using namespace std;

struct SEG_Tree {
   vector<int> mn;
   vector<pair<int, int>> Range;
   SEG_Tree(int n) {
      int sz = 1;
      while (sz < n) sz *= 2;
      sz *= 2;
      mn.assign(sz, n + 1);
      Range.assign(sz, {});
      build(1, n);
   }

   int Lson(int x) { return x * 2 + 1; }
   int Rson(int x) { return x * 2 + 2; }

   void build(int l, int r, int p = 0) {
      Range[p] = {l, r};
      if (l == r) return;
      int m = (l + r) >> 1;
      build(l, m, Lson(p));
      build(m + 1, r, Rson(p));
   }

   void set(int x, int v, int p = 0) {
      auto [l, r] = Range[p];
      if (l == r) {
         mn[p] = v;
         return;
      }
      int m = (l + r) >> 1;
      if (x <= m) set(x, v, Lson(p));
      if (x > m) set(x, v, Rson(p));
      mn[p] = min(mn[Lson(p)], mn[Rson(p)]);
   }

   int querry(int x, int y, int p = 0) {
      auto [l, r] = Range[p];
      if (x <= l && r <= y) {
         return mn[p];
      }
      int res = 1e9;
      int m = (l + r) >> 1;
      if (x <= m) res = min(res, querry(x, y, Lson(p)));
      if (y > m) res = min(res, querry(x, y, Rson(p)));
      return res;
   }
};

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   int n, m, x;
   cin >> n >> m >> x;
   vector<int> a(n + 1);
   for (int i = 1; i <= n; i++) cin >> a[i];

   vector<int> cnt(1 << 20, n + 1);

   SEG_Tree st(n);

   for (int i = n; i >= 1; i--) {
      st.set(i, cnt[a[i] ^ x]);
      cnt[a[i]] = i;
   }

   for (int i = 0; i < m; i++) {
      int l, r;
      cin >> l >> r;
      if (st.querry(l, r) <= r)
         cout << "yes\n";
      else
         cout << "no\n";
   }

   return 0;
}

E - 爬树的甲壳虫

我们只需要计算成功的时间即可。

首先我们有 $\frac{y-x}{y}$ 的概率成功，那么我们可以得到式子 $\frac{y-x}{y}E(i) = E(i - 1) + 1$

那么由此推得式子 $E(i) = \frac{y}{y-x}(E(i - 1) + 1)$

递推求解即可。

#include <iostream>

using namespace std;

const int MOD = 998244353;
long long E[100010];

long long Q_power(long long a, long long b = MOD - 2) {
   long long res = 1;
   while (b) {
      if (b & 1) res = res * a % MOD;
      a = a * a % MOD;
      b >>= 1;
   }
   return res;
}

int main() {
   int n;
   scanf("%d", &n);

   for (int i = 1; i <= n; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      E[i] = (E[i - 1] + 1) * y % MOD * Q_power(y - x) % MOD;
   }

   cout << E[n] << '\n';

   return 0;
}

F - 青蛙过河

这个题目稍微使用了题目上的障眼法。

首先去和回是一样的，也就是说我们可以看成 $2x$ 次从左到右。

再然后，每个石子可以跳跃固定次数，我们不妨看作 $h_i$ 个分开了的石头，然后我们就可以假设有 $2x$ 只青蛙从左往右跳。

那么最后，我们二分答案，然后依照贪心的想法，每次在脚力的范围内尽可能的跳到前面，那么开一个队列维护即可。

#include <cstring>
#include <iostream>
using namespace std;

long long h[100010];
long long now[100010];
int q[100010];

int n, x;
bool check(int k) {
   for (int i = 1; i <= n; i++) now[i] = 0;
   q[0] = 0;
   now[0] = 2 * x;
   for (int head = 0, tail = 0, i = 1; i <= n; i++) {
      if (h[i] == 0) continue;
      if (q[head] < i - k) return false;
      q[++tail] = i;
      while (q[head] < q[tail]) {
         if (now[q[head]] + now[q[tail]] <= h[q[tail]]) {
            now[q[tail]] += now[q[head]];
            head++;
         } else {
            now[q[head]] -= h[q[tail]] - now[q[tail]];
            now[q[tail]] = h[q[tail]];
            break;
         }
      }
   }
   return now[n] >= 2 * x;
}

int main() {
   cin >> n >> x;
   for (int i = 1; i < n; i++) scanf("%lld", &h[i]);
   h[0] = h[n] = 100000000000ll;
   int l = 1, r = n;
   int res = r;

   while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
         r = mid - 1;
         res = mid;
      } else {
         l = mid + 1;
      }
   }

   cout << res << '\n';

   return 0;
}

G - 最长不下降子序列

首先关于最长不降子序列题目中，我们通常做法是开一个栈维护。那么根据这个模式我们就可以得到两个数。

pre[i] 表示以 a[i] 结尾最大不降子序列的长度。

suf[i] 表示以 a[i] 开始最大不降子序列的长度。

那么我们考虑这个题目该怎么做。

首先题目有个基础框架

pre | k | suf

对于 pre 求结尾小于等于 value --- k 的最长不降子序列。对于 suf 求结尾大于等于 value --- k 的最长不降子序列。

那么我们可以贪心的考虑 k 不妨将数列恰好分为下面几段。

[... i] [i + 1 , i + 2 , ... i + k] [i + k + 1... n]

我们直接令结尾为 a[i] 然后往后长度为 k 的序列都为 a[i] ,然后求在 [i + k + 1 ... n] 中开头大于等于 a[i] 的所有不降子序列中的最大长度即可。

由于只是维护区间最大值，用权值线段树 / 树状数组维护即可。

那么最终答案就是 pre[i] + k + max_range_upseq(a[i] ... max_a)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;
int suf[N];
int pre[N];
int a[N];

vector<int> sufstk;
vector<int> prestk;

struct SEG_Tree {
   vector<int> mx;
   vector<pair<int, int>> Range;
   SEG_Tree() {
      int sz = 1;
      while (sz < M) sz *= 2;
      sz *= 2;
      mx.assign(sz, 0);
      Range.assign(sz, make_pair(0, 0));
      build(1, M);
   }

   int Lson(int x) { return x * 2 + 1; }
   int Rson(int x) { return x * 2 + 2; }

   void build(int l, int r, int p = 0) {
      Range[p].first = l, Range[p].second = r;
      if (l == r) return;
      int m = (l + r) / 2;
      build(l, m, Lson(p));
      build(m + 1, r, Rson(p));
   }

   void set(int x, int val, int p = 0) {
      int l = Range[p].first, r = Range[p].second;
      if (l == x && r == x) {
         mx[p] = val;
         return;
      }
      int m = (l + r) >> 1;
      if (m <= l) set(x, val, Lson(p));
      if (m > r) set(x, val, Rson(p));
      mx[p] = max(mx[Lson(p)], mx[Rson(p)]);
   }

   int querry(int x, int p = 0) {
      int l = Range[p].first, r = Range[p].second;
      if (x <= l || (l == r)) {
         return mx[p];
      }
      int m = (l + r) >> 1;
      int res = querry(x, Rson(p));
      if (x <= m) res = max(res, querry(x, Lson(p)));
      return res;
   }
};

int main() {
   int n, k;
   scanf("%d%d", &n, &k);
   for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
   for (int i = 1; i <= n; i++) {
      auto pos = upper_bound(prestk.begin(), prestk.end(), a[i]);
      if (pos == prestk.end()) {
         prestk.push_back(a[i]);
         pre[i] = prestk.size();
      } else {
         *pos = a[i];
         pre[i] = pos - prestk.begin() + 1;
      }
   }

   for (int i = n; i >= 1; i--) {
      auto pos = upper_bound(sufstk.begin(), sufstk.end(), a[i], less<int>());
      if (pos == sufstk.end()) {
         sufstk.push_back(a[i]);
         suf[i] = sufstk.size();
      } else {
         *pos = a[i];
         suf[i] = pos - sufstk.begin() + 1;
      }
   }

   int ans = k;

   SEG_Tree st;

   for (int i = n - k; i >= 0; i--) {
      ans = max(ans, pre[i] + k + st.querry(a[i]));
      st.set(a[i + k], suf[i + k]);
   }

   cout << ans << '\n';

   return 0;
}

H - 扫描游戏

给个思路 ~~ ，实现~~比较容易~~就不写啦。

首先按照极角序排序是免不了的啦。

至于排序呢，我们以下三个级别的关键词。

象限
叉积
z 值

这个比较容易实现。

排完序之后我们就得到了一个数组，a[1 ... n]，这是一个环，所以我们在尾巴上拷贝一份得到 a[1 ... 2n]，每次我们只用长为 n 的部分就好。

然后我们在这个上面开一个线段树，然后我们开一个 std::set, std::set中的排序关键字为 z 值。

那么现在开始我们需要维护两个值，棒子的高度 h，和当前的位置now（为了方便我们可以在 a[0] 处加入一个点 (0 , h) , z = 0）。

这个高度建议大家用平方后的值来表示避免精度损失问题。

那么我们最多进行 n 如下步骤的循环。

将 std::set 中所有小于当前的高度的值加入到线段树中(记得有两份 i 和 i + n)。

while(s.size() && *set.begin().z <= h) {
   auto [pos , z] = *set.begin();
   st.set(pos , pos) , st.set(pos + n , pos + n);
   s.erase(s.begin());
}

找到下一个应该找的值,并将该位置上的值置为 +inf 。如果没找到则结束。

int nxt = st.min(now , now + n);
if(nxt > 2 * n) break;
now = nxt % n;
if(now == 0) now = n;
st.set(now , +INF) , st.set(now + n , +INF);

写到这里，我们发现我们还缺少几个值，

方向 –> 我打算用向量表示 (x , y)
该填的值 –> 这个用 now_value

那么我们在上面的答案加上下面的语句就可以了。

auto [xx , yy] = a[now];
int g = __gcd(abs(x) , abs(y));
xx /= g , yy /= g;
if(xx == x && yy == y) ans[now] = now_value;
else ans[now] = ++now_value;

那么到这也就结束了，我感觉这应该是这张考卷上最难的题了吧。

还剩下了的边界条件，大家请自己探索，例如源点有点，那么我上面提供的的处理方案就不行了，需要特判。

SUCCESS🎉

有什么不懂的欢迎在评论留言奥 🤗

I - 数的拆分

这个数呢我们分为两个部分。

首先是这个数字是 $x^y$ 的形式。

然后是 $x_1^{y_1}\cdot x_2^{y_2}$ 的形式。

我们很容易发现一点 $x_1^2\cdot x_2^2=(x_1x_2)^2$ 那么的话，那么我们第二种形式最容易想到的是 $x_1^2x_2^3$

这个时候我们发现，如果我们要把 $10^{18}$ 拆成两个数字的话。下面的循环一定不会超过 1000。我们此时再做一个质因素分解，那么我们的循环最多不会超过 200 。

for (int i = 1 ; i <= limit ; i ++ ) {
    if(a % prime[i] == 0) break;
}

那么最后我们可以有以下的步骤了。

似乎 1000 还不够，惨失💀 需要 4000 ，以下均修改为 4000

拆出来一个 <= 4000 的素因子。得到 cnt (最多不超过 $256$ 次计算)。
判断是否成幂数。($O(\log \sqrt n)\approx 32$)

给个流程图

由于 1 也是完全幂数。

flowchart LR;
	a[step1] --->|拆出来 cnt >= 2|b[step2] --->|成功| c[输出yes]
	a --->|拆出来 cnt == 1|d[输出no]
	a --->|拆出来 cnt == 0|b

#include <iostream>
#include <vector>
using namespace std;

vector<int> prime;

long long nu[] = {2, 3, 5, 7};
long long rg[] = {1000000000ll, 1000000ll, 3982ll, 373ll};

bool is_prime(int x) {
   for (int i = 2; i * i <= x; i++) {
      if (x % i == 0) return false;
   }
   return true;
}

void init() {
   for (int i = 2; i <= 4000; i++)
      if (is_prime(i)) prime.push_back(i);
}

long long qpow(long long a, long long b) {
   long long res = 1;
   while (b) {
      if (b & 1) {
         res = res * a;
      }
      b >>= 1;
      a = a * a;
   }
   return res;
}

bool check(long long a, int times) {
   long long l = 1, r = rg[times];
   while (l <= r) {
      long long mid = (l + r) >> 1;
      long long val = qpow(mid, nu[times]);
      if (val == a) return true;
      if (val > a) r = mid - 1;
      if (val < a) l = mid + 1;
   }
   return false;
}

void solve() {
   long long a;
   scanf("%lld", &a);

   int cnt = 0;
   for (auto pri : prime) {
      if (a % pri == 0) {
         while (a % pri == 0) {
            a /= pri;
            cnt++;
         }
         break;
      }
   }

   if (cnt == 1) {
      puts("no");
      return;
   }

   for (int i = 0; i < 4; i++)
      if (check(a, i)) {
         puts("yes");
         return;
      }
   puts("no");
}

int main() {
   int t;
   cin >> t;
   init();
   while (t--) solve();
}

J - 推导部分和

简单版的题目可见

详情可见

这个题目如果化为前缀和的形式来看可以变为

S[r] - S[l - 1] = k --> S[r] = S[l - 1] + k

那么有这个关系我们建立图 / 或带权并查集即可。

我的代码是用并查集写的。

我发现我交的是 UNKNOW ,答案是 UNKNOWN. 这赛制。。。

#include <cassert>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int fa[N];
long long vue[N];

int find(int x) {
   if (fa[x] == x) return x;
   int f = fa[x];
   int ff = find(fa[x]);
   vue[x] += vue[f];
   return fa[x] = ff;
}

void merge(int l, int r, long long v) {
   l--;
   if (find(l) == find(r)) return;
   if (find(l) < find(r)) {
      int ff = find(r);
      vue[ff] = v - vue[r];
      fa[ff] = l;
   } else {
      v = -v;
      int ff = find(l);
      vue[ff] = v - vue[l];
      fa[ff] = r;
   }
}

int main() {
   int n, m, q;
   scanf("%d%d%d", &n, &m, &q);
   for (int i = 0; i <= n; i++) fa[i] = i;
   for (int i = 0; i < m; i++) {
      int l, r;
      long long v;
      scanf("%d%d%lld", &l, &r, &v);
      merge(l, r, v);
   }
   while (q--) {
      int l, r;
      scanf("%d%d", &l, &r);
      if (find(l - 1) == find(r)) {
         printf("%lld\n", vue[r] - vue[l - 1]);
      } else
         puts("UNKNOWN");
   }
}

有什么问题欢迎留言 😘

PREVIOUSMadoka And Laziness

NEXT第 2 章关系数据库

misc