专栏首页wymEducational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

Educational Codeforces Round 67 (Rated for Div. 2)

A. 

题意:

T组输入,n s t 三个数,有n个鸡蛋,s个贴纸,t个玩具 ,鸡蛋中放有贴纸和玩具。问最少买多少个鸡蛋才能使得有一个鸡蛋中既有玩具又有贴纸。

解:小的先填充n,还需n - min(s,t)填充开始出现重复 

//ECR 67 A
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int T,n,s,t;
	scanf("%d",&T);
	while(T--){
		scanf("%d %d %d",&n,&s,&t);
		printf("%d\n",n-min(s,t)+1);//小的先填充n,还需n - min(s,t)填充开始出现重复 
	} 
	return 0;
}

B.

题意:给一个串a,m个询问,每次询问时给出一个串b, b长度小于等于a

问至少取a前缀长度多少才能组成b。

题解:记录a中每个字母出现下标,找b中出现下标最大值

//B
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 200005;
int id[26][maxn];
char s[maxn];
int a[26];
int main()
{
	int n,m;
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		id[s[i]-'a'][++id[s[i]-'a'][0]]=i;//存每个字母第i个下标位置 
	}
	scanf("%d",&m);
	int ans = 0;
	for(int i=0;i<m;i++){
		scanf("%s",s); ans = 0; memset(a,0,sizeof(a));
		int sz = strlen(s);
		for(int j=0;j<sz;j++)
		{
			a[s[j]-'a']++; ans = max(id[s[j]-'a'][a[s[j]-'a']],ans);
			//遍历取最大值	
		}
		printf("%d\n",ans);
	}
	
	
	return 0;
}

 C.

题意:让你构造一个序列,有一系列条件 每行 t l r

t = 0, 让 l ,r 区间不是按非降序排序

t = 1,让  l ,r 区间是按非降序排序

题解:对所有t=1请求,相邻区间递减,区间内相同 

遍历检查不符合No

