A.Qualification Rounds
核心思路
- 每个问题用
k位掩码表示哪些队伍知道该题（位为1表示知道）。 - 选出的问题集合合法，当且仅当每个队伍的贡献和 ≥ 0，其中贡献定义为：知道该题 → -1，不知道 → +1。
- 关键性质：若存在合法集合，则必存在一个大小 ≤ 8 的合法集合（因为
k ≤ 4）。 - 因此只需枚举所有由 1~8 个问题组成的集合，检查贡献和是否非负。
- 问题类型最多 16 种（
2^k ≤ 16），将每种类型的出现次数截断至 8，用 DFS 枚举每种类型取 0~8 个，总个数 ≤ 8。
具体步骤
-
读取数据并压缩
- 读入
n, k。 - 对每个问题，读入
k个 0/1，构造掩码mask。 - 记录每种掩码的出现次数到
cnt[16]，但最多保留 8 个（cnt[mask] = min(cnt[mask] + 1, 8)）。
- 读入
-
DFS 搜索
-
函数
dfs(pos, total)表示处理到第pos种掩码（0~15），已选问题总数total。 -
若
total > 0，检查当前所有队伍的贡献和sum[0..k-1]是否全部 ≥ 0，若是则返回true。 -
若
pos == 16，返回false。 -
对当前掩码
pos，取maxTake = min(cnt[pos], 8 - total)，枚举take = 0..maxTake：- 将
take个该掩码的问题加入集合，更新sum[j]（若该位为1则 -1，否则 +1）。 - 递归
dfs(pos+1, total+take)，成功则返回true。 - 回溯，恢复
sum。
- 将
-
-
输出结果
- 调用
dfs(0, 0)，若返回true输出"YES"，否则"NO"。
- 调用
题解
#include <bits/stdc++.h>
using namespace std;
int n, k;
int cnt[16], cur[16], sum[4];
bool dfs(int pos, int total) {
if (total > 0) {
bool ok = true;
for (int j = 0; j < k; j++) {
if (sum[j] < 0) {
ok = false;
break;
}
}
if (ok) return true;
}
if (pos == 16) return false;
int maxTake = min(cnt[pos], 8 - total);
for (int take = 0; take <= maxTake; take++) {
cur[pos] = take;
int mask = pos;
for (int j = 0; j < k; j++) {
int bit = (mask >> j) & 1;
int delta = (bit == 1) ? -1 : 1;
sum[j] += take * delta;
}
if (dfs(pos + 1, total + take)) return true;
for (int j = 0; j < k; j++) {
int bit = (mask >> j) & 1;
int delta = (bit == 1) ? -1 : 1;
sum[j] -= take * delta;
}
}
return false;
}
int main() {
freopen("rtmrts.in", "r", stdin);
freopen("rtmrts.out", "w", stdout);
cin >> n >> k;
for (int i = 0; i < n; i++) {
int mask = 0;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
if (x) mask |= (1 << j);
}
cnt[mask] = min(cnt[mask] + 1, 8);
}
if (dfs(0, 0)) cout << "YES";
else cout << "NO";
return 0;
}
B.Dima and a Bad XOR
核心思路
从矩阵每行选一个数，使异或和大于 0。若所有行都选第 1 列时异或和已非零，则直接成功；否则，只需在某一行换成一个与该行第 1 列不同的数，异或和就会变成两个不同数的异或，必然非零。若每行的所有数都相同，则无论如何选择，异或和恒等于第一列的异或和（为零），无解。
具体步骤
-
读入矩阵
a[n][m]。 -
计算全选第 1 列的异或和
xorsum。 -
若
xorsum != 0：输出"TAK"，并输出每行选第 1 列（列号 1）。 -
否则，遍历每一行
i，寻找一个列j（j >= 2）使得a[i][j] != a[i][0]：- 若找到，输出
"TAK"，并输出方案：第i行选j列，其余行选第 1 列。
- 若找到，输出
-
若所有行的所有元素都相同，输出
"NIE"。
题解
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("badxor.in", "r", stdin);
freopen("badxor.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
int xorsum = 0;
for (int i = 0; i < n; i++)
xorsum ^= a[i][0];
if (xorsum != 0) {
cout << "TAK\n";
for (int i = 0; i < n; i++)
cout << 1 << ' ';
return 0;
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
if (a[i][j] != a[i][0]) {
cout << "TAK\n";
for (int row = 0; row < n; row++) {
if (row == i)
cout << j + 1 << ' ';
else
cout << 1 << ' ';
}
return 0;
}
}
}
cout << "NIE";
return 0;
}
C.Boboniu and Bit Operations
核心思路
枚举答案 ans 从 0 到 511，判定 ans 是否可行：对每个 a[i] 是否存在 b[j]，使得 (a[i] & b[j]) | ans == ans（即结果为 ans 的子集）。若所有行都满足，则最终或值不超过 ans。因为枚举递增，第一个可行 ans 即为最小答案。
具体步骤
-
读入 n,m 及数组 a,b。
-
令 X 从 0 到 511 循环：
- 对每个 i，初始化 row_ok=false。
- 对每个 j，计算 c = a[i] & b[j]，若 (c | X) == X，则 row_ok=true 并跳出。
- 若有任何行 row_ok==false，则当前 X 不可行，跳出外层循环。
-
若所有行都可行，输出 X 并结束程序。
题解
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("bit.in", "r", stdin);
freopen("bit.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
for (int ans = 0; ans < 512; ans++) {
bool ok = true;
for (int i = 0; i < n; i++) {
bool row_ok = false;
for (int j = 0; j < m; j++) {
int c = a[i] & b[j];
if ((c | ans) == ans) {
row_ok = true;
break;
}
}
if (!row_ok) {
ok = false;
break;
}
}
if (ok) {
cout << ans;
return 0;
}
}
return 0;
}
D.Factorials and Powers of Two
核心思路
枚举所有阶乘数的子集（仅使用 3! 到 14!，每个最多一次），对于每个子集，若其和 sum ≤ n，则用 n - sum 的二进制表示补足剩余部分。总项数为：子集中阶乘个数 + n - sum 的二进制中 1 的个数。取所有情况的最小值，并与直接使用二进制表示的项数比较，取最小。
具体步骤
-
预处理：计算 3! 到 14!，存入
fac数组（因为 15! > 1e12，不再需要）。 -
读入测试次数
t。 -
对每个
n：-
初始答案
ans = popcount(n)（即全部用 2 的幂表示）。 -
枚举
mask从 0 到(1 << fac.size()) - 1：- 计算所选阶乘的和
sum。 - 若
sum <= n，则当前项数为popcount(mask) + popcount(n - sum)，更新ans。
- 计算所选阶乘的和
-
输出
ans。
-
题解
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector <ll> fac;
int main()
{
freopen("factorials.in", "r", stdin);
freopen("factorials.out", "w", stdout);
ll x = 1;
for (int i = 1; i <= 14; i ++)
{
x = x * i;
if (x > (ll)1e12) break;
if (i >= 3) fac.push_back(x);
}
ll t;
cin >> t;
while (t --)
{
ll n;
cin >> n;
int ans = __builtin_popcountll(n);
for (int mask = 0; mask <= (1 << (int)fac.size()); mask ++)
{
ll sum = 0;
for (int i = 0; i <= (int)fac.size(); i ++)
{
if (mask >> i & 1)
{
sum += fac[i];
}
}
if (sum <= n)
{
ans = min(ans, __builtin_popcountll(mask) + __builtin_popcountll(n - sum));
}
}
cout << ans << '\n';
}
return 0;
}
E.Party Lemonade
核心思路
预处理价格使 c[i] 表示购买恰好 2^i 升的最小花费（可用多个小瓶或一个大瓶）。然后用数位 DP 处理 L 的二进制位：dp0 表示当前容量恰好等于 L 的高位前缀的最小花费，dp1 表示当前容量已经大于前缀的最小花费。按位决策：若 L 当前位为 1，必须买 1 个该位；若为 0，可选 0 个或 1 个（后者进入大于状态）。最后取 min(dp0, dp1)。
具体步骤
-
读入
n, L，价格数组c[0..30]，未给定的设为无穷大。 -
正向预处理：
c[i] = min(c[i], 2*c[i-1])（小瓶合成大瓶）。 -
反向预处理：
c[i] = min(c[i], c[i+1])（大瓶拆开可能更便宜）。 -
从高位到低位（30 到 0）遍历
L的二进制位：- 若该位为 1：
ndp0 = dp0 + c[i]。 - 若该位为 0：
ndp0 = dp0（选 0 个），ndp1 = min(ndp1, dp0 + c[i])（选 1 个进入大于状态）。 ndp1 = min(ndp1, dp1)（继承之前的大于状态）。
- 若该位为 1：
-
输出
min(dp0, dp1)。
题解
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 30;
const ll INF = 4e18;
int main()
{
freopen("party.in", "r", stdin);
freopen("party.out", "w", stdout);
int n;
ll L;
cin >> n >> L;
vector<ll> c(N + 1, INF);
for (int i = 0; i < n; i ++) cin >> c[i];
for (int i = 1; i <= N; i ++)
c[i] = min(c[i], 2 * c[i - 1]);
for (int i = N - 1; i >= 0; i --)
c[i] = min(c[i], c[i + 1]);
ll dp0 = 0, dp1 = INF;
for (int i = N; i >= 0; i --)
{
int bit = (L >> i) & 1LL;
ll ndp0 = INF, ndp1 = INF;
if (bit == 1)
{
ndp0 = min(ndp0, dp0 + c[i]);
}
else
{
ndp0 = min(ndp0, dp0);
ndp1 = min(ndp1, dp0 + c[i]);
}
ndp1 = min(ndp1, dp1);
dp0 = ndp0;
dp1 = ndp1;
}
cout << min(dp0, dp1);
return 0;
}
F.XOR, Expression and Two Binary Numbers
核心思路
填充过程只产生三类值：A = a1，B = aM，C = A xor B。
记最终序列中等于 A 或 B 的数量均为 end，等于 C 的数量为 mid。
递推关系：初始 end = 1, mid = 0；每增加一轮，end = end + mid，mid = 2 * old_end - 1。
答案 = end * cnt1(A)*(n-cnt1(A)) + end * cnt1(B)*(n-cnt1(B)) + mid * cnt1(C)*(n-cnt1(C))，其中 cnt1(X) 为二进制中 1 的个数。
具体步骤
- 读入
n, k及字符串s, t。 - 统计
oneA = s中 '1' 的个数，oneB = t中 '1' 的个数，oneC = s与t不同字符的个数（即A xor B中 1 的个数）。 - 初始化
end = 1, mid = 0，循环i = 1..k更新：
nend = end + mid，nmid = 2 * end - 1，end = nend, mid = nmid。 - 计算并输出
end * oneA * (n - oneA) + end * oneB * (n - oneB) + mid * oneC * (n - oneC)。
题解
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
freopen("binary.in", "r", stdin);
freopen("binary.out", "w", stdout);
int T;
cin >> T;
while (T --)
{
int n, k;
string s, t;
cin >> n >> k >> s >> t;
ll oneA = 0, oneB = 0, oneC = 0;
for(int i = 0; i < n; i++)
{
oneA += (s[i] == '1');
oneB += (t[i] == '1');
oneC += (s[i] != t[i]);
}
ll end = 1, mid = 0;
for(int i = 1; i <= k; i++)
{
ll nend = end + mid;
ll nmid = 2 * end - 1;
end = nend;
mid = nmid;
}
ll ans = 0;
ans += end * oneA * (n - oneA);
ans += end * oneB * (n - oneB);
ans += mid * oneC * (n - oneC);
cout << ans << '\n';
}
return 0;
}
评论
0