2016-E08-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||TaZoF||J||WA|| || ||G++||1195||2016-09-29 19:34:54||
||TaZoF||B||AC||3312||31||G++||1530||2016-09-29 18:18:39||
||TaZoF||F||TLE|| || ||G++||1675||2016-09-29 18:06:44||
||TaZoF||F||TLE|| || ||G++||1533||2016-09-29 18:02:47||
||TaZoF||B||WA|| || ||G++||1527||2016-09-29 17:43:52||
||TaZoF||B||WA|| || ||G++||1525||2016-09-29 17:33:49||
||TaZoF||A||AC||1420||15||G++||413||2016-09-29 16:20:15||
||TaZoF||C||AC||1412||78||G++||425||2016-09-29 15:52:34||

== 流水账 ==
=== TsReaper ===
开场我们很快发现B和C都比较可做。因为我7月选过类似B题的题目，所以很快就推出了做法，但是我们并不会大组和数取模，只好先放着...C题我们通过打表发现了sg函数的规律，'''C1y27'''。很快A题我们也通过打表发现了规律，'''A1y55'''。

后面就...不会做了- -我们分别开过H，F和K，但是都没有思路。后来hzf学长在一本书上找到了Lucas定理，我在几个特殊情况处理之后'''B3y173'''。之后我联想到以前一个CF题，猜想了J的一个结论，starve学长用这个结论写了搜索但是似乎没有过...

== 总结 ==

== 题解 ==
A和C都是打表大法好...

=== B - A Simple Chess ===
容易发现棋子每次只有两种移动方式：要么从(x,y)走到(x+2,y+1)，要么从(x,y)走到(x+1,y+2)。设棋子从(0,0)走到(x,y)的过程中，x方向走了a次+2，那么y方向就走了a次+1，x方向走了x-2a次+1，y方向走了x-2a次+2。联立起来得到a=(2x-y)/3。所以走过去的方案数就是C(x-a,a)，要求a>=0，2x-y>=0，2y-x>=0和3|(2x-y)。

接下来就和7月的那个题目差不多了，可以翻翻7月的ppt，以及大组合数取模用Lucas定理。

=== H - To My Girlfriend ===
感觉记状态的方式比较奇怪...记f(i,j,a,b)为用前i个物品凑出重量恰为j，而且前i个物品中有a个必选，b个必不选的方案数。那么转移就有以下三种：

第i个物品可选可不选，f(i,j,a,b) += f(i-1,j,a,b) + f(i-1,j-w(i),a,b)。

第i个物品必选，f(i,j,a,b) += f(i-1,j-w(i),a-1,b)。

第i个物品必不选，f(i,j,a,b) += f(i-1,j,a,b-1)。

== 补题 ==
=== TsReaper ===
F, ~~H~~, J
UserProblemResultMemoryTimeLanguageLengthSubmit Time
TaZoFJWA G++11952016-09-29 19:34:54
TaZoFBAC331231G++15302016-09-29 18:18:39
TaZoFFTLE G++16752016-09-29 18:06:44
TaZoFFTLE G++15332016-09-29 18:02:47
TaZoFBWA G++15272016-09-29 17:43:52
TaZoFBWA G++15252016-09-29 17:33:49
TaZoFAAC142015G++4132016-09-29 16:20:15
TaZoFCAC141278G++4252016-09-29 15:52:34

流水账

TsReaper

开场我们很快发现B和C都比较可做。因为我7月选过类似B题的题目，所以很快就推出了做法，但是我们并不会大组和数取模，只好先放着...C题我们通过打表发现了sg函数的规律，C1y27。很快A题我们也通过打表发现了规律，A1y55。

后面就...不会做了- -我们分别开过H，F和K，但是都没有思路。后来hzf学长在一本书上找到了Lucas定理，我在几个特殊情况处理之后B3y173。之后我联想到以前一个CF题，猜想了J的一个结论，starve学长用这个结论写了搜索但是似乎没有过...

总结

题解

A和C都是打表大法好...

B - A Simple Chess

容易发现棋子每次只有两种移动方式：要么从(x,y)走到(x+2,y+1)，要么从(x,y)走到(x+1,y+2)。设棋子从(0,0)走到(x,y)的过程中，x方向走了a次+2，那么y方向就走了a次+1，x方向走了x-2a次+1，y方向走了x-2a次+2。联立起来得到a=(2x-y)/3。所以走过去的方案数就是C(x-a,a)，要求a>=0，2x-y>=0，2y-x>=0和3|(2x-y)。

接下来就和7月的那个题目差不多了，可以翻翻7月的ppt，以及大组合数取模用Lucas定理。

H - To My Girlfriend

感觉记状态的方式比较奇怪...记f(i,j,a,b)为用前i个物品凑出重量恰为j，而且前i个物品中有a个必选，b个必不选的方案数。那么转移就有以下三种：

第i个物品可选可不选，f(i,j,a,b) += f(i-1,j,a,b) + f(i-1,j-w(i),a,b)。

第i个物品必选，f(i,j,a,b) += f(i-1,j-w(i),a-1,b)。

第i个物品必不选，f(i,j,a,b) += f(i-1,j,a,b-1)。

补题

TsReaper

F, H, J

附加文件