天平

• 题目：
  物理老师 YJ 有一个长杆天平，天平的两臂长均为 15，将长杆看作 x 轴，
  则平衡点在 0 位置处，负数位置在左臂上，正数位置在右臂上。长杆上有 n 个
  位置有挂钩可以挂秤砣。YJ 有 m 个秤砣，质量分别为 gi，每个挂钩可以不挂也
  可以挂任意个秤砣。YJ 想要知道，在使用所有秤砣的条件下，有多少种不同的
  挂秤砣的方案，可以使得天平平衡？问题太过复杂，仅凭物理知识难以解决，
  所以请你来帮助他。
  天平的平衡条件是所有秤砣的位置质量之和为 0。例如有质量为 2,3,4 的
  秤砣分别挂在-3,-2,3 位置处，则 2(-3) + 3(-2) + 43 == 0，天平是平衡
  的。
• 10% 数据满足 2≤n,m≤4。100% 数据满足 2≤n,m≤20
• 唯一做出来的。类似背包，f[i][j]->考虑前i个秤砣现总重量为j的方案数.由于天平长度有负数，所以给所有
  杆长加上\(inf/2\)，转移方程为f[i][j]+=f[i-1][j-dis[k]*mg[i]]，最终答案为f[n][所有秤砣挂在中间位置的重量]

山峰数

• 题目:
  山峰数是指数字排列中不存在山谷(先降后升)的数，例如 0,5,13,12321 都
  是山峰数，101，1110000111 都不是山峰数。
  现给出 n 个数，请依次判断它们是否为山峰数，如果不是，输出-1。如果
  是，求出比它小的数中有多少个山峰数。
• 20% 数据满足 x ≤ \(10^6\)。100% 数据满足 n ≤ 10, x ≤ \(10^{60}\)
• 没做出来，从此可以看出我对数位DP还是一窍不通。实际上就是板子题，先判断是不是山峰数
  再记搜，加上last记上一位和down记是否在下降

粉刷匠2

• 有一个 4*N 的木板需要粉刷，第 i 行 j 列的颜色记为 A(i, j)。
  有 256 种颜色，记为 0..255，为了使得粉刷比较好看，粉刷需要满足如下m条要求:

1. A(x,y) >= A(x,y-1)
2. 有一些指定的(x1, y1)和(x2, y2)，要求 A(x1, y1) = A(x2, y2)
   请问有多少种满足要求的粉刷方式？输出答案的最后 5 位即可。

• 30% 数据满足 n ≤ 3，m = 0。 100% 数据满足 1 ≤ n ≤ 15，0 ≤ m ≤ 100，X1,X2≤4，Y1,Y2≤n
• 枚举已经处理到了i号颜色，f[a][b][c][d]表示1、2、3、4行分别从a、b、c、d位及后全部涂成i颜色
  对于要求，就设立一个vis数组，提前将不满足要求的dp状态标记，枚举到的时候就将其值标为0。
  状态转移如下所示

for(int k=1;k<=n;k++)
{
	for(int col=1;col<=4;col++)
	{
		for(int a=1;a<=n;a++)
		{
			for(int b=1;b<=n;b++)
			{
				for(int c=1;c<=n;c++)
				{
					for(int d=1;d<=n;d++)
					{
						long long tmp=f[a][b][c][d];
						if(col==1) a++;if(col==2) b++;if(col==3) c++;if(col==4) d++;
						f[a][b][c][d]=(f[a][b][c][d]+tmp)%p;
						if(col==1) a--;if(col==2) b--;if(col==3) c--;if(col==4) d--;
					}
				}
			}
		}
	}
	
}

棋盘

• 题目:
  有一个 N*M 的棋盘，要在上面摆上 knight，每个格子可以放至多一个国际象棋的马。
  所有 马不能互相攻击，请问总共有多少可行的摆法？答案对1000000007 取模
• 70% 数据满足 m≤100。100% 数据满足 t≤10, n≤3, m