HDU5389 – Zero Escape(01背包)

HDU5389

【题意】有n个人，每个人都有一个值[1,9],现在两扇门，所有人都要进入其中一扇门，问最后进入两扇门的所有人价值之和的 digital root为门的值的所有可能情况。还有需要注意所有人都进入同一扇门也可以。

【分析】首先可以发现，一些数的和的digital root就是这些数之和MOD 9的值(为0时变成9)；然后因为同余就可以每次相加都求digital root和最后一起算digital root的值是相同的，这样就相当于背包容量为9的01背包，只是求的过程需要从前往后推；最后统计答案的时候：对于两扇门都满足的时候加上a和b的可能性的任意一个；对于只进同一扇门的时候如果digital root(a) == digital root(sum)则说明所有人可以都进入A门，而且只有一种情况，对于第二扇门也相同。

【AC CODE】124ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10,MAXIN = 10000, MOD = 258280327;
char buf[MAXIN], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe) pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;
	do{ rnext(); if('-' == *ps) f = -1;} while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;
	do{ ans = (ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
int dp[2][10];

int mymod(int x)
{
	int ans = x%9;
	if(!ans) ans = 9;
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	in(t);
	while(t--)
	{
		int n,x,y,sum = 0,a,now = 1;
		in(n);in(x);in(y);
		clc(dp,0);
		dp[now^1][0] = 1;
		repe(i,1,n)
		{
			in(a), sum += a, now ^= 1;
			memcpy(dp[now^1],dp[now],sizeof(dp[now]));
			repe(j,0,9)
			{
				int w = mymod(j+a);
				dp[now^1][w] = (dp[now^1][w]+dp[now][j])%MOD;
			}
		}
		int ans = 0;
		if(mymod(x+y) == mymod(sum))
		{
			ans += dp[now^1][y];
			if(x == mymod(sum)) ans--;
		}
		if(x == mymod(sum)) ans++;
		if(y == mymod(sum)) ans++;
		printf("%d\n", ans%MOD);
	}
	return 0;
}