• 2022牛客多校（五）

    2022牛客多校（五）

    文章目录

    一、比赛小结

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

    这场是草酸哥出的一套题，最后 unrated 了

    二、题目分析及解法（基础题）

    A、Don’t Starve

    题目链接：A-Don’t Starve

    题意：

    给定 n 个点有食物（每个点可以吃多次），每个点有一个坐标，对与行走的规则是每一步都必须严格短于上一步，问最优的方案下能够吃到多少次食物

    题解：

    观察可得，当你站在某一个特定的点上时，会影响你的接下来转移的只有上一步所走的距离具体是多少，但如果想把上一步的距离设入状态的话内存是不允许的。所以我们考虑设立状态dp[i][j]表示上一步在i，当前这步走到j了的情况下最多已经吃到次数是多少，而对于转移，因为我们知道了最近两步的行走

    所以可以直接计算出上一步的长度从而进行转移了，复杂度O(n^2)

    代码：

    #include 
using namespace std;
const int maxn = 2e3 + 5;
const int Max = 0x3f3f3f3f;
int n;
int x[maxn], y[maxn];
struct Edge {
  int u, v, dis;
  Edge(int u = 0, int v = 0, int dis = 0) : u(u), v(v), dis(dis) {}
  bool operator<(const Edge &a) const { return dis > a.dis; }
};
vector<Edge> e;
int f[maxn], g[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  memset(f, -Max, sizeof f);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
  for (int i = 0; i <= n; i++) {
    for (int j = 1; j <= n; j++)
      if (i != j)
        e.push_back(Edge(i, j, pow(x[j] - x[i], 2) + pow(y[j] - y[i], 2)));
  }
  sort(e.begin(), e.end());
  f[0] = 0;
  for (int i = 0, j = 0; i < e.size(); i = j) {
    vector<Edge> v;
    for (; j < e.size() && e[i].dis == e[j].dis; j++) v.push_back(e[j]);
    for (auto e : v) g[e.v] = -Max;
    for (auto e : v) g[e.v] = max(g[e.v], f[e.u] + 1);
    for (auto e : v) f[e.v] = max(f[e.v], g[e.v]);
  }
  cout << *max_element(f, f + n + 1) << endl;
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    B、Watches

    题目链接：B-Watches

    题意：

    给定 n (1e5) 件商品的价格，如果你选购 k 件商品，那么购买第i件物品的花费就是 a i + k ∗ i a_i+k*i ai​+k∗i ，问最多能买多少件（第 i 件是原序列中的第 i 个）

    题解：

    注意到答案具有单调性，考虑二分答案 k 则问题变为判定是否能选择 k 件物品，总花费不超过 M 元，直接贪心即可

    代码：

    #include 
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn], b[maxn];
int n, m;
int ans;
bool check(int k) {
  for (int i = 1; i <= n; i++) {
    b[i] = a[i] + k * i;
  }
  sort(b + 1, b + 1 + n);
  int sum = 0ll;
  for (int i = 1; i <= k; i++) {
    sum += b[i];
    if (sum > m) return false;
  }
  return true;
}
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  while (cin >> n >> m) {
    for (int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = n;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        ans = max(ans, mid);
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    C、Bit Transmission

    题目链接：C-Bit Transmission

    题意：

    有个01组成的字符串 对某些位置询问是否是1 询问3n次，有至多一次询问 返回的答案是错误的，问这些询问结果能否唯一确定字符串

    题解：

    记录每一位上被问过的YES/NO次数。如果存在不被问到的位置，输出-1 ，如果某一位YES/NO次数相同，输出-1 ，如果某一位YES/NO次数均大于1，输出-1

    否则，我们判断下是否存在YES和NO均出现过的位置，假设共出现x次

    如果x>1，输出-1；如果x=1，表明错误位置确定，此时能够确定唯一字符串；

    如果x=0，那么我们判断下是否存在YES和NO总共出现1次的位置，存在表明无法确定，否则则能够唯一确定字符串

    其实这个题是有 bug 的，出题人少考虑了一种情况，导致我们比赛时 WA 了好几发

    代码：

    #include 
using namespace std;
const int maxn = 1e5 + 5;
int n, x;
string s;
int yes[maxn], no[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= 3 * n; i++) {
    cin >> x >> s;
    if (s == "YES")
      yes[x]++;
    else
      no[x]++;
  }
  s = "";
  bool ok = 1;
  for (int i = 0; i < n; i++) {
    if (no[i] && yes[i]) {
      if (ok)
        ok = 0;
      else {
        cout << -1 << endl;
        return 0;
      }
      if (yes[i] == 1 && no[i] == 1) {
        cout << -1 << endl;
        return 0;
      } else if (no[i] == 1)
        s += "1";
      else if (yes[i] == 1)
        s += "0";
      else {
        cout << -1 << endl;
        return 0;
      }
    } else if (no[i])
      s += "0";
    else
      s += "1";
  }
  cout << s << endl;
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    D、Birds in the tree

    题目链接：D-Birds in the tree

    题意：

    给定n个节点的树，树上每个节点的颜色为0或1，问最终有多少个子树（连通块）的所有叶子颜色都是一样的

    题解：

    树上间接计数，大概率是树形 dp ，然后我们推一下式子

    考虑设立DP状态，dp[u][1/2]分别表示以u为根的子树里，有多少种颜色为1/2的合法子树使得所有叶子节点颜色都是相同的，考虑u节点有一个儿子节点v，此时分两种情况，一个是u本身和v的子树产生的贡献，另一个是u之前的所有子树和v的子树产生的贡献，前者比较容易统计，就是dp[v][a[u]]，后者是dp[u][1]*dp[v][1]和dp[u][2]*dp[v][2]，同时考虑在计算完v的贡献后需要将其加入dp[u]中

    代码：

    #include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=3e5+5;
const int mod=1e9+7;
ll dp[maxn][2],ans;
int a[maxn];
vector<int>Q[maxn];
int n;
void dfs(int u,int fa,int now){
	ll mul=1,sum=0;
	for(int i=0;i<Q[u].size();i++){
		int to=Q[u][i];
		if(to==fa)continue;
		dfs(to,u,now);
		mul=mul*(dp[to][now]+1)%mod;
		sum=(sum+dp[to][now])%mod;
	}
	dp[u][now]=(mul-1+(a[u]==now)+mod)%mod;
	if(now==a[u])
	ans=(ans+dp[u][now])%mod;
	else 
	ans=(ans+dp[u][now]-sum+mod)%mod;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%1d",&a[i]);
    for(int i=1,u,v;i<n;i++){
    	scanf("%d%d",&u,&v);
    	Q[u].push_back(v);
    	Q[v].push_back(u);
	}
	dfs(1,1,1);
	dfs(1,1,0);
	cout<<ans<<endl;
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    F、A Stack of CDs

    题目链接：F-A Stack of CDs_

    题意：

    给出 n   ( n ≤ 1000 ) n \ (n \le 1000) n (n≤1000) 个盘子，这些盘子会两两相交，求最后露在外面的轮廓线

    题解：

    n n n 比较小，可以乱搞，求两两相交即可

    代码：

    #include 

#define x first
#define y second

using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;

const int INF = 0x3f3f3f3f;
const double eps = 1e-15;

const int N = 1005;
const double PI = acos(-1);
typedef long double LD;
typedef pair<LD, LD> pdd;
struct circle {
  int x, y;
  double r;
} c[N];
int n;
pdd q[N * 2];
int cnt;

int sign(long double x) {
  if (fabs(x) < eps) return 0;
  if (x < 0) return -1;
  return 1;
}

inline int dcmp(long double a, long double b) { return sign(a - b); }

pii operator-(circle a, circle b) { return {a.x - b.x, a.y - b.y}; }

inline LD get_len(pii a) {
  LD dx = a.x, dy = a.y;
  return sqrt(dx * dx + dy * dy);
}

void get_intersection(circle &a, circle &b) {
  pii v = b - a;
  LD dist = get_len(v);
  if (dcmp(a.r + b.r, dist) <= 0) return;
  if (dcmp(a.r, b.r + dist) > 0) {
    return;
  } else {
    if (dcmp(a.r + dist, b.r) <= 0) {
      q[cnt++] = {-PI, PI};
      return;
    }
  }
  LD base = atan2(v.y, v.x);
  LD theta = acos((a.r * a.r + dist * dist - b.r * b.r) / (2 * a.r * dist));

  if (base + theta > PI) {
    q[cnt++] = {base - theta, PI};
    q[cnt++] = {-PI, base + theta - PI * 2};
  } else if (base - theta < -PI) {
    q[cnt++] = {-PI, base + theta};
    q[cnt++] = {base - theta + PI * 2, PI};
  } else
    q[cnt++] = {base - theta, base + theta};
}

int main() {
  //    freopen("input.txt","r",stdin);

  //====================
  cin >> n;
  for (int i = 1; i <= n; i++) scanf("%d%d%lf", &c[i].x, &c[i].y, &c[i].r);
  LD ans = 0;
  for (int i = 1; i <= n; i++) {
    cnt = 0;
    for (int j = 1 + i; j <= n; j++) get_intersection(c[i], c[j]);
    if (!cnt) {
      ans += 2 * PI * c[i].r;
      continue;
    }
    sort(q, q + cnt);
    LD alpha = 0;
    LD st = q[0].x, ed = q[0].y;
    for (int j = 1; j < cnt; j++)
      if (q[j].x <= ed)
        ed = max(ed, q[j].y);
      else
        alpha += ed - st, st = q[j].x, ed = q[j].y;
    alpha += ed - st;
    ans += (2 * PI - alpha) * c[i].r;
  }
  printf("%.10lf\n", (double)ans);

  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93

    G、KFC Crazy Thursday

    题目链接：G-KFC Crazy Thursday_

    题意：

    以kfc结尾的回文子串计数

    题解：

    跑下马拉车即可

    代码：

    #include 
using namespace std;
const int maxn = 1e6 + 10;
int len, len_tmp;
char str[maxn], tmp[maxn];
int pal[maxn];
int ans_k, ans_f, ans_c;
void init() {
  tmp[0] = '@';
  for (int i = 0; i < len; i++) tmp[2 * i + 1] = str[i];
  for (int i = 1; i < len; i++) tmp[2 * i] = '#';
  tmp[2 * len] = '&';
  len_tmp = 2 * len + 1;
}
void manachar() {
  int mx = 0, pos = 0;
  for (int i = 1; i < len_tmp - 1; i++) {
    if (i < mx)
      pal[i] = min(pal[2 * pos - i], mx - i);
    else
      pal[i] = 1;
    while (tmp[i + pal[i]] == tmp[i - pal[i]]) pal[i]++;
    if (i + pal[i] > mx) {
      mx = i + pal[i];
      pos = i;
    }
  }
}
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> len >> str;
  init();
  manachar();
  for (int i = 1; i < len_tmp - 1; i++) {
    for (int j = 0; j < pal[i]; j++) {
      if (tmp[i - j] == 'k') ans_k++;
      if (tmp[i - j] == 'f') ans_f++;
      if (tmp[i - j] == 'c') ans_c++;
    }
  }
  printf("%d %d %d\n", ans_k, ans_f, ans_c);
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    H、Cutting Papers

    题目链接：H-Cutting Papers_

    题意：

    给出一个不等式，问这个不等式构成的封闭区域和以这个封闭区域中心为圆心的圆形的面积并

    题解：

    根据不等式画出封闭区域，直接计算圆形和阴影部分的并集，答案就是 (n/2)^2*(2+pi/2)

    代码：

    #include 
#define double long double
#define pi 3.14159265358979323846
using namespace std;
double n;
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  while (cin >> n) {
    double ans = n * n * (pi + 4) / 8.0;
    cout << fixed << setprecision(10) << ans << "\n";
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    K、Headphones

    题目链接：K-Headphones

    题意：

    有 N 对耳机，Yasa拿出正好 k 对，NIO至少要取出多少只，能够比Yasa取出的多。耳机左右为一对，Yasa拿出的都是一对，NIO要取的是一只一只的。

    题解：

    鸽巢原理，最坏情况下NIO拿到的耳机全是单只的，只要判断一下NIO要拿的个数是否已经超过剩下的耳机对数就行。

    代码：

    #include 
#define int long long
using namespace std;
int n, k;
signed main() {
 // freopen("in.txt", "r", stdin);
 // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  while (cin >> n >> k) {
    if (n - k < k + 1) {
      cout << -1 << endl;
      continue;
    }
    cout << n + 1 << "\n";
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    三、题目分析及解法（进阶题）

    不会X

    E、Fraction Game

    I、Board Game

    J、Check In

  • 相关阅读:
    ipad触控笔是哪几款？开学季便宜的ipad电容笔推荐
    vue项目打包，使用externals抽离公共的第三方库
    云原生在各大厂的落地与分析
    win10 下 ipmitool 1.8.19编译
    B-Tree 索引和 Hash 索引的对比
    西电数据挖掘实验3——复杂网络社团检测
    微服务学习第三十二节
    【UI测试】内容及流程
    Mysql整理-主从复制
    【Timm】timm.data 数据集全面详实概念理解
  • 原文地址：https://blog.csdn.net/m0_54646258/article/details/126937109