Problem A
从n个数的和，也就是入手。
如果和为奇数，显然无法二等分，其最小的差只能为1。
如果和为偶数，显然其可以二等分，故其最小的差可以为0。
具体的分割策略的话，可以求出向下取整，然后在n个数中找出部分数凑出这个数，剩下的作为另一部分。自行dp一下可以发现这总能够凑得出来的。
类比一下用不同面额的金币凑出各种金额的问题就行了。实在不行自己写个dp验证一下。
时间复杂度为
#include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n)
{
n = (n + 1) >> 1;
cout << n%2 << endl;
}
return 0;
}
Problem B
首先，先列出会输出NO的情况：
- 颜色太少（k太小）
- 颜色太多（k太大）
对于第二种情况的话，当且仅当的时候会发生。
而对于第一种情况的话，当且仅当k小于最少使用颜色数的时候会发生。
重点在于最少使用颜色数。这个其实就是数组a中重复次数最多的元素重复的次数。
排除掉NO的情况之后，k种颜色的涂法就是：
- 先按最少使用颜色数的方案涂（枚举1到k，每次用该颜色涂尽可能多的元素）
- 然后看还剩多少种颜色需要涂，去找重复颜色的块去涂即可（例如，有两个元素都是颜色1的话，其中就有一个可以涂成别的颜色）
用最暴力的方法来做的话，时间复杂度为
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int a[5005], n, k;
int ans[5005];
while(cin >> n >> k)
{
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
memset(ans, -1, sizeof(ans));
if(n < k)
{
cout << "NO" << endl;
continue;
}
int cnt = 0;
for(int i = 1; i <= k; i++)
{
bool vis[5005] = {0};
if(cnt == n)
{
for(int j = 0; j < n; j++)
{
if(vis[ans[j]])
{
ans[j] = i;
i++;
if(i > k)
{
break;
}
}
else
{
vis[ans[j]] = true;
}
}
}
else
{
for(int j = 0; j < n; j++)
{
if(ans[j] == -1)
{
if(vis[a[j]])
{
continue;
}
vis[a[j]] = true;
ans[j] = i;
cnt++;
}
}
}
}
if(cnt == n)
{
cout << "YES" << endl;
for(int i = 0; i < n; i++)
{
if(i)
{
cout << " ";
}
cout << ans[i];
}
cout << endl;
}
else
{
cout << "NO" << endl;
}
}
return 0;
}
Problem C
分情况讨论：
如果的话，显然跟他慢慢耗总能踹爆所有门的，答案为n。
否则，只要无法一次踹爆的门他都能跟你耗让那个门耐久越来越高。所以需要挑能一次踹爆的门下手。当然他也知道这一点，所以每当你一次踹爆一个门的时候他就会修一个【能被你一次踹爆的门】，使其成为【无法被你一次踹爆的门】。直接计算即可。
时间复杂度为
#include <iostream>
using namespace std;
int a[1005];
int main()
{
int n, x, y;
while(cin >> n >> x >> y)
{
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
if(x > y)
{
cout << n << endl;
}
else
{
int cnt = 0;
for(int i = 0; i < n; i++)
{
if(a[i] <= x)
{
cnt++;
}
}
cout << (cnt + 1) / 2 << endl;
}
}
return 0;
}
Problem D
考虑两种情况：
- 小的数位有多出的，大的数位有缺少的：为了让字典序最小，我们需要尽可能的替换掉靠后的小的数位为更大的数位。
- 大的数位有多出的，小的数位有缺少的：为了让字典序最小，我们需要尽可能的替换掉靠前的大的数位为更小的数位。
基于这个思想写个函数然后对所有可能的数位组合（其实就三种：0和1，0和2，1和2）调用一下就行了。
时间复杂度为
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
string s;
int cnt[5], n;
void Fix(int a, int b)
{
int pos = 0;
while((cnt[a] < 0) && (cnt[b] > 0))
{
if(s[pos] == b + '0')
{
s[pos] = a + '0';
cnt[a]++;
cnt[b]--;
}
pos++;
}
pos = n - 1;
while((cnt[b] < 0) && (cnt[a] > 0))
{
if(s[pos] == a + '0')
{
s[pos] = b + '0';
cnt[b]++;
cnt[a]--;
}
pos--;
}
}
int main()
{
while(cin >> n)
{
cin >> s;
for(int i = 0; i < 3; i++)
{
cnt[i] = -1 * (n / 3);
}
for(int i = 0; i < n; i++)
{
cnt[s[i] - '0']++;
}
Fix(0, 2);
Fix(0, 1);
Fix(1, 2);
cout << s << endl;
}
return 0;
}
Problem E
一个显然的性质是，对于任意区间，如果
，那么对于数组
而言，这个区间内的数必须相同。
于是我们便可以提出若干个这样的区间，然后对这些区间进行合并（有相交区域的区间可以合并成一个新的大区间），最终我们可以得到若干个互不相交的区间。
设这些区间数为，那么答案显然就是
。
提取区间的话我们可以使用一个map用于记录每种数字的最大下标。那么合并区间的话我们便可以从左往右扫，每次通过这个map来更新区间右值，直至无法更新为止。
时间复杂度为
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL GetAns(int p)
{
p -= 1;
LL ans = 1;
while(p--)
{
ans <<= 1;
ans %= mod;
}
return ans;
}
map<int, int> mapR;
int a[200005];
int FindR(int pos)
{
int ret = pos;
for(int i = pos; i <= ret; i++)
{
ret = max(ret, mapR[a[i]]);
}
return ret;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
mapR.clear();
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
mapR[a[i]] = i;
}
int pos = 0;
int cnt = 0;
while(pos < n)
{
pos = FindR(pos) + 1;
cnt++;
}
printf("%lld\n", GetAns(cnt));
}
return 0;
}
Problem F
首先需要计算出对于任意两行（第i行和第j行）：
- 如果第j行接在第i行下面的话，两行中每列的两个数的差的绝对值的最小值
- 如果以第i行为结尾，第j行为开头的话，第i行中每个数与第j行中同样位置的下一个数的差的绝对值的最小值（也就是
）
对于第一个计算的量而言，将每一行看作是一个点，且每个针对有序数对计算出来的量作为从点i到点j的有向边的权值。就可以构成一个有向图（我们假设该有向图为图A）。以同样的方法对第二个计算出来的量建图可以得到另一个有向图B。
于是问题就转换为，在有向图A中求一条路径使其经过所有的点，且【所经过的边的权值】和【这条路径上的终点和起点在图B上的边的权值】的最小值最大。
对于前者的话显然就是一个旅行商问题的变体，照着旅行商问题的解法便可以解出来。现在需要处理掉的是后者。事实上我们可以通过枚举起点来简化后者的问题。对于每个枚举的起点求出【经过所有点的权值的最小值最大】的路径。根据终点不同会有n条不同的路径。然后对这些路径再去查图B再求一遍两两最小，然后从中取最大即可。
不知道旅行商问题的同学可以自行学习一下状态压缩dp。旅行商问题算是状态压缩dp的一个入门题目。
总的时间复杂度为，前者为建图过程的复杂度，后者为枚举起点+状压dp的时间复杂度。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int INF = 1.5e9;
int e[25][25], nxt[25][25];
int a[25][10005];
void Build(int &n, int &m)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
int w = INF;
for(int k = 0; k < m; k++)
{
w = min(w, abs(a[i][k] - a[j][k]));
}
e[i][j] = w;
w = INF;
for(int k = 1; k < m; k++)
{
w = min(w, abs(a[i][k-1] - a[j][k]));
}
nxt[i][j] = w;
}
}
}
int dp[70000][25];
int GetAns(int &src, int &n)
{
memset(dp, -1, sizeof(dp));
dp[1 << src][src] = INF;
for(int bitm = 1; bitm < (1 << n); bitm++)
{
for(int i = 0; i < n; i++)
{
if(!(bitm & (1 << i)))continue;
for(int j = 0; j < n; j++)
{
if(i == j)continue;
if(!(bitm & (1 << j)))continue;
if(bitm == (1 << j))continue;
dp[bitm][i] = max(dp[bitm][i], min(dp[bitm - (1 << i)][j], e[j][i]));
}
}
}
int ret = -1;
for(int i = 0; i < n; i++)
{
ret = max(ret, min(dp[(1 << n) - 1][i], nxt[i][src]));
}
return ret;
}
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m))
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
scanf("%d", &a[i][j]);
}
}
Build(n, m);
int ans = -1;
for(int i = 0; i < n; i++)
{
ans = max(ans, GetAns(i, n));
}
printf("%d\n", ans);
}
return 0;
}
