首页 > 其他分享 >一些数 题解

一些数 题解

时间:2023-12-31 21:57:32浏览次数:26  
标签:return int 题解 代码 元素 && 一些 false

首先我们考察 LIS 长度为 \(n-1\) 的数列的性质。可以发现,这必定是 \(1,2,3,\cdots,n\) 中拎出一个不听话的元素甩到其他地方去,剩下的元素依次补齐所构成的。这意味着,最多只有一个元素满足 \(a_i-i\ge2\),更具体的,不考虑只对邻项交换的排列(即形如 \(1,2,3,\cdots,i,i-1,\cdots,n\)),每个满足要求的排列都有且仅有一个元素满足 \(a_i-i\ge 2\)。

接下来对所有钦定了值的元素进行考察。这意味着下文中我们已经默认了 \(a_i\not=-1\)。

  • 所有 \(a_i=i\)。那么我们只能对下标的空隙部分做操作。也就是假设相邻的两个下标分别为 \(i,j\),那么这一段对答案的贡献是 \((j-i-2)^2\)。不难写出如下的代码:
int cur = 0;
for(int i = 1; i <= n; i++){
	if(!~a[i]) cur++;
	else if(cur){
		ans += pow(cur - 1, 2);
		cur = 0;
	}
}
if(cur) ans += pow(cur - 1, 2);
  • 存在 \(|a_i-i|\ge 2\)。因为这样的 \(i\) 只能有一个,所以如果找到多个这样的下标直接 cout<<0<<"\n" 走人。即使仅有一个这样的 \(i\),合法的也最多只能有一个排列。因此判断一下是否合法即可。不难写出下面的代码:
int p = -1;
for(int i = 1; i <= n; i++){
	if(!~a[i]) continue;
	if(abs(a[i] - i) >= 2){
		if(~p) return false;
		else p = i;
	}
}
if(~p){
	//found one abs(a[i] - i) >= 2
	if(a[p] > p){
		int l = p, r = a[p];
		for(int i = 1; i <= n; i++){
			if(!~a[i]) continue;
			if((i < l || i > r) && a[i] != i) return false;
			if((i > l && i <= r) && a[i] != i - 1) return false;
		}			
	}else{
		// just a reversion of a[p] > p...
		int l = a[p], r = p;
		for(int i = 1; i <= n; i++){
			if(!~a[i]) continue;
			if((i < l || i > r) && a[i] != i) return false;
			if((i >= l && i < r) && a[i] != i + 1) return false;
		}
	}
}
  • 存在 \(a_i=i+1,a_{i+1}=i\)。这种比较好判断,而且也最多只能存在一个这样的 \(i\)。
int cnt = 0;
for(int i = 1; i <= n; i++){
	if(a[i] != i && ~a[i]){
		if(a[i] == i + 1 && a[i + 1] == i) i++, cnt++;
		else return false;				
	}
}
if(!cnt) return false;

在写代码的时候,我把上述两个情况合并在一起了。因为它和下面的情况相差较大,但这两个本质是一个情况,即指定了开头所提到的“不听话的元素”。

  • 存在一段 \(a_i=i+1\) 或一段 \(a_i=i-1\)。注意判断仅能存在一个这样的段!因此我们不难写出下面的代码,其中 \(flag\) 标志了目前在什么阶段(进入段前,段中,第一段后)。
int flag = 0;
p = 0;
for(int i = 1; i <= n; i++){
	if(!~a[i]) continue;
	if(a[i] == i){
		if(flag == 1) flag = 2;// signal if i is out of the offset area.
	}else{
		// a[i] != i
		r = i;
		if(flag == 0){
			//no offset currently
			p = a[i] - i;
			l = i, flag = 1;// into the offset area;
		}else{
			if(flag == 1){
				if(a[i] - i != p) return false;
			}else{
				assert(flag == 2); return false;// out of the offset area and found another section,
				// which is impossible to generate any valid solution in this occasion.
			}
		}
	}
}
return true;
int lcnt = 0, rcnt = 0;
for(int i = l - 1; i && !~a[i]; i--) lcnt++;
for(int i = r + 1; i <= n && !~a[i]; i++) rcnt++;
ans = 1ll * lcnt * rcnt;
ans += (~p ? rcnt : lcnt);

把几段代码融合一下,就得到了此题的代码。完整代码不给!

