「LibreOJ Round #8」MINIM

#### 题目描述

NIM is a game of strategy in which two players take turns removing stones from distinct piles. On each turn, a player must remove at least one stone, and may remove any number of stones provided they all come from the same pile. The player who has no stones to remove loses.

There are $n$ piles of stones, the $i$-th pile has $l_i$ stones. Alice needs to remove some of the stones from each pile (removing zero or all of the stones from a certain pile is allowed). If the $i$-th pile remains at least one stone after this operation, Alice has to pay a price of $v_i$. After Alice’s operation, Bob will create a pile of stones whose number is in $[0,m]$ and add it to the game to make sure that Alice — the player who moves first in this NIM game will lose.If he can’t ensure that Alice will lose,he will exit from the game immediately.

Now Alice has $q$ queries. Each query gives an integer $c$, and you need to calculate the minimal total price Alice needs to pay to ensure Bob’s new pile has exactly $c$ stones(making Bob exit from the game isn’t allowed,even if $c=0$). If this is impossible, print -1 instead.

#### 输入格式

The first line contains two integers $n,m$.
Each of the following $n$ lines contains two integers $v_i,l_i$.
The next line contains an integer $q$. Each of the following $n$ lines contains an integers $c$.

#### 输出格式

Output contains $q$ lines,containing the answer of each query in order.

#### 样例

##### 样例输入 Sample Input
4 6
2 3
4 4
3 5
5 2
7
0
1
2
3
4
5
6

##### 样例输出 Sample Output
0
2
2
2
3
3
5


#### 数据范围与提示

Subtask # 分值（百分比） $n,q$ $l_i,m$ 特殊性质
1 15 $\leq 10$ $\leq 10$ -
2 20 $\leq 100$ $\leq 100$ -
3 20 - - 对于每个 $i$ 存在非负整数 $k$ 满足 $l_i=2^k-1$
4 20 $\leq 20000$ $\leq 20000$ $l_i,v_i$ 在范围内均匀随机（使用 std::mt19937 并对最大值取模）
5 25 - - $l_i,v_i$ 在范围内均匀随机（使用 std::mt19937 并对最大值取模）

## 题解

35pts

55pts

### Subtask 4 & 5

CommonAnts的证明是这样的

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void gmin(int &a, int b) { if (a > b) a = b; }
const int MAXN = 100005;
int M;
struct data
{
int v, l;
data(int _v = 0, int _l = 0) : v(_v), l(_l) {}
data operator + (const data &a) const
{
data c(v + a.v, l | a.l);
for (int i = M; i >= 0; i--)
if (l & a.l & (1 << i))
{
c.l |= ((1 << (i + 1)) - 1);
break;
}
return c;
}
bool operator < (const data &a) const
{
return v < a.v;
}
}a[MAXN], s[MAXN], t[MAXN], tmp[MAXN];
int cnt, len;
int Calc(int x)
{
for (int i = 1; i <= cnt; i++)
if (s[i].l >= x)
return s[i].v;
return -1;
}
int main()
{
// freopen ("1.out", "w", stdout);
int n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i].v = read(), a[i].l = read();
for (M = 31; M && (1 << (M - 1)) >= m; M--);
s[++cnt] = data(0, 0);
tmp[0] = data(0, -1);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= cnt; j++)
t[j] = s[j] + a[i];
len = 0;
int j = 0, k = 0, l;
while (j < cnt || k < cnt)
{
data tp = j >= cnt ? t[++k] : (k >= cnt ? s[++j] : s[j + 1] < t[k + 1] ? s[++j] : t[++k]);
for (l = 1; l <= len; l++)
if (tmp[l].l >= tp.l)
break;
if (l == len + 1)
tmp[++len] = tp;
}
for (int j = 1; j <= len; j++)
s[j] = tmp[j];
cnt = len;
}
int q = read();
while (q--)
{
printf ("%d\n", Calc(read()));
}
}