NOI2021 加油！

RainAir's Blog

「BZOJ3489」A simple rmq problem

题目链接题意输入一个长度为 $n$ 的序列 接着处理 $m$ 次在线询问。每组询问给出 $l,r$ ，要求你找出 $[l,r]$ 中只出现过一次的数的最大值，如果没有输出 $0$。$n \leq 10^5,m \leq 2 \times 10^5$题解套路般地处理出 $pre_i$ 和 $suf_i$ 表示上一个和下一个和它值相同的位置。一次询问相当于是询问 $i \in [l,r],pre...

  • RainAir
  • April 22, 2020
  • No comments

    • 「CodeChef」Game Of Numbers

    题意题目链接给定一个长度为 $n$ 的 $A$ 数组和 $B$ 数组，你有两个集合 $S_1,S_2$ 初始时为空。每次你的操作是选择两对 $(i,j),(p,q)$ 满足 $(i,j) \notin S_1,(p,q) \notin S_2,A_i<B_j,B_p<A_q,\gcd(A_i,B_j) \neq 1,\gcd(A_q,B_p) \neq 1,\gcd(A_q,B_...

  • RainAir
  • April 20, 2020
  • No comments

    • 「CF600F」Edge coloring of bipartite graph

    题意给你一个左边 $a$ 个点 右边 $b$ 个点 有 $m$ 条边的二分图。现在要求你给每一个边染色 使得每个点的所有边的颜色互不相同。要求使用的颜色最少 输出一种方案。$a,b \leq 1000,m \leq 10^5$题解猜结论好题很容易可以发现度数最大值是答案的一个下界。但其实它也是答案的上界。接下来我们将会基于一组构造来证明它（这组构造就是要求你输出的方案）我们依次考虑每一条边，...

  • RainAir
  • April 20, 2020
  • No comments

    • 「ARC080F」Prime Flip

    题目大意你现在有一个无限长的数组 每个数组的取值为 0 或 1。初始有 $n$ 个地方的位置是 $1$ 。你每次可以将长度为奇数的连续段翻转 求至少翻转几次可以全部变成 0。$n \leq 100,x \leq 10^7$题解Atcoder 的题还是好啊。。就是我都不会首先我们看到区间操作+大值域 第一时间应该想到的是将其差分后转化成单调操作。转化后原本对 $[l,r]$ 的操作现在就变成了...

  • RainAir
  • April 20, 2020
  • No comments

    • 「CF103E」Buying Sets

    题目链接题目大意有一个大小为 $n$ 的全集，每个元素是一个数，有$n$个子集，题目保证任意$k$个子集的并的大小$\geq k$。你需要选出一些子集使得这些子集的并大小等于子集个数，且其并中元素和最小，可以为空集。$n \leq 300$题解这个题有两种做法。做法 1如果不考虑限制条件 权值取反之后就是一个最大权闭合子图模型（选了集合就要选对应的元素）考虑条件 “任意$k$个子集的并的大小...

  • RainAir
  • April 18, 2020
  • No comments