首页 > 其他分享 >2024-03-14

2024-03-14

时间：2024-03-14 18:11:45浏览次数：18  
标签：二分 03 14 int 询问 mid 2024 include ql

2024-03-14

Riddle

继续做上次没做出来的题

2-SAT
限制是

  • 如果一个点不选，那么与它相连的所有点都必须选
  • 如果一个点选了，那么和他在同一个部分的所有点都不能选

对于边的限制直接建
但是“部分”的限制直接建图是 \(O(n^2)\) 的

优化方法是 前缀优化建图
对于每一个部分，用 \(a_i\) 表示这一个部分的第 \(i\) 个点
\(p_{a_i}\) 表示 \(a_i\) 这个点之前的点有没有被选上的

那么直接按下面的方式建边即可

\[a_i \longrightarrow p_{a_i} \ \ \ \ \ {p_{a_i}}^{\prime} \longrightarrow {a_i}^{\prime} \ \ \ \ \ p_{a_{i-1}} \longrightarrow {a_i}^{\prime} \ \ \ \ \ a_i \longrightarrow {p_{a_{i-1}}}^{\prime} \ \ \ \ \ p_{a_{i-1}} \longrightarrow p_{a_i} \ \ \ \ \ {p_{a_i}}^{\prime} \longrightarrow {p_{a_{i-1}}}^{\prime} \]

这样的建图和原来等价

#include<iostream>
#include<cstring>
#include<algorithm>

#define v1(x) (x)
#define v0(x) (x+n)
#define p1(x) (x+n+n)
#define p0(x) (x+n+n+n)

using namespace std;

const int N=1e6+100;
const int V=4*N,E=2*V;

int n,m,k;
int w,a[N];

int hd[V],edg[E],nxt[E],idx;

void adde(int u,int v) {
	edg[idx]=v,nxt[idx]=hd[u],hd[u]=idx++;
}

int grp[V],cnt;
int dfn[V],low[V],idt;
int stk[V],top;
bool st[V];

