洛谷:P3068 [USACO13JAN] Party Invitations S(枚举、前缀和)

这题我们数据范围太大,用二维肯定是不行的,我们可以采用一维线性存储。

如题意,我们可以将每组奶牛编号都存在一维数组里面,只需记录每组的头尾指针就可以了。

如题中样例我们就可以存储成1 3 3 4 1 2 3 4 5 6 7 4 3 2 1

然后第一组头尾指针就是 1,2 。

第二组头尾指针就是3,4。

第二组头尾指针就是 5,11。

第二组头尾指针就是12,15。

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
pair<int, int> q[N]; //q用于记录每组的头和尾
int e[N], d[N]; //d用于记录每组的数量,e用于将所有组的奶牛线性存储
int n, g, ans;
bool f[N]; //用于判断当前编号是否被邀请过
bool fz[N];//用于判断每组是否都邀请过
int main()
{
	cin >> n >> g;
	int idx = 0;
	for(int i=1;i<=g;i++)
	{
		cin >> d[i];
		for (int j = 1; j <= d[i]; j++)
		{
			cin >> e[++idx];  //将所有组奶牛线性存储,
		}
		//存储每组的头尾指针
		//如例题e中存入的是1 3 3 4 1 2 3 4 5 6 4 3 2 1
		//第一组是1 3,那么q[1]的头尾指针就对应1 3下标,也就是1,2
		int head = idx - d[i] + 1; 
		int tail = idx;
		q[i] = { head,idx };
	}
	f[1] = true;
	int mm = 0;
	do
	{
		mm = 0;
		for (int i = 1; i <= g; i++)
		{
			int hh = q[i].first;
			int tt = q[i].second;
			int c = 0; //当前组邀请的人数
			int flag = 0; //记录没被邀请人的下标
			for (int j = hh; j <= tt; j++)
			{
				if (f[e[j]]) //如果当前编号已经被邀请了,当前组邀请的人数++
					c++;
				else
					flag = j;
			}
			if (c == d[i] - 1)
			{
				f[e[flag]] = true; //邀请前组唯一一个没被邀请的人
				fz[i] = true;  //现在当前组就全部被邀请了
				mm = 1;  //既然已经新邀请了一个人,那么就要判断是否还要再继续邀请
			}
			if (c == d[i]) //如果相等就说明改组已经全部邀请
				fz[i] = true;
		}
	} while (mm == 1); //如果mm=1才说明需要进一步邀请,否则就不需要邀请了

	for (int i = 1; i <= n; i++)
		if (f[i])ans++; //如果被邀请数量就+1
	cout << ans << endl;

	return 0;
}

算法小白的刷题日记.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/431408.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

docker部署aria2-pro

前言 我平时有一些下载视频和一些资源文件的需求&#xff0c;有时候需要离线下载&#xff0c;也要速度比较快的方式 之前我是用家里的玩客云绝育之后不再写盘当下载机用的&#xff0c;但是限制很多 我发现了aria2 这个下载器非常适合我&#xff0c;而有个大佬又在原来的基础…

基于 Vue3打造前台+中台通用提效解决方案(上)

基于 Vue3打造前台+中台通用提效解决方案 1、项目架构 本项目使用vite + vue3来实现前中台解决方案 2、为什么使用vite ? 因为,之前的项目一直都是使用webpack作为构建工具;vite出来这么久了,也没有用过;所以想在当前项目下进行使用; 2.1、为什么vite比webpack块? …

android开发文档下载,你的技术真的到天花板了吗

Android 基础 1.Activity 1、 什么是 Activity&#xff1f; 2、 请描述一下 Activity 生命周期 …… 2.Service 3.Broadcast Receiver32 4.ContentProvider 5.ListView 6.Intent 7.Fragment 1.Fragment 跟 Activity 之间是如何传值的 2.描述一下 Fragment 的生命周期 3.Fragme…

Qt多弹窗实现包括QDialog、QWidget、QMainWindow

1.相关说明 独立Widget窗口、嵌入式Widget、嵌入式MainWindow窗口、独立MainWindow窗口等弹窗的实现 相关界面包含关系 2.相关界面 3.相关代码 mainwindow.cpp #include "mainwindow.h" #include "ui_mainwindow.h" #include "tformdoc.h" #incl…

容器云平台巡检实战:运维进阶技巧与策略

1 docker容器日常巡检 通过以下方式进行检查&#xff1a; 1.1 docker/podman ps查看容器状态 Docker/podman ps -a 查看容器状态STATUS&#xff1a; Exited(0)&#xff1a;表示容器正常退出 Exited(其他数字)&#xff1a;容器异常退出&#xff0c;需要通过log 查看原因 Up…

080|为什么阿里的价值观值得你关注?

在阿里巴巴20周年年会现场&#xff0c;万众瞩目之下&#xff0c;马云和张勇完成了阿里巴巴董事长职务的交接。 不过你也知道&#xff0c;这次接棒在一年前就已经公布了&#xff0c;在年会上只是一个仪式。在20周年年会过后&#xff0c;我找到了互联网圈的资深媒体人阳淼&#…

julia语言使用PyCall包调用Python代码及Python包

Julia语言虽然好&#xff0c;但是包管理方面和生态环境感觉还有一点小小的缺陷&#xff0c;但是Julia可以调用Python丰富的包&#xff0c;用起来很方便。 安装PyCall 在安装之前先确认下Julia和Python的版本&#xff0c;我使用的稳定版本的 Julia1.6.7&#xff0c;Python版本是…

