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;
}

Codeforces 1030E – Vasya and Good Sequences (前后缀和+DP)

题意

给你$n$个数,每个数可以任意改变二进制中1的位置,问你有多少区间$[l,r]$满足操作后异或和为0。

题解

这题真是太妙了!(直接看题解的屑)

首先贪心,计算出二进制表示中1的个数$b_i$。计算出$b_i$的后缀和,那么对于某一个区间,可以$O(1)$计算出这个区间内1的个数的和。

满足条件的区间需要具备两个条件:

  • 1的个数之和为偶数
  • 1的个数最多的那个数的1的个数小于其他数1的个数的和(贪心)

那么只要穷举所有的$l$,$r > l+64$且后缀和奇偶性相同的一定满足(因为那个最大的数最多也就64位),其他的暴力判断一下就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n = 0, ans = 0;
ll oddCnt = 0, evenCnt = 0;
ll s[300005] = {};
bool sumEven[300005] = {};

ll bitCnt(ll ori) {
  ll cnt = 0;
  while (ori) {
    cnt += ori & 1;
    ori >>= 1;
  }
  return cnt;
}

int main() {
  cin >> n;
  for (ll i = 0; i < n; ++i) {
    cin >> s[i];
    s[i] = bitCnt(s[i]);
  }

  ll sum = 0;
  oddCnt = 0, evenCnt = 1, sumEven[n] = true;
  for (ll i = n - 1; i >= 0; --i) {
    sum += s[i];
    if (sum & 1) {
      ans += oddCnt;
      oddCnt++;
    } else {
      ans += evenCnt;
      sumEven[i] = true;
      evenCnt++;
    }
  }

  for (ll i = 0; i < n; ++i) {
    ll sumx = 0, maxi = 0;
    for (ll j = i; j < min(n, i + 64LL); ++j) {
      if (s[j] > maxi) {
        sumx += maxi;
        maxi = s[j];
      } else {
        sumx += s[j];
      }
      if (sumx < maxi && sumEven[i] == sumEven[j + 1]) {
        ans--;
      }
    }
  }

  cout << ans;
  return 0;
}

GCC Magic

看了出题人大佬的题解才知道GCC有一个魔法函数__builtin_popcountll(unsigned)。其功能是计算无符号数的二进制表达式中1的个数。这个函数使用了分块查表的方法,跑得非常快!

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);
}