CF R 632 div2 1333D Challenges in school №41

LINK：Challenges in school №41

考试的时候读错题了+代码UB了所以wa到自闭然后放弃治疗。

赛后发现UB的原因是 scanf读int类型的时候宏定义里面是lld的类型导致UB.

读错题的原因是太急了而且题目描述不是很清晰导致按照自己含糊不清的想法+样例的佐证成为了另外一个题目。

这道题是要求我们进行构造。

对于一个要求我们每轮都要进行一次扭头且刚好在k轮都进行完。

(这类似于冒泡排序但是我们不考虑冒泡排序的性质也是可以写的。

考虑会进行多少次这样的操作显然可以统计出来也就是说我们最多能坚持的轮数是逆序对的个数.

因为左箭头一直在向左传递右箭头同理对于左箭头在左右箭头在右的情况那么他们一定会进行相遇。->逆序对个数.

考虑最少坚持多少轮这个我们每轮都进行一次模拟也可以求出来这个模拟的过程不能每次便利序列考虑由上一次的位置进行拓展可以发现最多拓展n^2个所以复杂度为n^2.

如果k在最大值和最小值之间那么显然可以构造出来。

一种比较简单的构造方法：先以轮为单位做然后发现后面的不够的时候再也个位单位进行拓展即可。

update：看了其他人的题解发现唯一的不同是在求最小的时候他们都暴力拓展了并没有由上次的得到现在的。

这样做的复杂度为最少做几轮*n。通过不断打表可以发现最少n轮但是我无法证明这个结论所以为了求稳还是考虑我的那种方法稳定n^2.

const int MAXN=3010,maxn=3000010;

int n,k,ans;

vector<int>g[maxn];

char a[MAXN];

int b[MAXN],s1[MAXN],c[MAXN],top1,s2[MAXN],top2,vis[MAXN];

int main()

{

	freopen("1.in","r",stdin);

	gt(n);gt(k);gc(a);b[n+1]=-1;b[0]=-1;

	for(int i=1;i<=n;++i)if(a[i]=='R')b[i]=1;

	rep(1,n,i)if(b[i]==1&&!b[i+1])s1[++top1]=i,s1[++top1]=i+1,vis[i]=vis[i+1]=1;

	int w1=0,w2=0;

	while(top1)

	{

		top2=0;++w1;

		if(w1>k){puts("-1");return 0;}

		rep(1,top1,i)

		{

			b[s1[i]]^=1;vis[s1[i]]=0;

			if(!b[s1[i]])g[w1].pb(s1[i]),++w2;

		}

		rep(1,top1,i)

		{

			if(b[s1[i]-1]==1&&!b[s1[i]]&&!vis[s1[i]])s2[++top2]=s1[i]-1,s2[++top2]=s1[i],vis[s1[i]-1]=1,vis[s1[i]]=1;

			if(b[s1[i]]==1&&!b[s1[i]+1]&&!vis[s1[i]])s2[++top2]=s1[i],s2[++top2]=s1[i]+1,vis[s1[i]+1]=1,vis[s1[i]]=1;

		}

		top1=0;

		rep(1,top2,j)s1[++top1]=s2[j];

	}

	if(w2<k){puts("-1");return 0;}

	rep(1,w1,i)

	{

		int sz=g[i].size();

		if(w2-sz>=k-1)

		{

			printf("%d",sz);--k;w2-=sz;

			rep(0,sz-1,j)printf(" %d",g[i][j]);

			puts("");

		}

		else

		{

			--k;w2-=sz;

			int res=k-w2;

			printf("%d",sz-res);

			for(int j=0;j<=sz-res-1;++j)printf(" %d",g[i][j]);

			puts("");

			for(int j=sz-res;j<sz;++j)printf("1 %d",g[i][j]),puts("");

			++i;

			while(i<=w1)

			{

				for(int j=0;j<g[i].size();++j)printf("1 %d",g[i][j]),puts("");

				++i;

			}

		}

	}

	return 0;

}

巴特西

CF R 632 div2 1333D Challenges in school №41

最新文章

热门文章