Type: Default

File IO: xor

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一长度为 $N$ 的由非负整数组成的数组 $a$ ，你需要进行一系列操作，每次操作选择一个区间 $[l,r]$ ，将 $a_{[l,r]}$ 异或上 $w$ 。你需要将 $a_i$ 全部变为 $0$ 。

求最小操作次数。

输入格式

第一行输入一个正整数 $N$ ；

第二行输入 $N$ 个非负整数表示 $a_i$ 。

输出格式

输出一行最小操作次数。

样例1

输入样例

6
7 6 4 1 3 5

输出样例

样例解释

操作编号	$l=$	$r=$	$w=$	操作后数组
$1$	$3$	$4$	$2$	$[7,6,6,3,3,5]$
$2$	$1$	$5$	$7$	$[0,1,1,4,4,5]$
$3$	$2$	$5$	$1$	$[0,0,0,5,5,5]$
$4$		$6$	$5$	$[0,0,0,0,0,0]$

可以证明，操作次数相同的方案不止这一个，但是不存在操作次数更少的方案。

数据范围

$1\le N\le17$ ；

$0\le a_i\le1\times10^{18}$

Subtask 编号	数据点编号	特殊性质	分值
$1$	$[1,5]$	$N,a_i\le3$	$10$
$2$	$[6,10]$	$N\le3,a_i\le31$	$15$
$3$	$[11,15]$	$N\le7$	$20$
$4$	$[16,25]$	无特殊性质	$55$

NOIP 模拟赛（五）

Not Attended

Status: Done
Rule: OI
Problem: 4
Start at: 2023-11-2 8:00
End at: 2023-11-2 12:00
Duration: 4 hour(s)
Host: 梁泽贤 (liangzexian)
Partic.: 11

#B. 异或(xor)

异或(xor)

题目描述

输入格式

输出格式

样例1

输入样例

输出样例

样例解释

数据范围

NOIP 模拟赛（五）

Status

Development

Support

#B. 异或(xor)

异或(xor)

题目描述

输入格式

输出格式

样例1

输入样例

输出样例

样例解释

数据范围

NOIP 模拟赛（五）

Status

Development

Support

Don't have an account?

SIGN IN