noip模拟测试45

这次考试策略出现了问题,首先看一遍题面,先打了个T4的暴力,觉得T2可做,于是就先打T2,但是我想错了,认为蛇只能转一个弯,当时觉得这不就一个分情况讨论吗?于是就大力分情况讨论,结果三个小时全磕在T2上了,最后也没打完,考完试后我想继续打,但是讲题人直接上黑板画了一个蛇走S形的图,当时我就自闭了,原来我想错了。。。。。再看那些就打了个dfs就能65分的人,而我就拿了10分。。。。还有,因为之前考试我只看pdf,但是这次考试T3换题了,但是我在考试快结束的时候才看见,连暴力分也没拿。
总结一下:1.考试时不要花大量时间死磕一道题,最起码要拿到所有题的暴力分
2.不能只看pdf,也要看oj,可能会换题

T1 打表

\(ans=\dfrac{\sum\limits_{i=1}^{n}a[i]-a[ans]}{2}\)
证明:如果只剩下一位没填,那么剩下一位是等可能的0,1,那么考虑多位,两边等概率选择,一个让答案尽可能大,一个为了不让他大而选同一位相反数字。所以最终每个数是等概率的。
代码如下:

AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int mo=1e9+7;
const int N=(1<<19);
int k,ans;
int a[N];
ii read()
{
	int x=0;
	char ch=getchar();
	bool f=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
ii ksm(int d,int z)
{
	int out=1;
	while(z)
	{
		if(z&1) out=out*d%mo;
		z>>=1,d=d*d%mo;
	}
	return out;
}
signed main()
{	
	int out=0,inv;
	k=read();
	ans=read();
	int n=(1<<k)-1;
	for(re i=0;i<=n;i++)
		a[i]=read();
	for(re i=0;i<=n;i++)
		out=(out%mo+abs(a[i]-a[ans])%mo)%mo;
	inv=ksm(2,k);
	out=out%mo*(ksm(inv,mo-2)%mo)%mo;
	printf("%lld\n",out%mo);
	return 0;
}

T2 虫它

咕了

T3 购物

思路:,假设我们已经对 a 数组排好序,用 \(sum_i\) 表示前 i 位 a 的
前缀和,那么当 \(a_i /2\) 大于 \(sum_{i-1}\) ,那么说明在\([sum_i-1 ,a_i /2]\)的地方产生了一个缺口,既然我们已经排好序,那么这个缺口是不可弥补的,所以这一段区间里的数是不会造成贡献的,接着我们考虑下一个端点是不是\(sum_i\),既然\(sum_{i-1}< a_i/2\),那么\(\dfrac{sum_{i-1}+a_i}{2}<a_i\),所以这一段区间是合法的,那么我们只需要记录不合法的个数,最后用总数减去不合法的即可。
代码如下:

AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=1e5+10;
int n,sum,he,no;
int a[N];
ii read()
{
	int x=0;
	char ch=getchar();
	bool f=1;
	while(!isdigit(ch))
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
int ql(int x)
{
   if(x&1) return (x+1)>>1;
   return x>>1;
}
signed main()
{	
	n=read();
	for(re i=1;i<=n;i++)
	{
		a[i]=read();
		he+=a[i];	
	}
	sort(a+1,a+n+1);
	for(re i=1;i<=n;i++)
	{
		if(ql(a[i])>sum)
			no+=ql(a[i])-sum-1;
		sum+=a[i];
	}
	printf("%lld\n",he-no);
	return 0;
}

T4 ants

回滚莫队模板题,当然我当时并不会莫队......
这个也没什么可写的,等我找时间吧。。
代码如下:

AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=1e6+10;
int n,m,maxx;
int l[N],r[N],s[N],ans[N];
struct CUN
{
	int L,R,id,p;
	friend bool operator < (CUN a,CUN b)
	{
		return a.p==b.p?a.R<b.R:a.p<b.p;
	}
}cun[N];
struct node
{
	int p,p_left,p_right;
	int val_left,val_right;
}sta[N];
ii read()
{
	int x=0;
	char ch=getchar();
	bool f=1;
	while(!isdigit(ch))
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
signed main()
{	
	n=read(),m=read();
	int nl,nr;
	int base=sqrt(n);
	for(re i=1;i<=n;i++)
		s[i]=read();
	for(re i=1;i<=m;i++)
	{
		cun[i].L=read();
		cun[i].R=read();
		cun[i].id=i;
		cun[i].p=cun[i].L/base+1;
	}
	sort(cun+1,cun+m+1);
	for(re i=1;i<=m;i++)
	{
		if(cun[i].p!=cun[i-1].p)
		{
			maxx=0;
			for(re j=1;j<=n;j++)
				l[j]=r[j]=0;
			nr=cun[i].p*base;
		}
		while(nr<cun[i].R)
		{
			++nr;
			l[s[nr]]=l[s[nr]-1]+1;
			r[s[nr]]=r[s[nr]+1]+1;
			int tmp=r[s[nr]]+l[s[nr]]-1;
			maxx=max(maxx,tmp);
			l[s[nr]+r[s[nr]]-1]=tmp;
			r[s[nr]-l[s[nr]]+1]=tmp;
		}
		int top=0,rec=maxx;
		for(re j=cun[i].L;j<=min(cun[i].R,cun[i].p*base);j++)
		{
			#define i j
			l[s[i]]=l[s[i]-1]+1;
			r[s[i]]=r[s[i]+1]+1;
			int tmp=l[s[i]]+r[s[i]]-1;
			rec=max(rec,tmp);
			sta[++top]=(node){s[i],s[i]-l[s[i]]+1,s[i]+r[s[i]]-1,r[s[i]-l[s[i]]+1],l[s[i]+r[s[i]]-1]};
			r[s[i]-l[s[i]]+1]=tmp;
			l[s[i]+r[s[i]]-1]=tmp;
			#undef i
		}
		ans[cun[i].id]=rec;
		while(top)
		{
			r[sta[top].p_left]=sta[top].val_left;
			l[sta[top].p_right]=sta[top].val_right;
			top--;
		}
		for(re j=cun[i].L;j<=min(cun[i].R,cun[i].p*base);j++)
			r[s[j]]=l[s[j]]=0;
	}
	for(re i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

上一篇:45.qt quick-qml虚拟软键盘详解(一)


下一篇:操作系统实战45讲 - 第十讲 【笔记】