2022杭电多校（八）

2022杭电多校（八）

一、比赛小结

比赛链接：Problems (hdu.edu.cn)

这场签到题挺多

二、题目分析及解法（基础题） 1001、Theramore

题目链接：Problem - 7220 (hdu.edu.cn)

题意：

一个 01 序列，可以任意翻转奇数长度的区间，求能达到的最小字典序。

题解：

考虑操作不变性，位置的奇偶性不变，按奇偶分类即可

代码：

// 1001, std
#include 
using namespace std;
const int MAXN = 100005;

char s[MAXN];
int n, cnt[2][2];

void solve() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  cnt[0][0] = cnt[0][1] = cnt[1][0] = cnt[1][1] = 0;
  for (int i = 1; i  T; T--;) {
    scanf("%d", &n);
    printf("%d\n", n * 2);
  }
}

1005、Ironforge

题目链接：Problem - 7224 (hdu.edu.cn)

题意：

一条链，每个点上有一个数 a a a ，每条边上有一个质数 b i b_i bi​ 。一开始在某个点上，有一个空背包，走到一个点上可以把它的质因子放进背包，一条边如果背包里有那个质数就可以走。多组询问求从 x 出发能否走到 y（即求每个点能走到的最大范围）。

题解：

求出从每个点出发能到达的最大的范围，即可 O ( 1 ) O(1) O(1) 回答所有询问。

先从大到小枚举，预处理每个点只向右走的最大范围，如果能向右走一步就先取 i+1 的范围，然后沿着之前预处理的范围向后跳。向后跳的次数是均摊 O ( 1 ) O(1) O(1) 的。

然后从小到大枚举，求每个点能走到的最大范围。

如果 i i i 能走到 i + 1 i+1 i+1 ：如果 i + 1 i+1 i+1 已经预处理的向右的范围无法让它走回 i i i 则取预处理的答案；否则 i + 1 i+1 i+1 和 i i i 范围相同。

如果 i i i 不能走到 i + 1 i+1 i+1 ：先取预处理的范围，然后向左向右扩展，都沿着已知的范围暴力跳即可。向左向右跳的次数都是均摊 O ( 1 ) O(1) O(1) 的。

判断一个范围内是否存在某个质因子，方法有很多，标程采用的是对每个质因子维护一个 vector 存它出现的所有位置，在 vector 上二分。

时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn) 。

代码：

// 1005, std
#include 
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
using namespace std;
typedef long long LL;
const int MAXN = 200005;

template 
inline void read(T &WOW) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  WOW = flag * x;
}

int n, m, a[MAXN], b[MAXN], clean[MAXN], tim;
int L[MAXN], R[MAXN];

int pr[MAXN], pcnt, vis[MAXN], low[MAXN];
vector pos[MAXN];

bool Check(int p, int l, int r) {
  if (!pos[p].size() || pos[p].back()