[ICPC2024 Xi'an I] XOR Game

题目背景

statement updated:

$$$z$$$ is the number of numbers whose values are $$$0$$$.

题目描述

Alice and Bob are playing a game against each other.

In front of them are a multiset $$${a_i}$$$ of non-negative integers and a single integer $$$x$$$. Each number in $$$a$$$ is $$$0$$$ or $$$2^i(0\le i<k)$$$ before the game.

This game will be a turn-based game, and Alice will go first. In one person's turn, he or she will choose an integer from $$$a$$$. Let this number be $$$p$$$. Then this person will choose whether or not to make $$$x\gets x\oplus p$$$, then remove $$$p$$$ from $$$a$$$. Here, operation $$$\oplus$$$ means bitwise xor.

Alice wants to make $$$x$$$ as big as possible, and Bob wants to make $$$x$$$ as small as possible.

You are a bystander who wants to know the final value of $$$x$$$. However, the size of $$$a$$$ is a huge number. Formally, there are $$$b_i$$$ numbers whose values are $$$2^i$$$ in $$$a$$$ for all $$$0\le i<k$$$, and $$$z$$$ numbers whose values are $$$0$$$. But you still want to challenge this impossible problem.

If Alice and Bob are smart enough, please output the final value of $$$x$$$.

输入格式

The first line contains two integers $$$k,z(1\le k\le10^5,0\le z\le 10^9)$$$.

The next line contains $$$k$$$ integers, the $$$i$$$ -th integer is $$$b_{i-1}(0\le b_{i-1}\le10^9)$$$.

输出格式

Output the answer in binary format. Note that you should output exactly $$$k$$$ digit from high to low even though this number has leading $0$s.

样例 #1

样例输入 #1

1 0
3

样例输出 #1

1

样例 #2

样例输入 #2

2 0
2 1

样例输出 #2

11

样例 #3

样例输入 #3

2 0
2 2

样例输出 #3

00

[ICPC2024 Xi'an I] Turn Off The Lights

题目描述

Kitty has $$$n^2$$$ lights, which form an $$$n\times n$$$ matrix.

One day, Kitty found that some of these lights were on, and some were off. Kitty wants to turn them all off.

To achieve her goal, Kitty can perform three types of operations:

• (1) Choose a row, reverse the state of this row. It means if a light of this row is on, after this operation, it is now off. If a light of this row is off, after this operation, it is now on.

• (2) Choose a column, reverse the state of this column. It means if a light of this column is on, after this operation, it is now off. If a light of this column is off, after this operation, it is now on.

• (3) Choose exactly one light, reverse the state of this light. This operation can only be performed not more than $$$k$$$ times.

For the current state, help Kitty achieve her goal within $$$3n$$$ operations.

输入格式

The first line contains two integers $$$n(1\leq n\leq 1000),k(0\leq k\leq n)$$$, indicating as described above.

Then $$$n$$$ lines follow, each line has exactly $$$n$$$ numbers, $$$0$$$ represents that the light is turned off at this time, while $$$1$$$ represents the opposite.

The $$$y$$$-th number of the $$$(x+1)$$$-th line in input means the light at coordinate $$$(x,y)$$$.

输出格式

If Kitty can not achieve her goal,print $$$-1$$$ in a single line.

Otherwise, print $$$M(0\leq M\leq 3n)$$$ in the first line, indicating the number of operations she needs to perform.

The next $$$M$$$ lines, each line contains $$$2$$$ integers $$$x,y$$$, separated by white space.

If $$$1\leq x\leq n,1\leq y\leq n$$$, it means Kitty will reverse the light at coordinate $$$(x,y)$$$.

If $$$x=0,1\leq y\leq n$$$, it means Kitty will reverse all lights at coordinates $$$(z,y)1\leq z\leq n$$$.

If $$$1\leq x\leq n,y=0$$$, it means Kitty will reverse all lights at coordinates $$$(x,z)1\leq z\leq n$$$.

If there are multiple answers, print any of them.

样例 #1

样例输入 #1

2 0
0 1
1 0

样例输出 #1

2
0 2
2 0

样例 #2

样例输入 #2

3 1
1 0 0
0 1 0
0 0 1

样例输出 #2

-1

[ICPC2024 Xi'an I] Make Them Straight

题目描述

There is a sequence $$$a$$$ of non-negative integers of length $$$n$$$, the $$$i$$$-th element of it is $$$a_i(1\leq i\leq n)$$$.

A sequence is defined as 'good' if and only if there exists a non negative integer $$$k(0\leq k\leq 10^6)$$$ that satisfies the following condition:

$$$a_{i}=a_{1}+(i-1)k$$$ for all $$$1\leq i\leq n$$$.

To make this sequence 'good', for each $$$i(1\leq i\leq n)$$$, you can do nothing, or pay $$$b_i$$$ coin to replace $$$a_i$$$ with any non-negative integer.

The question is, what is the minimum cost to make this sequence 'good'.

输入格式

The first line contains an integer $$$n(1\leq n\leq 2\times 10^5)$$$, described in the statement.

The second line contains $$$n$$$ integers $$$a_1,...,a_n(0\leq a_i\leq 10^6)$$$.

The third line contains $$$n$$$ integers $$$b_1,...,b_n(0\leq b_i\leq 10^6)$$$.

输出格式

One integer, the answer.

样例 #1

样例输入 #1

5
1 4 3 2 5
1 1 1 1 1

样例输出 #1

2

样例 #2

样例输入 #2

5
1 4 3 2 5
1 9 1 1 1

样例输出 #2

3