题面
题解
想了好久,其实很水tt
想写题解主要是因为这题题面是 Fate 很有意思
我们注意到 “所有 \(v_i\) 值域在 \([1,5]\)” 这个部分分,这种情况下,初始的不同情况数只有 \(5!=120\) 种,可以直接暴力做
没有这个限制直接离散化就好了.
所以最终做法就是:对每一位分别考虑,发现离散化后只有 \(5!=120\) 种不同情况,然后对 \(120\) 种情况都暴力进行 Unlimited Blade Works ,然后回答询问,时间复杂度 \(\Theta(5!\cdot m)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
const int fc[] = {1,1,2,6,24,120,720};
int n,m,v[N][6],w[N][6],p[125][6],r[125][N];
int perm_to_id(int k)
{
int ans=0;
for(int i=1; i<=5; i++)
{
int cnt=0;
for(int j=i+1; j<=5; j++) if(w[k][j]<w[k][i]) cnt++;
ans+=cnt*fc[5-i];
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=5; i++) p[1][i]=i;
int c=1; do { c++; for(int i=1; i<=5; i++) p[c][i]=p[c-1][i]; } while(next_permutation(p[c]+1,p[c]+6)); c--;
for(int i=1; i<=5; i++) for(int j=1; j<=c; j++) r[j][i]=i;
for(int j=1; j<=5; j++) for(int i=1; i<=n; i++) scanf("%d",&v[i][j]);
int d[6];
for(int i=1; i<=n; i++)
{
for(int j=1; j<=5; j++) d[j]=j;
sort(d+1,d+6,[&](const int &x, const int &y){ return v[i][x]<v[i][y] or (v[i][x]==v[i][y] and x<y); });
for(int j=1; j<=5; j++) w[i][d[j]]=j;
}
for(int j=6; j<=m+5; j++)
{
int op,a,b,k; scanf("%d%d%d%d",&op,&a,&b,&k);
for(int i=1; i<=c; i++)
if(op==1) r[i][j]=(p[i][r[i][a]]<p[i][r[i][b]])?r[i][b]:r[i][a];
else r[i][j]=(p[i][r[i][a]]>p[i][r[i][b]])?r[i][b]:r[i][a];
int pn=perm_to_id(k)+1;
printf("%d\n",v[k][r[pn][j]]);
}
return 0;
}
这边用了 Cantor 展开求排列的顺序,也可以用哈希写.
标签:const,3498,剑制,int,题解,120,DTOJ From: https://www.cnblogs.com/copper-carbonate/p/16886590.html