HDU 暑假多校 2023 第三场

写在前面

补题地址：https://acm.hdu.edu.cn/listproblem.php?vol=64，题号 7300~7311。

坐牢场。

老东西怎么还在圈里混啊（恼

以下按个人向难度排序，标题为题库中题号。

7310

模拟这个过程。缩放至 \(Z\%\) 即将原来的某个像素覆盖的范围 \((x-1, y-1)\rightarrow (x, y)\) 变为 \(((x - 1)\times Z\%, (y - 1)\times Z\%)\rightarrow (x\times Z\%, y\times Z\%)\)。

出题人良心地让 \(Z\) 为 25 的倍数，于是先把所有坐标扩大 4 倍，再按照上述规则模拟即可，这样所有像素覆盖的范围都成了整数。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//=============================================================
int n, z, n1;
char s[60][60];
char temp[510][510];
char ans[120][120];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Init() {
  n = read(), z = read();
  for (int i = 1; i <= n; ++ i) scanf("%s", s[i] + 1);
}
bool Judge1() {
  if (n * z % 100) return false;
  return true;
}
bool Solve() {
  n1 = n * z / 100;
  int k = 4 * z / 100;

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= n; ++ j) {
      for (int x = (i - 1) * k + 1; x <= i * k; ++ x) {
        for (int y = (j - 1) * k + 1; y <= j * k; ++ y) {
          temp[x][y] = s[i][j];
        }
      }
    }
  }

  int flag = 1;
  for (int i = 1; i <= n1; ++ i) {
    for (int j = 1; j <= n1; ++ j) {
      ans[i][j] = 0;
      for (int x = (i - 1) * 4 + 1; x <= i * 4; ++ x) {
        for (int y = (j - 1) * 4 + 1; y <= j * 4; ++ y) {
          if (ans[i][j] == 0) ans[i][j] = temp[x][y];
          else if (ans[i][j] != temp[x][y]) flag = 0;
          if (!flag) break;
        }
        if (!flag) break;
      }
      if (!flag) break;
    }
    if (!flag) break;
  }
  return flag;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    if (!Judge1()) {
      printf("error\n");
      continue;
    }
    if (!Solve()) {
      printf("error\n");
      continue;
    }

    for (int i = 1; i <= n1; ++ i) {
      for (int j = 1; j <= n1; ++ j) {
        printf("%c", ans[i][j]);
      }
      printf("\n");
    }
  }
  return 0;
}

7304

对于某个长度为 \(n\) 的数列 \(x\) 定义一种运算，运算的结果是一个长度为 \(n\) 的数列 \(b\)，且有：

\[b_{i} = \max_{i = 1}^{i} x_i \]

\(T\) 组数据，每组数据给定一长度为 \(n\) 的数列 \(x\)，现从数列中选择任意个元素并任意排列后进行运算，求所有情况中可以得到的 \(b\) 的种类数，答案对 \(10^9+7\) 取模。
\(1\le T\le 100\)，\(1\le n\le 3000\)，\(1\le x_i\le 10^9\)，\(\sum n\le 3\times 10^4\)。
2S，512MB。

仅关注权值的相对大小，先离散化，对于每种权值记录出现次数 \(c\)。

发现往某个序列后面插入数时，插入的数的变化仅需考虑与结尾的数的相对大小。于是考虑 DP，设 \(f_{i, j}\) 表示长度为 \(i\) 的，结尾为权值 \(j\) 的运算结果数列 \(b\) 的种类数。

初始化 \(f_{1, j} = 1\)，转移时考虑插入的数和结尾数的关系。若大于上一个数，则需要从结尾小于 \(j\) 的状态转移而来；若小于等于上一个数则插入后结尾不变，则需要保证小于等于 \(j\) 的数至少有 \(i\) 个。综上则有：

