首页 > 其他分享 >DTOJ 3498 无限剑制 题解

DTOJ 3498 无限剑制 题解

时间:2022-11-13 19:33:38浏览次数:57  
标签:const 3498 剑制 int 题解 120 DTOJ

题面

题目链接

题解

想了好久,其实很水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

相关文章

  • DTOJ 5932 Counting 题解
    题目链接portal题解认识到了生成函数很好用,于是摆了一篇题解10分直接dp,\(f_{i,j}\)表示走了\(i\)步之后,当前位置在\(j\)的方案数然后就有状态转移方程\(f_{i,......
  • DTOJ 5769 下棋 题解
    题目链接portal题解首先比较容易想到\(dp\),因为任意一段绝对值不超过\(k\),所以白棋个数减黑棋个数要在\([-k,k]\)区间里,我们于是考虑把状态设为白棋减黑棋个数......
  • DTOJ 5093 淘淘种地 题解
    题面题目链接题解这个是CSP前最后一场测试的T2,打的不是很好,没有想到这题正解,但是这题暴力分很多ww二进制拆位的思想要有((30分暴力模拟\(O(nmT)\)70分满足\(1\le......
  • DTOJ 6316 沙丘 题解
    DTOJ6316沙丘题解题面:http://59.61.75.5:8018/p/P6316在满天的星光下,灰大狼一人孤独地堆起了小沙丘。有\(n\)堆沙丘,每堆沙丘有相对高度\(h_i\),每次灰大狼可以选择......
  • CF1748E Yet Another Array Counting Problem 题解
    可能更好的阅读体验题目传送门题目大意给定一个长度为\(n\)的序列\(a\)和\(m\),定义\([l,r]\)的最左边的最大值为最小的\(l\lei\ler\)满足\(x_i=\max\{a_......
  • CF1748D ConstructOR 题解
    可能更好的阅读体验题目传送门题目大意给定\(a,b,d\),要求找到一个\(0\lex\le2^{60}\),满足\(a|x,b|x\)都是\(d\)的倍数(\(|\)代表按位或)。\(T\le10^4\),\(0\le......
  • 能力提升综合题单-模拟,前缀和差分 题解
    好久没有写题解了,今天回来了!!A-铺地毯在luogu,享受coding的快乐见到题以后,一道水题直接模拟二位数组。。。《真·ACcode》:点击查看代码#include<bits/stdc++.h>u......
  • CF1746D题解
    很好的一道贪心题。首先对于每条路径,由于要最大化权值,每条路径肯定要延伸到叶子节点。切入点肯定在\(|c_u-c_v|\leq1\),也就是说由节点\(i\)延伸下去的路径要均匀分配......
  • DTOJ 2022.11.02 图论专题
    题单P1117无序字母对P5240「NOIP2020」排水系统P4042「NOIP2018」旅行P5169「CSP-S2020」函数调用P4563「NOIP2017」逛公园题解A题面:给定\(n\)个各不相同的......
  • [CEOI2016] kangaroo题解
    P5999[CEOI2016]kangaroo一类插入式的dp。对于这道题,我们得先做出一个转化,依次考虑每个数插到哪个位置,于是变成了求\(1\)~\(n\)的排列同时满足每个位置上的元素要么......