【解题报告】2021牛客寒假算法基础集训营4

【解题报告】2021牛客寒假算法基础集训营4

前面的话

  • 比赛连接：2021牛客寒假算法基础集训营4
  • 有些题目是自己思考做出来的，有些是看他人的思路自己做的，也有的是参考别人的代码然后写的。
    我决定这里以及以后都会写出来，标记在思路右边。
    不同解法的时间复杂度也不同，会标记在代码内。
    如果是简单题或者复杂度(做出来的或者没做出来的)，我可能都会带一些补充，放在每题的后面。

A ：九峰与签到题 | 模拟 (签到题)

  • 【题意】
    求出任何时刻，通过率都 的题目。
  • 【细节】
    判断通过率 不建议这么写：
    而是建议这么写：

B： 武辰延的字符串 | exKMP

  • 【题意】
    给你两个字符串
    设 表示字符串 的长度为 的前缀。
    设 表示 和 的直接拼接。
    问你有多少对不同的 ，满足

  • 【范围】

  • 【思路】赛内
    首先如果能满足要求，一定要
    接下来就是对于每一个位置 ， 与 的最长公共前缀是多少。
    暴力计算肯定会超时的，不过我们有 ，可以快速计算。

  • 【代码】
    时间复杂度：

    /* 求解 T 中 next[]，注释参考 GetExtend() */
void GetNext(string & T, int & m, int next[])
{
  int a = 0, p = 0;
  next[0] = m;

  for (int i = 1; i < m; i++){
      if (i >= p || i + next[i - a] >= p){
          if (i >= p)
              p = i;
          while (p < m && T[p] == T[p - i])
              p++;
          next[i] = p - i;
          a = i;
      }
      else
          next[i] = next[i - a];
  }
}
/* 求解 extend[] */
void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
{
  int a = 0, p = 0;
  GetNext(T, m, next);

  for (int i = 0; i < n; i++){
      if (i >= p || i + next[i - a] >= p){
          if (i >= p)
              p = i;
          while (p < n && p - i < m && S[p] == T[p - i])
              p++;
          extend[i] = p - i;
          a = i;
      }
      else
          extend[i] = next[i - a];
  }
}
int nxt[100050];
int extend[100050];
int main()
{
  string S, T;
  int n, m;

  cin >> T >> S;
  n = S.size();
  m = T.size();
  GetExtend(S, n, T, m, extend, nxt);

  long long res = 0;
  for (int i = 0; i < n; i++){
      if(S[i] == T[i])res += (long long)extend[i+1];
      else break;
  }
  cout << res;
  return 0;
}

  • 【补充】
    其实这题推荐解应该是二分查找+字符串哈希，不过 应该是时间最优解了。
    不过后面有字符串哈希的题...

D ：温澈滢的狗狗 | 二分

  • 【题意】
    从左到右有 个点，每个点有颜色
    如果 ，那么点对 之间有亲密度
    我们把所有有亲密度的点对取出来，优先级按照 **亲密度从高到低， 从高到低， 从高到低** 排序。
    问你亲密度排序后第 对点对是哪两个点，或者告诉她不存在亲密度第 的点对。
  • 【范围】

  • 【思路：第一步】参考题解
    因为亲密度排序的最高优先级是亲密度大小，容易想到我们可能可以二分 找出亲密度 的异色点对个数，然后确定最终第 对点对的亲密度的值是多少。
    假设我们知道了最终亲密度为 ，且亲密度 的点对数量 ，我们只要 ，从左到右扫一遍距离为 的点对，如果颜色不同那么 自增 ，直到 即可。
    那么我们想知道怎么去**二分找亲密度 的异色点对的个数**。
  • 【思路：第二步】
    首先，直接求很难求，我们根据容斥得到：**异色点对的个数 所有点对个数 同色点对个数**。
    有 个数，距离 的所有点对个数是多少呢？假设距离为 ，我们得到这个式子：有 个数，距离 的同色个数是多少呢？
    我们肯定枚举每一种颜色 ，然后用 滑动窗口 去计算 距离 的点对个数。
    我们会事先把颜色为 的点按照下标升序丢到 中预处理。
    假设窗口左端、右端下标分别为 ，我们新加进来下标为 的同色点。
    如果新的窗口长度 ，那么新的点产生的点对个数为 。
    如果新的窗口长度 ，那么我们把窗口向右移动，直到距离合法，返回上一步。
  • 【代码】
    时间复杂度：
    const int MAX = 2e5+50;
