csps2020动物园

发表于 2021-10-01 更新于 2022-06-27

这道题思路很简单，我们拆分考虑每一个二进制位
由于有些二进制位需要饲料有些不用，我们就直接把所有动物的编号按位或起来，并得到饲料列表（其实饲料列表不用计算，记录一下对应的位就好了。
从高往低考虑每一位，若这一位已经买过饲料，或者指南上面没有提到需要这一位买饲料，那么这一位就是任选的，计任选的位有 $j$ 个
把所有任选的位组合，可以得到 $2 ^ j$ 个答案
再减去原有的 n 个就可以了

但是

阅读全文 »

NOIP2020微信步数

发表于 2021-10-01 更新于 2022-06-27

直接从每个点开始走肯定超时，也没有什么办法可以优化
关键的是整体思路，让所有点一起走。
最开始，所有点塞满了整个空间，是一个k维的超立方体

然后，所有点一起移动，显然也是一个k维超立方体。
于是就一直维护这个超立方体的边界。
-1特判就是看一个点在一个维度所能到达的最左与最右的差值是否小于这个维度上限。

NOIP2020移球游戏

发表于 2021-10-01

题目

要将所有同种颜色的球移到同一根柱子上, 所能进行的操作只有把一个柱子上的球移动到另一个柱子上。
关键操作：

借助空栈C和满栈B, 把所有A的x移动到顶

int excute(stk &A, stk &B, stk &C, int x)
{
	int res = 0;
	for(int i = 1; i <= A.tt; i++) if(A.a[i] == x) res++;
	// cout << "!!res = " << res << endl;
	for(int i = 1; i <= res; i++)
	{
		anss.push_back(make_pair(B.id, C.id));
		C.insert(B.pop());
	}
	// 是 x 放 B, 不是放 C
	while(A.tt) 
	{
		if(A.a[A.tt] == x)
		{
			B.insert(A.pop());
			anss.push_back(make_pair(A.id, B.id));
		}
		else
		{
			C.insert(A.pop());
			anss.push_back(make_pair(A.id, C.id));
		}
	}
	
	for(int i = 1; i <= m - res; i++) 
	{
		A.insert(C.pop());
		anss.push_back(make_pair(C.id, A.id));
	}

	for(int i = 1; i <= res; i++)
	{
		A.insert(B.pop());
		anss.push_back(make_pair(B.id, A.id));
	}

	for(int i = 1; i <= res; i++)
	{
		B.insert(C.pop());
		anss.push_back(make_pair(C.id, B.id));
	}
}

想到了这一点就可以做出了
一种可行的方法是对着样例2模拟

zroicspday3T2

发表于 2021-09-12

CSP 7 连测 day3 T2 总结

PS: 此题就是点灯游戏的最小步数问题

算法很简单，由于第一行确定后，下面的怎么放就确定了
于是，就只要枚举第一行，就可以确定以后的行，然后判断有没有成功就可以了。
时间复杂度 $O(2 ^ n n ^ 2)$ , $n \le 17$ 因此可以过

当时在赛场上面没有考虑到点当前行会影响下一行，只得了10分.

满分代码:

#include <bits/stdc++.h>
using namespace std;
const int dx[5] = {1, -1, 0, 0, 0}, dy[5] = {0, 0, 1, -1, 0};
int n, m, ans, sum, a[20][20], b[20][20];
char s[20];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; j++)
            if (s[j] == 'X')
                a[i][j] = 1;
    }
    ans = 1e9 + 7;
    for (int i = 0; i < (1 << m); i++)
    {
        sum = 0;
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= m; k++)
                b[j][k] = a[j][k];
        for (int j = 1; j <= m; j++)
            if (i & (1 << (j - 1)))
            {
                sum++;
                for (int i = 0; i < 5; i++)
                {
                    int xx = 1 + dx[i], yy = j + dy[i];
                    if (xx < 1 || xx > n || yy < 1 || yy > m)
                        continue;
                    b[xx][yy] ^= 1;
                }
            }
        for (int j = 2; j <= n; j++)
            for (int k = 1; k <= m; k++)
                if (b[j - 1][k])
                {
                    sum++;
                    for (int i = 0; i < 5; i++)
                    {
                        int xx = j + dx[i], yy = k + dy[i];
                        if (xx < 1 || xx > n || yy < 1 || yy > m)
                            continue;
                        b[xx][yy] ^= 1;
                    }
                }
        bool tmp = 1;
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= m; k++)
                if (b[j][k])
                {
                    tmp = 0;
                    break;
                }
            if (!tmp)
                break;
        }
        if (tmp)
            ans = min(ans, sum);
    }
    printf("%d\n", ans);
    return 0;
}