CF243A The Brand New Function
The Function New
2023-09-11 14:20:14 时间
CF243A The Brand New Function
题意翻译
题目大意
Polycarpus有一个由n个非负整数组成的序列
我们定义函数f(l,r)(1 \le l,r \le n)f(l,r)(1≤l,r≤n),表示序列的子串[l,r]各项的“或”和:f(l,r)=a_l|a_{l+1}|⋯|a_rf(l,r)=a**l∣a**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;
}
相关文章
- What are the Web.Debug.config and Web.Release.Config files for?
- cannot apply the specified columns kentico
- Found conflicts between different versions of the same dependent assembly that could not be resolved
- css footer not displaying at the bottom of the page
- 解决Maven打包时报错"The packaging for this project did not assign a file to the build artifact"
- English trip V2 - 23 Planning for the Future 为未来筹划 Teacher: Corrine
- The connection to the server ip:6443 was refused - did you specify the right host or port
- The last access date is not changed even after reading the file on Windows 7
- 程序员2020年新书推荐之 《Coders: The Making of a New Tribe and the Remaking of the World》
- The library 'xxx.jar' contains native libraries that will not run on the device. 解决方法(Eclipse)
- Unity 报错之 The type or namespace name ‘UI‘ does not exist in the namespace ‘UnityEngine‘
- Solve Warning: The elevation provided <Paper elevation={24}> is not available in the theme.
- Eclipse中使用MySql遇到:Loading class `com.mysql.jdbc.Driver'. This is deprecated. The new driver class is `com.mysql.cj.jdbc.Driver'. The driver is automatically registered via the SPI and manual loading o
- 1144 The Missing Number
- * resolve_conffiles: Existing conffile /etc/config/dhcp is different from the conffile in the new package. The new conffile will be placed at /etc/config/dhcp-opkg.