首页 > 其他分享 >AT_agc012_f [AGC012F] Prefix Median 题解

AT_agc012_f [AGC012F] Prefix Median 题解

时间:2024-11-11 16:31:28浏览次数:5  
标签:AGC012F le int 题解 Prefix 序列 103 define

首先将序列排序,这是显然的。

考虑倒着确定 \(b\) 序列中的每个数。即从完整的 \(a\) 序列开始,每次删掉两个数,记录中位数。

先找出 \(b\) 序列合法的条件。容易发现对于所有 \(i\),在 \(b_{p_i}\) 成为中位数时,\(p_i,p_{i+1}\) 之间的所有数都已经被删除了,且 \(i\le p_i\le 2n-i\)。

考虑 dp,记 \(f_{i,j,k}\) 表示当前确定了 \(b\) 的后 \(i\) 个值,当前区间左边有 \(j\) 个可能作为这个数,右边有 \(k\) 个也可能作为这个数,直接枚举取哪个数转移即可。注意到可能存在重复的值,假设 \(a_l\) 和 \(a_{l-1}\) 相同,那么此时统一取 \(a_l\) 即可,右边同理。

参考代码:

#include<bits/stdc++.h>
#define md 1000000007
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int n,ans,a[103],f[53][103][103];
signed main(){
	cin>>n;
	rept(i,1,n<<1)cin>>a[i];
	sort(a+1,a+n+n);
	f[n][0][0]=1;
	drep(i,n-1,1){
		int c1=a[i]!=a[i+1],c2=a[n*2-i]!=a[n*2-i-1];
		rept(j,0,n<<1){
			rept(k,0,n<<1)if(f[i+1][j][k]){
				f[i][j+c1][k+c2]=(f[i][j+c1][k+c2]+f[i+1][j][k])%md;
				rept(x,0,j+c1)f[i][x][k+c2+1]=(f[i][x][k+c2+1]+f[i+1][j][k])%md;
				rept(x,0,k+c2)f[i][j+c1+1][x]=(f[i][j+c1+1][x]+f[i+1][j][k])%md;
			}
		}
	}
	rept(i,0,n<<1)rept(j,0,n<<1)ans=(ans+f[1][i][j])%md;
	cout<<ans;
	return 0;
}

标签:AGC012F,le,int,题解,Prefix,序列,103,define
From: https://www.cnblogs.com/zifanoi/p/18540013

相关文章

  • Eplan2022卡顿问题解决
    EPLAN2022卡顿崩溃怎么解决 第一步:可以检查下用户设置。打开菜单"选项→设置:用户→翻译→字典":不勾选"自动完成"和"自动更正"。在选项设置框中输入"自动",快速找到用户设置,取消勾选,如下图。 第二步:可以检查下电脑语言设置。设置:常规→兼容性"。如下图。 ......
  • CF 1257 题解
    CF1257题解ATwoRivalStudents每次交换都可以让距离增加\(1\),上界是\(n-1\).题目说至多而不是恰好交换\(x\)次,于是不需要考虑边界.BMagicStick一个重要的观察是:如果能够得到\(x\),那么就能得到任意小于等于\(x\)的数,这是操作二保证的.考虑操作\(1\)......
  • 2024中高级前端面试真题解析
    我是一名本科毕业的前端程序媛,工作5年了,周末双休待遇还不错。公司最近要搬迁新地址,业务要整合到一起,所以最近比较清闲,天天上班摸鱼,闲着没事,整理了以前面试时用的资料文档有945道:JavaScript(323题)CSS(61题)HTML(57题)React(83题)Vue(80题)算法(19题)计算机网络(71题)Node.js(2......
  • 【题解】CF1993【EF】
    A注意到一种选项最多填对\(n\)个题所以答案是\(\min(n,cnt_a)+\min(n,cnt_b)+\min(n,cnt_c)+\min(n,cnt_d)\)B注意到操作只能让奇数变多,偶数变少,所以我们只能把偶数全变成奇数特判掉全是偶数的情况,容易得到答案下界:偶数个数容易想到一个naive贪心做法:每次都拿出奇数......
  • 2024ccpc女生赛题解
    考场上写的A,C,H,L,M下来补一下剩下的E注意\(p[i]<i\)这个性质和重心关系不大,一个简单的构造,手模几个样例就能发现规律。倒着枚举:\(c[i]=0\)的是叶子,不用处理\(c[i]>0\),这个点连到父亲所在连通块的根上即可。并查集维护连通块以及连通块的根,根就是连通块中最小编号的点。#inc......
  • 题解:P11250 [GESP202409 八级] 手套配对
    题目传送门思路讲解一道非常经典的排列组合的题。首先,我们要先从nnn对手套中取走kk......
  • MySQL问题解决记录(1):IP address 'xxx.xxx.xxx.xxx' could not be resolved: 这是在主机
    目录问题描述排查流程解决方案总结问题描述[Warning][MY-010055][Server]IPaddress'xxx.xxx.xxx.xxx'couldnotberesolved:这是在主机名解析时通常出现的暂时错误,它意味着本地服务器没有从权威服务器上收到响应。问题表现:A主机的服务在访问B主机的MySQL数据库时,产......
  • Jmeter并发线程场景下共享变量错乱问题解决
    问题复现问题描述使用IF控制器获取前一个请求的后置脚本中设置的全局变量->并发线程下通过vars.get获取变量时,第一个线程和第二个线程获取的变量值一样->导致不同基础数据的请求入参一样方法如下:vars.put("shoppingCartIdList",shoppingCartIdList.toString());/......
  • CF1974题解
    闲话1974年第一次在东南亚打自由搏击就取得了冠军······CF1974A简单计数题点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intt;signedmain(){ scanf("%lld",&t); while(t--){ intx,y,ans=0,num=0; scanf("%lld%lld",&x,......
  • [CodeForces] CF1978 题解
    A.AliceandBooksLink-CFLink-Luogu【题目大意】\(n\)本书,编号为\(1\)到\(n\),价值为\(a_1\)到\(a_n\)。将这些书分成两堆,你获得每堆编号最大的书的价值。求可以获得的最大的价值。【解题思路】无论怎样,编号为\(n\)的书不管在那一堆都是编号最大的,所以一定会有它......