A - Sign Flipping
题意简述：
给定长为 (n)（(n) 是奇数）的整数数组 (a)，你可以进行任意次操作，每次选择一个 (a_i) 并将它变成 (-a_i)。你需要让最终的数组满足以下条件：
- 至少有 (frac{n-1}{2}) 个相邻数的差值 (le 0)。
- 至少有 (frac{n-1}{2}) 个相邻数的差值 (ge 0)。
输出任意一个满足条件的最终数组。如果有多个解，输出任意一个，可以证明，解总是存在的。
多组测试数据。
( exttt{Data Range:} 1le tle 500, 3le nle 99, -10^9le a_ile 10^9)。
简单构造。
一正一负即可。
const int N = 103;
int n, a[N];
int main()
{
int T = gi();
while (T--)
{
n = gi();
for (int i = 1; i <= n; i+=1) a[i] = gi();
for (int i = 1; i <= n; i+=1)
{
if (i & 1) printf("%d ", -abs(a[i]));
else cout << abs(a[i]) << ' ';
}
puts("");
}
return 0;
}
B - Neighbor Grid
题意简述：
给你一个 (n) 行 (m) 列的矩阵，要求你让这个矩阵是“完美”的。
“完美”的定义如下：
若当前的格子里是一个正整数 (k)，那么与这个网格相邻（有公共边）的 (k) 个格子也必须有一个正整数。
若当前的格子里是
0，那么不受上述的限制。你可以对任意的一个格子加上
1，次数不受限制。如果可以做到“完美”，请输出
YES之后，将修改过的矩阵输出。否则只输出一行
NO。多组测试数据。
( exttt{Data Range:}1le tle 5000, 2le n,mle 300,n imes mle 10^5,0le a_{i,j}le 10^9)。
简单构造。
每个角上的数为 (2)，每个边上的数为 (3)，中间的数为 (4)，无解判断一下即可。
const int N = 303;
int n, a[N][N];
int main()
{
int T = gi();
while (T--)
{
n = gi(), m = gi();
for (int i = 1; i <= n; i+=1)
for (int j = 1; j <= m; j+=1)
a[i][j] = gi();
bool ok = true;
if (a[1][m] > 2 || a[n][1] > 2 || a[n][m] > 2 || a[1][1] > 2)
{
puts("NO");
continue;
}
for (int i = 2; i < m; i+=1)
{
if (a[1][i] > 3 || a[n][i] > 3) ok = false;
}
for (int i = 2; i < n; i+=1)
if (a[i][1] > 3 || a[i][m] > 3) ok = false;
for (int i = 2; i < n; i+=1)
for (int j = 2; j < m; j+=1)
if (a[i][j] > 4) ok = false;
if (!ok) puts("NO");
else
{
puts("YES");
a[1][m] = a[n][1] = a[n][m] = a[1][1] = 2;
for (int i = 2; i < m; i+=1)
a[1][i] = 3, a[n][i] = 3;
for (int i = 2; i < n; i+=1)
a[i][1] = 3, a[i][m] = 3;
for (int i = 2; i < n; i+=1)
for (int j = 2; j < m; j+=1)
a[i][j] = 4;
for (int i = 1; i <= n; i+=1)
{
for (int j = 1; j <= m; j+=1)
cout << a[i][j] << ' ';
puts("");
}
}
}
return 0;
}
C - Element Extermination
题意简述：
给定一个 (1) 到 (n) 的排列 (a)。在一次操作中，你可以选择一个满足 (a_i<a_{i+1}) 的下标 (i(1 leq i<n))，删除 (a_i) 或 (a_{i+1})。
你需要求出是否可能通过若干次操作使得 (a) 只剩下一个元素。
多组测试数据。
( exttt{Data Range:}1le tle 2 imes 10^4,2le nle 3 imes 10^5,sum nle 3 imes 10^5,1le a_ile n)。
结论是 (a_1 < a_n) 就有解，否则无解。
证明留给读者作为练习。
const int N = 300003;
int n, m;
int a[N];
int main()
{
int T = gi();
while (T--)
{
n = gi();
for (int i = 1; i <= n; i+=1) a[i] = gi();
if (a[1] < a[n]) puts("YES");
else puts("NO");
}
return 0;
}
D - Replace by MEX
题意简述：
给一个序列 (a)，每次操作可以选定一个位置 (p)，令 (a_p=) 这个序列的 ( ext{MEX})。你需要进行若干次操作，使得这个序列单调不降。操作次数不能超过 (2 imes n)。
多组测试数据。
( exttt{Data Range:}1le tle 200,n leq 1000,a_i in [0,n])。
考虑把原序列变成 (0,1,dots,n-1)。
每一次求出序列的 ( ext{MEX})，如果 ( ext{MEX}=n)，那么找到一个没有匹配上的数将它替换；否则将 (a_{ ext{MEX}+1}) 替换成 ( ext{MEX})。
const int N = 1003;
int n, m, a[N], ton[N];
inline bool check()
{
for (int i = 1; i < n; i+=1)
if (a[i] > a[i + 1])
return false;
return true;
}
inline int MEX()
{
for (int i = 0; i <= n; i+=1)
if (!ton[i]) return i;
}
int main()
{
int T = gi();
while (T--)
{
n = gi();
for (int i = 1; i <= n; i+=1) a[i] = gi();
if (check()) {puts("0
"); continue;}
vector <int> ans;
while (1)
{
if (check()) break;
for (int i = 0; i <= n; i+=1) ton[i] = 0;
for (int i = 1; i <= n; i+=1)
++ton[a[i]];
int now = MEX();
if (now == n)
{
for (int i = 1; i <= n; i+=1)
if (a[i] != i - 1)
{
a[i] = now;
ans.push_back(i);
break;
}
}
else
{
a[now + 1] = now;
ans.push_back(now + 1);
}
}
cout << ans.size() << endl;
for (auto x : ans) cout << x << ' ';
puts("");
}
return 0;
}