刷题记录（NC24623 Tree Decoration，NC16612 [NOIP2009]靶形数独，NC16665 [NOIP2004]虫食算）

NC24623 Tree Decoration

题目链接

关键点：

1、从根开始往下搜，搜到子节点，在满足子节点的情况下，看每一个父亲结点是否还需要装饰，如果需要就从他儿子里面找花费最少的，在那个特定的结点上装上装饰，所以每一次的遍历都要找孩子结点花费最小的

# include 
using namespace std;
typedef long long ll;
const int N = 100000+10;
ll fa[N], c[N], t[N], sz[N];
int n, root;
vectorint> >ve(N);
ll find(int x)
{
//     cout<<1<
    ll ans = 0;
    for (int i=0; isize(); i++)
    {
        int a = ve[x][i];
        ans += find(a);
        sz[x] += sz[a];
        t[x] = min(t[x], t[a]);
    }
    if (sz[x] < c[x])
    {
        ans += (c[x]-sz[x])*t[x];
        sz[x] = c[x];
    }
    return ans;
}
int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>fa[i]>>c[i]>>t[i];
//         cout<<"1"<
        if (fa[i] == -1)
            root = i;
        else
        {
            ve[fa[i]].push_back(i);
        }
    }
//     cout<<1<
    cout<<find(1);
    return 0;
}

NC16612 [NOIP2009]靶形数独

题目链接

关键点:

1、首先还是采用数独题目的做法，主要是如何优化

2、我们可以采用对每一行的空格进行优化，先从空格最少的行开始搜索

# include 
using namespace std;
struct ty{
	int hang, kong;
	vector<int>lie;
}h[10];
int hang[10][10];
int lie[10][10];
int g[10][10];
int t[10][10];
int ans=-1;
int cnt[10][10] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
    0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
    0, 1, 1, 1, 2, 2, 2, 3, 3, 3,
    0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
    0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
    0, 4, 4, 4, 5, 5, 5, 6, 6, 6,
    0, 7, 7, 7, 8, 8, 8, 9, 9, 9,
    0, 7, 7, 7, 8, 8, 8, 9, 9, 9,
    0, 7, 7, 7, 8, 8, 8, 9, 9, 9,
};
int cheng[10][10] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    0, 6, 7, 7, 7, 7, 7, 7, 7, 6,
    0, 6, 7, 8, 8, 8, 8, 8, 7, 6,
    0, 6, 7, 8, 9, 9, 9, 8, 7, 6,
    0, 6, 7, 8, 9, 10, 9, 8, 7, 6,
    0, 6, 7, 8, 9, 9, 9, 8, 7, 6,
    0, 6, 7, 8, 8, 8, 8, 8, 7, 6,
    0, 6, 7, 7, 7, 7, 7, 7, 7, 6,
    0, 6, 6, 6, 6, 6, 6, 6, 6, 6,
};
bool cmp(ty t1, ty t2)
{
	return t1.kong
}
void dfs(int ha, int l, int score)
{
	if (ha == 10)
	{
		ans = max(ans, score);
		return;
	}
	int tmp = h[ha].hang;
	for (int i=1; i<=9; i++)
	{
		if (hang[tmp][i] || lie[h[ha].lie[l]][i] || g[cnt[tmp][h[ha].lie[l]]][i])
		continue;
		hang[tmp][i] = 1;
		lie[h[ha].lie[l]][i] = 1;
		g[cnt[tmp][h[ha].lie[l]]][i] = 1;
		if (l == h[ha].kong-1)
		dfs(ha+1, 0, score+i*cheng[tmp][h[ha].lie[l]]);
		else
		dfs(ha, l+1, score+i*cheng[tmp][h[ha].lie[l]]);
		hang[tmp][i] = 0;
		lie[h[ha].lie[l]][i] = 0;
		g[cnt[tmp][h[ha].lie[l]]][i] = 0;
	}
}
int main()
{
	int res = 0;
	for (int i=1; i<=9; i++)
    {
        for (int j=1; j<=9; j++)
        {
            int x;
            cin>>x;
            t[i][j] = x;
            if (x!=0)
            {
                int c = cnt[i][j];
                hang[i][x] = 1;
                lie[j][x] = 1;
                g[c][x] = 1;
                res += x*cheng[i][j];
            }
            else
            {
                h[i].hang = i;
                h[i].kong++;
                h[i].lie.push_back(j);
            }
        }
    }
	sort(h+1, h+1+9, cmp);
	dfs(1, 0, res);
	cout<
	return 0;
} 

NC16665 [NOIP2004]虫食算