void Tarjan(int u) {
    dfn[u]=low[u]=++idt;
    stk[++top]=u,st[u]=true;
    for(int i=hd[u];~i;i=nxt[i]) {
        int v=edg[i];
        if(!dfn[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(st[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]) {
        int v;
        cnt++;
        do {
            v=stk[top--];
            st[v]=false;
            grp[v]=cnt;
        }while(v!=u);
    }
}

int main() {
	memset(hd,-1,sizeof(hd));
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		adde(v0(u),v1(v)),adde(v0(v),v1(u));
	}
	for(int i=1;i<=k;i++) {
		scanf("%d",&w);
		for(int j=1;j<=w;j++) scanf("%d",&a[j]);
		for(int j=1;j<=w;j++) {
			adde(v1(a[j]),p1(a[j])),adde(p0(a[j]),v0(a[j]));
			if(j>1) {
				adde(p1(a[j-1]),p1(a[j])),adde(p0(a[j]),p0(a[j-1]));
				adde(p1(a[j-1]),v0(a[j])),adde(v1(a[j]),p0(a[j-1]));
			}
		}
	}
	for(int i=1;i<=4*n;i++) if(!dfn[i]) Tarjan(i);
	string ans="TAK";
	for(int i=1;i<=n;i++) {
		if(grp[v0(i)]==grp[v1(i)]) {
			ans="NIE";
			break;
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

整体二分

复习整体二分

整体二分用于处理

  • 多次询问 可以离线
  • 答案可以二分

我们可以对于每个询问都猜测它的答案是 mid 然后分为 不大于 mid 和 大于 mid 两个部分继续分治 l==r 时结束这个部分的分治

引用题解的一段话理解

显然可以给每个询问二分答案，统计该询问中小于等于mid的元素个数。如果大于等于k，说明猜大了，否则说明猜小了。

如果用这种方法的话，对于每个询问都至少要用O(询问矩阵大小*log值域)的时间复杂度解决，多组询问的话时间不能接受。

发现多个询问的二分答案是可以同时被检验的，我们可以为所有询问同时二分答案，把所有答案小于等于mid的询问放在询问序列的左侧，大于mid的放到询问序列的右侧然后递归处理。

Dynamic Rankings

板子题：区间带修改第 K 大

不贴代码占地了

矩阵乘法

# 题目描述 #
给你一个 \(n×n\) 的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第 \(k\) 小数。

把树状数组改成二维的
把值小于 mid 的所有点涂黑，就能查询每个询问的子矩阵里面小于等于 mid 的点的个数了
因为要清空，所以记录一个 cur 数组，每次如果这个询问要被分到右边的话就更新一下

树状数组不要写 while 循环了，不知道怎么就寄了。。改成for循环就对了

for(int i=x;i<=n;i+=lowbit(i))
	for(int j=y;j<=n;j+=lowbit(j))
		//...

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510,M=60010;

int n,m;

struct BIT {
	int lowbit(int x) {
		return x&-x;
	}
	int n;
	int tr[N][N];
	void update(int x,int y,int k) {
		for(int i=x;i<=n;i+=lowbit(i))
			for(int j=y;j<=n;j+=lowbit(j))
				tr[i][j]+=k;
	}
	int query(int x,int y) {
		int res=0;
		for(int i=x;i;i-=lowbit(i))
			for(int j=y;j;j-=lowbit(j))
				res+=tr[i][j];
		return res;
	}
	int submatr(int x1, int y1, int x2, int y2) {
		return query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1);
	}
}T;

struct Num {
	int x,y;
	int val;
	friend bool operator < (Num A,Num B) {
		return A.val<B.val;
	}
}mat[N*N];
int cm;

struct Query {
	int x1,y1,x2,y2,k;
}q[M];

int id[M];
int t1[M],t2[M];

int ans[M],cur[M];

int count_black(Query Q) {
	return T.submatr(Q.x1,Q.y1,Q.x2,Q.y2);
}

#define mid ((lft+rgh)/2)
void solve(int lft,int rgh,int ql,int qr) {
	if(ql>qr) return;
	if(lft==rgh) {
		for(int i=ql;i<=qr;i++) ans[id[i]]=mat[lft].val;
		return;
	}
	for(int i=lft;i<=mid;i++) T.update(mat[i].x,mat[i].y,1);
	int c1=0,c2=0;
	for(int i=ql;i<=qr;i++) {
		int nw=id[i];
		int sum=cur[nw]+count_black(q[nw]);
		if(sum>=q[nw].k) t1[++c1]=nw;
		else t2[++c2]=nw,cur[nw]=sum;
	}
	int qc=ql-1;
	for(int i=1;i<=c1;i++) id[++qc]=t1[i];
	for(int i=1;i<=c2;i++) id[++qc]=t2[i];
	for(int i=lft;i<=mid;i++) T.update(mat[i].x,mat[i].y,-1);
	solve(lft,mid,ql,ql+c1-1),solve(mid+1,rgh,ql+c1,qr);
}

int main() {
	scanf("%d%d",&n,&m);
	T.n=n;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			cm++;
			mat[cm].x=i,mat[cm].y=j;
			scanf("%d",&mat[cm].val);
		}
	}
	sort(mat+1,mat+cm+1);
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2,&q[i].k);
		id[i]=i; 
	}
	solve(1,cm,1,m);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	
	return 0;
}

混合果汁

整体二分 + 线段树上二分

对于一个单独的询问，显然可以二分
对于所有美味度大于当前的二分值的果汁，贪心地选择便宜的，一直买到小朋友满意为止，然后看钱够不够

这个过程可以用线段树上的二分实现
建一棵权值线段树，下标是果汁的价格，每个节点维护价格在当前区间的所有果汁的总量和总价钱
每到一个节点，看左儿子的总量够不够，够就递归左边，不够就递归右边

多次询问可以考虑整体二分

每次调整权值线段树内维护的是从 left 到 middle 即可

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

