[bzoj2138]stone

news/2024/4/24 4:26:14/

题目描述

话说Nan在海边等人,预计还要等上M分钟。为了打发时间,他玩起了石子。 Nan搬来了N堆石子,编号为1到N,每堆包含Ai颗石子。每1分钟,Nan会在编号在[Li,Ri]之间的石堆中挑出任意Ki颗扔向大海(好疼的玩法),如果[Li,Ri]剩下石子不够Ki颗,则取尽量地多。为了保留扔石子的新鲜感,Nan保证任意两个区间[Li,Ri]和[Lj,Rj] ,不会存在Li<=Lj & Rj<=Ri的情况,即任意两段区间不存在包含关系。可是,如果选择不当,可能无法扔出最多的石子,这时NN就会不高兴了。所以他希望制定一个计划,他告诉你他m分钟打算扔的区间[Li,Ri]以及Ki。现在他想你告诉他,在满足前i-1分钟都取到你回答的颗数的情况下,第i分钟最多能取多少个石子。

hall定理

我们假设钦定了每次要扔多少颗,怎么判断是否合法呢?
如果网络流呢?
那么就是二分图求最大流是否满流!
把点拆开也可以看做是求有没有完美匹配!
那我们用hall定理吧!
但是hall定理居然是选任意子集QAQ
没事,我们来证明一个结论:
只需要考虑选一个区间。
当然,首先我们要按照右端点排序(每次丢石子对应一段区间),然后我们注意要剔除掉永远不会被拿石子丢的区间。
题目有个性质,保证了右端点有序时左端点也有序,好东西!
假设我们选了一个子集,它们对应的编号是不连续的。
假如是两段,多段的情况是类似的。那么左边那段的最右对应区间如果和右边那段的最左对应区间不相交的话,那么它们是否满足hall定理其实取决于两边是否分别满足hall定理,因此我们并不需要来验证它是否满足hall定理。
那么就考虑一下相交咯!如果相交了的话,把中间那一段补上后,连接的Y集合节点数并没有增多(这是利用了题目的特殊性质),而X集合节点数增多了,所以它是否满足hall定理其实取决于补上后是否满足hall定理,补上后不满足整个图就是不行的,而补上后满足我们也没有验证它的必要了。
因此,我们只需要让每一个区间满足hall定理即可!

推合法情况

设bi表示排序后第i次丢石子丢了多少颗。
ai表示第i个石子堆的石子数。
则对于任意l<=r,都要满足
ri=lbi<=R[r]i=L[l]ai
设s表示b的前缀和,ss表示a前缀和。
同时为了方便,令v[i]=ss[R[i]],vv[i]=ss[L[i+1]-1]
那么上面式子可写为
SrSl1<=VrVVl1
SrVr<=Sl1VVl1
继续为了方便,令c[i]=s[i]-v[i],cc[i]=s[i-1]-vv[i-1]
那么上面式子可写为
Cr<=CCl
只要让这个满足,完美匹配便是存在的。

做法

