Codeforces Round 887 (Div. 2)补题

Desorting（Problem - A - Codeforces）

题目大意：现有一个数组a[],我们可以执行如下操作：
选择一个下标i
将a[1]-a[i]的数全部加1
将a[i+1]-a[n]的数全部减1
问将a[]变成未排序数组需要操作多少次。

思路：这里很显然，全部加1和全部减1的时候，相同变化不改变相对大小，如果原数组就是非排序数组，那么自一次操作也不用，如果是排序数组，那么后面的一定大于等于前面的，我们只需要找到差值最小的地方，在这里进行操作即可。

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int c=-2e9,flag=0;
		for(int i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			if(x<c) flag=1;
			c=x;
			a[i]=x;
		}
		if(flag) printf("0\n");
		else 
		{ 
			int mi=2e9;
			for(int i=2;i<=n;i++)
			{
				int d=a[i]-a[i-1]+1;
				int tmp=ceil(d*1.0/2);
				mi=min(mi,tmp);
			}
			printf("%d\n",mi);
		}
	}
}

Fibonaccharsis（Problem - B - Codeforces）

题目大意：如果以n作为序列的第k的个数，整个序列的规律类似斐波那契数列，问有多少个这样的序列。

思路：很显然我们只要找到第k-1个数是多少，那么就可以倒着往前把整个序列推出来，但是由于n的范围比较大，肯定不能暴力枚举，那么就需要考虑一下第k-1个数是否满足单调性，如果满足就可以二分查找，一下就快了，如果我们找到一个倒数第二个数不可以，那么再小的话，肯定不可以，所以需要大一点，如果可以的话，就可以往下找。然后就是check函数怎么写，k的值也很大，很是很明显，哪怕是正常的斐波那契数列，到1e18也只需要88位，所以这个k不需要担心。而且题目也要求了，要是非负数构成的序列。怎么讲，实际上没有什么单调性，倒数第二位数没办法确定，但是，直接暴力枚举n是可以实现的，只要check函数在情况不对的时候及时退出就好，虽然t和n都到2e5了，但是并不会拉满，所以不用担心。

#include<bits/stdc++.h>
using namespace std;
int n,k;
int check(int mid)
{
	int cnt=2;
	int a=n,b=mid;
	while(b)
	{
		int t=a-b;
		if(t>b) break;
		a=b;
		b=t;
		cnt++;
	}
	if(cnt>=k) return 1;
	else return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		int ans=0;
		for(int i=n;i>=0;i--)
		{
			if(check(i)) ans++;
		}
		printf("%d\n",ans);
	}
}

Ntarsis' Set（Problem - C - Codeforces）

题目大意：现在有一个数组，其中填了1,2,3,...,10^1000，另有一个长为n的数组a[],我们需要执行k次操作，每次将原数组中第a[i]大的数删掉，问最后原数组中最小的数是多少。

思路：这道题是一道模拟题，我们现在只知道要求的是第k次操作后排在第一个的数，正着推没什么思路，那么我们倒着推看看。来第二组样例，我们已知结果是9，第一次删除的五个数都在9前面，9变成第4大的数，然后前面有两个需要删除，9又变成第2小的数，然后前面有一个数，9变成第1小的数。

那么我们倒着往回推呢，9现在在第一位，[1 3 5 6 7],我们来推上一次9的位置，上次删除删掉了第一小的数，那么9至少在第二位，然后删掉了第三小的数，不会影响9，那么9就在第二位。

在往前推，9现在在第二位，上次删除了1，在9前面，所以9往后推一位，9在第3位，删除了3，所以9还得往后推1位，9在第4位，删除了5，那么就不影响了。

再往前推，9在第4位，上次删除了1，3，所以9往后推两位，9在第6位，删除了第5位，所以再往前推9在第7位，删除了6，再往前推，9在第8位，删除了7，再推，9在第9位。

如上我们倒推了3次删除，就找到了结果。

我们可以这样通过倒推找出答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010];
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n,k;
		scanf("%lld%lld",&n,&k);
		for(int i=0;i<n;i++) scanf("%lld",&a[i]);
		int x=1,j=0;
		while(k--)
		{
			while(j<n&&x+j>=a[j]) j++;
			x += j;//往后推了下次就不用从头开始找了，直接从j开始找。
		}
		printf("%lld\n",x);
	}
}

