如何正确处理三角恋？

如何正确处理三角恋？ || solution - CF2034E

littlebug

·

2024-12-08 15:55:59

·

题解

省流：本文将教你如何正确处理三角恋。

感觉没有那么难呀，几乎一眼秒了，大概 *1700 的样子。

虽然 CD 因为某些原因没过，导致 E 没看就是了。

Solution

首先，如果 k 为偶数，那直接两两配对即可，即每个 a 和 n+1-a 配对，在 n! 个排列中刚好每个排列都有另一半。连排列都有另一半了，你呢？

主要讲讲 k 为奇数应该怎么搞，我们发现，无论怎么搞都需要有一组个数 \ge 3 的排列互相配对（三角恋），于是考虑如何把这三个排列搞出来。我们可以手动模拟一下解决，根据每个位置的三个数相加和必须为 3(n+1)，多试几次就可以，于是我们得到了这个表（设 x 为 \lfloor \frac n 2 \rfloor）：

1

2

3

4

5

\ldots

2x-1

2x

2x+1

x+1

2x+1

x

2x

x-1

\ldots

2

x+2

1

2x+1

x

2x

x-1

2x-1

\ldots

x+2

1

x+1

懒得敲了，直接把官方题解的搬过来了。

那么我们就把三角恋的情况搞定了，剩下的和偶数情况一样，两两配对就可以了。

不过还要注意判无解，共有 4 种情况：

若 k=1 且 n \ne 1，则显然无解。

若 k > n!，由于排列数最多只能有 n! 个，所以无解。

根据上面那个表可得 n 必须为奇数，所以若 k 为奇数但是 n 为偶数则无解。

当 k 为奇数时，我们发现，在上面那个表中，已经用掉了 3 个两两不配对的排列，所以在所有 n! 个排列中，就出现了 3 个没法配对的排列，于是最多能有 n!-3 个排列被使用，所以 k> n!-3 时无解。

Code

#include

#include

#include

#define int long long

#define il inline

#define rep(i,a,b) for(int i=(a);i<=(b);++i)

#define rpe(i,a,b) for(int i=(a);i>=(b);--i)

#define pb emplace_back

using namespace std;

template il void clr(T &x) {T().swap(x);}

const int fac[20]={1,1,2,6,24,120,720,5040,40320,362880,3628800};

int n,k;

vector < vector > a;

vector p,b1,b2,b3,c1,c2,c3;

il void solve(int __Ti)

{

clr(a),clr(b1),clr(b2),clr(b3),clr(c1),clr(c2),clr(c3),clr(p);

cin>>n>>k;

if(k==1) return n==1 ? cout<<"YES\n1\n" : cout<<"NO\n",void(); // 无解情况 1

if(n<=10 && k>fac[n]) return cout<<"NO\n",void(); // 无解情况 2

if(k&1)

{

if(!(n&1)) return cout<<"NO\n",void(); // 无解情况 3

if(n<=10 && k>fac[n]-3) return cout<<"NO\n",void(); // 无解情况 4

int x=n>>1; // 三角恋！

rep(i,1,n) b1.pb(i);

b2.resize(n),b3.resize(n);

for(int i=1,j=x+1;i<=n;i+=2,--j) b2[i-1]=b3[((i-1)?:n)-1]=j;

for(int i=2,j=2*x+1;i<=n;i+=2,--j) b2[i-1]=b3[i-1-1]=j;

a.pb(b1),a.pb(b2),a.pb(b3);

rep(i,0,n-1) c1.pb(n+1-b1[i]),c2.pb(n+1-b2[i]),c3.pb(n+1-b3[i]);

k-=3;

}

rep(i,1,n) p.pb(i);

do // 两两配对

{

if(p==b1 || p==b2 || p==b3 || p==c1 || p==c2 || p==c3) continue;

a.pb(p);

a.pb(vector());

for(auto i:p) a.back().pb(n+1-i);

k-=2;

} while(k>0 && next_permutation(p.begin(),p.end()));

cout<<"YES\n";

for(auto j:a) {for(auto i:j) cout<

}

signed main()

{

ios::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);

int __T; cin>>__T; rep(__Ti,1,__T) solve(__Ti);

return 0;

}

这样，我们就成功处理了三角恋！

看来 Rayan 给 Reyhaneh 送礼物的时候很危险呢，还要提防三角恋破坏他的礼物哦！