CF Educational67_educational 67-程序员宅基地

技术标签: CF  ACM算法日常  Educational67  ACM  二次换根法  Codeforce  

ACM题集:https://blog.csdn.net/weixin_39778570/article/details/83187443
题目链接:https://codeforces.com/contest/1187

A

题意: 有n个蛋,蛋里放着物品A,或者物品B,或者物品A和B,A有s个,B有t个,问至少拿多少个蛋才能拿到A和B。

解法:模拟~画一条线,长度为n,A从左边开始,B从右边开始,中间是重叠部分,左右两边是不重叠部分,取大的一边,再加一就是答案了…

#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
int T;
int main(){
    
	cin>>T;
	while(T--){
    
		ll n,s,t;
		cin>>n>>s>>t;
		ll ans = max(n-s,n-t)+1;
		cout<<ans<<endl; 
	} 
	return 0;
}

B

题意:有一个字符串s,有N个字符串t,问要包含字符串t的所有字母,至少去字符串s的前缀多长。

解法:统计字符串s的信息,cnt[‘a’][x]=num:表示a出现x次在位置num.如cnt[‘a’][1000]=1005表示a的第1000次 出现在位置1005
对于每个t,统计它的字母出现的次数。然后根据这些次数在cnt里面查找答案。

#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=2e5+5;
int n,m,cnt[33][N],cnt1[33],cnt2[33];
char s[N],t[N];
void init(){
    
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1; i<=n; i++){
    
		cnt[s[i]-'a'][++cnt1[s[i]-'a']]=i; // s[i]出现cnt1次在位置i 
	}
}
int main(){
    
	init();
	scanf("%d",&m);
	while(m--){
    
		scanf("%s",t+1);
		int len = strlen(t+1);
		int ans = 0;
		memset(cnt2,0,sizeof(cnt2));
		for(int i=1; i<=len; ++i){
    
			cnt2[t[i]-'a']++;
		}
		for(int i=0; i<26; i++){
    
			ans=max(ans, cnt[i][cnt2[i]]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

C

题目:有一个长度为n的未知数列A,这里有m条信息,包含三个信息(t,l,r)
当t=1,表示A[l,r]是上升数列
当t=0,表示A[l,r]是非上升数列,也就是这是有一对相邻的对前者大于后者
如果数列存在,输出数列,否则输出NO

解法:n比较小,只有1000。
对于t=1来说,这是必须上升的,所以我们可以先把t=1的情况处理了,把上升的位置全都标记出来s[i]=1表示A[i]<A[i-1],数据比较小,直接暴力标记了,也可以用差分,最后再一次性标记

对于t=0来说,我们只有能找到一个s[i]!=1的就行 l < = i < r l<=i<r l<=i<r,否则就无法构造数列

然后构造数列

非暴力法,就是差分之后确定了上升序列的位置后,然后构造数列
接着使用t=0的来进行验证

code略微暴力

#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=1e3+5;
int n,m,s[N],ans[N];
struct node{
    
	int t,l,r;
	bool operator < (const node &p)const{
    
		return t>p.t;
	} 
}a[N];
int main(){
    
	cin>>n>>m;
	fo(i,1,m){
    
		int t,l,r;
		cin>>a[i].t>>a[i].l>>a[i].r;
		
	}
	sort(a+1,a+m+1);
	fo(i,1,m){
    
		if(a[i].t==1){
    
			for(int j=a[i].l; j<a[i].r; j++){
    
				s[j]=1; // 上升 
			}
		}else{
    
			bool flag = 0;
			for(int j=a[i].l; j<a[i].r; j++){
    
				if(s[j]!=1){
     // 只要有非上升就标记为下降 
					s[j]=2;
					flag = 1;
					break;
				}
			}
			if(!flag){
    
				cout<<"NO"<<endl;
				return 0;
			}
		} 
	}
	ans[1]=1005;
	for(int i=2; i<=n; i++){
    
		if(s[i-1]==2){
    
			ans[i]=ans[i-1]-1; 
		} else{
    
			ans[i]=ans[i-1]+1;
		}
	}
	cout<<"YES"<<endl;
	fo(i,1,n){
    
		cout<<ans[i]<<" "; 
	}
	return 0;
}

code差分优化

#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=1e3+5;
int n,m,s[N],ans[N],d[N];
struct node{
    
	int t,l,r;
	bool operator < (const node &p)const{
    
		return t>p.t;
	} 
}a[N];
int main(){
    
	cin>>n>>m;
	fo(i,1,m){
    
		int t,l,r;
		cin>>a[i].t>>a[i].l>>a[i].r;
		
	}
	sort(a+1,a+m+1);
	fo(i,1,m){
    
		if(a[i].t==1){
    
			d[a[i].l] += 1;
			d[a[i].r] -= 1; 
		}
	}
	
	fo(i,1,n){
    
		d[i] += d[i-1];
	}
	// 构造答案 
	ans[1]=n;
	for(int i=2; i<=n; i++){
    
		if(d[i-1]>0){
    
			ans[i]=ans[i-1]+1;
		}else{
    
			ans[i]=ans[i-1]-1;
		}
	}
	
	// 检查答案
	fo(i,1,m){
    
		if(a[i].t==0){
    
			if(ans[a[i].r]-ans[a[i].l] == a[i].r-a[i].l){
    
				// 完全上升 
				cout<<"NO"<<endl; 
				return 0;
			}
		}
	} 
	cout<<"YES"<<endl;
	fo(i,1,n){
    
		cout<<ans[i]<<" "; 
	}
	return 0;
}

E

题意:有一个无向图(树),第一次选择一个点作为根,
(之后选择的点是已经选过的点的子节点)每选择一个点,对答案的贡献为树的大小
问:怎么选使得答案最大

解法:
暴力:n遍dfs统计出来(T)
优化:二次扫描和换根法

二次换根法简单介绍:先一次统计出确定了一个根的答案(由所有子节点的答案加自己的和),换根:把新根的答案(在旧根里是子儿子,在新根里它已经成为一棵树的根了)去掉,然后加上旧根的答案(旧根原来是一刻树的根,现在变成子节点了)
code

#include<bits/stdc++.h>
#define ll long long
#define fo(i,j,n) for(register int i=j; i<=n; ++i)
using namespace std;
const int N=2e5+5,M=N*2;
int n;
int head[N],Next[M],ver[M],tot;
void add(int x, int y){
    
	ver[++tot]=y;
	Next[tot]=head[x], head[x]=tot;
}
int son[N];
ll ans;
void dfs(int x, int fa){
    
	son[x]=1;
	for(int i=head[x]; i; i=Next[i]){
    
		int y=ver[i];
		if(y==fa)continue;
		dfs(y,x);
		son[x]+=son[y];
	}
	ans+=son[x]; // 每个选择的点对答案的贡献 
}
void DFS(int x, int fa, ll now){
    
	ans = max(ans, now);
	for(int i=head[x]; i; i=Next[i]){
    
		int y = ver[i];
		if(y==fa)continue;
		DFS(y, x, now-son[y]+(n-son[y]));
	}
} 
int main(){
    
	cin>>n;
	int x,y;
	fo(i,2,n){
    
		cin>>x>>y;
		add(x,y);
		add(y,x);
	} 
	dfs(1,-1); 
	DFS(1,-1,ans);
	cout<<ans<<endl;
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39778570/article/details/102637853

智能推荐

python:输入要查找的数,若在列表中找到,则返回其下标(索引)_python编写函数,根据关键字查询列表,返回下标。-程序员宅基地

文章浏览阅读3.4k次,点赞5次,收藏8次。废话不多说,直接上代码代码如下:nums = [1, 3, 5, 8, 8, 9, 10, 14, 15, 19, 19, 20, 25, 28, 29, 35, 37, 44, 49]w = int(input('请输入要查找的数据:'))while True: if w in nums: print(f'{w}的下标为{nums.index(w)}') break else: print('找不到该数据') .._python编写函数,根据关键字查询列表,返回下标。

【bzoj3555】[Ctsc2014]企鹅QQ_一个企鹅船新体验-程序员宅基地

文章浏览阅读701次。题目描述:PenguinQQ是中国最大、最具影响力的SNS(Social Networking Services)网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。小Q是PenguinQQ网站的管理员,他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析,小Q发现同一个人注册的账户名_一个企鹅船新体验

LuaXml使用_lua操作xml格式文件-程序员宅基地

文章浏览阅读1k次。LuaXml使用版本Lua 5.3写入再读取XML操作xml = require('LuaXml')local xNewFile = xml.new()-- 一级标题xNewFile[0] = "CATALOG"--[[-- 再增加一级标题写法local describ = {"Empire Burlesque"}local price = {30}local title..._lua操作xml格式文件

数据库高级语言-开窗函数-行转列-listagg_listagg over partition-程序员宅基地

文章浏览阅读942次。一,开窗函数:为了解决复杂的子查询引入进来的,开窗函数也是对行集组进行聚合计算的,并且它返回是多个值,目前oracle db2 sqlserver都支持,但是mysql不支持1.row number() over partition by :分组排名SELECT ORDER_NUMBER, PRODUCT_TYPE, ROW_NUMBER() OVER ( PARTITION BY O..._listagg over partition

Java文本框内文字显示不同颜色、字号等属性【函数调用一键实现】_java编写多线程聊天室时改变不同信息的字体颜色-程序员宅基地

文章浏览阅读6.8k次,点赞35次,收藏8次。Hello!你好哇,我是灰小猿!最近在做聊天室相关项目的开发的时候,需要对文本框中的字体进行区别显示,但是由于JTextArea文本框属于纯文本形式的,无法对其中的文本进行不同格式的显示,所以这个时候就需要使用JTextPane文本域进行文本内容的显示了。其主要原因是:JTextPane文本域中可以设置html样式JTextArea文本框不可以设置html样式这就造成了JTextPane文本域中的内容可以根据需要自行设置属性,从而实现不同文字内容的颜色、字号等属性。通过以下函数可以直_java编写多线程聊天室时改变不同信息的字体颜色

Ubuntu 16.04无法登录图形界面_ubuntu16.04图形界面登录失败-程序员宅基地

文章浏览阅读3k次。Ubuntu 16.04无法登录图形界面0、分析个人猜测,这个问题,有可能是图形界面文件受损,或者没有安装图形界面,或者图形界面没有设置默认Ubuntu开机启动1、方法1:重装Ubuntu图形界面(1)、如果不知道是否安装了图形界面,可以通过下面指令测试出:sudo apt-get install ubuntu-desktop如果存在安装了的图形界面,那么会有信息提示(2)、卸载图形界面sudo apt-get --purge remove ubuntu-desktop上面这条命令操作_ubuntu16.04图形界面登录失败

随便推点

Linux运维之(三)Samba服务器原理及安装配置_linux操作系统samba的工作原理-程序员宅基地

文章浏览阅读1.7k次。Samba服务器原理及安装简介Samba是在Linux系统上实现SMB(Session MessageBlock)协议的一个免费软件,以实现文件共享和打印机服务共享。服务器组件samba有两个主要的进程smbd和nmbd。smbd进程提供了文件和打印服务,而nmbd则提供了NetBIOS名称服务和浏览支持,帮助SMB客户定位服务器,处理所有基于UDP的协议。安装[root@..._linux操作系统samba的工作原理

异步FIFO(verilog简单实现)_verilog 简单fifo-程序员宅基地

文章浏览阅读273次。对其他网友的代码进行了改进纠正,使代码更加完整,并用vivado2020.1进行了仿真测试源代码(不到100行):`timescale 1ns/1psmodule test #(parameter data_width =4,depth =8,addr_width=3)( wclk,rst_w,w_en,din,w_ptr, rclk,rst_r,r_en,dout,r_ptr, fifo_empty,fifo_full);input wclk,rst_w,w_en;i_verilog 简单fifo

怎样用异或查找出多出的字母_已知异或怎么求字符-程序员宅基地

文章浏览阅读2.1k次。今天刷leetcode,遇到了一道题,很有意思,就是给了俩字符串,一个A,一个B,字符串B是这样子的,先把字符串A打乱,然后随机在A中加入一个任意字母,就变成了B。问加入的是啥字母?   举个例子:   A:“abc”   B:“cbea”   那么很明显,加入的字母是e。如何求出来呢?   这里介绍一种非常简答的方法,就是使用异或。   因为字母是char类型,char类型可以当做in_已知异或怎么求字符

计算机驱动空间的c盘不足怎么办,c盘空间不足-程序员宅基地

文章浏览阅读5.7k次。c盘空间不足怎么办?尽管现在的硬盘普通都已以T记,但系统分区一般我们还是分得比较小的,电脑久用未清理时较常出现安装软件或运行程序时会提示空间不足,或磁盘空间不够的提示,那么出现c盘空间不足怎么解决呢?下面就来简单介绍一下。c盘空间不足解决一: 将页面分区文件移到其它分区1、将系统页面文件从C盘移走,该文件比较大:2、右击“计算机”,选择“属性”:3、在弹出的“系统属性”对话框中,选择“高级”选项卡..._驱动器c空间不足怎么办

CSS3各个模块详解-程序员宅基地

文章浏览阅读2.2k次。一, CSS3 盒子 阴影 属性 box- shadow 也是 CSS3 新增 的 一个 重要 属性, 用来 定义 元素 的 盒子 阴影。inset: 阴影 类型, 可选 值。 如果不 设置, 其 默认 的 投影 方式 是 外 阴影; 如果 取其 唯一 值“ inset”, 就是 给 元素 设置 内 阴影。 x- offset: 阴影水平偏移量, 其值可以是正负值。 如果取正值, 则..._css3模块包括:盒子模型、列表模块、

layui upload 上传无反应_layui upload 超时时间-程序员宅基地

文章浏览阅读5.4k次,点赞2次,收藏2次。upload.js中://防止事件重复绑定 if(options.elem.data('haveEvents')) return; …… options.elem.data('haveEvents', true);第一次render之后,button '#selectFileBtn' 会被添加属性haveEvents 值为true;下一次render,haveEvents的值依然为tru..._layui upload 超时时间

推荐文章

热门文章

相关标签