「USACO 2022.2 Platinum」 题解

First Post:

Last Update:

没有一道题想出完整做法。真是让人自闭。

按体感难度排序。

loj3668 Sleeping in Class

题意：给出一个序列 ，一次操作可以将两个相邻的数 合并为 ，也可以将数 分解为两个相邻的数 ，问最后使得序列中的所有数都等于 的最少操作次数。可能无解。 次询问，每次给出不同的 。

。

设 表示 的前缀和。

那么 则无解。

否则最优策略一定如下：

维护当前准备参与操作的数 ，初始 。从左到右扫描到 ，把 与 合并，如果此时 ，就不停地从 中分出 来。

观察这个过程，发现 （特例，如果 ，）

我们发现，如果没有 的位置，那么分裂要进行 次，合并要进行 次，而每出现一个这样的位置，可以少一次分裂，少一次合并。故答案为 。

我当时转化出来的东西没有这么简洁明了，所以寄了。

考虑如何求出 ，注意到 ，所以我们只关心所有的 。考察 和 的质因子分解。设其分别为 ，那么 对 有贡献当且仅当 。我们发现这是一个高维后缀和的形式，而这事实上也是可以做的，因为 在 时大约只有 级别，而维数也是 ，很小。这里高维后缀和的时间复杂度为 （这里的 是使用 map 进行离散化的复杂度）。

现在的问题在于如何求出 的质因子分解了。做过 AGC003D 的同学应该熟悉这样一个方法：设值域为 ，先将不超过 的质因子试除掉。如果剩下的数小于 ，那么其一定是一个质数 ，否则其质因子就被试除掉了。如果大于 ，那么先前试除掉的部分总共就不超过 ，而剩余部分一定是至多两个质数相乘的形式。此时 。

此题中 。对于最后的那种情况，可能的 只有几千个，直接暴力即可。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int n,Q;
ll a[N];
map<long long,long long> mp;
int pri[N],cnt[N],tot;
ll pw[N];
map<long long,int> f;
inline ll calc(int *p) // 把幂次数组压成long long 整数
{
	ll res = 0;
	for(int i = 1;i <= tot;i++)
		res += 1ll * p[i] * pw[i];
	return res;
}
inline ll rev(ll x) // 把状压后的整数变为质因数分解前的数
{
	ll res = 1;
	for(int i = 1;i <= tot;i++)
	{
		ll pp = (x / pw[i]) % (cnt[i] + 1);
		while(pp--) res = res * pri[i];
	}
	return res;
}
void dfs(int x,ll now,int fix)
{
	if(x > tot)
		return f[now - pw[fix]] += f[now],void();
	ll np = cnt[x] * pw[x];
	for(int i = cnt[x];i >= (x == fix);i--)
		dfs(x + 1,now + np,fix),np -= pw[x];
}
int tp[N];
inline void Divide()
{
	ll tmp = a[n];
	for(int i = 2;i <= 1e6;i++)
		if(tmp % i == 0)
		{
			pri[++tot] = i;
			while(tmp % i == 0) tmp /= i,++cnt[tot];
		}
	if(tmp > 1e12) return;
	if(tmp > 1) pri[++tot] = tmp,cnt[tot] = 1;
	pw[tot] = 1;
	for(int i = tot - 1;i >= 0;i--)
		pw[i] = pw[i + 1] * (cnt[i + 1] + 1);
	for(int i = 1;i < n;i++)
	{
		tmp = a[i];
		for(int j = 1;j <= tot;j++)
		{
			tp[j] = 0;
			while(tmp % pri[j] == 0) ++tp[j],tmp /= pri[j];
			tp[j] = min(tp[j],cnt[j]);
		}
		f[calc(tp)]++;
	}
	for(int i = 1;i <= tot;i++)
		dfs(1,0,i);
	for(int i = 0;i < pw[0];i++)
		mp[rev(i)] = (a[n] / rev(i) - 1) + (n - 1) - 2 * f[i];
}
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i],a[i] += a[i - 1];
	Divide();
	cin >> Q;
	for(int i = 1;i <= Q;i++)
	{
		ll x;
		cin >> x;
		if(a[n] % x) {puts("-1");continue;}
		if(!mp[x])
		{
			int res = 0;
			for(int j = 1;j < n;j++) res += (a[j] % x == 0);
			mp[x] = (a[n] / x - 1) + (n - 1) - 2 * res;
		}
		cout << mp[x] << endl;
	}
	return 0;
}

loj3669 Phone Number

题意：https://loj.ac/p/3669

我当时先思考的前两个包，因为只有两键的状态转移较为简单，只需记录一个 便可通过。后来想直接从 转移到 。发现难以配出简单系数，转移跟你填的那些数关联性较强，然后就不会了。

事实上大力 DP，设状态 。 分别表示第 位你填的是什么字符， 表示前缀 能否根据题目规则匹配得上。转移枚举下一个字符填什么，比较简单。

但是直接做会有 个状态，过不去的。

发现当 时， 已经没有用了（因为 只会用来帮我们判断 能否匹配，从而接上 ，但如果 本身就无法匹配，我们也不用做这个判断了），同理，当 时， 无用，当 时， 也无用了。全为 就是不合法状态了。

根据这个进行裁剪，状态数好像只减少了不到一半。

还有一个优化，即若 ，那么对于 ，如果它们中有一个数不在 中，或者它们再加一个数也拼不出正方形，那么 就没用了，我们可以将其设为 。对于 也可以类似处理。

考虑分析状态数的上界。如果 ，那么 的方案就是在 种选三个数的方案数，只有 种选法， 不确定，一共 状态。如果 ， 就只有 有用，且在 中选，一共 种，乘上 的选法，一共 种。如果 ，就是 种状态。 就 种状态。总状态数有个上界 。

