首页 > 其他分享 >[JXOI2017] 加法 题解

[JXOI2017] 加法 题解

时间:2024-11-10 16:47:14浏览次数:5  
标签:JXOI2017 ad int 题解 long ge 加法

最小值最大,考虑二分答案,问题转为判断最小值是否能 \(\ge x\)。

假如 \(a_i\ge x\),那我们肯定不管;假如 \(a_i<x\),那最好能让选择的区间 \(r\) 值更大,用优先队列维护即可。区间增幅可以用树状数组维护。

时间复杂度 \(O(n\log^2n)\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int t,n,m,k,ad,a[N],c[N];
priority_queue<int>q;
vector<int>g[N];
void add(int x){
	for(;x<=n;x+=x&-x)
		c[x]+=ad;
}int sum(int x){
	int re=0;
	for(;x;x-=x&-x)
		re+=c[x];
	return re;
}int check(int x){
	for(int i=1;i<=n;i++) c[i]=0;
	while(q.size()) q.pop();
	for(int i=1,l=k;i<=n;i++){
		for(auto j:g[i]) q.push(j);
		int nw=a[i]+sum(n)-sum(i-1);
		while(nw<x&&q.size()&&l&&q.top()>=i)
			nw+=ad,add(q.top()),q.pop(),l--;
		if(nw<x) return 0;
	}return 1;
}void solve(){
	for(int i=1;i<=n;i++) g[i].clear();
	cin>>n>>m>>k>>ad;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1,l,r;i<=m;i++)
		cin>>l>>r,g[l].push_back(r);
	int l=0,r=2e8,ans;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid))
			ans=mid,l=mid+1;
		else r=mid-1;
	}cout<<ans<<"\n";
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--) solve();
	return 0;
} 

标签:JXOI2017,ad,int,题解,long,ge,加法
From: https://www.cnblogs.com/chang-an-22-lyh/p/18538185/jxoi2017-jia_fa-tj

相关文章

  • [CF1981E] Turtle and Intersected Segments 题解
    好题好题。难点在建图,因为图的边数将会决定最小生成树的时间复杂度。我们肯定希望能够只建\(O(n)\)级别的边,这样时间复杂度就可以做到\(O(n\logn)\)。观察到当\(i,j,k\)三个区间能够互相连边时(这里假设\(a_i<a_j<a_k\)),我们绝对不会连\((i,k)\)这条边。那么假如我们将......
  • [CF1981E] Turtle and Intersected Segments 题解
    好题好题。难点在建图,因为图的边数将会决定最小生成树的时间复杂度。我们肯定希望能够只建\(O(n)\)级别的边,这样时间复杂度就可以做到\(O(n\logn)\)。观察到当\(i,j,k\)三个区间能够互相连边时(这里假设\(a_i<a_j<a_k\)),我们绝对不会连\((i,k)\)这条边。那么假如我们将......
  • ABC379E 题解
    ABC379E题解一道很好的题,开始还以为是高精度来着,但是发现不必要也不能用高精度,而是用一种技巧代替。题意Youaregivenastring\(S\)oflength\(N\)consistingofdigitsfrom1through9.Foreachpairofintegers\((i,j)\(1\leqi\leqj\leqN)\),define\(f(......
  • CF2030D QED's Favorite Permutation 题解
    题目传送门前置知识差分解法对于移动,我们可以无脑进行交换来保证移动,然后将中途交换的位置再交换回去。通过手摸不难发现,\(p_{i}\)能移动到\(i\)当且仅当\(s_{\min(i,p_{i})\sim\max(i,p_{i})}\)中不含有LR子串。反向考虑,即LR子串不被上述区间包含,差分判断即可。......
  • JavaCC 实战三:整数加法运算
    前两篇文章我们主要介绍了JavaCC安装以及入门介绍。在这篇文章中介绍如何使用Javacc实现判断输入是否是一个合法的加法运算。在如下这个例子中,我们需要实现对如下数字进行加和:99+42+0+15并且在输入中可以允许在数字之间的任意位置出现空格或者换行符。除此之......
  • 题解:[ABC379D] Home Garden
    [ABC379D]HomeGarden题意:开始有一个空集,有\(Q\)次操作,每次有标识数\(op\):若\(op\)为\(1\):为集合添加一个元素\(0\)。若\(op\)为\(2\):输入\(T\),为集合内所有元素增加\(T\)。若\(op\)为\(3\):输入\(H\),删除集合内不小于\(H\)的元素,并输出删除元素个数。......
  • 题解:AT_abc379_e [ABC379E] E - Sum of All Substrings
    很水的一道题。我们先把题目上各地的数字看成一个序列,然后考虑计算该序列分别会对答案的每一位产生多少贡献。具体的,我们从后往前考虑答案的每一位。通过简单推演可知,设你当前考虑到答案的第\(i\)个数字,那么原序列对这一位的贡献为\(\sum_{j=1}^{n-i+1}a_j\timesj\)。这个......
  • 题解:AT_abc379_d [ABC379D] Home Garden
    难度严格小于C题。你考虑每盆花被种植的时间一定单调不降,这启示我们去用二分。具体的,我们用一个数组\(a\)表示当前所有的花的种植时间,并记录一个当前时间\(t\)。对于每个1操作都在数组后面加上个元素\(t\),对于\(2\)操作让\(t\leftarrowt+T\)。对于操作3,能够摘取的......
  • Toyota Programming Contest 2024#11(AtCoder Beginner Contest 379)题解
    总体情况A-Cyclic题意给你一个三位整数\(N\),其中每个数字都是介于\(1\)和\(9\)之间的整数。设\(a\),\(b\),\(c\)分别是\(N\)的百位、十位和个位数。打印一个按此顺序排列\(b\),\(c\),\(a\)所组成的整数,以及一个按此顺序排列\(c\),\(a\),\(b\)所组成......
  • 2024.11.9组队训练题解记录
    Teleportation鲍勃最近访问了一个奇怪的传送系统。该系统包含\(n\)个房间,编号为\(0\)到\(n-1\)。每个房间都安装了一个传送设备。每个传送设备都有一个看起来像钟表表面的仪表板,上面有一个指针,显示数字\(0\)到\(n-1\),按顺时针顺序排列。最初,第\(i\)个房间的传送设备上......