维护一个前缀和即可 \(O(n)\) 转移。总时空复杂度均为 \(O(n^2)\) 级别。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const LL p = 1e9 + 7;
const int kN = 3e3 + 10;
//=============================================================
int n, a[kN], datanum, cnt[kN];
LL f[kN][kN], g[kN][kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Init() {
  n = read();
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    cnt[i] = 0;
  }

  datanum = 0;
  std::sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++ i) {
    if (a[i] != a[i - 1]) a[++ datanum] = a[i];
    ++ cnt[datanum];
  }
  for (int i = 1; i <= datanum; ++ i) cnt[i] += cnt[i - 1];
}
void DP() {
  for (int i = 1; i <= datanum; ++ i) {
    f[1][i] = 1;
    g[1][i] = i;
  }
  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= datanum; ++ j) {
      f[i][j] = g[i - 1][j - 1];
      if (cnt[j] >= i) f[i][j] += f[i - 1][j];
      g[i][j] = g[i][j - 1] + f[i][j];
      
      f[i][j] %= p, g[i][j] %= p;
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    DP();
    for (int i = 1; i <= n; ++ i) {
      printf("%lld\n", g[i][datanum]);
    }
  }
  return 0;
}

7311

\(T\) 组数据，每组数据给定 \(n\) 个有序数对 \((a_i, b_i)\) 和 \(q\) 次询问。每次询问中给定有序数对 \((A, B)\)，可以对 \((A, B)\) 进行若干次如下操作：

1. \((A, B)\rightarrow (A+B, B)\)。
2. \((A, B)\rightarrow (A, A+B)\)。

求进行若干次操作后，给定的有序数对中有多少个可以与之相同。
\(1\le T\le 100\)，\(1\le n, q\le 5\times 10^4\)，\(1\le a_i, b_i, A, B\le 10^{18}\)，\(\sum n, \sum q\le 5\times 10^5\)。
10S，512MB。

哈，10S，要升天了。

一直想着正着做就输了。

考虑给定的某个有序数对可以由哪些数对转化而来。对于 \((a_i, b_i)\)，若 \(a_i > b_i\)，则它一定是由 \((a_i - b_i, b_i)\) 进行操作 1 转化而来；同理若 \(a_i < b_i\)，则它一定是由 \((a_i, b_i - a_i)\) 进行操作 2 转化而来；若 \(a_i = b_i\)，保证了 \(1\le a_i, b_i, A, B\le 10^{18}\)，则到达了一个不能被其他数对转化而来的的状态，我们称之为起点状态。发现上述过程和辗转相减非常类似，则起点状态一定为 \(\left(\gcd(a_i, b_i), \gcd(a_i, b_i)\right)\)。

发现从起点状态出发转化到某个数对的操作序列是唯一的。

赛时 YY 的写法是把每个状态看做结点，向上一个状态连边，发现构成了一片以起点状态为根的森林。查询时仅需找到 \((A, B)\) 对应的状态并查询其子树中的叶节点个数即可，可以建树后 DP 得到。

但是直接辗转相减建树会出现很多长链，节点个数会很恐怖。于是考虑把长链压缩，把辗转相减变为辗转相除，如令状态 \((a_i, b_i)\) 直接连向 \((a_i \bmod b_i, b_i)\)。但这样压缩会丢失相交的链的信息，如 \((15, 3)\) 和 \((12, 3)\) 都会直接连向 \((3, 3)\)，而压缩前 \((15, 3)\) 会连向 \((12, 3)\)。于是另外在每个节点上维护通过某种操作（对 \(a_i\) 还是对 \(b_i\) 操作）连向该节点的状态的集合，查询时先对 \((A, B)\) 进行一次辗转相除来找到对应结点，然后在这个集合中二分找到比查询状态大的对应的子树的叶节点个数即可。

由于辗转相除只会进行 \(\log v\) 次，总时间复杂是常数飞天的 \(O((n + q)\log (n + q)\log v)\) 级别，跑了 9S 呃呃呃呃。

