题目分析

题意理解

这是一个导师选择系统：

• n 个选手，m 个导师
• 每个导师有战队人数上限
• 每个选手有志愿表（最多C个导师每档志愿）
• 录取规则：按排名顺序，每个选手被其最高可录取志愿录取
• 需要回答两个问题：
  1. 在最优方案中，每个选手被第几志愿录取
  2. 选手需要上升多少名才能达到理想志愿

关键难点

1. 最优录取规则：前i名的录取结果最优
2. 动态匹配：每个选手的录取会影响后续选手
3. 二分排名：计算最少需要上升的名次

算法思路

核心思想：动态匈牙利算法 + 二分答案

1. 第一问：模拟最优录取

• 按排名顺序处理每个选手
• 对于每个选手，从第1志愿到第m志愿尝试匹配
• 使用类似匈牙利算法的DFS进行匹配

2. 第二问：二分最少上升名次

• 对于每个选手i，二分他需要上升到哪个排名
• 检查在某个排名时，他能否被理想志愿录取

代码详解

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int N = 205;
int t, c, n, m;
int b[N];        // 导师战队上限
int a[N][N];     // a[i][j]: 选手i将导师j排在第几志愿
int s[N];        // 选手的理想志愿
int to[N];       // to[i]: 选手i匹配的导师
vector<int> v[N][N];  // v[i][j]: 选手i的第j志愿包含的导师
bool vis[N];     // 访问标记
int ans[N];      // 第一问答案

// 存储历史状态
vector<int> h[N][N];  // h[i][j]: 处理完前i个选手后，导师j的战队成员
int g[N][N];          // g[i][j]: 处理完前i个选手后，选手j的匹配结果

// DFS匹配：u-当前选手, st-从第几志愿开始尝试
bool dfs(int u, int st) {
    if (st) {
        // 按志愿顺序尝试匹配
        for (int i = 1; i <= st; i++) {
            for (int j : v[u][i]) {  // 遍历第i志愿的所有导师
                if (!vis[j]) {
                    vis[j] = 1;
                    bool ok = false;
                    
                    // 如果导师还有空位，直接匹配
                    if (h[0][j].size() < b[j]) {
                        ok = true;
                    } else {
                        // 否则尝试让已匹配的选手换导师
                        for (int k : h[0][j]) {
                            if (dfs(k, 0)) {  // 递归尝试
                                ok = true;
                                break;
                            }
                        }
                    }
                    
                    if (ok) {
                        to[u] = j;  // 记录匹配
                        return true;
                    }
                }
            }
        }
        return false;
    } else {
        // 为已匹配选手寻找新的匹配（用于调整）
        for (int i : v[u][a[u][to[u]]]) {
            if (!vis[i]) {
                vis[i] = 1;
                bool ok = false;
                
                if (h[0][i].size() < b[i]) {
                    ok = true;
                } else {
                    for (int k : h[0][i]) {
                        if (dfs(k, 0)) {
                            ok = true;
                            break;
                        }
                    }
                }
                
                if (ok) {
                    to[u] = i;  // 更新匹配
                    return true;
                }
            }
        }
        return false;
    }
}

