冲刺省选2月8日第十二场

T1

\(f_i\) 表示以 \(i\) 结尾的最大答案

发现只考虑当 \(a_i\) 是最大值时的转移也是正确的

\(f_i=\max_{j=1}^{i-1} \{ (b_j-b_i)^2+c+f_j \}\)

因为若中间夹着个比 \(a_i,a_j\) 值都大的值的话肯定不会优

然后李超树维护就行

T2

首先,如果知道了序列的最大值 \(mx\),设询问的集合为 \(S\),并且询问 \(S\bigcup {mx}\),就可以知道集合所有元素与最大值的差

先考虑找到最大值,首先全体询问得到极差 \(k\),然后二分前缀得到 \(k\) 第一次出现的位置,即为最大值或最小值,设为 \(x\)

然后设 \(S_i\) 表示第 \(i\) 个二进制位为 \(1\) 的数的集合,询问 \(S_i\)\(S\bigcup {x}\) 得到与 \(x\) 的差

然后就能得到 \(a_i\)\(x\) 的差

\(qry1\) 询问差最大的那个数并与 \(x\) 比较,就能确定 \(x\) 是最大还是最小

代码

T1

#include<cstdio>
#include<iostream>
using namespace std;
#define il inline
#define int long long
const int N=1e6+11;
const int inf=1e18;
struct seg_{
	int k,val;seg_(){}
	seg_(int k_,int val_){k=k_,val=val_;}
};
struct tree{bool jd;seg_ x;}tre[N*4];
int n,c;
int a[N];
il int pd(int x){return x*x;}
il int max_(int x,int y){return x>y?x:y;}
int get_ans(seg_ a,int x){return a.k*x+a.val;}
bool check(seg_ a,seg_ b,int x){return get_ans(a,x)<get_ans(b,x);}
il int read(){
	int s=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void ins(int i,int l,int r,seg_ x){
	int mid=(l+r)>>1;
	if(!tre[i].jd){tre[i].jd=1;tre[i].x=x;return;}
	if(check(tre[i].x,x,mid))swap(tre[i].x,x);
	if(l==r)return;
	if(check(tre[i].x,x,r))ins(i<<1|1,mid+1,r,x);
	if(check(tre[i].x,x,l))ins(i<<1,l,mid,x);
}
int qry(int i,int l,int r,int x){
	if(!tre[i].jd)return -inf;
	if(l==r)return get_ans(tre[i].x,x);
	int mid=(l+r)>>1;
	int ans=tre[i].jd?get_ans(tre[i].x,x):-inf;
	if(x<=mid) return max_(ans,qry(i<<1,l,mid,x));
	else return max_(ans,qry(i<<1|1,mid+1,r,x));
}
signed main(){
	freopen("array.in","r",stdin),freopen("array.out","w",stdout);
	n=read();c=read();
	for(int i=1;i<=n;++i)a[i]=read();
	ins(1,1,1e6,seg_(-2*a[1],pd(a[1])));
	for(int x,i=2;i<=n;++i){
		x=qry(1,1,1e6,a[i])+pd(a[i])+c;
		if(i==n)cout<<x<<endl;
		ins(1,1,1e6,seg_(-2*a[i],x+pd(a[i])));
	}
}

T2

#include "difference.h"
#include<set>
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define il inline
const int N=250+11;
const int M=N*N;
set<int> mrg(set<int> a,set<int> b){
	if(!a.size())return b;
	set<int> x;x.clear();
	for(set<int>::iterator it=a.begin();it!=a.end();++it){
		if(b.find(*it)!=b.end()){
			x.insert(*it);
			b.erase(*it);
		}
	}return x;
}
set<int> pop(set<int> a,set<int> b){
	for(set<int>::iterator it=b.begin();it!=b.end();++it){
		if(a.find(*it)!=a.end())a.erase(*it);
	}return a;
}
void find(int n,int m1,int m2){
	set<int> s[10];
	vector<int> a,b,ans;
	unordered_map<int,int>mp;

	for(int i=0;i<n;++i)a.push_back(i);
	b=qry2(a);sort(b.begin(),b.end());
	int mx_cz=b[b.size()-1];
	int l=1,r=n-1,mid,loc=0;
	while(l<=r){
		mid=(l+r)>>1;a.clear();
		for(int i=0;i<=mid;++i)a.push_back(i);
		b=qry2(a);sort(b.begin(),b.end());
		if(b[b.size()-1]==mx_cz)loc=mid,r=mid-1;
		else l=mid+1;
	}

	for(int i=0;i<8;++i){
		a.clear();
		for(int j=0;j<n;++j){
			if(j==loc)continue;
			if((1<<i)&j)a.push_back(j);
		}b=qry2(a);mp.clear();
		for(int j=0;j<b.size();++j)++mp[b[j]];
		a.push_back(loc);b=qry2(a);
		for(int j=0;j<b.size();++j){
			if(mp[b[j]])--mp[b[j]];
			else s[i].insert(b[j]);
		}
	}//for(int j : s[2])cout<<j<<" fdafd"<<endl;

	int jd=1;int k=0;
	for(int i=0;i<n;++i)ans.push_back(0);
	ans[loc]=qry1(loc);
	for(int x,i=0;i<n;++i){
		s[8].clear();
		if(i==loc)continue;
		for(int j=0;j<8;++j)if((1<<j)&i)s[8]=mrg(s[8],s[j]);
		for(int j=0;j<8;++j)if(!((1<<j)&i))s[8]=pop(s[8],s[j]);
		if(s[8].size())x=*s[8].begin();
		a.clear();a.push_back(i),a.push_back(loc);
		ans[i]=i?x:qry2(a)[0];
		if(ans[i]==mx_cz){
			k=i;ans[i]=qry1(i);
			if(ans[i]>ans[loc])jd=1;
			else jd=-1;
		}
	}
	for(int i=0;i<n;++i){
		if(i==k||i==loc)continue;
		ans[i]=ans[loc]+jd*ans[i];
	}answer(ans);
}

推荐这些技术文章:

冲刺省选2月17日 (互测)

T1 最短路
需要一个数据结构实现快速加一个 2 的幂和比较大小
考虑主席树维护二进制数,每个节点维护答案和第一个为 0 的位置
加 \(2^k\) 就从 k 往后找到第一个为 0 的位置改成 1,中间的位改为 0
比较大小线段树上二分就行了
T2 集合
要求一个集合 S ,满足 \(\prod_{i\in S}i!\) 为完全平方数
删的个数 <=3
若 n 为偶数,\(2^{\frac...

基础算法 791.高精度加法

#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int> &a, vector<int> &b){
if(a.size()<b.size()) return add(b, a);
ve...

最短hamilton路径

#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N=20,M=1<<N;int n;int w[N][N];int f[M][N];int main(){ cin>>n; for(int i=0;i<n;i...

88.合并两个有序数组

1.Go   2.C++ 方法1:借助新的容器 class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { vector<int>ans; for(int i=0;i&l...

求两个整数的和。 【输入】 一行,两个用空格隔开的整数。 【输出】 两个整数的和。 【输入样例】 2 3 【输出样例】 5

#include<iostream>
using namespace std;
int main(){
long long a,b,c;
cin>>a>>b;
c=a+b;
cout<<c<<endl;
return 0;
}

...

基础算法 792.高精度减法

#include<bits/stdc++.h>
using namespace std;
bool cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size())return A.size()>B.size();

for(int i=A.size();i&g...

P4305 [JLOI2011]不重复数字 简单的hash思想

P4305 [JLOI2011]不重复数字/*
简单的hash思想
*/
#include<bits/stdc++.h>
using namespace std;
const int Maxn=1000003;
vector<int> ans;
int has[Maxn+10];
bool pd(int x)
{
int ha=abs(x)%Maxn;
if (h...

Maven 在pom.xml的build中配置resources,来防止我们资源导出失败的问题

解决Maven 在pom.xml的build中配置resources,来防止我们资源导出失败的问题
<build>
<resources>
<resource>
<!-- 设定主资源目录 -->
<directory>src/main/resources</direc...

高精度计算模板 -感谢acwing

高精度加

1 // C = A + B, A >= 0, B >= 0
2 vector<int> add(vector<int> &A, vector<int> &B)
3 {
4 if (A.size() < B.size()) return add(B, A);
5
6 vector<...

解决Mybatis的mappers标签批量注册后无法找到对应xml文件的问题

在工程的pom.xml文件中增加以下内容:<build> <resources> <resource> <directory>${basedir}/src/main/java</directory> <includes> <i...

文章标题:冲刺省选2月8日第十二场
文章链接:https://www.dianjilingqu.com/51045.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>