题意分析

题目背景

本题模拟伊朗大学入学考试的选拔过程，属于稳定匹配问题的变种。系统需要根据学生的分数、志愿顺序和本地优先规则，将$N$名学生分配到$M$个FDU项目中，每个项目有固定招生名额。

核心规则

1. 本地优先规则：

   • 若学生$B$是FDU$F$所在区域的本地生，且其分数$M_B \geq 0.7 \times M_A$（$A$为非本地生），则$B$优先于$A$被$F$录取。
   • 数学表达：
     $ \text{优先级}(B) > \text{优先级}(A) \iff (R_B = R_F) \land (M_B \geq 0.7 \times M_A) $
     其中$R_B$为学生区域，$R_F$为FDU区域。

2. 公平规则：
   学生必须按其志愿顺序依次尝试匹配，未被任何志愿录取则落榜。

输入输出

• 输入：
  • 学生数据：区域$R_i$、分数$M_i$、志愿数$K$、志愿列表$F_{i1}, \dots, F_{iK}$。
  • FDU数据：区域$R_j$、名额$C_j$。
• 输出：每名学生的录取FDU编号或not accepted。

解题思路

1. 问题建模

• 学生与FDU的优先级排序：
  对每个FDU$F_j$，按以下规则排序所有申请学生：
  1. 本地生优先（若满足$M_B \geq 0.7 \times M_A$）。
  2. 按分数降序排序。
     公式化：
     $ \text{compare}(A, B) = \begin{cases} \text{true} & \text{if } (R_B = R_j) \land (M_B \geq 0.7 \times M_A) \\ \text{false} & \text{otherwise} \end{cases} $

2. 稳定匹配算法（Gale-Shapley变种）

• 学生主动提议：
  每名学生按志愿顺序依次尝试匹配FDU，若FDU名额未满则直接录取；否则与已录取学生中优先级最低者比较，优胜劣汰。
• 终止条件：
  所有学生完成志愿尝试或被标记为落榜。

3. 关键数据结构

• 排名映射：
  map2[FDU][学生ID]存储每个FDU对学生的优先级排名。
• 录取列表：
  woman[FDU].manname[]记录当前录取的学生ID。

算法实现

代码框架

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 200
#define eps 1e-6
using namespace std;
struct node
{
    int id,region,score,k;
}stu[N];
struct node1
{
    int region,num;
}sch[N];
struct node2
{
    int cnt;
    int manname[N];
}woman[N];
int r,n,m;
int map1[N][N],map2[N][N],man[N],times[N],vis[N];
int cmp(node a,node b)
{
    if(a.region==r)
    {
        if(b.region==r)
            return a.score>b.score;
        if(b.region!=r)
        {
            if(abs(a.score-0.7*b.score)<eps)
                return 0;
            else
                return a.score>0.7*b.score;
        }
    }
    else if(b.region==r)
    {
        if(a.region==r)
            return a.score>b.score;
        if(a.region!=r)
        {
            if(abs(b.score-0.7*a.score)<eps)
                return 1;
            else
                return b.score<0.7*a.score;
        }
    }
    else
        return a.score>b.score;
}
int cmp1(node a,node b)
{
    return a.id<b.id;
}
void makerank()
{
    int i,j;
    for(i=1;i<=m;i++)
    {
        r=sch[i].region;
        sort(stu+1,stu+n+1,cmp);
        for(j=1;j<=n;j++)
            map2[i][stu[j].id]=j;
    }
    sort(stu+1,stu+n+1,cmp1);
}
void Gale_Shapley()
{
    int flag=1,i,j,worstrank,worstrankj;
    memset(man,0,sizeof(man));
    for(i=1;i<=n;i++)
        times[i]=1;
    for(i=1;i<=n;i++)
        vis[i]=0;
    for(i=1;i<=m;i++)
        woman[i].cnt=0;
    while(flag)
    {
        flag=0;
        for(i=1;i<=n;i++)
        {
            while(!man[i]&&!vis[i])
            {
                flag=1;
                if(times[i]>stu[i].k)
                {
                    vis[i]=1;
                    break;
                }
                int name=map1[i][times[i]];
                if(woman[name].cnt<sch[name].num)
                {
                    woman[name].manname[++woman[name].cnt]=i;
                    man[i]=name;
                    times[i]++;
                }
                else if(woman[name].cnt==sch[name].num)
                {
                    worstrank=0;
                    for(j=1;j<=woman[name].cnt;j++)
                    {
                        if(map2[name][woman[name].manname[j]]>worstrank)
                        {
                            worstrank=map2[name][woman[name].manname[j]];
                            worstrankj=j;
                        }
                    }
                    if(map2[name][i]<worstrank)
                    {
                        man[woman[name].manname[worstrankj]]=0;
                        woman[name].manname[worstrankj]=i;
                        man[i]=name;
                        times[i]++;
                    }
                    else
                        times[i]++;
                }
            }
        }
    }
}
int main()
{ 
    int T,j,i;
    scanf("%d",&T);
    while(T--)
    {
        memset(map1,0,sizeof(map1));
        memset(map2,0,sizeof(map2));
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            stu[i].id=i;
            scanf("%d%d%d",&stu[i].region,&stu[i].score,&stu[i].k);
            for(j=1;j<=stu[i].k;j++)
            {
                scanf("%d",&map1[i][j]);
            }
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&sch[i].region,&sch[i].num);
        }
        makerank();
        Gale_Shapley();
        for(i=1;i<=n;i++)
            if(vis[i])
                printf("not accepted\n");
            else
                printf("%d\n",man[i]);
        if(T) printf("\n");
    }
    return 0;
}

复杂度分析

• 时间：$O(M \times N \log N)$（排序） + $O(N \times M)$（匹配），总体$O(N^2 \log N)$。
• 空间：$O(N \times M)$存储排名和志愿表。