B. Minimax
一个简单的动态规划，通过穷举法遍历每一个可能的行列分割点 (x, y)，计算并更新最小差值。
int a[510][510],mx[5][510][510];
void solve() {
int n,m; cin >> n >> m;
memset(mx,0,sizeof(mx));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
mx[1][i][j] = max({mx[1][i - 1][j],mx[1][i][j - 1],a[i][j]});
}
}
for(int i = 1; i < n; i++) {
for(int j = m; j > 1; j--) {
mx[2][i][j] = max({mx[2][i - 1][j],mx[2][i][j + 1],a[i][j]});
}
}
for(int i = n; i > 1; i--) {
for(int j = 1; j < m; j++) {
mx[3][i][j] = max({mx[3][i + 1][j],mx[3][i][j - 1],a[i][j]});
}
}
for(int i = n; i > 1; i--) {
for(int j = m; j > 1; j--) {
mx[4][i][j] = max({mx[4][i + 1][j],mx[4][i][j + 1],a[i][j]});
}
}
int ans = inf;
for(int i = 2; i < n; i++) {
for(int j = 2; j < m; j++) {
int t = max({mx[1][i - 1][j - 1],mx[2][i - 1][j + 1],mx[3][i + 1][j - 1],mx[4][i + 1][j + 1]})
- min({mx[1][i - 1][j - 1],mx[2][i - 1][j + 1],mx[3][i + 1][j - 1],mx[4][i + 1][j + 1]});
ans = min(ans,t);
}
}
cout << ans << endl;
}
C. Channel
要考虑到下线的人可能是一直是同一个人,所以只要一开始的人加上新上线的人比n大就有可能全部人都阅读了
void solve() {
int n, a, q, cnt = 0;
cin >> n >> a >> q;
int st = a;
string s; cin >> s;
bool flag = false;
if (a >= n) flag = true; // 如果初始时就有足够的在线人数
for (int i = 0; i < q; i++) {
if (s[i] == '-') a--;
else {
cnt++;
a++;
}
if (a >= n) flag = true; // 如果在任意时刻在线人数 >= n，直接认为所有人都阅读了
}
if (flag) cout << "YES" << endl;
else if (cnt + st >= n) { // 如果上线操作的次数加上初始在线人数 >= n，则有可能所有人都阅读
cout << "MAYBE" << endl;
}
else cout << "NO" << endl;
}
G. xortion
题意是找到一个索引 P，使得对于所有 i，A[P] ^ X >= A[i] ^ X，XOR 运算是按位进行的，所以我们可以通过字典树来优化查询,因为是^运算，所以我们按位时尽可能取反，才能使结果最大，字典树可以用来处理前缀之类的问题
int cnt[N * 32]; // 每个节点对应的编号
int tr[N * 32][2]; // Trie 树的每个节点的左右子节点
int idx = N * 31; // 节点编号的索引
int a[N];
void insert(int x, int id) {
int p = 0;
for (int i = 31; i >= 0; i--) {
int j = (x >> i) & 1;//x的第i位二进制
if (!tr[p][j]) tr[p][j] = ++idx;
p = tr[p][j];
cnt[p] = min(cnt[p], id); // 记录最小的 id
}
}
// 给定 x，返回使得 A[P] ^ X 最大的索引
int query(int x) {
int p = 0;
for (int i = 31; i >= 0; i--) {
int j = (x >> i) & 1;//x的第i位二进制
if (tr[p][!j]) p = tr[p][!j]; // 选择与当前位不同的路径，使结果最大
else p = tr[p][j]; // 否则选择当前位的路径
}
return cnt[p]; // 返回最小的索引
}
void solve() {
int n, q;
cin >> n >> q;
memset(tr, 0, sizeof(tr));
fill(cnt, cnt + N * 32, inf);
idx = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
insert(a[i], i);
}
while (q--) {
int x;
cin >> x;
cout << query(x) << endl;
}
}
L. Abstract Picture
我们可以先找到确定是第二次涂的行或列，再将它们从影响的其他行或列中剪掉，看看有没有新的明确的行列，最后那些没有明确的，可以都涂上a，输出时要反向输出，因为我们是倒着推的,这个过程可以用bfs实现
int n;
char a[N][N];
int col[N][200],vis[N],cnt[N];
vector<PII> ans;
void bfs() {
queue<PII> q;
for(int i = 1; i <= 2 * n; i++) {
if(cnt[i]) {
for(int j = 'a'; j <= 'z'; j++) {
if(cnt[i] == col[i][j]) {
q.push({i,j});
vis[i] = 1;
}//将那些确定染色的行列先加入队列（这些行和列一定是第二次的染色）
}
}
}
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
ans.push_back({x,y});
if(x <= n) {
for(int i = n + 1; i <= 2 * n; i++) {
if(a[x][i - n] != '?' && !vis[i]) {
cnt[i]--,col[i][y]--;
if(cnt[i]) {
for(int j = 'a'; j <= 'z'; j++) {
if(cnt[i] == col[i][j]) {
q.push({i,j});
vis[i] = 1;
}
}
}
}
}
}//将确定的行对每个列的影响减去，如果有列在其中确定了，也加入队列
else {
for(int i = 1; i <= n; i++) {
if(a[i][x - n] != '?' && !vis[i]) {
cnt[i]--,col[i][y]--;
if(cnt[i]) {
for(int j = 'a'; j <= 'z'; j++) {
if(cnt[i] == col[i][j]) {
q.push({i,j});
vis[i] = 1;
}
}
}
}
}
}////将确定的列对每个行的影响减去，如果有行在其中确定了，也加入队列
}
for(int i = 1; i <= 2 * n; i++) {
if(!vis[i]) {
ans.push_back({i,'a'});
}
}// 如果某一行或列还未染色，随便染个颜色（保证每行每列都染一次）
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(a[i][j] != '?') {
cnt[i]++,cnt[j + n]++;
col[i][a[i][j]]++,col[j + n][a[i][j]]++;//行，列中该颜色出现次数
}
}
}
bfs();
reverse(ans.begin(),ans.end());// 倒序输出
for(auto [x,y] : ans) {
if(x <= n) cout << 'h' << ' ' << x <<' ' << char(y) << endl;
else cout << 'v' << ' ' << x - n <<' ' << char(y) << endl;
}
}
