首页 > 其他分享 >3 月 15 日测试题解

3 月 15 日测试题解

时间：2023-03-19 16:34:14浏览次数：40  
标签：std 15 测试题 int text second vector include

3 月 15 日测试题解

这学校的评测机我是真的吐了，\(\text{380pts} \rightarrow \text{300pts}\)，电脑速度跟 BZOJ 有的一拼。

一句话总结：简单，过于简单，但是在练习读题能力上十分有用。

T1 挂分的原因是 std::cin 在读入 \(3 \times 5 \times 10^5\) 的数据情况下超时了，而 T2 纯纯自己傻逼，T3 跟 T4 又是因为这台奇快无比的评测机 T 了 \(\text{60pts}\)。

我还能做出什么评价呢？等我退役之后一定要给学校搭一台好一点的服务器之类的当评测机。

T1

题意

一个长度为 \(s\) 的区间与 \(n\) 个操作，初始区间内每个值都赋为 \(1\)，每次操作给出三个整数 \(l\)，\(r\) 与 \(t\)，表示将 \([l, r]\) 内的数修改为 \(t\)，求最后得到的区间和。

\(s \le 2 \times 10^9\)，\(n \le 5 \times 10^5\)。保证给出的区间没有重叠。

思路

\(\text{100pts}\)

因为保证了给出的区间没有重叠，简单模拟即可，没有什么思维难度。初始化 \(ans = s\)，然后每次修改让 \(ans\) 加上 \((r - l + 1) \times (t - 1)\) 就做完了。

但是这道题的数据离谱到了在明确强调没有区间重叠的情况后，第 2 ~ 3 个测试点仍然出现了重叠情况，虽然我没有因此挂分，但是我还是很想问问验题人：你自认为你是一个合格的验题人吗？这种如此简单的数据都不愿意写程序检验一下，我真的不知道要这种验题人有什么用。

为什么我知道这道题数据有问题呢？因为我旁边的老哥写的是 ODT。

代码

\(\text{100pts}\)

#include <bits/stdc++.h>
#include <iostream>

using i64 = long long;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  
  int s, n;
  std::cin >> s >> n;
  
  i64 ans = s;
  for (int i = 1; i <= n; i++) {
    i64 l, r, t;
    std::cin >> l >> r >> t;
    ans += (r - l + 1) * (t - 1);
  }
  
  std::cout << ans << "\n";
  
  return 0;
}

T2

题意

经典求最大矩形面积题。

\(n \le 10^5\)，\(m \le 50\)，其中 \(n\) 是列数，\(m\) 是每列最高的高度。

思路

\(\text{100pts}\)

单调栈做一下就完了。

代码

\(\text{100pts}\)

#include <bits/stdc++.h>

using i64 = long long;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  std::vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }

  std::vector<int> s(1, 0);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    while (s.size() != 1 && a[s[s.size() - 1]] >= a[i]) {
      s.pop_back();
    }
    s.push_back(i);
    for (int j = 1; j <= s.size() - 1; j++) {
      ans = std::max(ans, a[s[j]] * (s[s.size() - 1] - s[j - 1]));
    }
  }

  std::cout << ans << "\n";

  return 0;
}

T3

题意

有两支足球队，分别有 \(n\) 个人与 \(m\) 个人，你属于那只 \(n\) 个人的，给出每个人的坐标以及球门的坐标，射门的时间为球员与人的距离乘以二，传球的时间为两个球员之间的距离，但是若两个球员之间有另一支球队的人，也就是说三人位于同一直线上且中间的人是对方球队的，则无法传球，现在问你射门的最短时间是多少。

\(n \le 300\)，\(m \le 100\)。

思路

\(\text{100pts}\)

这一类问题都是可以归约到最短路上的。

我们把每个坐标都看成一个点，建图，考虑一下非法情况，然后直接跑最短路即可。由于这道题规模不大，最短路用 Floyd 跑一下就行了。时间复杂度为 \(O(n^2 m + n^3)\)。

判非法就枚举一下然后算一下斜率就好了，记得判斜率不存在。

代码

\(\text{100pts}\)

#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>