const int MX=100000,N=MX+10;
const int Inf=2e9;

int n,m;

struct Segtree {
	#define ls (u<<1)
	#define rs (u<<1|1)
	struct Node {
		ll sum,num;
	}tr[N*4];
	void pushup(int u) {
		tr[u].num=tr[ls].num+tr[rs].num;
		tr[u].sum=tr[ls].sum+tr[rs].sum;
	}
	void update(int u,int lft,int rgh,int p,int k) {
		if(lft==rgh) {
			tr[u].num+=k;
			tr[u].sum=1ll*lft*tr[u].num;
			return;
		}
		int mid=lft+rgh>>1;
		if(p<=mid) update(ls,lft,mid,p,k);
		else update(rs,mid+1,rgh,p,k);
		pushup(u); 
	}
	ll query(int u,int lft,int rgh,ll k) {
		if(!k) return 0;
		if(lft==rgh) return k*lft;
		int mid=lft+rgh>>1;
		if(tr[ls].num>=k) return query(ls,lft,mid,k);
		return tr[ls].sum+query(rs,mid+1,rgh,k-tr[ls].num);
	}
}T;

struct Juice {
	int val,pri,lim;
	friend bool operator < (Juice A,Juice B) {
		return A.val>B.val;
	}
}w[N];

struct Child {
	int id;
	ll csh,ltr;
}q[N],t1[N],t2[N];

int ans[N];
int now;

void solve(int lft,int rgh,int ql,int qr) {
	if(ql>qr) return;
	if(lft==rgh) {
		for(int i=ql;i<=qr;i++) ans[q[i].id]=w[lft].val;
		return;
	}
	int mid=lft+rgh>>1;
	while(now<mid) now++,T.update(1,1,MX,w[now].pri,w[now].lim);
	while(now>mid) T.update(1,1,MX,w[now].pri,-w[now].lim),now--;
	int c1=0,c2=0;
	for(int i=ql;i<=qr;i++) {
		if(T.tr[1].num<q[i].ltr) t2[++c2]=q[i];
		else if(T.query(1,1,MX,q[i].ltr)<=q[i].csh) t1[++c1]=q[i];
		else t2[++c2]=q[i];
	}
	int qc=ql-1;
	for(int i=1;i<=c1;i++) q[++qc]=t1[i];
	for(int i=1;i<=c2;i++) q[++qc]=t2[i];
	solve(lft,mid,ql,ql+c1-1),solve(mid+1,rgh,ql+c1,qr);
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&w[i].val,&w[i].pri,&w[i].lim);
	for(int i=1;i<=m;i++) scanf("%lld%lld",&q[i].csh,&q[i].ltr),q[i].id=i;
	w[++n]={-1,0,Inf};
	sort(w+1,w+n+1);
	solve(1,n,1,m);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	
	return 0;
}

整体二分总结

整体二分的模板：

void solve(int lft,int rgh,int ql,int qr) {
	if(ql>qr) return; //当前区间没有询问 
	if(lft==rgh) { //找到答案 
		for(int i=ql;i<=qr;i++) //记录答案 
		return;
	}
	int mid=lft+rgh>>1;
	//调整数据结构内维护的值为从 lft 到 mid 
	int c1=0,c2=0; //分成两部分 
	for(int i=ql;i<=qr;i++) {
		//对于每一个询问进行 check
		//并分成两部分 
	}
	//把临时数组复制到查询的数组
	//改变顺序，分成两拨 
	solve(lft,mid,ql,ql+c1-1),solve(mid+1,rgh,ql+c1,qr);//递归进行下一层二分 
}

标签：二分,03,14,int,询问,mid,2024,include,ql
From： https://www.cnblogs.com/Orange-Star/p/18072325

