KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） E - Patisserie ABC 2

题意

将$n^3$个三元组$(i,j,k),1\le i,j,k\le n$进行排序，问第$k$个三元组是什么

排序先按总和$i+j+k$进行排序，小的在前

相同和的情况下按$i\to j\to k$的顺序比对大小，小的在前（字典序小的在前）

思路

打表找规律，先按和进行分组，可得对于前几个$n$，和为$j\in [3,3\ast n]$的三元组数量如下
$$\begin{array}{rl}n=2:& 1,3,3,1\\ n=3:& 1,3,6,7,6,3,1\\ n=4:& 1,3,6,10,12,12,10,6,3,1\\ n=5:& 1,3,6,10,15,18,19,18,15,10,6,3,1\\ n=6:& 1,3,6,10,15,21,25,27,27,25,21,15,10,6,3,1\\ n=7:& 1,3,6,10,15,21,28,33,36,37,36,33,28,21,15,10,6,3,1\end{array}$$
由于呈左右对称规律，折半后表为（标红表示不进行对称处理）
$$\begin{array}{rl}n=2:& 1,3\\ n=3:& 1,3,6,7\\ n=4:& 1,3,6,10,12\\ n=5:& 1,3,6,10,15,18,19\\ n=6:& 1,3,6,10,15,21,25,27\\ n=7:& 1,3,6,10,15,21,28,33,36,37\end{array}$$
发现从第一个数到标绿的数字位置，之前每个数均为$1+2+\cdots +p$（$p$表示位置），每次增幅即下标，直到下标为$n$时截止

而从标绿数字的下一个数开始，每次增幅从$n-2$开始依次递减$2$

以$n=7$为例，第二个数到第七个数较前一个数的增幅为$+2,+3,+4,+5,+6,+7$，从第八个数开始变为$+5,+3,+1$

故根据上述规律，对于每组数据输入的$n$，我们可以将**和为$sum$时的三元组数量$tmp[sum]$**预处理出

int i=3; //sum的范围为3*1~3*n
for(int j=1;j<=n;i++,j++)tmp[i]=tmp[i-1]+j; //前n个数，每次增幅为j=1~n
for(int j=n-2;j>0;i++,j-=2)tmp[i]=tmp[i-1]+j; //第n+1个数开始，每次增幅从n开始每次-2
if(n%2) //这里处理对称，分奇偶处理
{int m=i-1;for(;i<=3*n;i++)tmp[i]=tmp[m-(i-m)];
}
else
{int m=i;for(;i<=3*n;i++)tmp[i]=tmp[m-1-(i-m)];
}

---

根据上方的预处理，我们可以得出$n,k$的限制下三元组$(i,j,k)$的和$sum$为多少

ll sum=3;
while(k>tmp[sum])
{k-=tmp[sum];sum++;
}

---

由于相同和的情况下是按照字典序进行排序的， 所以可以按从小到大的顺序枚举第一个数$a$，并得出后两个数相加之和$x=sum-a$

对于二元组$(j,k),1\le j,k\le n,j+k=sum$的情况数

明显当$sum\le n$时，种类数只有$sum-1$种：$(1,sum-1),(2,sum-2),\cdots ,(sum-1,1)$

故对于$sum\in [2,n+1]$，种类数为$1,2,\cdots ,n$

当$sum>n$时，种类数呈对称状逐级递减

即对于$sum\in [n+2,2n]$，种类数为$n-1,n-2,\cdots ,1$

由于$n$固定，这部分也可预处理成$tmp2$数组

rep(i,2,n+1)tmp2[i]=i-1;
rep(i,n+2,n+n)tmp2[i]=n*2+1-i;

---

于是枚举第一个数$a$，若$k>tmp2[sum-a]$，则第一个数比$a$大，继续枚举下去且让$k-=tmp2[sum-a]$

直到$k\le tmp2[sum-a]$，此时$a$便固定了下来，由于$n\le 10^6$，于是便可以直接枚举第二个数，求出第$k$个合法方案输出即可

程序

//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}ll tmp[3000050],tmp2[2000050];void init(int n)
{int i=3;for(int j=1;j<=n;i++,j++)tmp[i]=tmp[i-1]+j;for(int j=n-2;j>0;i++,j-=2)tmp[i]=tmp[i-1]+j;if(n%2){int m=i-1;for(;i<=3*n;i++)tmp[i]=tmp[m-(i-m)];}else{int m=i;for(;i<=3*n;i++)tmp[i]=tmp[m-1-(i-m)];}rep(i,2,n+1)tmp2[i]=i-1;rep(i,n+2,n*2)tmp2[i]=n*2+1-i;
}void solve()
{int n;ll k;cin>>n>>k;init(n);ll sum=3;while(k>tmp[sum]){k-=tmp[sum];sum++;}rep(a,sum-2*n,sum-2){if(a<1)continue;int x=sum-a;if(k>tmp2[x])k-=tmp2[x];else{cout<<a<<' ';int b,c;if(x>=n+1)b=x-n,c=n;elseb=1,c=x-1;while(--k)b++,c--;cout<<b<<' '<<c<<'\n';assert(b>=1&&b<=n&&c>=1&&c<=n);return;}}
}
int main()
{closeSync;//multiCase{solve();}return 0;
}

https://www.cnblogs.com/stelayuri/p/14746795.html