首页 > 其他分享 >231023校内赛

231023校内赛

时间：2023-10-24 19:35:41浏览次数：42  
标签：校内 lc int mid 231023 rc mx define

T1 区间

piEsKdx.jpg

题解

很容易想到的一点是如果 \(k\) 足够大，那么把区间单独放到一个组里总比多个区间在一个组优

对于多个区间来说，区间之间如果两两不包含的话这道题会是比较好做的

就可以注意到如果一个大区间包含了一个小区间，那么大区间要么单独一组，要么和小区间同一组，这样会是比较优的选择

所以只需要对小区间做 dp ，求出 \(f_i\) 表示小区间形成了 \(i\) 组的最大贡献，然后把前 \(k−i\) 大的大区间每一个单独一组即可

小区间设 \(f_{i,j}\) 表示现在分了 \(i\) 组，考虑了前 \(j\) 个区间的最大贡献。每个 \(i\) 分别单调队列即可省掉一维并优化复杂度

到底是谁出的这么难想的第一题

#include<bits/stdc++.h>
#define N 5010
#define inf (1e9)
using namespace std;
struct node{
	int l,r;
}a[N],p[N];
int n,k,m,ans,tot,mx,len[N],f[N],g[N],top,last,stk[N];
bool cmp(node x,node y){
	return x.r==y.r?x.l>y.l:x.r<y.r;
}
bool great(int x,int y){
	return x>y;
}
void solve(){
	for(int i = 1;i<=n;i++) f[i] = -inf;
	for(int i = 1;i<=k;i++){
		top = 0;last = 1;g[0] = -inf;
		for(int j = 1;j<=n;j++){
			while(top&&f[stk[top]-1]+p[stk[top]].r<=f[j-1]+p[j].r) top--;
			stk[++top] = j;
			last = min(top,last);
			while(p[stk[last]].r<=p[j].l) last++;
			g[j] = f[stk[last]-1]+p[stk[last]].r-p[j].l;
		}
		for(int j = 0;j<=n;j++) f[j] = g[j];
		ans = max(ans,f[n]+len[k-i]);
	}
}
int main(){
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i = 1;i<=n;i++)
		cin>>a[i].l>>a[i].r;
	sort(a+1,a+n+1,cmp);
	tot = mx = 0;
	for(int i = 1;i<=n;i++){
		if(!tot||mx<a[i].l){
			mx = a[i].l;
			p[++tot] = a[i];
		}else len[++m] = a[i].r-a[i].l;
	}
	sort(len+1,len+m+1,great);
	for(int i = 1;i<=m;i++)
		len[i]+=len[i-1];
	for(int i = m+1;i<=k;i++) 
		len[i] = -inf;
	n = tot;
	solve();
	cout<<ans;
	return 0;
}

T2妹子

piEysN6.jpg

题解

对于一个序列来说，它的最大值一定是单调不降的

所以很容易会往二分上想

那么对于一个决策点来说，如果左边的 \(a\) 序列的最大值比右边的 \(b\) 序列的最大值大

二分的时候那就应该把 \(mid\) 左移

反之，右移

对于这个二分，你可以在线段树上实现，做到 \(\mathcal O(n\log n)\) 的复杂度

也可以不在线段树上实现，只不过是 \(\mathcal O(n\log^2 n)\) 罢了

