brz的杯子

NC212174. brz的杯子

描述

蒟蒻 $\text{brz}$ 有 n 只杯子，现在 $\text{lzyking}$ 拿了一些数字，要求蒟蒻 $\text{brz}$ 装到杯子里。

$\text{lzyking}$ 拿了 1 ~ m 这些数字，每个数字有无限个，但每个杯子里只能放一个数。 $\text{lzyking}$ 很挑剔，对于两个编号为 x,y 的杯子，假如满足 $y|x,y\neq x$ ，那么第 x 个杯子里的数一定要比第 y 个杯子里的大。
但是小蒟蒻 $\text{brz}$ 不知道到底存不存在一个放数字的方案，所以只好求助于你。

输入描述

第一行一个整数，表示有T次询问。

每组询问内有两个整数n,m，意义如上所述。

$1\leq T\leq 10^6,1\leq n,m\leq 10^9$

输出描述

对于第 i 个询问，如果存在一个放数字的方案，那么贡献为 i，否则为 i-1，令 ans 等于所有询问的贡献异或和，最后你只需要输出 ans 即可。

示例1

输入:

2
3 3
2 1

输出:

说明:

对于第一组样例，可以在第一个杯子里放 1，在第二个杯子里放 2，在第三个杯子里放 3，贡献为 1。

对于第二组样例，在第一个杯子里放 1 后，由于第二个杯子里的数要比第一个杯子里的数大，但是又没有比 1 大的数可以放了，所以不存在一种方案，贡献为 2-1=1。

答案为 1 xor 1=0。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 292ms, 内存消耗: 388K, 提交时间: 2020-11-06 19:10:41

#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans;
int main(){
	scanf("%d",&t);
	for(int i=0;i<t;i++){
		scanf("%d%d",&n,&m);
		ans^=log2(n)<m?i+1:i;
	}
	printf("%d",ans);
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 1625ms, 内存消耗: 32280K, 提交时间: 2020-11-07 21:00:57

ans=0
for _ in range(1,int(input())+1):
    n,m=map(int,input().split())
    if(n.bit_length()<=m):
        ans^=_
    else:
        ans^=_-1
print(ans)

上一题

下一题

详情