[Hackerrank] CodeKnight 1.0 A-D题解（线段树, 二分, 组合计数, 尺取）

链接：https://www.hackerrank.com/contests/codeknight-1/challenges

这些题好蛋疼啊。。。。

Magical Cards：给你一个整数$n$，问你有多少种拆分方法，将这个数拆成素数的乘积。

首先将这个数分解质因数，并记下每个素因数的个数$c[i]$以及一共有多少个素因数$tot$，问题转化成将这$tot$个素因数有多少种排列方式了。直接考虑每一类素因数$p[i]$要在$tot$个位置中占据$c[i]$个位置，每一种素因数的排放实际上是相互独立的。则位置有$C_{tot}^{p[i]}$种，剩下$tot-p[i]$个空位下一个质因数再放就行。

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

using LL = long long;
const int maxn = 10010;
LL f[maxn];

signed main() {
    // freopen("in", "r", stdin);
    int T;
    scanf("%d", &T);
    int n;
    vector<int> c;
    f[1] = f[0] = 1;
    for(int i = 2; i < maxn; i++) f[i] = f[i-1] * i;
    while(T--) {
        scanf("%d", &n);
        LL m = n, tot = 0;
        c.clear();
        for(int i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                int cnt = 0;
                while(n % i == 0) {
                    cnt++; n /= i;
                    tot++;
                }
                c.emplace_back(cnt);
            }
        }
        if(n > 1) {
            tot++;
            c.emplace_back(1);
        }
        LL ret = 1;
        for(int i = 0; i < c.size(); i++) {
            ret = f[tot] / f[c[i]] / f[tot-c[i]] * ret;
            tot -= c[i];
        }
        printf("%lld\n", ret);
    }    
    return 0;
}

Shubham and Subarrays：给你n个数，和一个整数k。让你求有多少个子区间的乘积为k。

考虑这样的区间问题首先想到尺取，但是仅尺取还不够。考虑k=1的情况，假如有连续的1存在（如：1 1 1 1），那么实际上有6种（$\frac{3×(3+1)}{2}$）。特殊处理掉这个情况，剩下的再计算乘积恰好为k时，左右两个指针外部的1的贡献就行了。

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

using LL = long long;
using PLL = pair<LL, LL>;
const int maxn = 100100;
int n;
LL k, x[maxn];
vector<PLL> v;

signed main() {
  // freopen("in", "r", stdin);
  int T;
  scanf("%d", &T);
  while(T--) {
    scanf("%d%lld",&n,&k);
    v.clear(); v.emplace_back(0, -1);
    for(int i = 0; i < n; i++) {
      scanf("%lld", &x[i]);
      if(x[i] != 1) {
        v.emplace_back(x[i], i);
      }
    }
    v.emplace_back(0, n);
    LL one = 0, ret = 0, cur = 0;
    for(int i = 1; i < v.size(); i++) {
      cur = v[i].second - v[i-1].second;
      one += (cur - 1) * cur / 2;
    }
    if(k == 1) {
      printf("%lld\n", one);
      continue;
    }
    int l = 1, r = 1;
    cur = 1;
    while(r < v.size() - 1) {
      if(cur * v[r].first == k) {
        cur *= v[r].first;
        r++;
        ret += (v[r].second - v[r-1].second) * (v[l].second - v[l-1].second);
      }
      else if(cur * v[r].first < k) {
        cur *= v[r].first;
        r++;
      }
      else if(cur * v[r].first > k) {
        if(l == r) l++, r++;
        else {
          cur /= v[l].first;
          l++;
        }
      }
    }
    printf("%lld\n", ret);
  }
  return 0;
}

Chef and Cakes：这题太水，不多说了。

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

map<int, int> vis;

signed main() {
    // freopen("in", "r", stdin);
    int T;
    scanf("%d", &T);
    int n;
    while(T--) {
        scanf("%d", &n);
        vis.clear();
        int x, a = -1;
        for(int i = 0; i <n; i++) {
            scanf("%d",&x);
            vis[x]++;
        }
        for(auto x : vis) {
            a = max(a, x.second);
        }
        printf("%d %d\n", vis.size(), a);
    }    
    return 0;
}

