题解：蛋糕分享（Cake Share, POJ 3374）

一、题目分析

本题要求将蛋糕均分为不超过 N 块，按比例从小到大排列所有可能的分配方案（包括0和1），并查询第 k 个方案的具体比例。关键在于生成所有不可约分数（即最简分数）并排序。

二、核心思路

1. 法里数列（Farey Sequence）：
   法里数列是指所有介于0和1之间的最简分数，按从小到大排序。例如，当 N=5 时，法里数列是 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1。

2. 递归生成法里数列：
   通过递归中项法生成法里数列的前半部分（直到1/2），再利用对称性构造后半部分。对于两个相邻分数 a/b 和 c/d，其中项为 (a+c)/(b+d)。若中项的分子和分母均不超过 N，则加入数列。

3. 查询处理：

   • 若 k 在前半部分，直接返回对应分数。
   • 若 k 在后半部分，利用对称性 1 - 前半部分对应分数 计算。

三、代码解析

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>

#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 10010
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)

using namespace std;

int Read()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}

void Print(int a)
{
     if(a>9)
         Print(a/10);
     putchar(a%10+'0');
}

int total,n,farey[4000000][2],all;
// 递归生成法里数列的前半部分
void makefarey(int x1,int y1,int x2,int y2)
{
    if(x1+x2>n||y1+y2>n) return;
    makefarey(x1,y1,x1+x2,y1+y2);
    total++;
    farey[total][0]=x1+x2;
    farey[total][1]=y1+y2;
    makefarey(x1+x2,y1+y2,x2,y2);
}

int main()
{
    int q;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        if(n==1)  // 特殊处理N=1的情况
        {
            while(q--)
            {
                int k;
                scanf("%d",&k);
                if(k==1) printf("0/1\n");
                else if(k==2) printf("1/1\n");
                else puts("No Solution");
            }
            continue;
        }
        total=1;
        farey[1][0]=0;  // 初始化第一个元素为0/1
        farey[1][1]=1;
        makefarey(0,1,1,2);  // 生成0/1到1/2之间的分数
        farey[total+1][0]=1;  // 添加中间元素1/2
        farey[total+1][1]=2;
        all=total*2+1;  // 总元素数
        while(q--)
        {
            int k;
            scanf("%d",&k);
            if(k>all) puts("No Solution");
            else if(k<=total+1) printf("%d/%d\n",farey[k][0],farey[k][1]);
            else printf("%d/%d\n",farey[all-k+1][1]-farey[all-k+1][0],farey[all-k+1][1]);
        }
    }
    return 0;
}

四、步骤详解

1. 特殊处理N=1：
   当 N=1 时，只有两种情况：0/1 和 1/1。

2. 生成法里数列前半部分：

   • 从 0/1 开始，递归生成到 1/2 之间的所有最简分数。
   • 递归函数 makefarey 接受两个分数 x1/y1 和 x2/y2，生成它们的中项并继续递归。

3. 构造完整数列：

   • 前半部分：0/1 到 1/2。
   • 中间元素：1/2。
   • 后半部分：利用对称性构造，例如 1/2 之后的元素是 1 - 前半部分对应元素。

4. 查询处理：

   • 若 k 在前半部分，直接查询 farey[k]。
   • 若 k 在后半部分，通过 all - k + 1 找到前半部分对应元素，计算 1 - 该元素。

五、关键点总结

1. 法里数列性质：

   • 生成的分数均为最简形式，无需额外约分。
   • 递归生成的时间复杂度为 O(N²)，适用于 N ≤ 5000 的范围。

2. 对称性优化：

   • 利用 1 - x 的对称性，避免生成完整数列，节省空间和时间。

3. 边界处理：

   • 处理 k 超出范围的情况，输出 No Solution。

该解法通过法里数列的递归生成和对称性优化，高效地解决了分数排序和查询问题，确保在题目约束下快速响应查询。