B - Magical Subsequence (CCPC2021哈尔滨)

news/2024/7/15 19:32:05 标签: 算法, c++, 图论

思路:

(1)问题:对于已知数组,每组依次选两个,尽量选更多组,选的每组和相等;(假定和为x)

(2)于是问题拆分为两步,

  1. x是多少
  2. x确定时,怎样选更多组

(3)对于问题1,注意到A:(1,100),所以x:(2,200)枚举即可;

对于问题2,x确定条件下,显然能选则选最多,此时有两条思路,

  1. 前面拿到值从后面找(复杂度O(n^2)且不能保证尽可能长)
  2. 后面拿到值往前面找,(开st[]数组查询,此时充分利用前面信息,复杂度O(n+100),且尽可能靠前进行查找;

(4)于是选择思路2,(注意使用set会超时,数组小时应尽量用数组,因为查询复杂度小)

代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL a[N];
LL st[210];
int main()
{
	int n;
	cin >> n;
	for(int i = 0;i < n;i ++)
		scanf("%d",&a[i]);
	
	LL maxn = 0;
	for(int i = 2;i <= 200;i ++)
	{
		memset(st,0,sizeof st);
		LL tmp = 0;
		for(int j = 0;j < n;j ++)
		{
			if(st[i - a[j]] == 1)
			{
				tmp += 2;
				maxn = max(maxn,tmp);
				memset(st,0,sizeof st);
			}
			else st[a[j]] = 1;
		}

	}
	
	cout << maxn<< endl;
	
	return 0;
}


http://www.niftyadmin.cn/n/5119920.html

相关文章

ES6中的新增属性——解构赋值

首先我们要创建一个假数据&#xff0c;我们现在要取出user中的id和名称&#xff0c;如下&#xff1a; let user JSON.parse(sessionStorage.getItem(userInfo)) let id user.id; let name user.name; 非常的麻烦&#xff0c;我们需要一项一项的获取&#xff0c;这个时候可…

为什么Open3D可视化TensorFlow张量速度超慢

问题描述 在使用Open3D可视化TensorFlow张量表示的点云时速度超慢 原因分析 可能是因为Open3D没有针对tf.Tensor做优化&#xff0c;也可能是tf.Tensor本身没有对张量的操作做优化&#xff0c;所以可能如果要在CPU中计算&#xff0c;numpy可能性能更好。 解决方案 open3d.u…

SpringSecurity分布式安全框架

Spring Security是一个基于Spring框架的安全框架&#xff0c;它提供了全面的安全解决方案&#xff0c;包括用户认证和用户授权等Web应用安全性问题。Spring Security可以轻松扩展以满足自定义需求&#xff0c;它的真正强大之处在于它可以轻松扩展以满足自定义要求。 对于分布式…

温馨提示!小心不法分子的隐藏陷阱

《绝地求生》国服的”老兵回归”活动一经推出就受到广大玩家欢迎&#xff0c;因此也有不法分子想趁虚而入。就在近日&#xff0c;我们接到玩家举报&#xff0c;发现一些不法分子通过伪基站邮件群发的形式&#xff0c;以“第XXXX位老兵奖励”为主题&#xff0c;向用户推荐一个非…

【JavaScript】用字符串生成 DOM 元素

代码如下&#xff1a; function createElementFromHTML(htmlString) {var div document.createElement(div);div.innerHTML htmlString.trim();// Change this to div.childNodes to support multiple top-level nodes.return div.firstChild; }来源&#xff1a;Creating a …

0基础学习PyFlink——流批模式在主键上的对比

假如我们将《0基础学习PyFlink——使用PyFlink的Sink将结果输出到外部系统》中的模式从批处理&#xff08;batch&#xff09;改成流处理&#xff08;stream&#xff09;&#xff0c;则其在print连接器上产生的输出是不一样。 批处理 env_settings EnvironmentSettings \.new_…

C语言程序设计——题目:用*号输出字母C的图案。程序分析:可先用‘*‘号在纸上写出字母C,再分行输出。

题目&#xff1a;用*号输出字母C的图案。 程序分析&#xff1a;可先用*号在纸上写出字母C&#xff0c;再分行输出。 #include<stdio.h> int main() {printf(" *****\n");printf(" *\n");printf("*\n");printf("*\n");printf(&…

日本最新矢量图_日本地图的制作_都道府县_1都1道2府和43县(県)_日本shape

1、属性信息 2、属性表 3、简单图制作 4、简单统计分析 5、获取矢量数据&#xff0c;V&#xff1a;935255181