VIP-拔钉子之路-with ydnhaha-解题报告
i207M
2018-10-26 15:54:24
## [POI2016]Nim z utrudnieniem
A和B两个人玩游戏，一共有m颗石子，A把它们分成了n堆，每堆石子数分别为a[1],a[2],...,a[n]，每轮可以选择一堆石子，取掉任意颗石子，但不能不取。谁先不能操作，谁就输了。在游戏开始前，B可以扔掉若干堆石子，但是必须保证扔掉的堆数是d的倍数，且不能扔掉所有石子。A先手，请问B有多少种扔的方式，使得B能够获胜。
第一行包含两个正整数n,d(1<=n<=500000,1<=d<=10)。
第二行包含n个正整数a[1],a[2],...,a[n]，(1<=a[i]<=1000000)。
本题中m不直接给出，但是保证m<=10000000。
首先将题意转化为，从n个数中选取d的倍数个，使得异或出来等于s的方案数；
暴力的DP：$f[i][j][k]$表示前i个选了%d=j个，异或为k的方案数，感觉过不去？
先考虑时间：我们按a升序排序，这样异或出来的最大数不会超过2a，所以总复杂度$O(dm)$
空间：滚动数组都过不去！于是用tmp记一下$f[i-1][0][...]$即可；
```
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
#endif
in(n),in(d); dm=d-1;
for(ri i=1;i<=n;++i) in(a[i]),s^=a[i];
sort(a+1,a+1+n);
f[0][0]=1;
for(ri i=1,mx=1;i<=n;++i)
{
while(mx<=a[i]) mx<<=1;
for(ri j=0;j<mx;++j) tmp[j]=f[dm][j];
for(ri j=d-1,t;j>=1;--j)
{
t=j-1;
for(ri k=0;k<mx;++k)
add(f[j][k],f[t][k^a[i]]);
}
for(ri k=0;k<mx;++k)
add(f[0][k],tmp[k^a[i]]);
}
printf("%d\n",(f[0][s]-(n%d==0)+md)%md);
return 0;
}
```
## [POI2004]MOS
一个夜晚一些旅行者想要过桥. 他们只有一个火把. 火把的亮光最多允许两个旅行者同时过桥. 没有火把或者多于2个人则不能过桥.每个旅行者过桥都需要特定的时间, 两个旅行者同时过桥时时间应该算较慢的那个. 我们想知道所有旅行者最少要花费多少时间才能全部过桥?
想这题时，想到了正解一定是最快的两个人来回交替走，但是接下来思路就不清晰了；
我们考虑利用时间最小的两个人倒运，把时间大的人依次送过去
有两种方式：
1.时间最小的人和时间最大的人过去，然后时间最小的人把火把拿回来
2.时间最小和第二小的两个人过去，然后时间最小的人把火把拿回来；接着时间最大和第二大的两个人过去，时间第二小的人把火把拿回来
```
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
#endif
in(n);
for(ri i=1;i<=n;++i) in(a[i]);
if(n<=2)
{
printf("%lld",a[n]);
return 0;
}
for(ri i=n-1;i>=2;--i)
{
f[i]=f[i+1]+a[1]+a[i+1];
if(i+2<=n) f[i]=min(f[i],f[i+2]+a[2]+a[1]+a[i+2]+a[2]);
}
printf("%lld",f[2]+a[2]);
return 0;
}
```
## POI2017 Prawnicy (pra)
~~仙呐，仙呐~~
题意，，，懒得写了；
核心是：给定多个区间，每次询问一个区间，问它被多少个区间包含；而且询问区间的端点单调递增；
对于询问的左右区间遇到左右端点时分类讨论，统计贡献；
网上题解：对于一个左端点，选右端点前k大，用堆；
```cpp
int count(int l,int r)
{
while(cl<l)
{
++cl;
for(ri i=0;i<st[cl].size();++i)
if(st[cl][i].fi>=cr)
{
if(!ap[st[cl][i].se])
{
ap[st[cl][i].se]=1;
++cnt;
}
}
}
while(cr<r)
{
for(ri i=0;i<en[cr].size();++i)
if(ap[en[cr][i].se])
{
ap[en[cr][i].se]=0;
--cnt;
}
++cr;
for(ri i=0;i<en[cr].size();++i)
if(en[cr][i].fi<=cl)
{
if(!ap[en[cr][i].se])
{
ap[en[cr][i].se]=1;
++cnt;
}
}
}
return cnt;
}
```