上海计算机学会2021年1月月赛C++丙组T2康托表
发布时间
阅读量：
阅读量
题目背景
康托是一名数学家，他证明了一个重要的定理，需要使用一张表：
1/1 2/1 3/1 4/1 5/1⋯
1/2 2/2 3/2 4/2 5/2⋯
1/3 2/3 3/3 4/3 5/3⋯
1/4 2/4 3/4 4/4 5/4⋯
1/5 2/5 3/5 4/5 5/5⋯⋯⋯⋯⋯⋯⋯
这个表的规律是：
- 从上到下：每一行的分子依次增大；
- 从左到右：每一列的分母依次增大。
康托采用了一套独特的无一重复且无一遗漏的方式，在表格中罗列出了所有的数字。具体来说，在表格左上角的位置（1/1）开始，并按照Z字形路径依次进行遍历。其中：
- 首先从表格左上角的第一个单元格（1/1）开始。
- 然后向右移动至右端边缘。
- 接着向下移动一行并转为向左移动。
- 最后继续此过程直到所有单元格都被遍历完毕。
以下是按照指定规则对原文进行的同义改写
注
1/4, 2/3, 3/2, 4/1, 5/1, 4/2, ⋯
题目描述
给定一个分数 a/b，请计算该分数在康托表中排名第几。
输入格式
两个整数：a 与 b，表示一个分数 a/b。
输出格式
单个数字：表示输入分数在康托表中的名次。
数据范围
- 对于 50% 的分数，1≤a,b≤100；
- 对于 100% 的分数，1≤a,b≤10000。
样例数据
将矩形绕其右边缘逆时针旋转45度后会形成一个三角形结构。此时，在该结构中位于第a + b - 1行的位置上会放置分数a/b。具体而言，在计算完前a + b - 2行的所有数字之和之后（记作sum），我们可以根据a + b的奇偶特性来确定最终结果的位置：当a + b为奇数时，在该位置上的值为第a个元素；而当其为偶数时，则取该位置上的第b个元素。这部分逻辑可以通过参考代码中的相应实现来完成。
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long a,b;
cin>>a>>b;
long long ans;
ans=(1+a+b-2)*(a+b-2)/2;
if ((a+b)%2==1){
ans+=a;
}else{
ans+=b;
}
cout<<ans<<endl;
return 0;
}全部评论 (0)
还没有任何评论哟~