2022牛客多校（一）

2022牛客多校（一） 一、比赛小结

比赛链接："蔚来杯"2022牛客暑期多校训练营1

二、题目分析及解法（基础题） A、Villages: Landlines

签到题

题意：

给出一个发电站，给出n-1个村庄，要建立一些电塔使得发电站与村庄连通，发电站与村庄均有接收范围 [ x i − r i , x i + r i ] [x_i-r_i, x_i+r_i] [xi​−ri​,xi​+ri​] ，电塔与电塔连接成本为距离差，求使图形连通的最小成本

题解：

进行区间merge即可，将前后不相交的区间距离贡献至答案

代码：

#include 
#define int long long
#define pii pair
using namespace std;
const int maxn = 2e5 + 5;
int n;
vector vec, res;
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  int u, v;
  cin >> u >> v;
  vec.push_back({u - v, u + v});
  for (int i = 1; i > u >> v;
    vec.push_back({u - v, u + v});
  }
  sort(vec.begin(), vec.end());
  pii last = vec[0];
  res.push_back(last);
  for (auto e : vec) {
    if (e.first  x >> y;
    per[p] = {x, y};
    solve();
  }
  return 0;
}

D、Mocha and Railgun

签到题

题意：

给出圆，以及圆内一点，以及攻击方式，求该点攻击范围（与圆相交部分）最大值

题解：

如图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Dsp253xb-1662047660537)(file:///C:/Users/lenovo/AppData/Roaming/marktext/images/2022-08-23-18-01-29-image.png?msec=1661248906630)]

代码：

#include 
using namespace std;
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    double d, r;
    double x, y;
    cin >> r;
    cin >> x >> y >> d;
    double dis = sqrt(x * x + y * y);
    double ang1 = acos((dis - d) / r), ang2 = acos((dis + d) / r);
    double ans = (ang1 - ang2) * r;
    cout  1, k = 0;
    do {
      i >>= 1;
      k >>= 1;
      if ((quickpow(x, i) * quickpow(b, k) + 1) % mod == 0) k += (mod - 1 >> 1);
    } while (i % 2 == 0);
    ans = quickpow(x, i + 1 >> 1) * quickpow(b, k >> 1) % mod;
  }
  if (ans * 2 > mod) ans = mod - ans;
  return ans;
}
// 蝴蝶变换
void change(ll* a, int len) {
  static int rev[maxn];
  rev[0] = 0;
  for (int i = 0; i > 1] >> 1);
    if (i & 1) rev[i] |= len >> 1;
  }
  for (int i = 0; i  INTT , O(nlogn)
void NTT(ll* a, int len, int flag) {
  change(a, len);
  for (int h = 2; h