USACO 25FEB 铜组 题解整合

George222 Lv3
  2025-03-10 12:05:49 2025-03-10 12:05:49 创建   2025-03-10 12:11:15 2025-03-10 12:11:15 更新      

铜组 25FEB 所有题目链接

T1

大模拟。

思路挺简单的，就是调试比较麻烦。

初始化部分：

  • 只需要处理左上角四分之一的点 ，并计算它与对称点的 # 数量记为 。
  • 目标是使四个对称点的字符保持相同（全是 . 或全是 #）并计算 来找到最少修改次数。

模拟修改部分：

对于每次修改，如果是将 # 改为 .，就 ，反之 。

等于是重做初始化部分第一步。

然后将新计算出的答案加入即可。

注： 是上一次计算出的 值。

这条代码的意思是，在改变一个字符后（坐标设为 ）重新计算 与原先 进行对比然后将计算出来多或少的值更新至 中。

注：由于有特判，这个修改的字符绝对是在左上角部分。

例如：

1
2
#.
..

初始化部分的 计算为 ，假设修改左上角 # 至 .；

1
2
..
..

更新 ，此时根据修改后的 （值为 ），修改 值，， 修改值为 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int n, u;
string mp[2005];

int main()
{
    cin >> n >> u;
    for (int i = 0; i < n; i++)
        cin >> mp[i];

    int cnt[2005][2005];
    memset(cnt, 0, sizeof(cnt));
    ll ans = 0;
    for (int r = 0; r < n / 2; r++)
	{
        for (int c = 0; c < n / 2; c++)
		{
            if (mp[r][c] == '#')
				cnt[r][c]++;
            if (mp[r][n - 1 - c] == '#')
				cnt[r][c]++;
            if (mp[n - 1 - r][c] == '#')
				cnt[r][c]++;
            if (mp[n - 1 - r][n - 1 - c] == '#')
				cnt[r][c]++;
            ans += min(cnt[r][c], 4 - cnt[r][c]);
        }
    }
    cout << ans << "\n";
    for (int i = 0; i < u; i++)
	{
        int r, c;
        cin >> r >> c;
        int rr = min(r - 1, n - r);
        int cc = min(c - 1, n - c);
        int x = min(cnt[rr][cc], 4 - cnt[rr][cc]);

        if (mp[r - 1][c - 1] == '#')
		{
            mp[r - 1][c - 1] = '.';
            cnt[rr][cc]--;
        }
		else
		{
            mp[r - 1][c - 1] = '#';
            cnt[rr][cc]++;
        }
        ans += min(cnt[rr][cc], 4 - cnt[rr][cc]) - x;
        cout << ans << "\n";
    }
    return 0;
}

T2

思路

要让数组 中的 ，我们需要让数组 满足两个条件：

对于代码实现，我们可以先预处理一个数组 ， 表示数组 中数字 的个数。

对于每个 的询问，我们先遍历 ，查看有多少个数缺失，设为 （条件 1）；然后再调取 查看有多少它本身在数组 （条件 2）。

此时，我们已经得到了解法，但是这种解法在每次解决 时都要重新计算 ，时间复杂度 ，显然过不了 ，我们需要优化。

而显然， 可以预处理进行优化，具体思路类似递推或 dp。

设 为 中有多少个数缺失，而 可以从 转移：

时间复杂度约为 ，可以通过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a;
int cnt[200005];
int miss[200005];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		a.push_back(x);
		cnt[x]++;
	}
	sort(a.begin(), a.end());
	for (int i = 1; i <= n; i++)
	{
		if (cnt[i - 1] == 0)
			miss[i] = miss[i - 1] + 1;
		else
			miss[i] = miss[i - 1];
	}
	
	int q = 0;
	while (q <= n)
	{
		int now = cnt[q] - miss[q];
		if (now >= 0)
			cout << cnt[q] << "\n";
		else
			cout << cnt[q] + abs(now) << "\n";
		q++;
	}
	return 0;
}

T3

思路

本题解使用简单 dp 解决本问题。

设 为区间 中使用的 print 代码个数，判断 。

对于长度为 的子序列，，指使用一个 print 语句输出字符。

对于长度大于 的子序列，设子序列长度为 ，从 ；左右边界为 ，：

  1. 在子序列中遍历一个可能的分隔点，设为 ，；初始化 。
  2. 然后开始检查子序列是否可以由子序列中的一个子序列拼接而来。
  3. 枚举子序列中的子序列的长度，即周期长度，设为 ， 且 。
  4. 检查周期中每个位置 ，，是否满足 ，即为检查子序列中每 位是否与周期 相同。如果全部满足，则更新 。

输出：判断 即可。

时间复杂度约为 左右，其中 表示 的因子数量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;

int t;
int n, k;

int main()
{
    int t;
    cin >> t;
    while (t--)
	{
        int n, k;
        cin >> n >> k;
        int a[105];
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int dp[105][105];
        for (int i = 1; i <= n; i++)
        {
        	for (int j = 1; j <= n; j++)
        		dp[i][j] = 105;
		}
        for (int i = 1; i <= n; i++)
            dp[i][i] = 1;
        
        for (int len = 2; len <= n; len++)
		{
            for (int i = 1; i <= n - len + 1; i++)
			{
                int j = i + len - 1;
                for (int l = i; l < j; l++)
                    dp[i][j] = min(dp[i][j], dp[i][l] + dp[l + 1][j]);

                int x = len;
                for (int l = 1; l < x; l++)
				{
                    if (x % l != 0)
                        continue;
                    bool flag = true;
                    for (int p = i; p <= j; p++)
					{
                        if (a[p] != a[i + (p - i) % l])
						{
                            flag = false;
                            break;
                        }
                    }
                    if (flag)
                        dp[i][j] = min(dp[i][j], dp[i][i + l - 1]);
                }
            }
        }
        cout << (dp[1][n] <= k ? "YES" : "NO") << "\n";
    }
    return 0;
}
  • 标题: USACO 25FEB 铜组 题解整合
  • 作者: George222
  • 创建于 : 2025-03-10 12:05:49
  • 更新于 : 2025-03-10 12:11:15
  • 链接: https://george110915.github.io/USACO 25FEB B sol/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
USACO 25FEB 铜组 题解整合
  1. T1
  2. T2
    1. 思路
    2. 代码
  3. T3
    1. 思路
    2. 代码