CF243A The Brand New Function

CF243A The Brand New Function

洛谷传送门

题意翻译

题目大意

Polycarpus有一个由n个非负整数组成的序列

我们定义函数f(l,r)(1 \le l,r \le n)f(l,r)(1≤l,rn),表示序列的子串[l,r]各项的“或”和:f(l,r)=a_l|a_{l+1}|⋯|a_rf(l,r)=a**la**l+1∣⋯∣a**r

Polycarpus在纸上写下了所有的f(l,r)的值,他想知道他写下了多少个不同的值

输入

第一行1个整数n(1 \le n \le 10^5)n(1≤n≤105),表示序列a的元素个数。

第二行nn个整数,表示序列各项元素a_i(0 \le a_i \le 10^6)a**i(0≤a**i≤106)。

输出

输出f(l,r)f(l,r)有多少个不同的值。

样例解释

第一个样例中:66个f(l,r)f(l,r)分别为:f(1,1)=1,f(1,2)=3,f(1,3)=3,f(2,2)=2,f(2,3)=2,f(3,3)=0f(1,1)=1,f(1,2)=3,f(1,3)=3,f(2,2)=2,f(2,3)=2,f(3,3)=0。有4种不同的值:00, 11, 22, 33.


题解:

一开始想维护一棵线段树+遍历线段树。

过了所有样例,但是假了,因为线段树维护的区间并不是全部区间,所以不能直接这么维护。

于是开始想推性质。思考每次转移会对答案造成何种影响。失败。

最后看题解之后发现可以直接暴力枚举+剪枝。

很容易发现,暴力是\(n^2\)的。但是可以剪枝。当一个数各位都是1的话,怎么或都没有用了,直接剪枝。

代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
int a[maxn],n;
set<int>s;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		int x=a[i],y=0;
		s.insert(x);
		for(int j=i+1;j<=n;j++)
		{
			x|=a[j];
			y|=a[j];
			s.insert(x);
			if(x==y)
				break;
		}
	}
	printf("%d\n",s.size());
	return 0;
}
上一篇:学习笔记(32):4天速学JAVA面向对象-封装的具体实现


下一篇:桥接