题目链接

关键点:

1、首先的想法是对于每一个字母从0-n-1一个个的去尝试，且字母转换可以改成数字的映射

即0-A，1-B。。。。

2、如何处理n进制，计算时的进位判断，%n即可

3、如何剪枝：

（1）可以从低位开始计算，即我们开三个数组，用来存三个字符串对应的数字，我们从第一位开始存，倒着遍历字符串

for (int i=n-1; i>=0; i--)
{
	a[i] = s1[i]-'A';
	b[i] = s2[i]-'A';
	c[i] = s3[i]-'A';
}

（2）接下来是确定首先我们考虑的是哪个字母，同样的，我们也从最低位的字母开始选择，ne数组存的是每个字母的最佳的顺序（从最低位开始找顺序）

for (int i=n-1; i>=0; i--)
	{
		if (vis[a[i]]==-1)
		{
			vis[a[i]] = 1;
			ne[++num] = a[i];
		}
		if (vis[b[i]]==-1)
		{
			vis[b[i]] = 1;
			ne[++num] = b[i];
		}
		if (vis[c[i]]==-1)
		{
			vis[c[i]] = 1;
			ne[++num] = c[i];
		}
	}

（3）我们对于每一位，如果三个字符串的这一位都确定了，分别设三个字符串该位的数字为x1,

x2,x3,如果x1+x2没有进位，那么（x1+x2)%n==x3,如果有进位，那么(x1+x2+1)%n==x3。

for (int i=0; i
	{
		int x1 = ans[a[i]], x2 = ans[b[i]], x3 = ans[c[i]];
		if (x1 == -1 || x2 == -1 || x3 == -1)
		continue;
		if ((x1+x2)%n != x3 && (x1+x2+1)%n != x3)
		return false;
	}
	return true;

4、如何判断最终答案正确，我们可以将每一个字符串算出其对应的数字，相加判断

int check()
{
	int ans1 = 0, ans2 = 0, ans3 = 0;
	for (int i=0; i
	{
		ans1 = n*ans1 + ans[a[i]];
		ans2 = n*ans2 + ans[b[i]];
		ans3 = n*ans3 + ans[c[i]]; 
	}
	if (ans1 + ans2 == ans3)
	return 1;
	else
	return 0;
}

完整代码：

# include 
using namespace std;
const int N = 30;
int ans[N], a[N], b[N], c[N], ne[N], vis[N];
int n, num, flag;
string s1, s2, s3;
int check()
{
	int ans1 = 0, ans2 = 0, ans3 = 0;
	for (int i=0; i
	{
		ans1 = n*ans1 + ans[a[i]];
		ans2 = n*ans2 + ans[b[i]];
		ans3 = n*ans3 + ans[c[i]]; 
	}
	if (ans1 + ans2 == ans3)
	return 1;
	else
	return 0;
}
int find()
{
	for (int i=0; i
	{
		int x1 = ans[a[i]], x2 = ans[b[i]], x3 = ans[c[i]];
		if (x1 == -1 || x2 == -1 || x3 == -1)
		continue;
		if ((x1+x2)%n != x3 && (x1+x2+1)%n != x3)
		return false;
	}
	return true;
}
void dfs(int x)
{
	if (x == n+1)
	{
		if (check())
		{
			for (int i=0; i
			cout<" ";
			flag = 1;
		}
		return ;
	}
	if (flag)
	return ;
	if (!find())
	{
		return ;
	}
	for (int i=n-1; i>=0; i--)
	{
		if (vis[i] == -1)
		{
			vis[i] = 1;
			ans[ne[x]] = i;
			dfs(x+1);
			vis[i] = -1;
			ans[ne[x]] = -1;
		}
	}
}
int main()
{
	cin>>n;
	cin>>s1>>s2>>s3;
	for (int i=n-1; i>=0; i--)
	{
		a[i] = s1[i]-'A';
		b[i] = s2[i]-'A';
		c[i] = s3[i]-'A';
	}
	memset(vis, -1, sizeof(vis));
	for (int i=n-1; i>=0; i--)
	{
		if (vis[a[i]]==-1)
		{
			vis[a[i]] = 1;
			ne[++num] = a[i];
		}
		if (vis[b[i]]==-1)
		{
			vis[b[i]] = 1;
			ne[++num] = b[i];
		}
		if (vis[c[i]]==-1)
		{
			vis[c[i]] = 1;
			ne[++num] = c[i];
		}
	}
	memset(vis, -1, sizeof(vis));
	memset(ans, -1, sizeof(ans));
	dfs(1);
	
	
	return 0;
}