using i64 = long long;
using f80 = long double;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  
  static const f80 EPS = 1e-7;
  
  int n, m;
  std::pair<int, int> door;
  std::cin >> door.first >> door.second >> n >> m;
  
  std::vector<std::pair<int, int>> a(n), b(m);
  for (auto &i : a) {
    std::cin >> i.first >> i.second;
  }
  for (auto &i : b) {
    std::cin >> i.first >> i.second;
  }
  a.push_back(door);
  
  auto getDis = [&](int i, int j) {
    return std::hypot(a[i].first - a[j].first, a[i].second - a[j].second);
  };
  
  std::vector<std::vector<f80>> dis(n + 1, std::vector<f80>(n + 1, 1e18));
  for (int i = 0; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      bool flg = true;
      for (int k = 0; k < m; k++) {
        if (b[k].first < std::min(a[i].first, a[j].first)) {
          continue;
        }
        if (b[k].first > std::max(a[i].first, a[j].first)) {
          continue;
        }
        if (b[k].second < std::min(a[i].second, a[j].second)) {
          continue;
        }
        if (b[k].second > std::max(a[i].second, a[j].second)) {
          continue;
        }
        
        auto getK = [&](std::pair<int, int> p, std::pair<int, int> q) {
          int x1 = p.first, x2 = q.first;
          int y1 = p.second, y2 = q.second;
          if (x1 == x2) {
            return f80(-1);
          }
          return f80(y1 - y2) / (x1 - x2);
        };
        
        if (getK(a[i], a[j]) == -1) {
          if (a[i].first == b[k].first) {
            flg = false;
            break;
          }
        } else {
          if (fabs(getK(b[k], a[i]) - getK(b[k], a[j])) <= EPS) {
            flg = false;
            break;
          }
        }
      }
      
      if (flg) {
        dis[i][j] = dis[j][i] = getDis(i, j) * (j == n ? 2 : 1);
      }
    }
  }
  
  for (int k = 0; k <= n; k++) {
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= n; j++) {
        dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }
  
  std::cout << i64(std::round(dis[0][n])) << "\n";
  
  return 0;
}

T4

题意

一个高度为 \(n\) 的塔，每层都是一个正方形且第 \(i\) 层边长为 \((n - i + 1)\)。第 \(i\) 层的第 \(j\) 行第 \(k\) 列的节点 \((i, j, k)\) 有一个权值 \(t_{i, j, k}\)，表示经过这个节点所需的时间。

每个节点可以按如下方法拓展：

  1. 拓展至同一层的四联通的节点中。
  2. 拓展至上一层的 \((i + 1, j, k)\)，\((i + 1, j + 1, k + 1)\)，\((i + 1, j + 1, k)\) 或 \((i + 1, j, k + 1)\) 节点中。

此外，还有 \(m\) 条暗道 \((i_s, j_s, k_s, i_t, j_t, k_t, w)\)，表示可以花费 \(w\) 直接从 \((i_s, j_s, k_s)\) 直接走到 \((i_t, j_t, k_t)\)。

你现在从 \((1, 1, 1)\) 开始走，问走到 \((n, 1, 1)\) 的最短时间是多少。

对于 \(50\%\) 的数据，\(n \le 5\)；
对于 \(100\%\) 的数据，\(n \le 100\)，\(m \le 50\)。

思路

\(\text{50pts}\)

考虑直接爆搜，时间复杂度为 \(O(n^8)\) 上下。

不过同机房有个老哥写爆搜加几个玄学剪枝过了 \(\text{90pts}\)，而我因为学校所拥有的 Fastest CPU In The World 而 T 了 3 个点，果然还是建议验题人自裁呢。

\(\text{100pts}\)

还是利用图论建模的思想，考虑给每个坐标重新编号，在能够拓展的节点之间连边，再把点权转成边权，然后跑一遍最短路就好了。

但是这个图是稠密的，最短路可能要写 SPFA 之类的，不过我在 Luogu 上用 Dijkstra 跑过了。

事实上当然也可以写记忆化搜索，时间复杂度更为优秀。

个人认为讲的再多不如一份写得清楚的代码，所以有关建图的细节建议直接看代码，不仅更加高效，而且能够提升代码的阅读能力。

代码

\(\text{100pts}\)

#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>

using i64 = long long;

struct Graph {
  const int INF = 0x3f3f3f3f;
  int n, m;
  std::vector<std::vector<std::pair<int, int>>> e;
  std::vector<int> dis;
  std::vector<bool> vis;
  
  Graph(int n, int m = 0) {
    this->n = n;
    this->m = m;
    e.resize(n);
    dis.resize(n);
    vis.resize(n);
    return;
  }
  
  void add(int u, int v, int w) {
    e[u].emplace_back(v, w);
    return;
  }
  
  int dijkstra(int s, int t) {
    dis.assign(n, INF);
    vis.assign(n, false);
    dis[s] = 0;
    
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
    q.emplace(0, s);
    
    while (!q.empty()) {
      int u = q.top().second;
      q.pop();
      
      if (vis[u]) {
        continue;
      }
      vis[u] = true;
      
      for (auto i : e[u]) {
        int v = i.first, w = i.second;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          q.emplace(dis[v], v);
        }
      }
    }
    
    return dis[t];
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n, m;
  std::cin >> n >> m;
  
  Graph G(n * (n + 1) * (2 * n + 1) / 6 + 50);
  
