首页 > 其他分享 >HDU 暑假多校 2023 第三场

HDU 暑假多校 2023 第三场

时间：2023-07-27 12:00:11浏览次数：45  
标签：HDU ch int 多校 le mp include 第三场 size

目录

写在前面

补题地址：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\) 个。综上则有：

\[f_{i, j} = \sum_{k=1}^{j-1} f_{i - 1, k} + f_{i - 1, j}\left[\sum_{k=1}^{j} c_k\ge i\right] \]

维护一个前缀和即可 \(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
*/

写在最后

学到了什么：

  • 考虑简单实现。

标签：HDU,ch,int,多校,le,mp,include,第三场,size
From： https://www.cnblogs.com/luckyblock/p/17584594.html

相关文章

  • 杭电多校2023 第三场
    1005直接dp即可#include<bits/stdc++.h>usingnamespacestd;intdp[5005][5005];intN;inta[5005];constintMOD=1e9+7;intmain(){intT;cin>>T;while(T--){intN;memset(dp,0,sizeof(dp));dp[1][1]=......
  • 2023牛客多校7.24补题
    J-FineLogic题意：给定n个点和m对偏序关系(x,y)，构造最少的排列数目k，使得在这k个排列中至少有一个排列满足x出现在y的前面。分析：很考验思维的一道题，首先如果m对偏序关系不构成环，也就是一张有向无环图，于是用拓扑排序构造出一个合理排列即可。要是有环，就直接构造两个排列，一个是1<2<.......
  • HDU4738 Caocao's Bridges
    \(HDU4738\)\(Caocao\)'\(s\)\(Bridges\)一、题目描述曹操在长江上建立了一些点，点之间有一些边连着。如果这些点构成的无向图变成了连通图，那么曹操就无敌了。刘备为了防止曹操变得无敌，就打算去摧毁连接曹操的点的桥。但是诸葛亮把所有炸弹都带走了，只留下一枚给刘备。所以刘......
  • 暑假牛客多校第三场 2023-7-24
    未补完A.WorldFragmentsI算法：构造做法：从x中某一个数位选一个数，这个数有可能是0或者是1。求x变到y的最小数，这个数有可能是负数，要取绝对值。注意如果x是0，那么从x中取的数就只有0了，除非y也等于0，否则输出-1。code#include<iostream>#include<cstring>#include<algori......
  • 牛客暑假多校 2023 第三场
    写在前面比赛地址：https://ac.nowcoder.com/acm/contest/57357。发生了这种事……气槽她气得吐槽了啊！以下按个人向难度排序。A签到。除非\(x=0\)否则可以调整为任意数，步数即两数之差。///*By:Luckyblock*/#include<cmath>#include<cstdio>#include<cctype>#incl......
  • 牛客多校2023 第三场
    A签到，注意$0$的特判#include<bits/stdc++.h>usingnamespacestd;longlongx,y;intmain(){strings1,s2;cin>>s1;cin>>s2;intLen1=s1.length();intLen2=s2.length();for(inti=0;i<Len1;i++)......
  • 牛客多校 Day3
    H哥德巴赫J诈骗A签到D要么全\(0\)，要么全\(1\)B不得不说我真的纯纯SB真的。考场做法是先转成概率，然后就是计算长度大于等于\(i\)概率之和。\(f(i,j,0/1)\)前\(i+j\)个位置填\(i\)个小于等于\(n\)的数，\(j\)个大于\(n\)的数，最后一段是上升/下降的......
  • 牛客多校第二场-H
    H-0and1inBIT op1-->-x-1op2-->x+1由线性代数知识推每次操作要乘的矩阵，线段树维护一个矩阵信息 [op,d,1]就是代表一个f(x)=kx+b的方程，根据线性代数知识用矩阵表示该方程->f(x)=op*x+d,最后一个1只是凑矩阵用的，f代表该矩阵，因为刚开始就是x，所以op=1，d=0 #inclu......
  • 牛客多校1
    A.AlmostCorrect题意:给出一个长度为\(n\)的\(01\)串\(s\)，他一定是没有被排序的，构造不超过\(120\)对的操作序列，使得他不能对\(s\)排序，但可以对长度为\(n\)的其他\(01\)序列排序。思路：设\(s\)中最左边的位置为\(p\)，首先先让所有不在\(p\)位置的\(1\)与\(p\)操作，这样对原串没......
  • 牛客多校第二场补题
    牛客多校2I.LinkwithGomoku题意：两个人下五子棋，给出棋盘大小，构造一种方案，使得平局。思路：考虑这样构造xxxxooxxxxxxxxooooox以五一个为一个循环，多出来的部分也以这种方式构造，唯一的问题就是当有奇数行时会导致先手的棋子太多，因此当n为奇数时，让最后一行这样填充xoxoxox.......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99