那么现在按照时间顺序丢石子。
我们每次希望找到最大一个x,把bt赋值为x,使得完美匹配仍存在。
考虑给bt赋值为x的影响。
那么s[t~m]会加上x。
对应有c[t~m]+x,cc[t+1~m]+x。
那么我们考察每一对i<=j是否还满足 Cj<=CCi
如果j在[t,m],i在[t+1,m],因为均加x,关系不变。
如果j不在[t,m],i在[t+1,m],不符合i<=j!
如果j不在[t,m],i不在[t+1,m],因为均加x,关系不变。
只需要看j在[t,m],i不在[t+1,m]的情况!
那么有 Cj+x<=CCi
x<=CCiCj
右式最小值是x的上限值,可以在[1,t]中取CC的最小值,同时在[t,m]中取C的最大值。C和CC的修改和区间最值查询用线段树完成。
然后这题就做完啦~

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int maxn=40000+10;
struct dong{int time,id;
} b[maxn];
int mx[maxn*4],mi[maxn*4],ad[maxn*4][2];
int s[maxn],ss[maxn],c[maxn],cc[maxn],v[maxn],vv[maxn],a[maxn],L[maxn],R[maxn],K[maxn];
int ans[maxn],g[maxn],bz[maxn],num[maxn];
int i,j,k,l,t,n,m,x,y,z,p,tot,top;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
bool cmp1(dong a,dong b){return R[a.time]<R[b.time];
}
bool cmp2(dong a,dong b){return a.time<b.time;
}
void mark(int p,int v,int f){if (f>0){mi[p]+=v;ad[p][0]+=v;}else{mx[p]+=v;ad[p][1]+=v;}
}
void down(int p){if (ad[p][0]){mark(p*2,ad[p][0],1);mark(p*2+1,ad[p][0],1);ad[p][0]=0;}if (ad[p][1]){mark(p*2,ad[p][1],-1);mark(p*2+1,ad[p][1],-1);ad[p][1]=0;}
}
void change(int p,int l,int r,int a,int b,int v,int f){if (a>b) return;if (l==a&&r==b){mark(p,v,f);return;}down(p);int mid=(l+r)/2;if (b<=mid) change(p*2,l,mid,a,b,v,f);else if (a>mid) change(p*2+1,mid+1,r,a,b,v,f);else{change(p*2,l,mid,a,mid,v,f);change(p*2+1,mid+1,r,mid+1,b,v,f);}mx[p]=max(mx[p*2],mx[p*2+1]);mi[p]=min(mi[p*2],mi[p*2+1]);
}
int query(int p,int l,int r,int a,int b,int f){if (l==a&&r==b) return f>0?mi[p]:mx[p];down(p);int mid=(l+r)/2;if (b<=mid) return query(p*2,l,mid,a,b,f);else if (a>mid) return query(p*2+1,mid+1,r,a,b,f);else if (f>0) return min(query(p*2,l,mid,a,mid,f),query(p*2+1,mid+1,r,mid+1,b,f));else return max(query(p*2,l,mid,a,mid,f),query(p*2+1,mid+1,r,mid+1,b,f));
}
int main(){//freopen("data.in","r",stdin);n=read();x=read();y=read();z=read();p=read();fo(i,1,n) a[i]=((i-x)*(i-x)%p+(i-y)*(i-y)%p+(i-z)*(i-z)%p)%p;m=read();K[1]=read();K[2]=read();x=read();y=read();z=read();p=read();fo(i,3,m) K[i]=(x*K[i-1]+y*K[i-2]+z)%p;fo(i,1,m){L[i]=read(),R[i]=read();g[L[i]]=max(g[L[i]],R[i]-L[i]+1);}k=0;fo(i,1,n){if (k) k--;k=max(k,g[i]);if (!k) bz[i]=1;num[i]=num[i-1]+bz[i];}fo(i,1,n) if (!bz[i]) a[i-num[i]]=a[i];fo(i,1,m) L[i]-=num[L[i]],R[i]-=num[R[i]];n-=num[n];fo(i,1,n) ss[i]=ss[i-1]+a[i];fo(i,1,m) b[i].time=i;sort(b+1,b+m+1,cmp1);fo(i,1,m) b[i].id=i;fo(i,1,m){v[i]=ss[R[b[i].time]];if (i<m) vv[i]=ss[L[b[i+1].time]-1];c[i]=s[i]-v[i];cc[i]=s[i-1]-vv[i-1];}fo(i,1,m) change(1,1,m,i,i,c[i],-1);fo(i,1,m) change(1,1,m,i,i,cc[i],1);sort(b+1,b+m+1,cmp2);fo(i,1,m){t=b[i].id;j=query(1,1,m,t,m,-1);k=query(1,1,m,1,t,1);ans[i]=min(K[i],k-j);change(1,1,m,t,m,ans[i],-1);change(1,1,m,t+1,m,ans[i],1);}fo(i,1,m) printf("%d\n",ans[i]);
}

http://www.ppmy.cn/news/670768.html

相关文章

MacOS10.9平台配置Appium+Java环境

1) 安装JDK 下载地址:Java Downloads | Oracle 安装:JDK安装很简单,按默认安装即可。 配置环境变量: 打开终端新建.bash_profile文件:touch .bash_profile 打开bash_profile文件:vi .bash_profile 配置JAVA_HOME export JAVA_HOME=$(/usr/libexec/java_home) 保存退出…

如何上传图片

开发工具与关键技术&#xff1a;VS jQuery 作者&#xff1a;黄海滨 撰写时间&#xff1a;2019年5月7日 在网上经常会看到图片&#xff0c;但是图片是怎么上传的呢 这个是个简单的例子&#xff0c;左边的框就是装图片的&#xff0c;具体怎么实现呢 、 这些就是它的代码&#x…

java保存网络图片到硬盘

此博文为原创技术分享&#xff0c;如需转载请标明出处 import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStream; import java.net.HttpURLConnection; import java.net.URL;public static void main(String[] args) {String netImagePath …

base64图片如何解密

第一&#xff1a; http://www.jsons.cn/img2base64/第二&#xff1a;在新建一个666.php文件,然后 ?php echo "<img src里面写http://www.jsons.cn/img2base64/ 图片加密后的编码 />第三&#xff1a;输出即可.

java中button添加图片无法显示的问题

1.图片的相对路径要设置正确&#xff0c;比如String pow_url"src/main/resources/123.png"; 2.要注意查看图片的格式&#xff0c;有的从浏览器上下载的图片是webp格式&#xff0c;即便你保存的时候更改为jpg&#xff0c;它的项目类型依旧可能是webp&#xff0c;有时…

SA的恶魔:态势感知的敌人

构建和维护态势感知对于许多不同工作和环境中的人来说可能是一个困难的过程。飞行员们报告说&#xff0c;他们的大部分时间一般都花在努力确保他们对发生的事情的心理描述是实时、准确的。对于许多其他领域&#xff1a;那些系统复杂且必须处理大量实时信息&#xff0c;信息快速…

选择图片

选择图片 PopupWindow的Xml布局 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match…

骑砍自建服务器,恶魔之魂玩家不忍服务器关闭 自建服务器上线运行

