# 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个玩具 ，鸡蛋中放有贴纸和玩具。问最少买多少个鸡蛋才能使得有一个鸡蛋中既有玩具又有贴纸。

```//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.

```//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 = 0, 让 l ,r 区间不是按非降序排序

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

```//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.

```//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;
}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求最优解。

```//E
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 200005;
struct N{
int v,nxt;
}edge[maxn*4];
ll t[maxn],ans;
{
++cnt;
edge[cnt].v = v;
}
void dfs(int u,int f)
{
t[u] = 1;
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)
{
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);
}
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 版权协议，转载请附上原文出处链接和本声明。

• ### [LightOJ-1356] Prime Independence 二分图+素数分解

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

• ### 并查集(个人模版)

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

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

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

• ### cf1037D. Valid BFS?(BFS?)

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

• ### LeetCode 164. Maximum Gap (排序)

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

• ### Topcoder SRM 563 Div1 500 SpellCards

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

• ### 关于数组的算法

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