ps:这种题但从正向思考会比较麻烦，那么我们不妨转换思路从结果模拟，然后看看是否能正向模拟出这个过程。总体来说就是正向没思路就倒着看。

Imbalanced Arrays(Problem - D - Codeforces)

题目大意：现在需要求出一个数组b[],对于b[]有如下限定：
-n<bi<n;
不存在一对(i,j)使得bi+bj=0
同时我们已知一个数组a[i]表示有多少个j使得b[j]+b[i]>0.
问b[]数组是否存在，如果存在输出b[]，如果不存在输出NO

思路：这题乍一看没什么思路，那么我们就讨论一些比较特殊的情况来找结果。

n=4

4 3 2 1

这里出现了4，那么就是说这一位上的数加上所有的数都大于0的，那么这一位就是4

然后来看下一位3，很显然，这里有一个大于0是加上前一个数得到的，那么这一位和自己以及后面的数加起来应该只有2个大于0的数，这两个数出自哪里实在不好确定，那么我们换个角度去看1，对于1来说，很显然它仅仅与第一个数的和是正的，那么我们就将它赋为-3，

然后再来看，对于3来说，这时候就能确定了，显然它剩余的这两个一个是与自己，一个是与2，所以它的绝对值要小于最后一个数，那么就可以赋成2

然后再来看2，很显然这里的2是和前面两个数，那么它与自己的和是负的，那么显然可以直接赋成-1.

至此这个样例就都讨论完了。

我们从中来找规律，显然一个正的数要是能被确定，那么就是它与哪些数的和为正能够准确的确定下来。如果等于n，那么很好说就是与所有的数的和都为正，直接赋成n即可。那么后面所有的a[i]都应该减1，因为这已经确定了一个，但是我们不是直接减，我们用一个 变量记录下来。对于3，我们首先确定了它跟4能确定下来一个正和，然后得出它跟最后一个数的结果一定不是正的，所以才定下来，那么3确定时的条件就是，当前还有now个数没确定，然后此处的a[i]-已经确定的正和==now。

然后我们再看如果给一个数赋负值的条件是什么，显然就是它减去已经确定的正和之后再没有任何正和了，那么此处直接赋一个负值。

按照上述的讨论，我们就可以将所有的数都确定下来。

但是我们要注意到一个特殊的情况，当前有一个被赋成正数和一个被赋成负数的数同时存在的话，那么显然是不成立的。

然后如果此时既不能确定一个可以被赋成正值的数，也不能确定一个能被赋成负值的数，那么显然也是不成立的。

至此所有的情况就都讨论好了。

哦还有，很显然如果按照上述过程来赋值，我们的数组显然是有序的，而且为了同时对正值和负值进行判断，我们还需要用到双指针。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int a,b,idx;
}e[200010];
int ans[200010];
bool cmp(node x,node y)
{
	return x.a>y.a;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&e[i].a),e[i].idx=i;
		sort(e+1,e+1+n,cmp);
		int l=1,r=n;//前大后小
		int now=n;//还有多少个没确定
		int add=0;//已经确定了多少个为正值的地方
		int flag=1;
		for(int i=n;i>=1;i--)
		{
			if(e[l].a+add==now&&e[r].a+add==0)
			{
				flag=0;
				break;
			}
			else if(e[l].a+add==now)
			{
				e[l].b=i;
				add--;
				now--;
				l++;
			}
			else if(e[r].a+add==0)
			{
				e[r].b=-i;
				now--;
				r--;
			}
			else
			{
				flag=0;
				break;
			}
		}
		if(flag)
		{
			printf("YES\n");
			for(int i=1;i<=n;i++) ans[e[i].idx]=e[i].b;
			for(int i=1;i<=n;i++) printf("%d ",ans[i]);
		}
		else printf("NO");
		printf("\n");
	}
}

ps:这道题的核心就在于在什么情况下一个地方的值才可以确定下来，显然就是当它和哪些位置的和为正可以被确定下来，然后此处的值才能被确定。