四川第十届省赛 A.Angel Beats bitset
2024-08-31 20:19:57
四川第十届省赛 A.Angel Beats bitset
题解参考:http://www.cnblogs.com/Aragaki/p/9142250.html
考虑用bitset来维护对于所有的\(x\),需要翻转的位置。但是这样来搞的话,很难处理题目的要求。
所以换个角度,考虑翻转哪些位置会影响这一位。我们会发现,如果位置编号为某些数的公倍数,那么就会受到那些位置的影响。进一步深入想,其实会发现可以考虑只翻转某一位需要翻转哪些位置,这样的方案是唯一的。
设\(s[i]\)为只翻转第\(i\)位需要翻转哪些位置,那么\(s[i]=s[i]\) ^ \(s[2*i]\) ^ ... ^ \(s[k*i]\),因为翻转第\(i\)位会影响后面的位置,我们消去影响即可得只翻转第\(i\)位的位置。
之后就按照题意搞下就行了。
代码如下:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5, M = 1e5 + 5;
int T;
int n, m;
bitset <N> s[N], pre[N], ans;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m) ;
for(int i = 1; i <= n; i++) s[i].reset() ;
for(int i = n; i >= 1; i--) {
s[i].set(i) ;
for(int j = 2 * i; j <= n; j += i) s[i] ^= s[j] ;
}
for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ s[i] ;
ans.reset() ;
for(int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y) ;
ans ^= pre[x - 1] ^ pre[y] ;
printf("%d\n", ans.count()) ;
}
}
return 0;
}
最新文章
- Linux(Centos)之安装Java JDK及注意事项
- Linux x64 下 Matlab R2013a 300 kb 脚本文件调试的 CPU 占用过高问题的解决办法
- 虚拟化平台cloudstack(7)——新版本的调试
- Linux_CentOS6.5安装vncserver实现图形化访问
- 怎样避免 i f 判断过多,全复杂度较高,代码不美观的问题?
- 《微信小程序七日谈》- 第三天:玩转Page组件的生命周期
- ubuntu adb devices 找不到任何东西,安装驱动
- PHP开发APP接口(二)
- Python爬虫实战:使用Selenium抓取QQ空间好友说说
- Java注解开发与应用案例
- 2019年2月编程语言最新排行:java稳居第一(java优势在哪里)
- 用树莓派改装电风扇及实现Android遥控
- wpf z
- Maven学习日记(一)----构建web项目
- ContentProvider与ContentResolver
- 使用Json Template在Azure China创建ARM类型的虚拟机
- 小象学院Python数据分析第二期【升级版】
- 转载 ----Android学习笔记 - 蓝牙篇 (Bluetooth)
- mysql学习之基础知识
- (十三)maven之release和snapshots
热门文章
- JS 常见问题
- jquery设置bootstrap-table的当前选中页码的获取与设置
- 【Maven插件】exec-maven-plugin
- Docker方式安装SonarQube
- unable to find utility ";simctl";, not a developer tool or in PATH解决方案
- JMeter工具学习(二)——获取登录 token
- Jenkins-slave 镜像集成 docker 和 kubectl
- SQLServer --------- 将sql脚本文件导入数据库
- Vim 入门教程
- 第三节:EF Core上下文DbContext相关配置和生命周期