首页 > 其他分享 >CF--841--C

CF--841--C

时间:2022-12-28 12:00:10浏览次数:49  
标签:cnt cout 841 -- CF int 异或 查找

关键

当时确实是想到了使用减法,但是没有想明白怎么快速查找异或为n*n的这种数
其实也就是反向查找xaa=x,也就异或两次后就不变了,在异或一次,其实也就是把前面的某段区间给去掉了
所以可以保证时间复杂度是够的
基于后面的这个数,快速查找前面的数

代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int M=1e6+5;

vector<int>v;
int a[M],cnt[M];

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=0;i*i<=400000;i++)
        v.push_back(i*i);
    int TT;cin>>TT;
    while(TT--) {
        int n;cin>>n;
        ll ans=1ll*n*(n+1)/2;
        cnt[0]=1;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            a[i]^=a[i-1];
            for(auto x:v) {
                if((x^a[i])>=2*n)break;
                ans-=cnt[a[i]^x];
            }
            cnt[a[i]]++;
        }
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)cnt[a[i]]=0;
    }
    return 0;
}
//也就是记录前缀和,算一下如果他们的异或是这个完全平方数
//需要在前面加一个怎么样的数
//这样子也可以达到枚举所有区间的目的
//也就是反向查找区间

标签:cnt,cout,841,--,CF,int,异或,查找
From: https://www.cnblogs.com/basicecho/p/17009829.html

相关文章

  • 3D数字化展示文物,用科技力量传达历史文化
    互联网技术的高速发展和数字化时代的到来促使信息传播方式改变、用户文化需求多样化,博物馆在传播文化方面倍感压力,在这样的背景下,博物馆展览急需运用数字化手段来设计布展,......
  • 启明智显2.4寸串口屏应用于电热水瓶方案
    受国内大多居民喝煮沸后的自来水的生活习惯影响,热水壶市场常年保持着较高的销量,其中新增需求和家庭更新换代是主要的市场需求动力。但热水壶存在结构简单、功能单一等问题,......
  • Linux用户和组管理
    相关系统文件/etc/passwd#保存用户信息的文件/etc/shadow#保存用户密码相关信息的文件/etc/group#保存组信息的文件/etc/gshadow......
  • 交叉编译esp8089
    交叉编译esp8089编译环境:硬件:全志R528ubuntu:Linuxubuntu4.15.0-194-generic#205-UbuntuSMPFriSep1619:49:27UTC2022x86_64x86_64x86_64GNU/Lin......
  • idea设置JDK无效
    目录问题背景解决方案01首先检查idea设置是否正确02清一下idea缓存ps:原文链接:idea设置JDK无效问题背景修改完idea的一些设置后,重启idea后,项目开始爆红,提示找不......
  • 第一本书-自学大全【微信读书】
    【序】 <作为一名自律的学习者,自学者必须根据自己的变化来重新规划自己的学习>所谓的自律,我真的能做到吗??<人类是一种不可救药的生物,他们虽然能够达成月球漫步这样的伟......
  • 表中的列和实体类的属性不一致解决方法
    1.数据库和java项目实体类的属性不一样,使用别名来解决   在java中   2.使用resultMap来解决数据库和java实体类属性不一致的问题    ......
  • 青少年CTF练习9
    T9  哥哥打篮球(经典小黑子)题目描述:你想想怎么把篮球和鸡,联系起来?flag格式为qsnctf{}(对此我只能说6)打开靶机    太6了!!!然后在调试器中找到js源代码,直接......
  • 驼峰转换
    css           jsfont-size     fontSize数据库列 实体类属性 stu_sid stuSid使用settings来设置驼峰转换 ......
  • 使用EB配置Spi驱动
    概述SPI驱动程序只在主模式和全双工通信模式下工作。驱动程序支持同步和异步通信,支持Level-0, Level-1和Level-2类型配置。Level等级和同/异步通信,传输seq,传输job,传......