标签:return,int,题解,代码,元素,&&,一些,false
From: https://www.cnblogs.com/Piggy424008/p/17938068/solution-p9436

相关文章

  • 自出题题解
    U288469Piggy算路程显然是简单贪心。黄。U306825Piggy数编号先推式子。令\(L(n,k)\)为最长区块长度为\(k\)的方案数,则\(Ans=\sum_{i=0}^n\limits{L(n,i)}\timesk\)。下面转为求\(L(n,k)\)。我们考虑可能的区块长度分别为多少。那么就相当于我们要枚举所有的长度在......
  • CF1438F 题解
    如果能想到这道题用随机化,想来这道题的解法就显然了。但是为什么这道题一定要随机呢?我们考虑一棵完美二叉树,编号随机。这棵树的熵毛估估一下应该是\(O(\log^nn)\)的,但是一次询问的话,考虑每次只能得到三个点的偏序关系为某几种情况的一种,这个熵是很小的,只有\(O(\logn)\),对减......
  • P7400 题解
    P7400,一个有趣的博弈论。下面称Paula和Marin都执行一轮操作的“一整轮”为一个周期。Sub1:\(n\le100\)我们采用\(O(n^2\timesn)=O(n^3)\)的DP即可。这里略去具体实现。Sub2:边的颜色均为洋红这意味着两人都可以走过任意一条边。考虑两方如何对对方进行“围追堵截”......
  • P9309 题解
    此题问\(\operatorname{lcm}(a\simb)\)的后导\(0\)个数。考虑\(\operatorname{lcm}\)相当于对唯一分解中的素数的指数取\(\max\),此题等价于:定义\(\operatorname{g}(x,y,z)\)在\([a,b]\)的所有整数中,分解出\(z\)的最高次幂是多少,那么\(ans=\min(\operatorname{g}......
  • CF1827F 题解
    不妨先考虑一个弱化版的问题,这个问题和原来的问题仅有一个区别:\(k\)是给定整数。称最后\(n-k\)个数是“特殊的”。那么我们可以注意到,每个特殊的数字的极大段必然递增放置或者递减放置。例如我们有排列\([7,5,8,1,4,2,6,3]\)而且\(k=2\),那么极大段的下标应该是\([1,4],[6,......
  • P4875 题解
    显然这道题的解法与\(8\)强相关。从这一点下手,我们不难想到先对每一种奶牛做前缀和,这样我们可以做到\(O(8)\)查询每个区间是否可行,从而有了一个\(O(4n^2)\)的纯暴力做法。不知道多少pts,反正不是正解。下一步我们考虑优化。如果我们能快速地找到哪些区间是合法的,那么时间复......
  • P5138 题解
    因为本题的代码难度远大于解法的思考,因此这里提供一种好写的写法。做法不再赘述,就是转化为\(depth\)差以后上线段树分别维护两个信息以后求和。题解中大多数使用同一个线段树维护两个信息,可读性并不高,且比较难写。事实上我们注意到两棵线段树仅有初始的信息不一样,剩下需要支持......
  • P4434 题解
    远古模拟赛里的一道题,前来写篇题解记录一下。我们考虑一个显然的转化。将每条边染色,那么原问题等价于求下面的染色的方案数:对于每个点对\(a,b\),我们记\(\operatorname{lca}(a,b)=c\)有\(a\simc\)上的所有边同色。\(b\simc\)上的所有边同色。\(a\simc\)和\(b\simc......
  • CF958E1 题解
    Meaning在二维平面内,有位置不同且不存在三点共线的\(R\)个红点和\(B\)个黑点,判断是否能用一些互不相交的线段连接每一个点,使得每条线段的两端都分别是黑点和白点。Solution当\(R\ne{B}\)时,显然无法实现红点与黑点的两两组合,故题干所述的情况一定不存在。当\(R=B\)时,我......
  • P5765 [CQOI2005] 珠宝 题解
    P5765[CQOI2005]珠宝题解思路好题,注意到有性质:颜色数最多为\(\lfloor\log_2n\rfloor+1\),有了这个性质之后直接树形DP糊上去就过了。简要的证明:考虑一个点,显然一种颜色即可。对于一个颜色为\(c\)的点,其儿子至少有\(c-1\)个,且为\(1\simc-1\)的排列,这样可......