据说实际状态大约只有 多个。可以用 unordered_map 存状态来进行转移。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,P = 1e9 + 7;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n;
char s[N];
int a[N];
bool Can[5][4096];
// Can[2] : 相邻
// Can[3] : 能否加一个数变成方
// Can[4] : 能否方

struct State{
	int t0,t1,t2;
	bool v0,v1,v2,v3;
	State(){}
	State(const int _t0,const int _t1,const int _t2 
		,const int _v0,const int _v1,const int _v2,const int _v3):
		t0(_t0),t1(_t1),t2(_t2),v0(_v0),v1(_v1),v2(_v2),v3(_v3){}
	bool operator == (const State &rhs) const {
		return t0 == rhs.t0 and t1 == rhs.t1 and t2 == rhs.t2
		and v0 == rhs.v0 and v1 == rhs.v1 and v2 == rhs.v2 and v3 == rhs.v3;
	}
};
struct Hash{
	static const int base = 131;
	typedef unsigned int uint;
	uint operator ()(const State &x) const 
	{
		uint res = 0;
		res = res * base + x.t0;res = res * base + x.t1;
		res = res * base + x.t2;res = res * base + x.v0;
		res = res * base + x.v1;res = res * base + x.v2;
		res = res * base + x.v3;return res;
	}
};
inline State Reduce(int id,const State &x)
{
	State res = x;
	if(res.v3 == 0) res.t2 = 10;
	if(res.v3 == 0 && res.v2 == 0) res.t1 = 10;
	if(res.v3 == 0 && res.v2 == 0 && res.v1 == 0) res.t0 = 10;
	int bk[10];memset(bk,0,sizeof bk);
	if(res.v3 == 1)
	{
		if(id > 2) bk[a[id - 2]] = 1;
		if(id > 1) bk[a[id - 1]] = 1;
		bk[a[id]] = 1;
		if(id < n) bk[a[id + 1]] = 1;
		if(!Can[3][(1 << res.t0) | (1 << res.t1) | (1 << res.t2)])
			res.v3 = 0;
		if(!bk[res.t0] || !bk[res.t1] || !bk[res.t2]) res.v3 = 0;
	}
	if(res.v2 == 1)
	{
		memset(bk,0,sizeof bk);
		if(id > 1) bk[a[id - 1]] = 1;
		bk[a[id]] = 1;
		if(id < n) bk[a[id + 1]] = 1;
		if(id < n - 1) bk[a[id + 2]] = 1;
		if(!bk[res.t0] || !bk[res.t1]) res.v2 = 0;
	}
	if(res.v1 == 1)
	{
		memset(bk,0,sizeof bk);
		bk[a[id]] = 1;
		if(id < n) bk[a[id + 1]] = 1;
		if(id + 1 < n) bk[a[id + 2]] = 1;
		if(id + 2 < n) bk[a[id + 3]] = 1;
		if(!bk[res.t0]) res.v1 = 0;
	}
	return res;
}
inline State Next(int id,State x,int c)
{
	State res;
	res.t2 = x.t1;res.t1 = x.t0;res.t0 = c;
	res.v3 = x.v2;res.v2 = x.v1;res.v1 = x.v0;
	res.v0 = 0;
	if(x.v0 && res.t0 == a[id + 1]) res.v0 = 1;
	if(x.v1) { 
		int tv = (1 << a[id]) | (1 << a[id + 1]);
		if(tv == (1 << res.t0) + (1 << res.t1) && Can[2][tv])
			res.v0 = 1;
	}
	if(x.v3)
	{
		int tv = (1 << a[id - 2]) | (1 << a[id - 1]) | (1 << a[id]) | (1 << a[id + 1]);
		if(tv == (1 << res.t0) + (1 << res.t1) + (1 << res.t2) + (1 << x.t2) && Can[4][tv])
			res.v0 = 1;
	}
	return res;
}
unordered_map<State,int,Hash> mp1,mp2;
inline void Work()
{
	cin >> (s + 1);
	n = strlen(s + 1);
	for(int i = 1;i <= n;i++) a[i] = s[i] - '0';
	mp1.clear();
	mp1[State(10,10,10,1,0,0,0)] = 1;
	for(int i = 0;i < n;i++)
	{
		mp2.clear();
		for(auto it : mp1)
		{
			State t = it.first;
			for(int c = 1;c <= 9;c++)
			{
				State nxt = Next(i,t,c);
				nxt = Reduce(i + 1,nxt);
				if(nxt.v3 + nxt.v2 + nxt.v1 + nxt.v0 == 0) continue;
				Plus(mp2[nxt],it.second);
			}
		}
		mp1 = mp2;
	}
	int ans = 0;
	for(auto it : mp1)
		if(it.first.v0 == 1)
			Plus(ans,it.second);
	cout << ans << endl;
}	
int main()
{
	for(int i = 1;i <= 9;i++)
		for(int j = i + 1;j <= 9;j++)
			if(abs(i - j) == 3 || (abs(i - j) == 1 && i != 3 && i != 6))
				Can[2][(1 << i) | (1 << j)] = 1;
	Can[4][32 + 16 + 4 + 2] = 1;
	Can[4][64 + 32 + 8 + 4] = 1;
	Can[4][256 + 128 + 32 + 16] = 1;
	Can[4][512 + 256 + 64 + 32] = 1;
	for(int i = 1;i <= 9;i++)
		for(int j = i + 1;j <= 9;j++)
			for(int k = j + 1;k <= 9;k++)
				for(int p = 1;p <= 9;p++)
					Can[3][(1 << i) | (1 << j) | (1 << k)] |= Can[4][(1 << i) + (1 << j) + (1 << k) + (1 << p)];
	int T;
	cin >> T;
	while(T--) Work();
	return 0;
}
≡