题解的做法是考虑把操作序列看成一个字符串，如：\((3, 3)\rightarrow (6, 3)\rightarrow (9, 3) \rightarrow (9, 12)\) 可以看做 \(001\)。

基于上述结论考虑某个有序数对 \((a_i, b_i)\) 可以被一次询问 \((A, B)\) 转化而来的条件：

• 起点状态相同，即 \(\gcd(a_i, b_i) = \gcd(A, B)\)。
• \((A, B)\) 的操作序列是 \((a_i, b_i)\) 的操作序列的前缀。

于是可以把所有操作序列按照 \(\gcd(a_i, b_i)\) 分类并按照字典序排序。查询时构造出 \((A, B)\) 对应的操作序列 \(S\)，在 \(\gcd(A, B)\) 对应的类中二分查找字典序大于等于 \(S\) 的，且小于 \(S + 111\cdots 1111\) 的数目即为答案。

此时复杂度瓶颈出现在比较字典序大小上。注意到可以把一段相同的字符串压缩起来，即由辗转相减变为辗转相除，这样字符串最多有 \(\log v\) 段，暴力比较两个字符串的时间复杂度变为 \(O(\log v)\) 级别，总时间复杂度为 \(O((n + q)\log (n + q)\log v)\) 级别。

但是和上面自己 YY 的相比常数小很多，平均只需要 3S。

想用题解做法再实现一遍但是调不出来，咕了，妈的。