#include<bits/stdc++.h>
#define ll long long
#define inf (0x5fffffff)
#define N 500010
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
struct tree{
	int a[N];
	struct node{
		int l,r;
		ll mx,flag;
	}t[N<<2];
	void pushnow(int p,ll v){
		t[p].mx+=v;
		t[p].flag+=v;
	}
	void pushdown(int p){
		if(t[p].flag){
			pushnow(lc,t[p].flag);
			pushnow(rc,t[p].flag);
			t[p].flag = 0;
		}
	}
	void build(int p,int l,int r){
		t[p].l = l,t[p].r = r;
		t[p].mx = -inf;t[p].flag = 0;
		if(l==r){
			t[p].mx = a[l];
			return ;
		}
		int mid = (l+r)>>1;
		build(lc,l,mid);
		build(rc,mid+1,r);
		t[p].mx = max(t[lc].mx,t[rc].mx);
	}
	ll query(int p,int l,int r){
		if(t[p].l>=l&&t[p].r<=r)
			return t[p].mx;
		pushdown(p);
		ll ans = -inf,mid = (t[p].l+t[p].r)>>1;
		if(l<=mid) ans = max(ans,query(lc,l,r));
		if(r>mid&&ans<t[rc].mx) ans = max(ans,query(rc,l,r));
		return ans;
	}
	void add(int p,int l,int r,int v){
		if(t[p].l>=l&&t[p].r<=r){
			pushnow(p,v);
			return ;
		}
		pushdown(p);
		int mid = (t[p].l+t[p].r)>>1;
		if(l<=mid) add(lc,l,r,v);
		if(r>mid) add(rc,l,r,v);
		t[p].mx = max(t[lc].mx,t[rc].mx);
	}
}T1,T2;
int n,m;
int main(){
	freopen("girl.in","r",stdin);
	freopen("girl.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
		cin>>T1.a[i];
	for(int i = 1;i<=n;i++)
		cin>>T2.a[i];
	T1.build(1,1,n);T2.build(1,1,n);
	for(int i = 1;i<=m;i++){
		char opt;int ql,qr,v;
		cin>>opt>>ql>>qr>>v;
		if(opt=='A') T1.add(1,ql,qr,v);
		else T2.add(1,ql,qr,v);
		cin>>ql>>qr;
		int l = ql-1,r = qr;
		while(l<r){
			int mid = (l+r)>>1;
			if(T1.query(1,ql,mid)>T2.query(1,mid+1,qr)) r = mid;
			else l = mid+1;
		}
		cout<<min(T1.query(1,ql,r),T2.query(1,r,qr))<<"\n";
	}
	return 0;
}

T3 数对

piE2Hds.jpg

题解

对于这个题有一个结论就是按 \(a+b\) 排序一定是最优的

因为可以分类讨论一下对于 \(a,b\) 大小关系的四种情况，就能得出这个结论

自己手写一下，挺简单的，我就不说了我是真的懒

然后其实就是 \(dp\) 的事了

设 \(f_{i,j}\) 表示前 \(i\) 个数中，已选的数的 \(\max(a) = j\) ，最多选了多少个数

转移时只需要更新选了第 \(i\) 个数的情况，分别考虑 \(j\le \min(a_i,b_i)\) 和 \(a_i< j \le b_i\)

用线段树维护即可做到 \(\mathcal O(n \log n)\)

#include<bits/stdc++.h>
#define N 100010
#define ll long long 
using namespace std;
struct node{
	int a,b;ll p;
}a[N];
struct tree{
	#define lc (p<<1)
	#define rc ((p<<1)|1) 
	struct node{
		int l,r;
		ll mx,flag;
	}t[N<<4];
	void pushnow(int p,ll v){
		t[p].mx+=v;
		t[p].flag+=v;
	}
	void pushdown(int p){
		if(t[p].flag){
			pushnow(lc,t[p].flag);
			pushnow(rc,t[p].flag);
			t[p].flag = 0;
		}
	}
	void build(int p,int l,int r){
		t[p].l = l,t[p].r = r;
		if(l==r) return ;
		int mid = (l+r)>>1;
		build(lc,l,mid);
		build(rc,mid+1,r);
		t[p].mx = max(t[lc].mx,t[rc].mx);
	}
	ll query(int p,int l,int r){
		if(t[p].l>=l&&t[p].r<=r)
			return t[p].mx;
		pushdown(p);
		ll ans = 0,mid = (t[p].l+t[p].r)>>1;
		if(l<=mid) ans = max(ans,query(lc,l,r));
		if(r>mid&&ans<t[rc].mx) ans = max(ans,query(rc,l,r));
		return ans;
	}
	void add(int p,int l,int r,ll v){
		if(t[p].l>=l&&t[p].r<=r){
			pushnow(p,v);
			return ;
		}
		pushdown(p);
		int mid = (t[p].l+t[p].r)>>1;
		if(l<=mid) add(lc,l,r,v);
		if(r>mid) add(rc,l,r,v);
		t[p].mx = max(t[lc].mx,t[rc].mx);
	}
	void change(int p,int x,ll v){
		if(t[p].l==t[p].r&&t[p].l==x){
			t[p].mx = max(t[p].mx,v);
			return ;
		}
		pushdown(p);
		int mid = (t[p].l+t[p].r)>>1;
		if(x<=mid) change(lc,x,v);
		else change(rc,x,v);
		t[p].mx = max(t[lc].mx,t[rc].mx);
	}
}T;
int n,m,w[N<<2];
bool cmp(node x,node y){
	return x.a+x.b<y.a+y.b;
}
int main(){
	freopen("pair.in","r",stdin);
	freopen("pair.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>a[i].a>>a[i].b>>a[i].p;
		w[++m] = a[i].a;
		w[++m] = a[i].b;
	}
	sort(w+1,w+m+1);
	m = unique(w+1,w+m+1)-w-1;
	for(int i = 1;i<=n;i++){
		a[i].a = lower_bound(w+1,w+m+1,a[i].a)-w;
		a[i].b = lower_bound(w+1,w+m+1,a[i].b)-w;
	}
	sort(a+1,a+n+1,cmp);
	T.build(1,1,m);
	for(int i = 1;i<=n;i++){
		int tmp = min(a[i].a,a[i].b);
		ll j = T.query(1,1,tmp)+a[i].p;
		T.change(1,a[i].a,j);
		if(tmp<a[i].b) T.add(1,tmp+1,a[i].b,a[i].p);
	}
	cout<<T.query(1,1,m);
	return 0;
}

T4

摆了，不写

标签：校内,lc,int,mid,231023,rc,mx,define
From： https://www.cnblogs.com/cztq/p/17785581.html

相关文章

  • 每日总结20231023
    代码时间（包括上课）3h代码量（行）：100行博客数量（篇）：1篇相关事项：1、今天是周一，新的一周开始了，然后软件模式是上机课，这节课写的第一个实验是UML的复习，赶上软考也考UML，正好趁着这个机会把uml的知识多看看。2、第二节课是人机交互技术，这节课老师点了五名同学讲了一下他们分别对H+这个模......
  • 20231023学习总结
    Hive数据库的数据类型：TINYINT:1个字节SMALLINT:2个字节INT:4个字节BIGINT:8个字节BOOLEAN:TRUE/FALSE）FLOAT:4个字节，单精度浮点型DOUBLE:8个字节，双精度浮点型STRING字符串ARRAY:有序字段MAP:无序字段STRUCT:一组命名的字段HiveQL:createdatabaseifnotexistsdbna......
  • 231019校内赛
    T1机器人题解傻逼题，但是有人\(90\)分一开始十分想直接暴力\(2^n\)判断每一步选不选求出所有可能性但是会发现它有制约关系有些步走了之后，有些就必须走了所以需要用一个数组记录当前位置走没走过，或者是不是障碍注意走没走过不能直接赋值\(1,0\)因为回溯时会直接将前......
  • 231019校内赛
    T1购买饮料题解简单且傻逼的题目有人更傻逼没做出来很容易就会想去拿最后能喝多少瓶去做未知量来求然后就有一个严重的问题，它会赊账非常明显这样算是不得行的那么考虑换个思路以能喝多少套饮料为未知量，先除去第一套，免得一套都买不起时赊账买了饮料然后将剩余的钱除以\(......
  • [校内]此方（konata）
    2023-10-14题目LittleBrother题目描述难度&重要性(1~10):7题目来源CQYC题目算法几何，二分解题思路Sol我们知道，对于两个圆，我们无非就只有三种情况：相离，相切，相交。而这道题目是不允许其他圆相交，而两个圆不相交只有两种情况：包含，不包含。根据垂径定理得知，过线段两端的圆的......
  • 231011校内赛
    T1树上的数题解比上一次好一些的第一题不过我还是没做出来一眼树形\(dp\)不过状态设计和转移不是很好列容易想到对于子树枚举，记录\(f_{i,j}\)表示\(i\)的子树空出了\(j\)个点时的方案数对于每一个节点的初始状态都是\(f_{i,0}=n-dep_i\\\f_{i,1}=1\)为......
  • 231009校内赛
    T1里群题解阴间第一题题目中有一个很明显的建图方法就是对于第\(i\)天入群的人在第\(j\)天退群那么就在\(i,j\)之间连一条边首先有一个结论，管理员个数不大于\(3\)对于这个结论，证明如下：首先第一次删除出现后就一定需要两个管理员了如果某次删除只删掉了某一个管理......
  • 231007校内赛
    T1karma题解首先从贪心的思路出发把所有零多的字符串放在前面，但如下一组数据便可以卡掉201100接着我们可以来思考对于贪心的更改多举几组不同的可以卡掉的样例后可以发现如下规律先将所有字符串按\(0\)的数量排一遍序对于每一个字符串的\(0\)和\(1\)的数量我......
  • 231004校内赛
    T1水管题解很简单的一道题，别想复杂了只要一边\(dfs\)即可先将当前点的所有水量给出去，如果缺水就给出去负数那么等到最后一个节点如果不是刚好合适，那么就把剩余水量回溯回来，无论正负再如此给下一个连边的点如果最后一个点刚好合适那么给下一个点的就是\(0\)实现很简单......
  • 231002校内赛
    T1数独题解十分简单的一道模拟题有sb少打了一个换行挂50分#include<bits/stdc++.h>#defineN15usingnamespacestd;structnode{ inta[N][N],be;}t[N*10];intT,n=9,q;intferror(intcnt,intx,inty,intk){ for(inti=1;i<=n;i++) if(t[cnt].a[x][i]==k)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99