本来这应该是一场 Div.4 的，但是被 tester 改成了 Div.3，于是就有了这场 8 道题的 Div.3。
比赛时只做出了 ( ext{A}sim ext{F})，( m{G}) 一直调不出来……
赛后找到了自己 ( m{G}) 的错误，于是改一改就 A 了（
题目难度都不算很大，就是题量有点多（
A - Minimal Square
题意简述：
找到一个面积最小的正方形，使它可以包含两个相同的边长分别为 (a) 和 (b) 的长方形。其中放置的两个长方形不能重叠。
多组测试数据。
( exttt{Data Range:} 1le tle 10000, 1le a, ble 100)。
比较简单的题目。
容易发现正方形的边长其实就是 (min{max{a imes 2, b}, max{a, b imes 2}})。
于是直接输出面积即可。
int T, a, b;
int main()
{
T = gi();
while (T--)
{
a = gi(), b = gi();
int mx1 = min(mx1, min(max(a << 1, b), max(a, b << 1)));
cout << mx1 * mx1 << endl;
}
return 0;
}
B - Honest Coach
题意简述：
有 (n) 个数 (s_i)，你需要将它们分成 (A)、(B) 两个组，且 (A) 和 (B) 中的元素个数至少为 (1)。
找到一个分组方案，使得 (|max(A) - max(B)|) 的值最小，其中 (max(A)) 表示 (A) 中元素的最大值，(min(B)) 表示 (B) 中元素的最小值。
多组测试数据。
( exttt{Data Range:} 1le tle 1000, 2le nle 50, 1le s_ile 1000)。
对原数组从小到大排序，直接输出 (min{s_{i+1}-s_{i}})。
const int N = 53;
int T, n;
int s[N];
int main()
{
T = gi();
while (T--)
{
n = gi();
for (int i = 1; i <= n; i+=1) s[i] = gi();
sort(s + 1, s + 1 + n);
int mn = 100000000;
for (int i = 1; i < n; i+=1) mn = min(mn, s[i + 1] - s[i]);
cout << mn << endl;
}
return 0;
}
C - Similar Pairs
题意简述：
定义：一对数 ((x, y)) 称为“类似的数对”，当且仅当 (x) 和 (y) 奇偶性相同或 (|x-y|=1)。
现给出 (n) 个数 (a_i)，问能否将这些数分成 (frac{n}{2}) 对“类似的数对”。能输出
YES，否则输出NO。多组测试数据。
( exttt{Data Range:} 1le tle 1000, 2le nle 50, 1le a_ile 100)，保证 (n) 为偶数。
首先将这些数按照奇偶性分成两组 (v1) 和 (v2)。
- 如果这两组数的大小都为偶数，那么一定有解。
- 否则：
- 如果存在 (|v1_i - v2_j|=1)，那么我们可以先将这两个数配对，然后将剩下的书按照第一种情况配对就行了。
- 如果不存在 (|v1_i - v2_j|=1)，那么输出无解。
int T, n;
vector <int> v1, v2;
int a[N];
int main()
{
T = gi();
while (T--)
{
n = gi();
v1.clear(), v2.clear();
for (int i = 1; i <= n; i+=1)
{
a[i] = gi();
if (a[i] & 1) v1.push_back(a[i]);
else v2.push_back(a[i]);
}
if (v1.size() % 2 == 0) {puts("YES"); continue;}
bool fl = true;
for (auto x : v1)
for (auto y : v2)
if (abs(x - y) == 1) {fl = false; break;}
if (fl) puts("NO");
else puts("YES");
}
return 0;
}
D - Buying Shovels
题意简述：
找到 (n) 的因数中第一个 (le m) 的数 (x)，输出 (frac{n}{x})。
多组测试数据。
( exttt{Data Range:} 1le tle 100, 1le n, kle 10^9)。
直接 (mathcal{O}(sqrt n)) 求出 (n) 的所有因数，然后排序直接找答案。
int T, n, m;
vector <int> v;
int main()
{
T = gi();
while (T--)
{
n = gi(), m = gi();
if (m > n) {puts("1"); continue;}
v.clear();
for (int i = 1; i * i <= n; i+=1)
if (n % i == 0)
{
v.push_back(i);
if (i * i != n) v.push_back(n / i);
}
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (auto x : v)
if (x <= m) {cout << n / x << endl; break;}
}
return 0;
}
E - Polygon
题意简述：
给出一个 (n imes n) 的
01矩阵，问能否从全0的矩阵根据如图所示的方式变成输入的矩阵。多组测试数据。
( exttt{Data Range:} 1le tle 1000, 1le nle 50)。
小清新结论题。
一个矩阵有解当且仅当不会出现以下情形：
1 0
0
于是直接判断即可。
const int N = 55;
int T, n;
char s[N][N];
int main()
{
T = gi();
while (T--)
{
n = gi();
for (int i = 1; i <= n; i+=1)
scanf("%s", s[i] + 1);
bool fl = true;
for (int i = 1; i < n; i+=1)
for (int j = 1; j < n; j+=1)
if (s[i][j] == '1' && s[i + 1][j] == '0' && s[i][j + 1] == '0')
{
fl = false;
break;
}
if (fl) puts("YES");
else puts("NO");
}
return 0;
}
F - Spy-string
题意简述：
输入 (n) 个字符串，每个字符串的长度为 (m)。
问能否找到一个长度为 (m) 的字符串，使得它与输入的每个字符串最多有 (1) 个字符不同。
多组测试数据。
( exttt{Data Range:} 1le tle 100, 1le n, mle 10)。
按照每一位扫描整个字符串，如果有不同的字符就依次尝试用别的字符去替代。
找到不同的字符可以用 set。
其实就是暴力枚举 + 判断。
时间复杂度约为 (mathcal{O}(n^4m^2log n))。
const int N = 13;
int T, n, m;
string s[N];
inline bool check(string ss)
{
bool fl = true;
for (int j = 1; j <= n; j+=1)
{
int cnt = 0;
for (int k = 0; k < m; k+=1)
if (ss[k] != s[j][k])
++cnt;
if (cnt > 1) {fl = false; break;}
}
return fl;
}
bool vis[30];
int main()
{
T = gi();
while (T--)
{
n = gi(), m = gi();
for (int i = 1; i <= n; i+=1) cin >> s[i];
bool ok = false;
for (int i = 1; i <= n; i+=1)
if (check(s[i]))
{
ok = true;
cout << s[i] << endl;
break;
}
if (ok) continue;
string ans = "-1";
for (int i = 0; i < m; i+=1)
{
set <int> t[30];
set <char> ss;
int cnt = 0;
memset(vis, 0, sizeof vis);
for (int j = 1; j <= n; j+=1)
{
if (!vis[s[j][i] - 'a'])
++cnt, vis[s[j][i] - 'a'] = true;
t[s[j][i] - 'a'].insert(j);
ss.insert(s[j][i]);
}
bool fl = false;
if (cnt > 1)
{
for (int j = 1; j <= n; j+=1)
{
string now = s[j];
for (auto x : ss)
{
char bf = now[i];
now[i] = x;
if (check(now))
{
ans = now;
fl = true;
break;
}
}
if (fl) break;
}
}
if (fl) break;
}
cout << ans << endl;
}
return 0;
}
G - A/B Matrix
题意简述：
问是否存在一个 (n) 行 (m) 列的
01矩阵，使得每一行有 (a) 个1，每一列有 (b) 个0。多组测试数据。
( exttt{Data Range:} 1le tle 1000, 1le ble n le 50, 1le ale m le 50)。
一种类似于轮换的构造方式。
思维比较巧妙，但比赛时没搞出来。
const int N = 103;
int T, n, m, a, b;
string s[N];
int main()
{
T = gi();
while (T--)
{
n = gi(), m = gi(), a = gi(), b = gi();
if (a * n != b * m)
{
puts("NO");
continue;
}
for (int i = 1; i <= n; i+=1) s[i] = "";
for (int i = 1; i <= n; i+=1)
for (int j = 1; j <= m; j+=1)
s[i] += "0";
int nowl = 0;
for (int i = 1; i <= n; i+=1)
{
for (int j = nowl, cnt = 1; cnt <= a; (j += 1) %= m, cnt+=1)
s[i][j] = '1';
nowl = (nowl + a) % m;
}
puts("YES");
for (int i = 1; i <= n; i+=1)
cout << s[i] << endl;
}
return 0;
}
H - Binary Median
题意简述：
有一个长度为 (2^m) 的
01二进制数序列，保证序列按照数值大小排列。现在要删去 (n) 个给定的二进制数，问接下来这个长度为 (2^m-n) 的二进制数序列的中位数为多少。
多组测试数据。
( exttt{Data Range:} 1le tle 1000, 1le n le min{2^m-1, 100}, 1le m le 60)。
首先把这些数转成十进制数。
我们首先用一个数 (p) 表示现在序列中位数的大小。
设 (k) 表示序列总长度，那么一开始 (p=frac{k-1}{2})（因为序列的数值范围为 (0sim 2^m-1)）。
然后对于每一个要删除的数 (x)：
- 如果当前序列长度为奇数，
- 若 (xge p)，那么 (p) 将要左移一位。
- 如果当前序列长度为偶数，
- 若 (xle p)，那么 (p) 将要右移一位。
注意这里的左移和右移都不能移动到已经删除过的数上面，因此我们需要开一个 map 记录删除过的数。
最后直接将 (p) 转成二进制数输出即可。
int T, n, m;
string s, ans;
LL p, k;
vector <LL> v;
map <LL, bool> ap;
int main()
{
T = gi();
while (T--)
{
n = gi(), m = gi();
v.clear();
ap.clear();
for (int i = 1; i <= n; i+=1)
{
cin >> s;
reverse(s.begin(), s.end());
LL now = 1ll, x = 0;
for (int j = 0; j < s.size(); j+=1)
{
x += (s[j] - '0') * now, now <<= 1ll;
}
v.push_back(x);
}
sort(v.begin(), v.end());
k = 1ll << m;
p = (k - 1) >> 1ll;
for (auto x : v)
{
ap[x] = true;
if (k & 1ll)
{
if (x >= p)
{
--p;
while (ap[p]) --p;
}
}
else
{
if (x <= p)
{
++p;
while (ap[p]) ++p;
}
}
--k;
}
ans = "";
for (int i = 0; i < m; i+=1)
if (p >> i & 1) ans += "1";
else ans += "0";
reverse(ans.begin(), ans.end());
cout << ans << endl;
}
return 0;
}