电磁兼容(EMC):单、双面PCB板设计要点

目录 1 产品设计原则&#xff1a;性价比为第一要素 2 布局设计要点 3 布线设计要点 4 完整地平面不是最优方案 1 产品设计原则&#xff1a;性价比为第一要素 PCB在电磁兼容设计中通常是要求有完整的地和电源平面。但多层价格让对价格敏感的产品望而却步&#xff0c;只能采…

GPT本地化研究(JAVA版本)

1.我觉得gpt3 600多G个人是不可能部署得成功的,回想我自己个人不可能每一方面知识都知道,我只是知道最多的是我自己擅长的,百事通需要靠大公司才能解决,我们只是要关注这个gpt是哪个领域的, 我想做的是工业—>自动化gpt(貌似这个方向日本很专业了*_*) 它山之石可以攻玉 2.gp…

【设计模式 03】抽象工厂模式

一个具体的工厂&#xff0c;可以专门生产单一某一种东西&#xff0c;比如说只生产手机。但是一个品牌的手机有高端机、中端机之分&#xff0c;这些具体的属于某一档次的产品都需要单独建立一个工厂类&#xff0c;但是它们之间又彼此关联&#xff0c;因为都共同属于一个品牌。我…

视觉Transformers中的位置嵌入 - 研究与应用指南

视觉 Transformer 中位置嵌入背后的数学和代码简介。 自从 2017 年推出《Attention is All You Need》以来&#xff0c;Transformer 已成为自然语言处理 (NLP) 领域最先进的技术。 2021 年&#xff0c;An Image is Worth 16x16 Words 成功地将 Transformer 应用于计算机视觉任务…

【go语言开发】yaml文件配置和解析

本文主要介绍使用第三方库来对yaml文件配置和解析。首先安装yaml依赖库&#xff1b;然后yaml文件中配置各项值&#xff0c;并给出demo参考&#xff1b;最后解析yaml文件&#xff0c;由于yaml文件的配置在全局中可能需要&#xff0c;可定义全局变量Config&#xff0c;便于调用 文…

面试题HTML+CSS+网络+浏览器篇

文章目录 Css预处理sass less是什么&#xff1f;为什么使用他们怎么转换 less 为 css&#xff1f;重绘和回流是什么http 是什么&#xff1f;有什么特点HTTP 协议和 HTTPS 区别什么是 CSRF 攻击HTML5 新增的内容有哪些Css3 新增的特性flex VS grid清除浮动的方式有哪些&#xff…

SAR ADC学习笔记(3)

一、SAR ADC采样电路 1.采样网络的时域响应&#xff1a;采保信号 2.采样网络的KT/C噪声 3.采样抖动 采样开关的种类 1.单MOS管开关 2.传输门开关 3.栅极自举&#xff08;Bootstrap&#xff09;开关 结论&#xff1a;M4的衬底需要和B点短接&#xff0c;保证B点能够到达高压&…

完美解决Iframe嵌入帆软报表出现跨域cookie写不进去的问题

随着google chrome对第三方cookie的限制越来越狠,现在发现之前使用iframe嵌入的帆软报表已经不好使了。官方现在解决iframe嵌入帆软报表出现跨域导致cookie写不进去的方案是主推 统一主域名的方案(谷歌浏览器单点登录失败- FineReport帮助文档 - 全面的报表使用教程和学习资料…

大唐杯学习笔记:Day5

1.1 小区搜索 搜索流程 PLMN选择 自动模式&#xff1a;UE根据NAS的请求或自主地向NAS报告可用的PLMN 手动模式&#xff1a;通过手动选择一个可用的VPLMN获取正常服务 频点选择 5G NR中,3GPP主要指定了两个频率范围,一个是6GHZ以下,另一个是毫米波,分别称之为FR1和FR2。 N…

稀碎从零算法笔记Day5-LeetCode:轮转数组

题型&#xff1a;数组、数学、双指针 前言&#xff1a;LC说你得用三种方法做出来(悲) 链接&#xff1a;189. 轮转数组 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 著作权归作者所有。商业转载请联系作者获得授权&#xff0c;非商业转载请注明出处。 …

专业145+总分410+西工大西北工业大学827信号与系统考研经验电子信息与通信工程,海航,真题,大纲,参考书。

经过一年的努力&#xff0c;分数终于出来。今年专业课827信号与系统145&#xff08;很遗憾差了一点点满分&#xff0c;没有达到Jenny老师的最高要求&#xff09;&#xff0c;数一130&#xff0c;英语和政治也都比较平衡&#xff0c;总分410分&#xff0c;当然和信息通信考研Jen…

学习java第一天(下载并配置环境+写第一个java程序)

一.安装 1.下载 直接去官网上选择与你电脑符合的版本下载 官网链接Java Archive Downloads - Java SE 8u211 and later &#xff08;拿我的为例 Windows x64版本&#xff09; ​ 2.然后安装好exe&#xff08;要让自己知道在哪&#xff09; 3.配置环境 大佬链接&#xff1…

蓝桥杯前端Web赛道-新鲜的蔬菜

蓝桥杯前端Web赛道-新鲜的蔬菜 题目链接&#xff1a;1.新鲜的蔬菜 - 蓝桥云课 (lanqiao.cn) 题目要求如下&#xff1a; 其实很容易联想到使用flex布局&#xff0c;这是flex布局一种非常经典的骰子布局&#xff0c;推荐Flex 布局教程&#xff1a;实例篇 - 阮一峰的网络日志 (r…