//C
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;
struct N{int t,l,r;}q[1001];
int a[1001],vis[1001];
int main()
{
	int l,r,fg=0;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&q[i].t,&q[i].l,&q[i].r);
	}	
	for(int i=0;i<m;i++){
		if(q[i].t==1){
			l = q[i].l,r = q[i].r;
			for(int j =l;j<r;j++)
				vis[j] = 1;
		}
	}
	int now = 1001;
	a[1]=now;
	for(int i=2;i<=n;i++){
		if(vis[i-1]==0)now--;
		a[i] = now;
	}
	for(int i=0;i<m;i++){
		l = q[i].l;r = q[i].r;
		int pos = 1;
		for(int j=l;j<r;j++){
			if(a[j]>a[j+1]){
				pos = 0; break;
			}
		}
		if(pos!=q[i].t){
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	for(int i=1;i<=n;i++){
		printf("%d%c",a[i]," \n"[i==n]);
	}
	
	return 0;
}

D.

题意:序列a能否通过任意次任意区间排序排序变成序列b

对b[i],找第一次未删除的下标k, 线段树维护区间[1,k]最小值num,若num<b[i],则无论如何排序都无解,

否则删除k号元素(令k号元素为无穷)继续处理i+1号元素

//D
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5+5;
const int inf = maxn;
struct N{
	int l,r;
	ll pre,add;
}node[maxn<<2];
queue<int> id[maxn];
int a[maxn],b[maxn];
void build(int p,int l,int r){
	node[p].l = l,node[p].r = r,node[p].add = 0;
	if(l==r){
		node[p].pre = a[l];
		return ;
	}
	int mid = (l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	node[p].pre = min(node[p<<1].pre,node[p<<1|1].pre);
}
int query(int p,int l,int r){//求最小值 
	if(node[p].l>=l&&node[p].r<=r){
		return node[p].pre;
	}
	int ans=inf;
	int mid = (node[p].l + node[p].r)>>1;
	if(l<=mid)ans = min(query(p<<1,l,r),ans);
	if(r>mid) ans = min(query(p<<1|1,l,r),ans);
	return ans;
}
void change(int p,int l,int r,int pos)//去掉 pos 点  
{
	if(l==r){
		node[p].pre = inf;
		return ;
	}
	int mid = (node[p].l + node[p].r)>>1;
	if(pos<=mid)change(p<<1,l,mid,pos);
	if(pos>mid)change(p<<1|1,mid+1,r,pos);
	node[p].pre = min(node[p<<1].pre,node[p<<1|1].pre);
}
int main()
{
	int T,n,fg = 0; scanf("%d",&T);
	while(T--){
		scanf("%d",&n); 
		fg = 0;
		for(int i=1;i<=n;i++){
			while(id[i].size())id[i].pop();
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			id[a[i]].push(i);
		}
		build(1,1,n);
		for(int i=1;i<=n;i++){
			scanf("%d",&b[i]);
			if(id[b[i]].empty())fg = 1;
			if(fg)continue;
			int  nid = id[b[i]].front();
			id[b[i]].pop();
			int num = query(1,1,nid);
			if(b[i]>num){
				fg = 1;
			}else{
				change(1,1,n,nid);
			}
		}
		if(fg)printf("NO\n");
		else printf("YES\n");
	}
	
	return 0;
 } 

E.题意:找一个根使得该树的子树之和最大

题解:

dfs一边得初始值,再带着初始值dfs求最优解。

若以u为根的子树总和是val, 则换为其孩子结点v为根 子树总和就等于val

减去大小为 t[v]的子树, 加上 u 为根大小为 n - t[v]的子树

//E
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 200005;
struct N{
	int v,nxt;
}edge[maxn*4];
int head[maxn*4],cnt,n;
ll t[maxn],ans;
void add(int u,int v)
{
	++cnt;
	edge[cnt].v = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}
void dfs(int u,int f)
{
	t[u] = 1;
	for(int i = head[u];i;i=edge[i].nxt){
		int v = edge[i].v;
		if(v==f)continue;
		dfs(v,u);
		t[u]+=t[v]; 
	}
	ans+=t[u];
}
void dfs1(int u,int f,ll val)
{
	for(int i = head[u];i;i=edge[i].nxt){
		int v = edge[i].v;
		if(v==f)continue;
		ll temp = val - t[v] + n - t[v];
		ans = max(ans,temp);
		dfs1(v,u,temp);
	}
}
int main()
{
	int u,v;
	scanf("%d",&n);
	for(int i=0;i<n-1;i++)
	{
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	} 
	dfs(1,0);
	dfs1(1,0,ans);
	cout<<ans<<endl;
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • 区间更新与点值

    用户2965768
  • 并查集(个人模版)

    并查集: 1 int find(int a) 2 { 3 int r=a; 4 while(f[r]!=r) 5 ...

    Angel_Kitty
  • 一遍记住Java常用的八种排序算法与代码实现

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    用户4143945
  • cf1037D. Valid BFS?(BFS?)

    可以这样想,在BFS序中较早出现的一定是先访问的,所以把每个点连出去的边按出现的前后顺序排个序

    attack
  • LeetCode 164. Maximum Gap (排序)

    题解:首先,当然我们可以用快排,排完序之后,遍历一遍数组,就能得到答案了。但是快速排序的效率是O(n* logn),不是题目要求的线性效率,也就是O(n)的效率...

    ShenduCC
  • 区间更新与点值

    用户2965768
  • Topcoder SRM 563 Div1 500 SpellCards

    有\(n\)张符卡排成一个队列,每张符卡有两个属性,等级\(li\)和伤害\(di\)。 你可以做任意次操作,每次操作为以下二者之一:

    attack
  • 关于数组的算法

    3.给定一个数组和一个数num,把小于num的书放在数组左边,大于num的书放在数组右边

    曼路

扫码关注云+社区

领取腾讯云代金券