June Challenge 2017 | Xenny and Coin Rankings

题意

Xenny 暑假时闲来无事，对国际安全局（ISA）发布的所有程序进行了逆向工程。作为奖励，ISA 向他提供了无限的字节币（其实是一种硬币）。 生活漫长又无趣，人生找不到意义。无所事事的 Xenny 决定把这些硬币铺开在二维平面上。Xenny 实在是无事可做，所以他决定按照一定规则来排列这些硬币，而不是像平常往储钱罐里存钱一样单调乏味。 平面上 x ≥ 0 且 y ≥ 0 的每个整点 (x, y) 上均放有一枚硬币。Xenny 要为每枚硬币赋予其等级，规则如下： 记第 k 枚的硬币坐标为 ( xk , yk )，其等级为 Rk 。假设有两枚硬币 i 和 j，如果 xi+yi<xj+yj ， 或者 xi+yi=xj+yj且xi<xj ，那么应当满足 Ri<Rj 。 由这一规则，我们可以确定所有硬币等级的顺序。将硬币按照其等级的顺序排序，Xenny 定义一枚硬币的等级为，硬币在序列中的下标（下标从 1 开始）。 按照此规则排好的一部分硬币如下图所示： 考虑以 (0, 0) 为左下角，(U, V ) 为右上角的矩形区域，位于矩形内部或边界上的所有硬币的最大等级是多少？

解题思路

由题意可知，最大等级在（U,V）上，所以我们只需知道（U,V）上的等级即可。 等级分布如下： … 7 … 4 8 … 2 5 9 … 1 3 6 10 … 可以发现横坐标是+2，+3，+4，…，纵坐标是+1，+2，+3，…,或者+2，+3，+4，…或者+3，+4，+5，…等，加的开始依据横坐标的位置。 所以（U,V）对应的等级为 (U+1)∗(U+2)2+(U+1)∗V+V∗(V−1)2

参考代码

#include <iostream> using namespace std; typedef long long ll; int main(){ int t; ll u,v; cin>>t; while (t--){ cin>>u>>v; ll ans=(u+1)*(u+2)/2+(u+1)*v+v*(v-1)/2; cout<<ans<<endl; } return 0; }