  int cnt = 0;
  std::vector<std::vector<std::vector<int>>> mp(n + 1), t(n + 1);
  for (int k = 1; k <= n; k++) {
    int len = n - k + 1;
    
    mp[k].resize(len, std::vector<int>(len));
    t[k].resize(len, std::vector<int>(len));
    
    for (int i = 0; i < len; i++) {
      for (int j = 0; j < len; j++) {
        mp[k][i][j] = ++cnt;
        std::cin >> t[k][i][j];
      }
    }
  }
  
  std::vector<std::vector<int>> d1 = {{0, 0}, {1, 1}, {1, 0}, {0, 1}};
  std::vector<std::vector<int>> d2 = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  
  for (int k = 1; k <= n; k++) {
    int len = n - k + 1;
    
    for (int i = 0; i < len; i++) {
      for (int j = 0; j < len; j++) {
        if (k != 1) {
          for (auto p : d1) {
            int dx = i + p[0], dy = j + p[1];
            G.add(mp[k - 1][dx][dy], mp[k][i][j], t[k - 1][dx][dy]);
          }
        }
        
        for (auto p : d2) {
          int dx = i + p[0], dy = j + p[1];
          if (dx < 0 || dy < 0 || dx >= len || dy >= len) {
            continue;
          }
          G.add(mp[k][i][j], mp[k][dx][dy], t[k][i][j]);
        }
      }
    }
  }
  
  for (int i = 1; i <= m; i++) {
    int sfl, sx, sy, tfl, tx, ty, ti;
    std::cin >> sfl >> sx >> sy >> tfl >> tx >> ty >> ti;
    G.add(mp[sfl][sx - 1][sy - 1], mp[tfl][tx - 1][ty - 1], ti + t[sfl][sx - 1][sy - 1]);
  }
  
  std::cout << G.dijkstra(mp[1][0][0], mp[n][0][0]) + t[n][0][0] << "\n";
  
  return 0;
}

标签：std,15,测试题,int,text,second,vector,include
From： https://www.cnblogs.com/forgot-dream/p/17233492.html

相关文章

  • 3 月 19 日测试题解
    3月19日测试题解原来这就是AK的滋味吗，不过，我却完全没感到开心呢。T1题意给出两个整数\(a\)，\(b\)，重复以下操作直到\(a=b\)：设\(a>b\)，否则交换\(a\)与\(......
  • P1157 组合的输出
    题目链接P1157组合的输出题解#include<bits/stdc++.h>usingnamespacestd;intn,r;intans[25];intvis[25];voiddfs(intdep){ if(dep==r+1){ for(inti=......
  • QT5.15.2静态编译包下载
    QT5.15.2静态编译包下载      经过反复的折腾，终于编译成了QT5.15.2的静态编译。网上指导静态编译的资料很多，但是只有自己趟过坑，才知道有多深。最终明白“纸上......
  • 代码随想录训练营day 15||二叉树的层序遍历、翻转二叉树、对称二叉树
    二叉树的层序遍历题目链接：二叉树的层序遍历题目描述：给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点```输入：root=[3,9,20,nu......
  • Educational Codeforces Round 115 (Rated for Div. 2)（D,E)
    EducationalCodeforcesRound115(RatedforDiv.2)（D,E)DD题目给出\(n\)个问题，每个问题都会有一个主题和一个难度，并且没有两个题目的问题和主题都是一样的，我们需要选......
  • day15
    day15正则表达式由一些特定的字符组成，代表的是一个规则作用用来校验数据格式是否合法、、在一段文本中查找满足要求的内容[]:只能匹配单个字符.:任意字符\：转......
  • day15
    day15正则表达式由一些特定的字符组成，代表的是一个规则作用用来校验数据格式是否合法、、在一段文本中查找满足要求的内容[]:只能匹配单个字符.:任意字符\：转......
  • Hate That You Know Me (15黑龙江省赛) (数学公式题)(数论分块) (前缀和,小的数学结论
      思路;遇到数学公式,一层一层剥开发现那个式子就是求n内的每一个数的倍数在n以内的数量,明显数论分块来处理这个问题然后就是因子的^2,^3,这个子问题......
  • 15、K8S资源对象&资源清单
    1、资源对象基本属性介绍1.1、资源对象学习完成Kubernetes集群中的基本架构角色，那么不能不提的集群实现的核心：资源对象。那么在Kubernetes集群中，这些资源对象是如何产......
  • ARC158
    啥都不会，省选要寄了呀。A考虑将操作$(+3,+5,+7)$改成$(+3+c,+5+c,+7+c)$不会影响操作的次数，所以可以将操作改成$(-2,+0,+2)$。这样每次操作之后$x_1$，$x_2$，$x_3$的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99