//
/*
By:Luckyblock
*/
#include <map>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kNode = 3e6;
//=============================================================
int n, q;
int nodenum, fa[kNode], sz[kNode], sz1[kNode];
int edgenum, head[kNode], v[kNode], ne[kNode];
pr <LL, LL> node[kNode];
std::map <pr <LL, LL>, int> NODEID;
std::vector <pr <pr <LL, LL>, int> > havex[kNode], havey[kNode];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(LL a_, LL b_) {
  LL x = a_, y = b_;
  if (x == 0 || y == 0) {
    if (!NODEID.count(mp(x, y))) NODEID[mp(x, y)] = ++ nodenum;
    int nowid = NODEID[mp(x, y)];
    sz[nowid] ++;
    sz1[nowid] ++;
    return ;
  }
  int last = -1;

  while (x && y) {
    LL nextx = x, nexty = y;
    pr <LL, LL> now, idx, idy;
    if (x < y) {
      nexty = y % x ? y % x : x;
      now = mp(x, y), idx = mp(x, nexty);
    } else {
      nextx = x % y ? x % y : y;
    }

    int nowid = 0;
    if (!NODEID.count(mp(x, y))) {
      NODEID[mp(x, y)] = nowid = ++ nodenum;
      node[nowid] = mp(x, y);
      if (last != -1) fa[last] = nowid;
    } else {
      if (last != -1) fa[last] = NODEID[mp(x, y)];
      break;
    }

    if (x == y) break;
    last = nowid;
    x = nextx, y = nexty;
  }
  int nowid = NODEID[mp(a_, b_)];
  sz[nowid] ++;
  sz1[nowid] ++;
}
void AddEdge(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Dfs(int u_) {
  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    Dfs(v_);
    sz[u_] += sz[v_];
    havex[u_].push_back(mp(mp(node[u_].first, node[u_].second), sz1[u_]));
    havey[u_].push_back(mp(mp(node[u_].first, node[u_].second), sz1[u_]));
    if (node[v_].first > node[v_].second) {
      havex[u_].push_back(mp(mp(node[v_].first, node[v_].second), sz[v_]));
    } else if (node[v_].first < node[v_].second) {
      havey[u_].push_back(mp(mp(node[v_].first, node[v_].second), sz[v_]));
    }
  }
}
void Init() {
  NODEID.clear();
  // havex.clear(), havey.clear();
  for (int i = 1; i <= nodenum; ++ i) {
    fa[i] = sz[i] = sz1[i] = 0;
    havex[i].clear(), havey[i].clear();
    head[i] = 0;
  }
  nodenum = 0;
  edgenum = 0;

  n = read(), q = read();
  for (int i = 1; i <= n; ++ i) {
    LL a, b; scanf("%lld%lld", &a, &b);
    Add(a, b);
  }
  for (int i = 1; i <= nodenum; ++ i) {
    if (fa[i]) AddEdge(fa[i], i);
  }
  for (int i = 1; i <= nodenum; ++ i) {
    if (!fa[i]) Dfs(i);
  }
  for (int i = 1; i <= nodenum; ++ i) {
    std::sort(havex[i].begin(), havex[i].end());
    for (int j = 1, size = havex[i].size(); j < size; ++ j) {
      havex[i][j].second += havex[i][j - 1].second;
    }
    std::sort(havey[i].begin(), havey[i].end());
    for (int j = 1, size = havey[i].size(); j < size; ++ j) {
      havey[i][j].second += havey[i][j - 1].second;
    }
  }
}
void Query() {
  while (q --) {
    LL A, B, A1, B1, flag = 0; scanf("%lld%lld", &A, &B);
    if (A == 0) A += B;
    if (B == 0) B += A;
    
    if (A > B) A1 = A % B ? A % B : B, B1 = B, flag = 1;
    else if (A < B) A1 = A, B1 = B % A ? B % A : A, flag = -1;
    else A1 = A, B1 = B;

    // printf("----");
    if (NODEID.count(mp(A1, B1))) {
      int id = NODEID[mp(A1, B1)];
      
      if (flag == 1) {
        int size = havex[id].size(), ans = size;
        if (!size) {
          printf("0\n");
          continue;
        }
        for (int l = 0, r = size - 1; l <= r;) {
          int mid = (l + r) >> 1;
          if (mp(A, B) > havex[id][mid].first) {
            l = mid + 1;
          } else {
            ans = mid;
            r = mid - 1;
          }
        }
        if (ans == 0) printf("%d\n", havex[id][size - 1].second);
        else printf("%d\n", havex[id][size - 1].second - havex[id][ans - 1].second);
      } else if (flag == -1) {
        int size = havey[id].size(), ans = size;
        if (!size) {
          printf("0\n");
          continue;
        }
        for (int l = 0, r = size - 1; l <= r;) {
          int mid = (l + r) >> 1;
          pr <LL, LL> admire_vega = havey[id][mid].first;
          if (mp(A, B) > havey[id][mid].first) {
            l = mid + 1;
          } else {
            ans = mid;
            r = mid - 1;
          }
        }
        if (ans == 0) printf("%d\n", havey[id][size - 1].second);
        else printf("%d\n", havey[id][size - 1].second - havey[id][ans - 1].second);
      } else {
        printf("%d\n", sz[id]);
      }
    } else {
      printf("0\n");
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    Query();
  }
  return 0;
}
/*
1
3 4
6 9
5 3
1 1

6 3
1 2
2 1
5 3


1
2 2
7 14
7 14

7 7
7 14




1
5 5
3 3
6 3
9 3
12 3
6 15

3 3
6 3
9 3
12 3
6 9






1
4 1
3 3
6 3
9 3
15 3

9 3
*/

写在最后

学到了什么：

• 考虑简单实现。

本栏目推荐文章
• 2023年度总结
• CSP-J/S 2023 游记
• Libevent [补档-2023-08-29]
• 本地套接字 [补档-2023-07-24]
• UDP通信 [补档-2023-07-22]
• 多路io复用Select [补档-2023-07-16]
• 多路io复用pool [补档-2023-07-19]
• 多路io复用epoll [补档-2023-07-20]
• socket编程 [补档-2023-07-10]
• OFBiz RCE漏洞复现（CVE-2023-51467）

2023 HDU2023 hdu 题解round 2023 hdu 笔记2023 hdu 7287 2023 hdu hdu hdu-acm 馅饼hdu 老鼠hdu 寝室hdu 3681 hdu