ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 正文

[AtCoder Beginner Contest 261]E - Many Operations(Bitset + 思维)

2022年7月25日 198点热度 0人点赞 0条评论

题目链接:E - Many Operations (atcoder.jp)

题目 / Problem

给定N个操作,每个操作有3种模式,与运算、或运算、异或运算,数字x初始化为C,到第i层操作的时候将x按顺序执行一遍[1, i]的所有操作,问每次完成一层后x的值。

思路 / Thought

可以将数字x的每一个二进制位都维护一个函数f[i][0 / 1],表示初始为0 / 1的二进制位上的数字经过前i次操作后变成了什么数字。

复杂度为O(W * N),W就是二进制位数,选个30就够用了。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
bitset<32> f[2];

signed main()
{
	ios::sync_with_stdio(0);
	int N, C;scanf("%lld %lld", &N, &C);
	f[1] = (1LL << 31) - 1;
	bitset<32> x(C);
	for(int i = 1;i <= N; ++ i)
	{
		int T, A;scanf("%lld %lld", &T, &A);
		if(T == 1)
			f[0] = f[0] & bitset<32>(A), f[1] = f[1] & bitset<32>(A);
		else if(T == 2)
			f[0] = f[0] | bitset<32>(A), f[1] = f[1] | bitset<32>(A); 
		else if(T == 3)
			f[0] = f[0] ^ bitset<32>(A), f[1] = f[1] ^ bitset<32>(A);
		
		int ans = 0;
		for(int j = 30;j >= 0; -- j)ans = ans << 1 | (x[j] = f[x[j]][j]);
		printf("%lld\n", ans);
	}
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder bitset C++ 思维
最后更新:2022年7月25日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号