191111-模拟测试16

T1 星际旅行

题目描述

解析

傻逼题，upper_bound即可

题解

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,s,a[200009],ans;
signed main(){
	freopen("dwar.in","r",stdin);
	freopen("dwar.out","w",stdout);
	scanf("%lld%lld",&n,&s);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	a[n+1]=1000009;
	sort(a+1,a+n+2);
	for(int i=1;i<=n;i++){
		if(a[i]>(s/2)) break;
		int pos1=s-a[i];
		ans+=((upper_bound(a+1,a+n+1,pos1)-a-1)-i);
	}
	printf("%lldn",ans);
	return 0;
}

T2 temple

题目描述

解析

打表找规律，可以发现一个$O(n^2)$的dp，$f_{i,j}$表示从i个蛋糕中选取j个的合法方案数，那么于是就有：$\{\begin{array}{l}{f}_{i,j}=f_{i-1,j}(i，j奇偶性不相同)\\ f_{i,j}=f_{i-1,j}+f_{i,j-1}(i，j奇偶性相同)\end{array}$,然后就可以得到70分，

那么如何得到100分呢，首先将由dp得到的解题思路，当我们把$f_{i,j}$的值打表出来过后，就会发现缩一半过后就是杨辉三角形，然后直接用杨辉三角形的通项公式直接计算即可,答案即为$C_{(n+m)/2}^m$

第二种方法较为巧妙，设选出来的数从小到大为a1,a2,a3…,am，考虑令???????? = ???????? + ????，我们会发现，b中全是偶数并且两两互不相同，一个b唯一对应一个a，那么问题等价于从1到n+m中选择m个偶数的方案数，答案即为$C_{(n+m)/2}^m$

T3 ran

题目描述

解析

1，预处理出巡视每个区间的时间，然后$O(1)$查询，可以得到30分

2，正解做法
1.[l,r]包含[x,y]
2.[l,r]和[x,y]真相交
3.[x,y]包含[l,r]
4.[x,y]和[l,r]没有交集

第4类对答案没有贡献不考虑

第1类显然[x,y]的所有子区间都会影响[l,r]

第2类其实分成左相交和右相交两类，不过没有本质区别

贡献可以用总区间数-和[l,r]不相交的区间数

第3类稍微麻烦一点，贡献是总区间数-和[l,r]不相交的区间数-完

全包含[l,r]父亲的区间数

第1,2类区间总共只有$O(logn)$个，可以暴力计算

考虑第3类区间，在线段树上是$O(logn)$个子树，考虑预处理

写出贡献式子可以发现对于某个区间[l,r]，若[x,y]包含[l,r]，对答案的贡献可以写成$A{x}^2+Bxy+C{y}^2+Dx+Ey+F$的形式

直接对于每个点预处理出所有的系数然后求子树和

复杂度$O(nlogn)$

题解

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

int read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

void write(ll x) {
	char ch[20];int tot=0;
	for(;x;x/=10) ch[++tot]=x%10+'0';
	fd(i,tot,1) putchar(ch[i]);
	puts("");
}

const int N=1.2e6+5;

int n,q,sz[N],opt;
ll C[N],L[N],R[N],LR[N],sum;

void build(int v,int l,int r) {
	sz[v]=1;
	L[v]=(2*l+1);C[v]-=(ll)l*(l+1);
	R[v]=(2*r-1);C[v]-=(ll)r*(r-1);
	if (l==r) return;
	C[v]+=(ll)4*(l+1)*(r-1);LR[v]=4;
	L[v]-=4*(r-1);R[v]-=4*(l+1);
	int mid=l+r>>1;
	build(v<<1,l,mid);build(v<<1|1,mid+1,r);
	sz[v]+=sz[v<<1]+sz[v<<1|1];
	C[v]+=C[v<<1]+C[v<<1|1];LR[v]+=LR[v<<1]+LR[v<<1|1];
	L[v]+=L[v<<1]+L[v<<1|1];R[v]+=R[v<<1]+R[v<<1|1];
}

ll query(int v,int l,int r,int x,int y) {
	if (x<=l&&r<=y) {
		ll tmp=C[v];
		tmp+=(sum-(ll)x*x-(ll)y*y)*sz[v];
		tmp+=L[v]*x;tmp+=R[v]*y;tmp+=LR[v]*x*y;
		return tmp;
	}
	ll tmp=sum;
	if (x<=l) tmp-=(ll)(l-x)*(l-x+1);
	if (r<=y) tmp-=(ll)(y-r)*(y-r+1);
	int mid=l+r>>1;
	if (x<=mid) tmp+=query(v<<1,l,mid,x,y);
	if (y>mid) tmp+=query(v<<1|1,mid+1,r,x,y);
	return tmp;
}

int main() {
	freopen("ran.in","r",stdin);
	freopen("ran.out","w",stdout);
	n=read();q=read();opt=read();
	build(1,1,n);
	ll ans=0;
	for(;q;q--) {
		ll l=((ans*opt)^read())%n+1,r=((ans*opt)^read())%n+1;
		if (l>r) swap(l,r);
		sum=(ll)(r-l+1)*(r-l+2);
		write(ans=query(1,1,n,l,r)/2);
	}
	return 0;
}

T4 border

题目描述

解析

传送门

题解

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
#define ls now<<1
#define rs now<<1|1
inline int read()
{
	int re=0,f=1;char ch=getchar();
	while(!isdigit(ch))
		f=(ch=='-')?-1:f,ch=getchar();
	while(isdigit(ch))
		re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
	return re*f;
}
const int ff=1e6+1;
const int mod=1e9+7;
const int inf=1e17+1;
int n,q,a[ff],l[ff],r[ff];
int me[ff];
struct node{
	int l,r,id;
}t[ff];
int pre[ff],suf[ff],xx[ff],sum[ff];
bool cmp(node x,node y) {return x.r==y.r?x.id<y.id:x.r<y.r;}
int find(int x) {return (xx[x]==x)?x:xx[x]=find(xx[x]);}
void getme()
{
	int di=1;
	for(int i=0;i<=500000;++i)
		me[i]=di,di=(di*2)%mod;
}
int powe[ff],ks[ff],hd[ff],ans[ff];
void merge(int x,int y)
{
	xx[find(x)]=find(y);
	pre[y]=pre[x];
	int delta=x-pre[x];
	if(delta>30&&sum[y]>0)
	{sum[y]=mod;return;}
	sum[y]=(sum[x]+(sum[y]<<delta)>=mod)?mod:sum[x]+(sum[y]<<delta);
}
int getva(int l,int r) {return ((suf[l]%mod-suf[r+1]*me[r-l+1]%mod)%mod+mod)%mod;}
void init()
{
	getme();
	n=read();q=read();
	for(reg int i=1;i<=n;++i)
		a[i]=read(),sum[i]=a[i];
	for(reg int i=1;i<=q;++i)
		t[i].l=read(),t[i].r=read(),t[i].id=i;
	sort(t+1,t+1+q,cmp);
	for(reg int i=1;i<=n;++i)
		xx[i]=i,pre[i]=i-1;
	for(reg int i=n;i;--i)
		suf[i]=(((suf[i+1]*2)+a[i])%mod+mod)%mod;
	int head=1;
	for(reg int i=1;i<=n;++i)
	{
		while(pre[i]&&sum[i]>=0)
			merge(pre[i],i);
		ks[i]=(ks[pre[i]]+getva(pre[i]+1,i)*2)%mod;
		while(t[head].r==i&&head<=q)
		{
			int lc=find(t[head].l);
			ans[t[head].id]=(ks[i]-ks[lc]+getva(t[head].l,lc)+mod)%mod;
			head++;
		}
	 }
	for(reg int i=1;i<=q;++i)
		printf("%lldn",ans[i]);
}
signed main()
{//freopen("border.in","r",stdin);freopen("border.out","w",stdout);
init();}

最后

以上就是洁净钢笔为你收集整理的191111-模拟测试16191111-模拟测试16的全部内容，希望文章能够帮你解决191111-模拟测试16191111-模拟测试16所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。