【54.38%】【BZOJ 4300】绝世好题
BZOJ 好题
2023-09-14 09:03:46 时间
Submit: 1120 Solved: 609
[Submit][Status][Discuss]
Description
给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。
Input
输入文件共2行。
第一行包括一个整数n。
第二行包括n个整数,第i个整数表示ai。
Output
输出文件共一行。
包括一个整数,表示子序列bi的最长长度。
Sample Input
3
1 2 3
1 2 3
Sample Output
2
HINT
n<=100000,ai<=2*10^9
Source
【题解】
设f[i],二进制中倒数第i位为1的数(其他位置不一定)所形成的数列的最长长度;
【代码】
#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 101000; int n,ans = 0; int x; int f[31] = { 0 }; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &x); int temp = 0; for (int j = 0; j <= 30; j++) if (x & (1 << j)) temp = max(temp, f[j] + 1); for (int j = 0; j <= 30; j++) if (x & (1 << j)) f[j] = temp; ans = max(ans, temp); } printf("%d\n", ans); return 0; }
相关文章
- BZOJ 1695 [Usaco2007 Demo]Walk the Talk 链表+数学[通俗易懂]
- SP11444 MAXOR - MAXOR & bzoj 2741 【FOTILE模拟赛】L
- bzoj 4399: 魔法少女LJJ 题解
- bzoj 1052: [HAOI2007]覆盖问题 & Luogu P2218 [HAOI2007]覆盖问题 题解
- Luogu P2493 [SDOI2011]贪食蛇 & bzoj 2284. [Sdoi2011]贪食蛇 题解
- bzoj 3091 & Luogu P4842 城市旅行 题解
- bzoj 2959 长跑 题解
- bzoj 3653 谈笑风生 题解
- bzoj 3209 & Luogu P4317 花神的数论题 题解
- bzoj 1858. [Scoi2010]序列操作 题解
- bzoj 4337 BJOI2015 树的同构
- bzoj 4491. 我也不知道题目名字是什么 题解
- bzoj 2006. [NOI2010]超级钢琴 题解