广州二中NOI2018模拟赛（三十六）

返回首页 返回模拟赛列表

A.染色游戏

19分是很好搞的，爆搜一下就出来了

搜的时候传一个参，表示前一个选择的a是多少，然后接下来的数分一个不选的支，如果它不小于前一个选择的a就再分一个选的支，然后乱搞搞就好了

复杂度O(2^n)

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
LL a[50],n,ans=-1e9;

void dfs(int p,int pre,LL now,int ps)
{
	if(p>n){ans=max(ans,now-(LL)ps*(ps+1)/2);return;}
	dfs(p+1,pre,now,ps+1);
	if(a[p]>=pre) dfs(p+1,a[p],now+a[p]-(LL)ps*(ps+1)/2,0);
}

int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",a+i);
	dfs(1,-1e9,0,0);
	printf("%lld\n",ans);
	return 0;
}

41分也是很好搞的

设dp[i]表示选择a[i]能达到的最大值，那转移就是：

dp[i]=max{dp[j]+a[i]-(i-j-1)*(i-j)/2}，转移前提是a[j]≤a[i]

O(n²)大力枚举即可

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL INF=1ll<<60;
LL n,a[5010];
LL f[5010];

int main()
{
	scanf("%lld",&n);
	for(LL i=1;i<=n;i++) scanf("%lld",a+i);
	a[0]=-INF;
	for(LL i=1;i<=n+1;i++) f[i]=-INF;
	for(LL i=1;i<=n;i++)
		for(LL j=0;j<i;j++)
			if(a[i]>=a[j])
				f[i]=max(f[i],f[j]+a[i]-(i-j-1)*(i-j)/2);
	LL ans=-INF-INF;
	for(LL i=0;i<=n;i++)
		ans=max(ans,f[i]-(n-i)*(n-i+1)/2);
	printf("%lld\n",ans);
	return 0;
}

并不知道子任务3有什么用，直接来考虑正解吧

假设没有ai≤aj的限制？

那么将上面那个dp方程稍作变换，得到：

发现式子中很多东西都是定值，我们把定值去掉，问题就变成了最大化下面这个柿子的值：

我们把j看做x，把dp[j]-j(j+1)/2看做y，柿子就变成了

调整一下位置，变成

于是问题变成了：求一条直线与y轴截距的最大值，这条直线与y=-ix平行，且经过某个点(x0,y0)

容易看出这样的点(x0,y0)一定在上凸壳上，于是我们可以维护一个上凸壳，然后就可以搞了

那么加上ai≤aj的限制？

显然这里存在一个偏序关系，j号点对i号点的答案产生影响，当且仅当j≤i且aj≤ai

用CDQ分治来维护这个偏序关系即可（听说用数据结构维护会被卡常？）

由于答案具有单调性，所以可以用单调队列来维护，这样每段分治做询问就是线性的了

分治过程中用归并排序来维护偏序，用sort会多一个log导致TLE

最后的答案就是max{dp[i]-(n-i)*(n-i+1)/2}

时间复杂度O(n log n)

#include<bits/stdc++.h>
using namespace std;

const int S=1<<16;
char buf[S],*H,*T;
inline char Get()
{
	if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
	if(H==T) return -1;return *H++;
}
inline int read()
{
	int x=0,fg=1;char c=Get();
	while(!isdigit(c)&&c!='-') c=Get();
	if(c=='-') fg=-1,c=Get();
	while(isdigit(c)) x=x*10+c-'0',c=Get();
	return fg*x;
}

typedef long long LL;
const int N=1000010;
const LL INF=1ll<<60;
LL n,f[N],v[N];
struct Point{LL x,y;} a[N],tmp[N],q[N];
int que[N],head,tail;

bool operator < (const Point &a,const Point &b){return a.x<b.x||a.x==b.x&&a.y<=b.y;}

double slope(int p1,int p2)
{
	double x1=p1,x2=p2,y1=f[p1]-x1*(x1+1)/2,y2=f[p2]-x2*(x2+1)/2;
	return (y2-y1)/(x2-x1);
}

void gao(int L,int R)
{
	if(L==R) return;
	int M=(L+R)/2;
	int p1=L,p2=M+1;
	for(int i=L;i<=R;i++)
		if(q[i]<a[M]) tmp[p1++]=q[i];
		else tmp[p2++]=q[i];
	for(int i=L;i<=R;i++) q[i]=tmp[i];
	gao(L,M);
	p1=L;p2=M+1;head=1;tail=0;
	while(p2<=R)
		if(p1<=M&&q[p1].y<q[p2].y)
		{
			while(head<tail&&slope(que[tail-1],que[tail])<slope(que[tail-1],q[p1].y)) tail--;
			que[++tail]=q[p1].y;p1++;
		}
		else if(p2<=R)
		{
			while(head<tail&&slope(que[head],que[head+1])>-q[p2].y) head++;
			if(head<=tail)
			{
				LL i=q[p2].y,j=que[head];
				f[q[p2].y]=max(f[i],f[j]+v[i]-(i-j-1)*(i-j)/2);
			}
			p2++;
		}
	gao(M+1,R);
	p1=L;p2=M+1;int now=L;
	while(p1<=M&&p2<=R)
		if(p1<=M&&q[p1].y<q[p2].y) tmp[now++]=q[p1++];
		else tmp[now++]=q[p2++];
	while(p1<=M) tmp[now++]=q[p1++];
	while(p2<=R) tmp[now++]=q[p2++];
	for(int i=L;i<=R;i++) q[i]=tmp[i];
}