int n;
ll k;
vector<int>V[MAX];
ll solve(int x,int d){
  int st = 0;
  ll res = 0;
  for(int ed = 1;ed < V[x].size();++st){
      while(ed < V[x].size() && V[x][ed] - V[x][st] <= d){
          res += ed - st;
          ed++;
      }
  }
  return res;
}
bool check(ll d){
  ll sum = (ll)n * d - (1+d)*d/2;
  for(int i = 1;i <= n;++i){
      if(V[i].size() >= 2)sum -= solve(i,d);
  }
  return sum >= k;
}
int aa[MAX];
int main()
{
  scanf("%d%lld",&n,&k);
  for(int i = 1;i <= n;++i){
      int t;scanf("%d",&t);
      aa[i] = t;
      V[t].push_back(i);
  }
  ll L = 1,R = n - 1;
  while(L < R){
      ll M = (L + R) >> 1;
      if(check(M))R = M;
      else L = M + 1;
  }
  ll tmp = (L-1) * n - (1+L-1)*(L-1)/2;
  for(int i = 1;i <= n;++i){
      if(V[i].size() >= 2)tmp -= solve(i,L-1);
  }
  for(int i = 1;i + L<= n;++i){
      if(aa[i] != aa[i+L])tmp++;
      if(tmp == k){
          printf("%d %d",i,i+L);
          return 0;
      }
  }
  printf("-1");
  return 0;
}

E： 九峰与子序列 | + 字符串哈希

  • 【题意】
    有一个目标字符串
    有 个字符串序列，分别为
    问你有多少种方案，选出一些子序列使其拼接起来形成 串

  • 【范围】

  • 【思路】赛内一些 + 参考题解
    首先要读懂题意，是求子序列，即 和 是相同的一种。
    把一些字符串拼成目标串？很有 的感觉了。
    我们设 表示**前 个字符串序列拼成目标串到第 位的方案数**
    容易得到状态转移方程：

    但是关键是这个比较 特别花时间。那就用字符串哈希 ，然后比较哈希值吧。
    然后注意到，空间复杂度 是不大允许的，像背包算法一样，我们可以逆序滚动，把第一个维度给省略掉。

  • 【代码】
    时间复杂度：
    空间复杂度：

    const int MAX = 5e6+50;
const ll pri = 233;
char aim[MAX];
char aa[MAX];
unsigned long long hsh[MAX];
unsigned long long shs[MAX];
unsigned long long base[MAX];
ll dp[MAX];
int main()
{
  int n,k;scanf("%d%s",&n,aim+1);
  k = strlen(aim+1);
  base[0] = 1;
  for(int i = 1;i <= k;++i){
      hsh[i] = hsh[i-1] * pri + aim[i];
      base[i] = base[i-1] * pri;
  }
  dp[0] = 1;
  for(int i = 1;i <= n;++i){
      scanf("%s",aa+1);
      int ed = strlen(aa+1);
      shs[0] = 0;
      for(int j = 1;j <= ed;++j){
          shs[j] = shs[j-1] * pri + aa[j];
      }

      for(int j = k - ed + 1;j >= 1;--j){
          ll hash1 = hsh[j+ed-1] - hsh[j-1] * base[ed];
          if(hash1 == shs[ed]){
              dp[j+ed-1] += dp[j-1];
          }
      }
  }
  printf("%lld",dp[k]);
  return 0;
}

  • 【补充】
    特地去复习(预习)了一下字符串哈希，用双哈希直接 ，用单哈希还是
    结果只能用 自然溢出了...
    本题也可以用折半搜索去做，不过会比较麻烦。

F： 魏迟燕的自走棋 | 并查集

  • 【题意】
    有 个人， 个装备。每个人只能有一个装备，一个装备只能分配给一个人。
    其中第 件装备可以给 个人，分别为 ，装备了能总体增加 战斗力。
    问你总体战斗力最大值能为多少？

  • 【范围】

  • 【思路】参考题解
    我们把人当做点，装备当做边，就有了一个图。
    我们如果不要某个装备，相当于把这条边给删掉。
    我们最后的合法情况是什么情况？就是对于每一个连通图来说，要么： 个点连接 条边，为一棵树(或者一个有自环的点) 个点连接 条边，为一个基环树
    按照出题人的结论 按照贪心的思路，每次拿权值最大的边。如果是一个点，那么相当于删掉这个点。如果是两个不同的点，那么相当于把这两个点缩为一个点，可以通过并查集来实现。
    为什么贪心可以呢？考虑一个合法方案，假设是一个基环树。
    我们在树的任意地方添上一条权值大于树的所有边的新边。容易得到，我们都可以通过断掉一条小边，加上这条大边，使得最后得到的解合法且更大。

  • 【代码】
    时间复杂度：

    const int MAX = 2e5+50;
