【USACO1.5】解题报告

前言

这章只有两道题，但是质量都不比上一章低。
第一题正解肯定很难，但是数据神奇般的把 $O(n^4)$ 即 $O(250^4)$ 的程序过掉了。。。
第二题标准的深搜。
USACO：http://train.usaco.org

1.5.2.Arithmetic Progressions

这里只能给出神奇的卡常解法。对于想找正解的 $OIer$ 们感到非常抱歉。
首先需要证明当 $n\geq 4$ 时有 $4|b$ 。这里给出题解的证明，非常简洁明了。

设 $p=a^2+b^2$
1.当 $a,b$ 为偶数。设 $a=2m,b=2m$ ，则 $p=4(m^2+n^2)$ 。
2.当 $a,b$ 一奇一偶。不妨令 $a=2m+1,b=2n$ ，则 $p=4(m^2+n^2+m)+1$
3.当 $a,b$ 为奇数。设 $a=2m+1,b=2n+1$ ，则 $p=4[m(m+1)+n(n+1)]+2$
由于 $m，m+1$ 中有1个偶数，故 $m(m+1)$ 为偶数，同理， $n(n+1)$ 为偶数，即 $m(m+1)+n(n+1)$ 为偶数，有 $p=8l+2$ （ $l$ 为自然数）
即 $p\bmod 4\neq 3$ .
即 $n>=4$ ， $b$ 为偶数.
若 $4\nmid b$ ，则 $a$ 为偶数。由于能写成 $8l+6$ 的形式的数无法写生两个完全平方数的和（ $8l+6=4(2l+1)+2$ ），即能 $8l+6$ 写成 $4l+2$ 的形式，但已证能写成 $4l+2$ 形式的数一定不是完全平方数），故 $a$ 为奇数，矛盾。
即 $4\mid b$ 。

那么就分成 $n<4$ 和 $n\geq 4$ 的两块，前者每次加1，后者每次加4就可以了。

代码：

/*
ID:ssl_zyc2
TASK:ariprog
LANG:C++
*/

#include <cstdio>
#define N 135010
using namespace std;

int n,m,p[N],maxn,ok,OK;

int main()
{
	freopen("ariprog.in","r",stdin);
	freopen("ariprog.out","w",stdout);
    scanf("%d%d",&n,&m);
    if (n<4)
    {
        for (register int i=0;i<=m;i++)
     	 for (register int j=0;j<=m;j++)
          p[i*i+j*j]=1;
        for (register int j=1;j<=m*m*2;j++)
         for (register int i=0;i<=m*m*2;i++)
         {
         	if (i+(n-1)*j>m*m*2) break;
         	ok=1;	
         	for (register int k=0;k<n;k++)
         	 if (!p[i+k*j]) 
         	 {
         	 	ok=0;
         	 	break;
         	 }
         	if (ok) 
         	{
         		printf("%d %d\n",i,j);
         		OK=1;
         	}
         } 
    }
    else
    {
        for (register int i=0;i<=m;i++)
         for (register int j=0;j<=m;j++)
          p[i*i+j*j]=1;
        for (register int j=4;j<=m*m*2;j+=4)
         for (register int i=1;i<=m*m*2;i++)
         {
         	if (i+(n-1)*j>m*m*2) break;
         	ok=1;	
         	for (register int k=0;k<n;k++)
         	 if (!p[i+k*j]) 
         	 {
         	 	ok=0;
         	 	break;
         	 }
         	if (ok) 
         	{
         		printf("%d %d\n",i,j);
         		OK=1;
         	}
         } 
    }
    if (!OK) printf("NONE\n");
    return 0;
}

1.5.3.Mother’s Milk

思路：

标准的深搜。每次有六种转移方法：

$A→B$
$A→C$
$B→A$
$B→C$
$C→A$
$C→B$
加上判重即可。

代码：

/*
ID:ssl_zyc2
TASK:milk3
LANG:C++
*/

#include <cstdio>
#define N 25
using namespace std;

bool p[N][N][N],num[N];
int x,y,z;

void dfs(int a,int b,int c)
{
	if (p[a][b][c]) return;
	p[a][b][c]=1;  //标记
	if (!a) num[c]=1;
	if (a>=y-b) dfs(a-(y-b),y,c);
	 else dfs(0,b+a,c);
	if (a>=z-c) dfs(a-(z-c),b,z);
	 else dfs(0,b,c+a);
	if (b>=x-a) dfs(x,b-(x-a),c);
	 else dfs(a+b,0,c);
	if (b>=z-c) dfs(a,b-(z-c),z);
	 else dfs(a,0,c+b);
	if (c>=x-a) dfs(x,b,c-(x-a));
	 else dfs(a+c,b,0);
	if (c>=y-b) dfs(a,y,c-(y-b));
	 else dfs(a,b+c,0);
}

int main()
{
	freopen("milk3.in","r",stdin);
	freopen("milk3.out","w",stdout);
	scanf("%d%d%d",&x,&y,&z);
	dfs(0,0,z);
	bool writed=0;
	for (int i=0;i<=z;i++)
	 if (num[i]) 
	 {
	 	if (writed) printf(" ");  //因为USACO不允许多余空格和换行，所以要小心
	 	printf("%d",i);
	 	writed=1;
	 }
	printf("\n");
	return 0;
}