Domino’s：n个多米诺骨牌，每个骨牌的位置为$x_i$，高度为$h_i$，每个骨牌向右倒下能砸到$[x+1,x+h-1]$范围的骨牌。现在让你统计每一个骨牌从它的位置向右倒下后能砸倒多少骨牌（多米诺骨牌后面的骨牌被砸倒还会影响到后面的）。

我们给n个多米诺骨牌按$x_i$排序后发现，由于最右边的骨牌倒下的影响只有自己，即为1，于是我们考虑从右往左开始处理：设我们骨牌的结果为$dp_i$，每当处理到第$i$个骨牌时，我们单张骨牌砸中的范围为$[x_i+1,x_i+h_i-1]$，我们对再它右边的骨牌中找到能砸中骨牌最多的那张牌即可（当然这里也有递推关系）。使用线段树维护每一个骨牌的dp值，每次查询的时候首先二分$[x_i+1,x_i+h_i-1]$（即受到当前骨牌影响的骨牌）中的下标$aim$，然后在线段树上查询$[pos+1, aim]$内dp值最大的下标id$，对于每一个骨牌$i$，答案为这个骨牌右边的dp值+这个骨牌左边至$i$骨牌中的骨牌数量$id-pos-1+dp$。

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

using LL = long long;
using PLL = pair<LL, LL>;
using Node = struct {
  LL x, h, id;
};
const int maxn = 200100;
int n;
Node p[maxn];
LL dp[maxn];

#define lrt rt << 1
#define rrt rt << 1 | 1
LL seg[maxn<<4], id[maxn<<4];

void pushup(LL rt) {
  if(seg[lrt] > seg[rrt]) {
    seg[rt] = seg[lrt];
    id[rt] = id[lrt];
  }
  else {
    seg[rt] = seg[rrt];
    id[rt] = id[rrt];
  }
}

void build(LL l, LL r, LL rt) {
  if(l == r) {
    seg[rt] = 1;
    id[rt] = l;
    return;
  }
  LL m = (l + r) >> 1;
  build(l, m, lrt);
  build(m+1, r, rrt);
  pushup(rt);
}

void update(LL x, LL p, LL l, LL r, LL rt) {
  if(l == r) {
    seg[rt] = x;
    return;
  }
  LL m = (l + r) >> 1;
  if(p <= m) update(x, p, l, m, lrt);
  else update(x, p, m+1, r, rrt);
  pushup(rt);
}

PLL query(LL L, LL R, LL l, LL r, LL rt) {
  if(L <= l && r <= R) {
    return make_pair(seg[rt], id[rt]);
  }
  LL m = (l + r) >> 1;
  PLL ret = make_pair(-1, -1);
  if(L <= m) {
    ret = max(ret, query(L, R, l, m, lrt));
  }
  if(R > m) {
    ret = max(ret, query(L, R, m+1, r, rrt));
  }
  return ret;  
}

LL gao(LL pos) {
  LL l = pos + 1, r = n;
  LL hi = p[pos].x + p[pos].h - 1;
  LL aim = -1;
  while(l <= r) {
    int m = (l + r) >> 1;
    if(p[m].x <= hi) {
      aim = m;
      l = m + 1;
    }
    else r = m - 1;
  }
  if(aim == -1) return 0;
  PLL id = query(pos+1, aim, 1, n, 1);
  return (id.second - pos - 1) + id.first;
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  int T;
  scanf("%d", &T);
  while(T--) {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
      cin >> p[i].x >> p[i].h;
      p[i].id = i;
      dp[i] = 1;
    }
    sort(p+1, p+n+1, [](Node a, Node b) {
      return a.x == b.x ? a.h < b.h : a.x < b.x;
    });
    build(1, n, 1);
    for(int i = n - 1; i >= 1; i--) {
      dp[i] += gao(i);
      update(dp[i], i, 1, n, 1);
    }
    vector<LL> ret; ret.resize(n+1);
    for(int i = 1; i <= n; i++) {
      ret[p[i].id] = dp[i];
    }
    
    for(int i = 1; i <= n; i++) {
      printf("%lld%c", ret[i], ' ');
    }
    printf("\n");
  }
  return 0;
}