int fa[MAX];
bool used[MAX];
int find_fa(int x){
  if(x == fa[x])return x;
  return fa[x] = find_fa(fa[x]);
}
void add(int x,int y){
  int fx = find_fa(x);
  int fy = find_fa(y);
  if(fx != fy){
      fa[fx] = fy;
  }
}
bool sam(int x,int y){
  int fx = find_fa(x);
  int fy = find_fa(y);
  return fx == fy;
}
struct node{
  int ta,tb;
  ll w;
  bool operator <(const node &ND)const{
      return w > ND.w;
  }
}aa[MAX];
int main()
{
  int n,m;scanf("%d%d",&n,&m);
  for(int i = 1;i <= n;++i)fa[i] = i;

  for(int i = 1;i <= m;++i){
      int shu;scanf("%d",&shu);
      if(shu == 1){
          scanf("%d%lld",&aa[i].ta,&aa[i].w);
          aa[i].tb = aa[i].ta;
      }else{
          scanf("%d%d%lld",&aa[i].ta,&aa[i].tb,&aa[i].w);
      }
  }
  sort(aa+1,aa+1+m);
  ll res = 0;
  for(int i = 1;i <= m;++i){
      int x = find_fa(aa[i].ta);
      int y = find_fa(aa[i].tb);
      if(x != y){
          if(!used[x]){
              res += aa[i].w;
              used[x] = 1;
          }else if(!used[y]){
              res += aa[i].w;
              used[y] = 1;
          }
          fa[x] = y;
      }else{
          if(!used[x])
              res += aa[i].w;
          used[x] = 1;
      }
  }
  printf("%lld",res);
  return 0;
}

G：九峰与蛇形填数 | 差分 + 优先队列

  • 【题意】
    给定一个 的初始全 的矩阵。
    进行填数 次。每次选择左上角为 ，填边长为 的蛇形矩阵。
    蛇形矩阵类似下图：

    最后输出最终的矩阵。

  • 【范围】


  • 【思路】赛内想 + 来不及写了吃了个饭的时候想出来了
    我们希望快速算出每一个位置 最终是被哪一个矩形所覆盖的。
    找了很久的二维线段树的区间置数+单点查询的板子，但是找不到...
    我们二维区间差分可以做到给某一个矩形增加 ，但是也很难做到区间数字置为 呀。
    但是如果是一维的话，就好办了：
    假设有多次操作，第 次让编号为 的矩形覆盖位置 如果是这样的话我们怎么做呢？
    因为编号依次增大，我们可以搞一个优先队列，每次最优先考虑编号最大的矩形。然后我们要获得每个位置分别是哪些矩形的开始位置 记录在 中，以及每个矩形的最右范围 。
    这样，我们每次遇到 非空，就把矩形编号放进优先队列中去，还要判断队列中最大编号是否超过 了，是的话直接把该矩形编号 掉。
    二维怎么做呢？其实一样的！二维就是多个一维相加即可做，不要想复杂了。
    然后得到每个位置的最终矩形编号，我们容易直接计算出该位置的数字。

  • 【代码】
    时间复杂度：

    _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
      __/ |
     |___/
const int MAX = 3e3+50;
struct node{
  int z,y;
  int bh;
};
struct node2{
  int a,b,k;
}bb[MAX];
vector<node>V[MAX];
vector<int> de[MAX];
int aa[MAX][MAX];
unordered_map<int,int>MP;
priority_queue<int>Q;
int main()
{
  int n,m;scanf("%d%d",&n,&m);
  for(int i = 1;i <= m;++i){
      int x,y,k;scanf("%d%d%d",&x,&y,&k);
      bb[i].a = x;
      bb[i].b = y;
      bb[i].k = k;

      for(int j = x;j <= x + k - 1;++j)
          V[j].push_back({y,y+k-1,i});
  }
  for(int i = 1;i <= n;++i){
      for(int j = 1;j <= n;++j)de[j].clear();
      MP.clear();
      while(!Q.empty())Q.pop();
      MP[0] = INF;
      for(int j = 0;j < V[i].size();++j){
          de[V[i][j].z].push_back(V[i][j].bh);
          MP[V[i][j].bh] = V[i][j].y;
      }

      Q.push(0);
      for(int j = 1;j <= n;++j){
          for(int k = 0;k < de[j].size();++k)
              Q.push(de[j][k]);
          while(MP[Q.top()] < j)Q.pop();

          aa[i][j] = Q.top();
      }
  }

  for(int i = 1;i <= n;++i){
      for(int j = 1;j <= n;++j){
          int shu = aa[i][j];
          if(shu == 0)printf("0 ");
          else{
              int hang = i - bb[shu].a + 1;
              int lie  = j - bb[shu].b + 1;
              int res = (hang-1)*(bb[shu].k);
              if(hang&1){
                  res+=lie;
              }else{
                  res+=bb[shu].k-lie + 1;
              }
              printf("%d ",res);
          }
      }
      puts("");
  }
  return 0;
}

