题解 [美团2018年CodeM大赛-复赛 A] 子序列
子序列
https://ac.nowcoder.com/acm/problem/17065
题目描述
给定一个序列,问有多少子序列满足 。
正解
这种子序列里面元素不独立的题一般不好做,考虑如何将元素的值独立。
现在 和
的值独立了,发现原问题就是求一个上升子序列个数。
用树状数组单点加,区间求和可以做到 。
注意到 并不是整数,但其实只要知道相对大小就行,即还需要离散化。
代码
#include <bits/stdc++.h> #define N 105 using namespace std; const int mod = 1e9 + 7; const double eps = 1e-10; int n; int a[N]; namespace BIT { #define lowbit(x) (x & -x) int c[N]; inline void update(int p, int v) { for(int i = p; i <= n; i += lowbit(i)) c[i] = c[i] + v; } inline int query(int p) { int res = 0; for(int i = p; i; i -= lowbit(i)) res = res + c[i]; return res; } #undef lowbit } struct node { int id; double x; }A[N]; bool cmp(const node &u, const node &v) { return u.x < v.x; } int main() { scanf("%d", &n); for(int i = 1, x; i <= n; ++i) { scanf("%d", &x); A[i].id = i, A[i].x = log(x) / i; } A[0].x = -1; sort(A + 1, A + n + 1, cmp); for(int i = 1, rk = 0; i <= n; ++i) { if(A[i].x - A[i - 1].x > eps) ++rk; a[A[i].id] = rk; } for(int i = 1; i <= n; ++i) BIT::update(a[i], BIT::query(a[i] - 1) + 1); printf("%d\n", BIT::query(n)); return 0; }