相关文章

  • docker_03days
    迁移备份#镜像从哪来的？1dockerpull拉的2通过容器打包成镜像-centos镜像运行成容器---》装了vim-把装了vim的容器---》打包成镜像-以后拿到这个镜像--》再运行成容器，都会带vim命令3Dockerfile构建#容器保存为......
  • PG14:auth_delay 插件源码分析
    auth_delay让服务器在报告身份验证失败前短暂暂停，以增加对数据库密码进行暴力破解的难度。需要注意的是，这对阻止拒绝服务攻击毫无帮助，甚至可能加剧攻击，因为在报告身份验证失败前等待的进程仍会占用连接。要使用这个模块必须要在postgresql.conf中配置参数shared_preload_libr......
  • 2024年最新港区Apple ID注册教程
    大家都知道，许多海外应用在国内并不能直接下载，例如，TikTok在国内用不了，对跨境电商和海外社媒营销人员来说，如何有效地接触和利用各个国家或地区的在线资源，尤其是对于海外应用程序的接入是很重要的。不过许多做TikTok跨境电商的卖家会将Apple ID切换到港区，下载香港地区可用的TikT......
  • 14_学习日志_数据结构_冒泡排序_快速排序_插入排序
    #include<编织有意义的谎言，使我相信闭上眼再睁开眼时的世界是同一个>1.介绍    从后往前或者从前往后开始两两比较元素，使得最小数上浮或者最大数下沉为冒泡排序，快速排序利用分治思想，使得基准数左边都存放相对较小数，右边存放较大数，两边再按照同样的做法重复。插入排序......
  • 文心一言 VS 讯飞星火 VS chatgpt （214）-- 算法导论16.2 1题
    一、证明：分数背包问题具有贪心选择性质。如果要写代码，请用go语言。文心一言：要证明分数背包问题具有贪心选择性质，我们可以按照以下步骤进行逻辑推导：理解问题：分数背包问题允许我们选择物品的部分重量，目标是最大化背包内物品的总价值，同时不超过背包的总容量。贪心策略：我......
  • 2024最新华为OD机试，题库清单（按算法分类），高效刷题，举一反三，玩转OD
    目录专栏导读华为OD机试算法题太多了，知识点繁杂，如何刷题更有效率呢？一、逻辑分析二、数据结构1、线性表①数组②双指针2、map与list3、优先队列4、滑动窗口5、二叉树6、并查集7、栈三、算法1、基础算法①贪心算法②二分查找③分治递归④搜索算法⑤排序算法2、......
  • 3.14 CF Round 933 (Div. 3)
    (1)CF1941BRudolfand121给定一个长度为\(n\)的序列\(a\)。求最少进行多少次操作后所有\(a_i=0\)：选择一个\(2\lei<n\)，并让\(a_i\getsa_i-2,a_{i-1}\getsa_{i-1}-1,a_{i+1}\getsa_{i+1}-1\)。我们记选择\(i=x\)时的操作为\(\opera......
  • 百度网盘(百度云)SVIP超级会员共享账号每日更新（2024.03.14）
    一、百度网盘SVIP超级会员共享账号可能很多人不懂这个共享账号是什么意思，小编在这里给大家做一下解答。我们多知道百度网盘很大的用处就是类似U盘，不同的人把文件上传到百度网盘，别人可以直接下载，避免了U盘的物理载体，直接在网上就实现文件传输。百度网盘SVIP会员可以让自己百度账......
  • 计算机类主题会议推荐之——ICETIS 2024
    ​第九届电子技术和信息科学国际学术会议（ICETIS2024）大会官网：www.icetis.org大会时间：2024年5月17-19日大会地点：中国-杭州收录检索：EICompendex，Scopus​大会简介       ICETIS会议始于2016年，先后吸引众多来自国内外高等院校、科学研究所、企事业单位的专家、教授......
  • KubeSphere 社区双周报｜2024.02.29-03.14
    KubeSphere社区双周报主要整理展示新增的贡献者名单和证书、新增的讲师证书以及两周内提交过commit的贡献者，并对近期重要的PR进行解析，同时还包含了线上/线下活动和布道推广等一系列社区动态。本次双周报涵盖时间为：2024.02.29-03.14。贡献者名单新晋KubeSpherecontribu......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99