int main()
{
	n=read();
	for(LL i=1;i<=n;i++)
		v[i]=a[i].x=read(),a[i].y=i,q[i]=a[i];
	for(LL i=1;i<=n;i++) f[i]=v[i]-i*(i-1)/2;
	sort(a+1,a+n+1);
	gao(1,n);
	LL ans=-INF;
	for(LL i=0;i<=n;i++)
		ans=max(ans,f[i]-(n-i)*(n-i+1)/2);
	printf("%lld\n",ans);
	return 0;
}

B.异或II

20分还是很好拿的，只要每次操作先算一遍前缀异或和，每次操作就是O(n)的了，总复杂度O(Tn)

#include<bits/stdc++.h>
using namespace std;

const int N=2010;
int A[N],B[N];

int main()
{
	int n,k,t;
	scanf("%d%d%d",&n,&k,&t);
	for(int i=0;i<n;i++) scanf("%d",A+i);
	while(t--)
	{
		for(int i=n;i<2*n;i++) A[i]=A[i-n];
		for(int i=1;i<2*n;i++) A[i]^=A[i-1];
		B[0]=A[k-1];
		for(int i=1;i<n;i++)
			B[i]=A[i+k-1]^A[i-1];
		for(int i=0;i<n;i++) A[i]=B[i];
	}
	for(int i=0;i<n;i++) printf("%d ",A[i]);
	return 0;
}

然后打表，发现第2的次方次操作之后的序列很有规律，然后倍增搞它一下就出来了

甚至连什么FFT、MTT之类的狗屎东西都不用写。代码也很短，我的代码除掉IO优化就40行

复杂度O(n log n)

#include<bits/stdc++.h>
using namespace std;

namespace IO
{
	const int S=1<<16;
	//Input Correlation
	char buf[S],*H,*T;
	inline char Get()
	{
		if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
		if(H==T) return -1;return *H++;
	}
	template<class I>
	inline I read()
	{
		I x=0;char c=Get();
		while(!isdigit(c)) c=Get();
		while(isdigit(c)) x=x*10+c-'0',c=Get();
		return x;
	}
	//Output Correlation
	char obuf[S],*oS=obuf,*oT=oS+S-1,c,qu[55];int qr;
	inline void flush()
	{
		fwrite(obuf,1,oS-obuf,stdout);
		oS=obuf;
	}
	inline void putc(char x)
	{
		*oS++ =x;
		if(oS==oT) flush();
	}
	inline void print(int &x)
	{
		if(!x) putc('0');
		while(x) qu[++ qr]=x%10+'0',x /= 10;
		while(qr) putc(qu[qr--]);
		putc(' ');
	}
}

typedef long long LL;
using namespace IO;
const int N=500010;
int n,k,a[N];LL t;
bool vis[N];
int f[N],g[N];

void gao(int x,int d)
{
	int cnt=0;
	while(!vis[x])
	{
		f[++cnt]=x;vis[x]=1;
		g[cnt]=g[cnt-1]^a[x];
		x=(x+d>=n)?(x+d-n):(x+d);
	}
	int m1=k/cnt,m2=k%cnt;
	for(int i=1;i<=cnt;i++)
	{
		a[f[i]]=(m1&1)?g[cnt]:0;
		a[f[i]]^=(m2<=cnt-i+1)?(g[i+m2-1]^g[i-1]):(g[cnt]^g[i-1]^g[i+m2-cnt-1]);
	}
}

int main()
{
	n=read<int>();k=read<int>();t=read<LL>();
	for(int i=0;i<n;i++) a[i]=read<int>();
	for(LL i=1,d=1;i<=t;i<<=1,d=(d<<1)%n)
	{
		if(!(t&i)) continue;
		memset(vis,0,sizeof(vis));
		for(int j=0;j<n;j++)
			if(!vis[j]) gao(j,d);
	}
	for(int i=0;i<n;i++) print(a[i]);
	flush();
	return 0;
}

C.商店街派对

这题怎么做啊……不会啊

先留一个坑吧，下面是我抄的代码……

#include<bits/stdc++.h>
#define pLL pair<LL,LL>
#define pb push_back
using namespace std;

typedef long long LL;
LL read()
{
	LL x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}
const LL N=200010;
LL n,m,mx=0;
vector<pLL> sec[N];
LL sum,tot=0;
LL v[N],f[N],cnt[N];
LL p[N],fa[N];

inline LL find(LL x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void gao(LL x,bool fg)
{
	LL y;
	while(find(x)&&v[x]>0)
	{
		y=find(x)-1;
		v[x]+=v[y];
		fa[fa[x]]=fg?fa[y]:y;
		p[find(x)]=x;
	}
}

void Add(LL x,LL k)
{
	sum-=k;
	if(x==p[find(x)]) x++;
	x=p[find(x)];
	v[x]+=k;gao(x,0);
}

pLL gao(LL x)
{
	sum=0;
	for(LL i=0;i<=mx;i++)
		fa[i]=p[i]=i,cnt[i]=f[i]=v[i]=0;
	for(LL i=1;i<=mx;i++)
	{
		for(LL j=0;j<sec[i].size();j++)
			Add(sec[i][j].first-1,sec[i][j].second);
		f[i]=sum+v[p[0]]-x;
		cnt[i]=cnt[p[0]]+1;
		v[i]=f[i]-f[i-1];gao(i,1);
	}
	return pLL(cnt[p[0]],sum+v[p[0]]+tot);
}

int main()
{
	LL l,r,c;
	n=read(),m=read();
	for(LL i=1;i<=n;i++)
	{
		l=read();r=read();c=read();
		sec[r].pb(pLL(l,c));
		tot+=c;mx=max(mx,r);
	}
	l=0;r=tot+1;LL mid;
	while(l<r)
	{
		mid=(l+r)/2;
		if(gao(mid).first<m) r=mid;
		else l=mid+1;
	}
	printf("%lld\n",gao(l).second+l*m);
	return 0;
}