H：吴楚月的表达式 | 树形

  • 【题意】
    给定一颗有根树，根编号为
    有 个节点，每个节点有权值 ，每条边有一个操作符 中的一种。
    问你从根出发到各个节点，表达式按照正常的优先级去计算，到各个节点的权值分别为多少。
    对答案取模

  • 【范围】

  • 【思路】赛内
    考虑到没有 和 的括号的优先级干扰，我们把每个点的权值记录成 的形式。
    如果是乘法与除法，根据优先级，我们只对 进行计算。
    如果是加法与减法，根据优先级，我们把 替换成 ，然后把 替换该节点的权值，正负号表示加或者减。

  • 【代码】
    时间复杂度：

    _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
      __/ |
     |___/
const int MAX = 1e5+50;
ll q1[MAX],q2[MAX];
vector<int>V[MAX];
char op[MAX];
ll aa[MAX];
void dfs(int x){
  for(auto it : V[x]){
      if(op[it] == '+'){
          q1[it] = (q1[x] + q2[x]) % MOD;
          q2[it] = aa[it];
      }else if(op[it] == '-'){
          q1[it] = (q1[x] + q2[x]) % MOD;
          q2[it] = -aa[it] + MOD;
      }else if(op[it] == '*'){
          q1[it] = q1[x];
          q2[it] = q2[x] * aa[it] % MOD;
      }else if(op[it] == '/'){
          q1[it] = q1[x];
          q2[it] = q2[x] * inv(aa[it]) % MOD;
      }

      dfs(it);
  }
}
int main()
{
  int n;scanf("%d",&n);
  for(int i = 1;i <= n;++i)scanf("%lld",&aa[i]);
  for(int i = 2;i <= n;++i){
      int t;scanf("%d",&t);
      V[t].push_back(i);
  }
  scanf("%s",op+2);
  q1[1] = 0;q2[1] = aa[1];
  dfs(1);
  for(int i = 1;i <= n;++i){
      printf("%lld ",((q1[i] + q2[i]) % MOD + MOD) % MOD);
  }
  return 0;
}

I：九峰与分割序列 | + 单调队列优化

  • 【题意】嗯嗯题目挺言简意赅的就誊过来了
    给定一个长度为 的序列，将其分割成若干个子区间.
    子区间的贡献为：若前一个子区间的长度 且该区间长度 ，则贡献为区间和的两倍，否则贡献为区间和。
    第一个子区间的的前一个子区间长度视为 。
    求一种分割方法，使得所有子区间贡献之和最大，输出最大贡献。
  • 【范围】
  • 【思路】题解 + 代码
    这题貌似是除了魔方模拟外最难的题目了...我也理解了很久。
    容易想到，我们设一个 ，表示： 表示到 位置为止，且最后一个区间长 的最大贡献 表示到 位置为止，且最后一个区间长 的最大贡献
    更新也很好想到：最终答案为
    这样子貌似要用好多个线段树去维护，挺麻烦的。我们换一种设法：
    设 ，设
    这样转移就变成了：唔呼，每行都巧妙地别有深意 ???
    这个时候，我们发现唯一的麻烦就是去转移那个 的第二行了。
    我们直接用单调队列 去维护那个最大的 就可以了。
    为什么是单调队列呢？因为我们有 且需要求那个表达式的最大值。
  • 【代码】
    时间复杂度：
    const int MAX = 5e6+50;
int num[MAX];
ll pre[MAX];
int L,R;
int deq[MAX];
ll ans[MAX],f[MAX];
int main()
{
  int n,k;scanf("%d%d",&n,&k);
  for(int i = 1;i <= n;++i){
      scanf("%d",&num[i]);
      ans[i] = f[i] = pre[i] = pre[i-1] + num[i];
  }
  L = 0;R = 0;
  deq[R++] = k + 1;
  for(int i = k + 2;i <= n;++i){
      while(L < R && i - deq[L] > k)L++;
      ans[i] = max(f[deq[L]] + 2 * (pre[i] - pre[deq[L]]),ans[i-1] + num[i]);
      f[i] = ans[i - k - 1] + pre[i] - pre[i - k - 1];
      while(L < R && f[deq[R-1]] + 2 * (pre[i] - pre[deq[R-1]]) < f[i])R--;
      deq[R++] = i;
  }
  printf("%lld",ans[n]);
  return 0;
}