网页游戏 传奇 online | 传奇单机版 | 海盗路飞 | 贪玩蓝月 | 2018 新传奇 | 悟空 | 青囊尸衣 | 航海王 OL | 魔域 2.0|MU: 大天使 | 天剑狂刀 | 山海经 | 太极功夫 OL 热门单机 NBA 2K18 | 巫师 3 狂猎 | 合金装备 5 | 黑暗之魂 3 | 饥荒 | 方舟 | 看门狗 2 | 骑马与砍杀 | 龙…

【JS对象】打败JS原型、原型链大恶魔方法详解

文章目录 什么是对象&#xff1f;什么是面向对象&#xff1f;创建对象的方式原型是什么&#xff1f;__proto__属性constructor属性原型链函数的定义类型有哪些&#xff1f;函数也是一个对象完整的原型链 打败恶魔第一步&#xff0c;我们先要了解什么是 面向对象编程&#xff1…

做一个简单的Swagger文档案例,图片上传,Excel导入导出

目录 一、swagger 一、swagger 号称世界上最流行的Api框架;RestFul Api文档在线自动生成工具>Api文档与API定义同步更新直接运行&#xff0c;可以在线测试API接口;支持多种语言:(Java&#xff0c;Php… 举个栗子user来实现增删改查以及Excel的导入导出还有图片上传 项目目…

使用jqGrid进行图片上传

1.jsp代码 <%--引入bootstrap的样式--%><link rel"stylesheet" href"statics/boot/css/bootstrap.min.css"><%--引入bootstrap和jqgrid的整合样式--%><link rel"stylesheet" href"statics/jqgrid/css/trirand/ui.jqgr…

3D游戏恶魔与牧师(动作分离)

这次作业和上次比起来在代码量上会更大一些&#xff0c;处理上也更复杂&#xff0c;其中一个比较主要的要求就是使用MVC框架&#xff1a; Model View Controller&#xff0c;是模型 (model)&#xff0d;视图 (view)&#xff0d;控制器 (controller)的缩写&#xff0c; 目的在于…

php 二进制字符串转图片,PHP实现接收二进制流转换成图片的方法

本文实例讲述了PHP实现接收二进制流转换成图片的方法。分享给大家供大家参考&#xff0c;具体如下&#xff1a; 这里实现php 接收二进制流转换成图片,所使用的图片类imageUpload.php如下: /** * 图片类 * version 1.0 * * PHP默认只识别application/x-www.form-urlencoded标准的…

恶意PNG:隐藏在图片中的“恶魔”

<img src&quot;http://image.3001.net/images/20150227/14250428964561.jpg!small&quot; title&quot;214201hhuuhubsuyuukbfy_meitu_1_meitu_2.jpg&quot;/></strong></span></p> 在互联网安全这场持久战中&#xff0c;网络攻击者一直在…

AR小游戏 牧师与恶魔

AR小游戏 牧师与恶魔 前言 这是中山大学数据科学与计算机学院2019年3D游戏编程与设计的第十一次作业 所有项目与代码已上传至github当中&#xff0c;欢迎大家访问。 github个人主页: https://starashzero.github.io 3D游戏编程与设计主页: https://starashzero.github.io/3DG…

mysql读取图片数据宽度_jQuery获取file控件中图片的宽高与大小

问题 如何判断input file表单里上传的图片的宽高和大小呢&#xff1f; 解决方案 这个时候图片还没真正上传&#xff0c;也不是在页面上展示&#xff0c;不能使用$(“#id”).width(),$(“#id”).height()这种方式。 在Stack Overflow找到一个方法获取input file图片文件的宽高&a…

恐怖地狱火恶魔叉404模板下载

简介&#xff1a; 恐怖地狱火恶魔叉404模板下载 网盘下载地址&#xff1a; http://kekewl.cc/3fz7QAQBjDV0 图片&#xff1a;

图片移位原理

import cv2 import numpy as np img cv2.imread(d://python1//image//1.jpg,1)imgInfo img.shape height imgInfo[0] width imgInfo[1]matShift np.float32([[1,0,100],[0,1,20]]) #2行3列 dst cv2.warpAffine(img,matShift,(width,height))cv2.imshow(image1,img) cv2.i…

浅析 base64 处理图片

Base64是一种用64个字符来表示任意二进制数据的方法&#xff1b; 在网络中&#xff0c;base64编码后的文件可以通过http协议传输&#xff0c;因此我们常看到base64编码后的图片&#xff1b;比如&#xff1a; <img src"https://img-blog.csdnimg.cn/2022010704111397712…

java web 存储图片_idea2019配置,Javaweb项目实现上传图片保存到本地文件文件夹,Tomcat服务器...

1.首先设置Tomcat的安装目录下E:\Tomcat8\conf\server.xml文件中标签中添加配置 path&#xff1a;你的虚拟路径 docBase:保存图片的绝对路径 2.然后配置项目图片的路径&#xff1a; 选择你保存图片的文件夹 选择在前面server.xml中设置的虚拟路径 点击确定就设置好了 保存图片的…