首页 > 其他分享 >luoguP5369 [PKUSC2018] 最大前缀和

luoguP5369 [PKUSC2018] 最大前缀和

时间:2024-08-29 22:37:28浏览次数:12  
标签:twoN 前缀 int PKUSC2018 luoguP5369 fo sum define

题目

n<=20

题解

想了半天3位状态的折半,然后发现空间开不下(时间也不太行)

所以放弃思考,直接枚举答案


答案是a中的一个集合,设为S;记集合S的和为sum[S]

考虑当S确定时,有多少种方案能使答案恰好为sum[S]。为了处理多种sum相同的情况,记S为从前往后考虑,第一次出现最大ans的集合;记剩余部分为\(\bar S\)

那么考虑S和\(\bar S\)在序列上的情况,记前者组成的子段为L后者为R;
有L中任意真后缀的和>0,R中任意前缀的和<=0(否则S会变)

所以取到S的情况就是二者方案乘积,都可以用\(O(n2^n)\)状压不断加数求解(真后缀要特殊处理最后的全集,开两个状态搞)

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (int a=b; a<=c; a++)
#define fd(a,b,c) for (int a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define mod 998244353
#define Mod 998244351
#define ll long long
#define file
using namespace std;

const int N=21;
const int twoN=1048576;
int T,n,K=11;
int a[N];
int sum[twoN];
int F[twoN],f[twoN],g[twoN];
ll ans;

int main()
{
//	freopen("luogu5369.in","r",stdin);
	
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	fo(s,1,(1<<n)-1)
	{
		fo(i,1,n)
		if (s&(1<<(i-1)))
		{
			sum[s]=sum[s-(1<<(i-1))]+a[i];
			break;
		}
	}
	
	F[0]=1;
	fo(s,0,(1<<n)-1-1)
	{
		fo(i,1,n)
		if (!(s&(1<<(i-1))))
		{
			if (sum[s|(1<<(i-1))]>0)
			add(F[s|(1<<(i-1))],F[s]);
			add(f[s|(1<<(i-1))],F[s]);
		}
	}
	g[0]=1;
	fo(s,0,(1<<n)-1-1)
	{
		fo(i,1,n)
		if (!(s&(1<<(i-1))) && sum[s|(1<<(i-1))]<=0)
		add(g[s|(1<<(i-1))],g[s]);
	}
	
	fo(s,1,(1<<n)-1)
	{
		int s2=((1<<n)-1)^s;
		add(ans,1ll*f[s]*g[s2]%mod*sum[s]);
	}
	printf("%lld\n",(ans+mod)%mod);
}

标签:twoN,前缀,int,PKUSC2018,luoguP5369,fo,sum,define
From: https://www.cnblogs.com/gmh77/p/18387652

相关文章

  • Nuxt3 全局变量接口前缀全局配置,全局方法,全局状态管理
    接口前缀全局配置,全局变量1.像api前缀这类的全局变量一般配置在nuxt.config.ts文件中。如下:nuxt.config.ts可以在public下定义全局变量,且public下的变量可以在客户端和服务端使用在其他任意vue或者js、ts文件中,可通过以下方式获取变量const{public:{apiBase}}=u......
  • (算法)最⻓公共前缀————<链表—模拟>
    1.题⽬链接:14.最⻓公共前缀2.题⽬描述:3.解法:算法思路:解法⼀(两两⽐较):我们可以先找出前两个的最⻓公共前缀,然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较,这样就可以找出所有字符串的最⻓公共前缀。C++算法代码: classSolution{public: stringlongestCommonPr......
  • 【数据结构-前缀异或和】力扣1177. 构建回文串检测
    给你一个字符串s,请你对s的子串进行检测。每次检测,待检子串都可以表示为queries[i]=[left,right,k]。我们可以重新排列子串s[left],…,s[right],并从中选择最多k项替换成任何小写英文字母。如果在上述检测过程中,子串可以变成回文形式的字符串,那么检测结果为......
  • ZBlog的数据库表是可以设置前缀-修改ZBlog数据库前缀
    ZBlog的数据库表是可以设置前缀,程序安装的时候默认是zbp_,所以很多同学也就默认用了zbp_,但是因为某些原因需要修改ZBlog数据的前缀。例如烽烟前几天搭建了几个演示站,多个演示站都使用的是一个数据库,但是由于之前的演示站数据表也是默认的zbp_,这样的话就与现在存在的网站数据表......
  • 「字符串」前缀函数|KMP匹配:规范化next数组 / LeetCode 28(C++)
    概述为什么大家总觉得KMP难?难的根本就不是这个算法本身。在互联网上你可以见到八十种KMP算法的next数组定义和模式串回滚策略,把一切都懂得特别混乱。很多时候初学者的难点根本不在于这个算法本身,而是它令人痛苦的百花齐放的定义。有的next数组从0下标开始,有的从1开始;有的表......
  • 汇编语言的神秘面纱:指令前缀的深度解析
    标题:汇编语言的神秘面纱:指令前缀的深度解析在计算机编程的底层世界中,汇编语言以其接近硬件的特性,扮演着至关重要的角色。指令前缀是汇编语言中一个关键的概念,它为指令提供了额外的信息,使得程序能够执行更加复杂和灵活的操作。本文将深入探讨指令前缀的作用、类型以及如何在......
  • 【C++二分查找 前缀和 】1292. 元素和小于等于阈值的正方形的最大边长
    本文涉及的基础知识点C++二分查找C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频LeetCode1292.元素和小于等于阈值的正方形的最大边长给你一个大小为mxn的矩阵mat和一个整数阈值threshold。请你返回元素总和小于或等于阈值的正方形区......
  • zblog该数据库里已存在相关的表和数据,请更改表前缀或是更换清空数据库再安装
    问题原因:其实这个提示已经说的很清楚了。意思就是之前你应该安装过zblog程序,所以你的数据库里面已经存在了zblog数据表。再次安装的时候因为表名是一样的所以会冲突,就会出现这个提示。解决办法:第一种:填写数据库信息的时候修改下表前缀,如下图:该数据库里已存在相关的表和数据,请......
  • 前缀和与差分
    前缀和与差分前缀和作用:快速求出数值中某段位置的数值和,降低时间复杂度一维前缀和//基本思想S[i]=a[1]+a[2]+...a[i]a[l]+...+a[r]=S[r]-S[l-1]//实现案例/*输入一个长度为n的整数序列。接下来再输入m个询问,每个询问输入一对l,r。对于每个询......
  • leetcode前缀和(2438. 二的幂数组中查询范围内的乘积)
    前言经过前期的基础训练以及部分实战练习,粗略掌握了各种题型的解题思路。现阶段开始专项练习。描述给你一个正整数 n ,你需要找到一个下标从 0 开始的数组 powers ,它包含 最少 数目的 2 的幂,且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述,构造......