牛客练习赛16 E - 求值

时间：2021-02-23 01:09:59

题目大意：

链接：https://www.nowcoder.com/acm/contest/84/E

给定n个数字a1, a2, ..., an。
定义f(l, r) = al | al+1| ... | ar。
现在枚举(1 <= l <= r <= n)，问不同的f值一共有多少个。

思路：确定一个 l 的情况下， 从 l 出发的的不同值最多只有20多个， 从后往前暴力更新就好啦。

 #include<bits/stdc++.h>

 #define LL long long

 #define pii pair<int,int>

 #define mk make_pair

 #define fi first

 #define se second

 using namespace std;

 const int N=1e5+;

 const int M=2e6+;

 const int inf=0x3f3f3f3f;

 const LL INF=0x3f3f3f3f3f3f3f3f;

 const int mod=1e9+;

 int n, a[N], ans;

 bool vis[M];

 set<int> st;

 vector<int> v[N];

 int main() {

     scanf("%d", &n);

     for(int i = ; i <= n; i++)

         scanf("%d", &a[i]);

     vis[a[n]] = true;

     v[n].push_back(a[n]);

     ans++;

     for(int i = n - ; i >= ; i--) {

         if(!vis[a[i]]) {

             vis[a[i]] = true;

             ans++;

         }

         st.insert(a[i]);

         for(int u : v[i + ]) {

             if(!vis[a[i] | u]) {

                 vis[a[i] | u] = true;

                 ans++;

             }

             st.insert(a[i] | u);

         }

         for(int u : st)

             v[i].push_back(u);

         st.clear();

     }

     printf("%d\n", ans);

     return ;

 }

 /*

 */

相关文章