NowCoder 203H – Travel (排列组合)

题意

地图为一棵树,进行m次旅游,每次游览至少一座城市。为了方便,每次旅游游览的城市必须是连通的。此外,所有城市恰好只浏览一次。求总方案数。

思路

树长什么样根本不影响题解。只要找到$m-1$条边把这棵树断开即可。答案为$$\binom{n-1}{m-1} \times m!$$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modulo = (ll) 1e9 + 7;
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    exgcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
ll getInv(ll a, ll p) {
  ll d, x, y;
  exgcd(a, p, d, x, y);
  return d == 1 ? (x + p) % p : -1;
}
 
ll frac[100005] = {};
ll inv[100005] = {};
 
void init() {
  frac[0] = frac[1] = 1;
  for (int i = 2; i <= 100000; ++i) {
    frac[i] = frac[i - 1] * i % modulo;
  }
  for (int i = 0; i <= 100000; ++i) {
    inv[i] = getInv(frac[i], modulo);
  }
}
 
ll C(ll n, ll k) {
  return (frac[n] * inv[k] % modulo) * inv[n - k] % modulo;
}
 
int n = 0, m = 0, tmp = 0;
ll ans = 0;
 
int main() {
  init();
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; ++i) {
      scanf("%d%d", &tmp, &tmp);
    }
     
    ans = C(n-1, m-1) * frac[m] % modulo;
    printf("%lld\n", ans);
  }
  return 0;
}

NowCoder 203D – Shopping (贪心)

题意

你有$n$个商品要买,总共有$m$个购物车。如果购物车内买了个凳子,那么这个购物车最贵的商品半价。问你最小的花费是多少。

思路

最多只能有$m$或者凳子数量个商品半价。半价商品一定是最贵的。

代码

#include <bits/stdc++.h>
using namespace std;
 
int n = 0, m = 0;
int s[1005] = {};
double total = 0;
 
int main() {
  int T = 0;
  scanf("%d", &T);
  while (T--) {
    total = 0;
    scanf("%d%d", &n, &m);
 
    int tmp = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
      scanf("%d%d", s + i, &tmp);
      if (tmp == 1) cnt++;
    }
 
    m = min(m, cnt);
    sort(s, s+n);
 
    for (int i = 1; i <= m; ++i) {
      total += (double) s[n - i] / 2;
    }
    for (int i = 0; i < n - m; ++i) {
      total += s[i];
    }
 
    printf("%.1lf\n", total);
 
  }
  return 0;
}

NowCoder 202F – 平衡二叉树 (贪心+递归)

题意

平衡二叉树的参数$d$表示每个节点两子树高度差不超过$d$。求高度为$n$的所有平衡二叉树中左右子树节点数差的最大值。

思路

一开始以为只要左边全满右边一条链就搞定了然后快乐WA

思考后发现右边的所有节点也要满足高度差$\le d$的条件。所以只要左边是满二叉树右边是满足平衡条件的最小二叉树就可以了。

最小二叉树节点数可用递归求出,$$C_h = C_{h-1} + 1 + C_{h-1-d}$$

然后TLE了(内心OS:出题人一定是清华的,又红又橙的题,还是树)

用记忆化搜索还因为垃圾代码越界WA找了半天……

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mt[100] = {};
ll mintree(int h, int d) {
  if (h <= 0) return 0;
  if (mt[h] >= 0) return mt[h];
  else if (h == 1) return 1;
  else return mt[h] = mintree(h - 1, d) + mintree(h - 1 - d, d) + 1;
}

int main() {
  memset(mt, -1, sizeof(mt));
  int n = 0, d = 0;
  ll ans = 0;
  scanf("%d%d", &n, &d);
  if (n == 0) {
    ans = 0;
  } else {
    ans = (1LL << (n - 1)) - 1 - mintree(n - 1 - d, d);
  }
  printf("%lld", ans);
}