int main() {
    scanf("%d%d", &t, &c);
    
    while (t--) {
        scanf("%d%d", &n, &m);
        
        // 读入导师上限
        for (int i = 1; i <= m; i++) {
            scanf("%d", &b[i]);
            h[0][i].clear();  // 清空当前状态
        }
        
        memset(to, 0, sizeof(to));
        
        // 初始化志愿表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                v[i][j].clear();
            }
        }
        
        // 读入选手志愿
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
                if (a[i][j]) {
                    v[i][a[i][j]].pb(j);  // 记录选手i的第a[i][j]志愿包含导师j
                }
            }
        }
        
        // 读入理想志愿
        for (int i = 1; i <= n; i++) {
            scanf("%d", &s[i]);
        }
        
        // 第一问：计算最优录取结果
        for (int i = 1; i <= n; i++) {
            memset(vis, 0, sizeof(vis));
            
            // 为当前选手寻找匹配
            if (dfs(i, m)) {  // 从第1志愿到第m志愿尝试
                ans[i] = a[i][to[i]];  // 记录录取志愿
            } else {
                ans[i] = m + 1;  // 没有匹配成功
            }
            
            printf("%d ", ans[i]);
            
            // 保存当前状态（处理完前i个选手）
            for (int j = 1; j <= m; j++) {
                h[i][j] = h[0][j];  // 保存导师战队状态
            }
            for (int j = 1; j <= n; j++) {
                g[i][j] = to[j];    // 保存选手匹配状态
            }
        }
        printf("\n");
        
        // 第二问：计算最少需要上升的名次
        for (int i = 1; i <= n; i++) {
            int l = 0, r = i - 1, mid;
            
            // 二分查找：找到最大的l，使得选手i在排名l+1时能被理想志愿录取
            while (l < r) {
                mid = (l + r + 1) / 2;
                
                // 恢复到处理完前mid个选手的状态
                memset(vis, 0, sizeof(vis));
                for (int j = 1; j <= m; j++) {
                    h[0][j] = h[mid][j];
                }
                for (int j = 1; j <= n; j++) {
                    to[j] = g[mid][j];
                }
                
                // 检查选手i能否被理想志愿录取
                if (dfs(i, s[i])) {
                    l = mid;    // 可以录取，尝试更小的排名
                } else {
                    r = mid - 1; // 不能录取，需要更大排名
                }
            }
            
            // 最终检查
            memset(vis, 0, sizeof(vis));
            for (int j = 1; j <= m; j++) {
                h[0][j] = h[l][j];
            }
            for (int j = 1; j <= n; j++) {
                to[j] = g[l][j];
            }
            
            if (dfs(i, s[i])) {
                // 需要上升的名次 = 当前排名 - (l + 1)
                printf("%d ", i - 1 - l);
            } else {
                // 无论如何都无法满足理想志愿
                printf("%d ", i);
            }
        }
        printf("\n");
    }
    
    return 0;
}

算法核心要点详解

1. 匹配算法（类匈牙利算法）

dfs(u, st) 函数：

• st > 0: 为选手u从第1志愿到第st志愿尝试匹配
• st = 0: 为已匹配选手u寻找新的匹配（用于调整）

匹配过程：

1. 按志愿顺序尝试导师
2. 如果导师有空位，直接匹配
3. 如果导师已满，尝试让已匹配的选手换导师（递归调整）

2. 状态保存与恢复

• h[i][j]: 处理完前i个选手后，导师j的战队成员
• g[i][j]: 处理完前i个选手后，选手j的匹配结果
• 用于第二问的二分检查

3. 二分查找策略

对于每个选手i：

• 二分查找最大的l，使得选手i在排名l+1时能被理想志愿录取
• 需要上升的名次 = i - (l + 1)

4. 复杂度分析

• 第一问: O(n × m × n) 每个选手最多尝试m个导师，每个导师最多调整n个选手
• 第二问: O(n × logn × 匹配复杂度)
• 总体可以接受 n ≤ 200 的数据

示例演示

以样例1第一组数据为例：

选手1: 志愿1-无, 志愿2-导师1,2
选手2: 志愿1-导师1, 志愿2-导师2
导师1,2: 上限各1人

处理过程：
1. 选手1: 志愿1无导师 → 志愿2尝试导师1(成功) → 录取志愿2
2. 选手2: 志愿1导师1(已满) → 尝试调整选手1 → 选手1换到导师2 → 选手2录取导师1 → 录取志愿1

总结

这道题综合运用了：

1. 二分图匹配 的匈牙利算法思想
2. 动态状态保存 用于后续查询
3. 二分答案 计算最少上升名次
4. 贪心策略 按志愿顺序尝试匹配

是一个很好的匹配问题，考察了对动态匹配和状态管理的理解。