J：邬澄瑶的公约数 | 数论

  • 【题意】
    求

    答案取模

  • 【范围】

  • 【思路】赛内
    考虑到 的本质就是求出 ，求出每个质数的最小幂次。
    我们算出每个质数的最小幂次，乘起来即可。
    其实细想只要 的暴力判断代码即可，我这个由于是第二题，直接瞎敲敲就随意了ww

  • 【代码】
    时间复杂度： 带优化，卡不卡估计都能过 虽然过的飞快

    _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
      __/ |
     |___/
const int MAX = 2e4+50;
int cnt;
bool vis[MAX];
int prime[MAX];
int shu[MAX];
int xx[MAX],pp[MAX];
void shai(int n){
  for(int i = 2;i <= n;++i){
      if(!vis[i]){
          prime[++cnt] = i;
      }
      for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
          vis[i * prime[j]] = 1;
          if(i % prime[j] == 0)break;
      }
  }
}
int main()
{
  int n;scanf("%d",&n);
  shai(10000);
  for(int i = 1;i <= cnt;++i)shu[i] = INF;
  int mn = INF;
  for(int i = 1;i <= n;++i)scanf("%d",&xx[i]);
  for(int i = 1;i <= n;++i)scanf("%d",&pp[i]);

  for(int i = 1;i <= n;++i){
      int t = xx[i];
      int p = pp[i];
      for(int j = 1;j <= cnt;++j){
          if(prime[j] > t){
              mn = min(mn,j-1);
              break;
          }
          int ci = 0;
          while(t % prime[j] == 0){
              ci++;
              t /= prime[j];
          }
          ci *= p;
          shu[j] = min(shu[j],ci);
      }
  }
  ll res = 1;
  for(int i = 1;i <= mn;++i){
      res = res * qpow(prime[i],shu[i]) % MOD;
  }
  printf("%lld",res);
  return 0;
}

参考

全部评论

相关推荐

11-18 23:23
中国药科大学 外贸业务员
点赞 评论 收藏
分享
今天 13:29
已编辑
湖南铁道职业技术学院 后端
offer决赛圈求大佬意见
小红书 后端选手 n*16*1.18+签字费期权
点赞 评论 收藏
分享
11-04 20:14
中北大学 结构工程师
点赞 评论 收藏
分享
10-18 21:51
西安电子科技大学 C++
看看逆天公司😅😅😅
ArisRobert：统一解释一下，第4点的意思是，公司按需通知员工，没被通知到的员工是没法去上班的，所以只要没被通知到，就自动离职。就是一种比较抽象的裁员。
点赞 评论 收藏
分享
11-19 12:12
北京理工大学 管理培训生
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
293637次浏览 2575人参与
# 如果不工作真的会快乐吗 #
58432次浏览 505人参与
# 北方华创开奖 #
25845次浏览 279人参与
# 地方国企笔面经互助 #
3629次浏览 8人参与
# 国央企薪资爆料 #
6643次浏览 50人参与
# 选完offer后，你后悔学本专业吗 #
19000次浏览 135人参与
# 百度开奖 #
156190次浏览 936人参与
# 学历or实习经历，哪个更重要 #
49936次浏览 384人参与
# 美团求职进展汇总 #
1325006次浏览 12433人参与
# 投递实习岗位前的准备 #
1178253次浏览 18383人参与
# 面试体验感最好的是哪家？ #
84783次浏览 841人参与
# 正在实习的你，几点下班 #
51224次浏览 381人参与
# 如何一边实习一边秋招 #
990760次浏览 12630人参与
# 得物求职进展汇总 #
65905次浏览 679人参与
# 实习生应该准时下班吗 #
167203次浏览 1159人参与
# 提前批简历挂麻了怎么办 #
146081次浏览 1942人参与
# 0offer是寒冬太冷还是我太菜 #
896641次浏览 7999人参与
# 腾讯求职进展汇总 #
195188次浏览 1637人参与
# 银行笔面经互助 #
82454次浏览 873人参与
# 网申一定要掌握的小技巧 #
5279次浏览 52人参与
# 数据人offer决赛圈怎么选 #
116429次浏览 1461人参与
# 海康威视求职进展汇总 #
398215次浏览 3403人参与
牛客网
牛客企业服务