Codeforces Round 913 (Div. 3)补题

Rook

题目大意：我们给定一个棋盘(如下图)，棋盘上有一个车，问车可以到的位置，任意顺序输出即可。

思路：输出车的行列中非它本身的点即可。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		char s[3];
		scanf("%s",s);
		for(int i=1;i<=8;i++)
		{
			if((s[1]-'0')!=i)
			printf("%c%d\n",s[0],i);
		}
		for(int i=0;i<8;i++)
		{
			if('a'+i!=s[0]) printf("%c%c\n",'a'+i,s[1]);
		}
	}
}

YetnotherrokenKeoard

题目大意：我们需要输入一串字符，但是键盘上"b"按键出问题了，我们按下"b"时会删除最后一个小写字母，按下"B"时，会删除最后一个大写字母，如果待删除的字母不存在那么就不进行任何操作，我们需要输出最后的字串。

思路：这题的核心在于考虑最后哪些结果出现在答案中，因为涉及到大写和小写，而且还要分开删除，那么我们直接用两个容器来装访问到的字母，然后对应进行删除即可。最后输出只用按顺序输出即可，那么这个顺序是怎样的呢？我们记录下它们在原字串中的下标，然后按顺序输出即可（这里可以用下双指针）

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		string s;
		cin>>s;
		vector<pair<char,int>>d,x;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='B')
			{
				if(d.size()) d.pop_back();
				continue;
			}
			if(s[i]=='b')
			{
				if(x.size())x.pop_back();
				continue;
			}
			if('A'<=s[i]&&s[i]<='Z') d.push_back({s[i],i});
			if('a'<=s[i]&&s[i]<='z') x.push_back({s[i],i});
		}
		int i=0,j=0;
		while(i<d.size()&&j<x.size())
		{
			if(d[i].second<x[j].second) cout<<d[i].first,i++;
			else cout<<x[j].first,j++;
		}
		while(i<d.size()) cout<<d[i].first,i++;
		while(j<x.size())cout<<x[j].first,j++;
		cout<<endl;
	}
}

Removal of Unattractive Pairs

题目大意：有一串字符串，我们可以将相邻两个不同的字符删除，问我们删除尽可能多次后，剩下的字符串的长度最短是多少。

思路：我们可以发现，最后就算剩下也只能剩下一种字符，一旦有两种及以上字符剩下，那么必然存在两个相异的字符相邻，那么就必须删除。所以我们只用去统计每种字符出现的个数，并记录个数的最大值，如果最大值小于等于n/2那么一定是可以全部消掉的，否则，最多的那个字母就会剩下，另外，要注意n为奇数，那么最终不管mx是多少，都会剩下一个字符，因为没有能跟它配对的了。

#include<bits/stdc++.h>
using namespace std;
char s[200010];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		scanf("%s",s);
		map<char,int>mp;
		int mx=0;
		for(int i=0;i<n;i++) mp[s[i]]++,mx=max(mp[s[i]],mx);
		if(n%2)
		{
			if(mx>n/2+1) mx -= (n-mx);
			else mx=1;
		}
		else
		{
			if(mx>n/2) mx -= (n-mx);
			else mx=0;
		}
		printf("%d\n",mx);
	}
}

Jumping Through Segments

题目大意：有n个区间，标号分别为1,2,..,n,它们都是x轴上的区间，我们初始在位置0，每次最多移动距离k,现在需要找到一个最小的k，使得第i次移动落在区间i内。

思路：这道题虽然一眼二分，但是check()很容易出差错，因为惯性思维还是考虑移动多少落在哪个点，然后就会去考虑每步怎么移动才是最优的。但是这是没必要的事情，这和另外一个题有点像（Absolute Sorting），不能考虑单点，需要考虑每次移动会落在哪个区间内。那么我们就从这个角度来考虑，首先每次的移动肯定要落在[l[i],r[i]]区间内部，在这个区间之外就没必要移动了，其次，我们假设上一次落在区间[L,R]内，那么能移动到的区间最多只能是[L-x,R+x](假设每次可以移动的最远距离是x)，那么我们实际上这一次移动合法且有效的区间就是两个区间取交集，那么这一次移动的落点区间就找出来了。判否的条件就是这两个区间没有交集，至此问题解决。

#include<bits/stdc++.h>
using namespace std;
int l[200010],r[200010];
int n;
bool check(int x)
{
	int L=0,R=0;
	for(int i=1;i<=n;i++)
	{                            
		L=max(l[i],L-x);
		R=min(r[i],R+x);
		if(L>R) return false;
	}
	return true;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int mx=0;
		for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]),mx=max(mx,r[i]);
		int l=0,r=mx;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(check(mid)) r=mid;
			else l=mid+1;
		}
		printf("%d\n",l);
	}
}

ps:既然本题和Absolute Sorting比较像，那么我们就来顺便复习一下这道题。

题目大意：给定一个数组a[],我们需要对a[]进行排序，但是我们能进行的操作就是选定一个x,然后对于所有的ai,用|ai-x|替换ai，找出最小的x或者报告x不存在输出-1.

思路：这道题首先要明确|ai-x|表示的是距离（上次卡在这个地方，竟然没卡在从区间的角度考虑，还是得卡住才能影响深刻嘞，不过上次比较幸运最后想到了这个，直接把思路顺出来了），然后我们替换表示用距离去代替它们，所以很显然如果如果a[i]<a[i+1]那么选的x肯定要里a[i]更近，然后替换完两者的大小关系不会变，如果a[i]>a[i+1]那么两者的大小关系要改一下，那么就是选的x要离a[i+1]更近。这道题最开始也是想的考虑单点，即在最优策略下x选在哪个点，然后对其他的情况是否成立，但是很显然这个最优策略就很难评，所以后来想到去遍历确定x的合法区间，这个题甚至连二分都不用。因为这个题不需要知道具体x的值（而且这个题用二分还写不了，因为就算我们二分出x的值，判断对于所有的a[i]改变后是否成立，但是如果不成立，x该变大还是变小，我们并没有办法确定），上个题是不需要知道具体的区间落在哪里，但是转移需要x，所以需要二分x的值。但是它们的共同点都是去考虑合法区间而非单点。

Good Triples

题目大意：我们给定一个非负整数n，需要把n拆成3个数a,b,c，要求n=a+b+c,定义digit(n)为n的数位和，同时还要求:digit(n)=digit(a)+digit(b)+digit(c),求这样的三元组有多少个，同时规定[a,b,c]与[b,a,c]是两个三元组。

思路：我们首先来看，要使和和数位和都相等，那么a+b+c得是不进位直接加的，这样才能保证满足条件。那么就是对每一位上的数字进行拆解，那么拆解之后如何拼起来呢？我们可以发现，如果只将目光聚焦在每一位上的时候，那就相当于将当前这个数的这一组拆解放入3个容器，问有多少种放法，然后有多少组拆解，把它们的方法求和，就得到这一位能产生的不同情况，然后我们注意到，总共有若干位，将每一位的放法都求出来然后相乘即可。另外注意到，每一位上的数字都是0-9的，那么我们可以预处理一个数组出来，数值比较少，可以直接手算：

int a[]={1,3,6,10,15,21,28,36,45,55};

那么问题就解决了。讲真这个题实际比D简单，如果D的那个点卡住的话，真不如先写E。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[]={1,3,6,10,15,21,28,36,45,55};
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		long long ans=1;
		if(n==0) ans=1ll;
		else
		{
			while(n)
			{
				int d=n%10;
				ans *= (long long)a[d];
				n/=10;
			}
		}
		printf("%lld\n",ans);
	}
}

Shift and Reverse

题目大意：现有一个大小为n的数组a[],我们可以进行如下两个操作任意多次：

1.将末尾元素移到开头

2.将数组反转

我们最后需要使a[]变成非递减数组，问最少需要进行多少次操作，如果不管怎么操作都得不到就输出-1。

思路：我们来分析一下操作的实际意义。

我们将操作1命名为z,操作2命名为f。(一下描述中f或者z可能表示连着这么操作很多次)

对于数组:a[1]a[2]a[3]...a[n-2]a[n-1]a[n]:

z:a[n]a[1]a[2]a[3]...a[n-2]a[n-1]

f:a[n]a[n-1]a[n-2]...a[3]a[2]a[1]

fz:a[n]a[n-1]a[n-2]...a[3]a[2]a[1]->a[2]a[1]a[n]a[n-1]a[n-2]...a[3]

zf:a[n-1]a[n]a[1]a[2]a[3]...a[n-2]->a[n-2]...a[3]a[2]a[1]a[n]a[n-1]

fzf:a[n]a[n-1]a[n-2]...a[3]a[2]a[1]->a[2]a[1]a[n]a[n-1]a[n-2]...a[3]->

a[3]...a[n-2]a[n-1]a[n]a[1]a[2]

~~zfz:a[n-1]a[n]a[1]a[2]a[3]...a[n-2]->a[n-2]...a[3]a[2]a[1]a[n]a[n-1]->~~

~~a[n-1]a[n-2]...a[3]a[2]a[1]a[n]~~(相当于zf中的z少执行几次而已，故而没有存在的必要)

~~fzfz:a[n]a[n-1]a[n-2]...a[3]a[2]a[1]->a[2]a[1]a[n]a[n-1]a[n-2]...a[3]->~~

~~a[3]...a[n-2]a[n-1]a[n]a[1]a[2]->a[2]a[3]...a[n-2]a[n-1]a[n]a[1]~~

（相当于fzf中的z少执行几次而已，也没有存在的必要，后面就不用再讨论了，延伸不下去了。）

那么实际有效的只有z,f,fz,zf,fzf这几个操作，我们就对每个操作执行到底，看看能不能生成目标数组，如果可以取操作最小值，否则输出-1。另外记录一下，如果数组本身单增，那么输出0，单减输出1.

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010],tmp[100010];
int n;
int z()
{
	//不管怎样都是转
	int c=a[1],idx=n+1;
	for(int i=n;i>=1;i--)
	{
		if(a[i]<=c) c=a[i],idx=i;
		else break;
	}
	int j=0;
	for(int i=idx;i<=n;i++) tmp[++j]=a[i];
	for(int i=1;i<idx;i++) tmp[++j]=a[i];
	//判增
	c=tmp[1];
		idx=n-idx+1;
	for(int i=2;i<=n;i++)
	{
		if(tmp[i]<c) 
		{
			idx=-1;
			break;
		}
		c=tmp[i];
	}
	return idx;
}
int zf()
{
	//先转成单减的再反
	int c=a[1],idx=n+1;
	for(int i=n;i>=1;i--)
	{
		if(a[i]>=c) c=a[i],idx=i;
		else break;
	}
	int j=0;
	for(int i=idx;i<=n;i++) tmp[++j]=a[i];
	for(int i=1;i<idx;i++) tmp[++j]=a[i];
	reverse(tmp+1,tmp+1+n);
	//判增
	c=tmp[1];
		idx=n-idx+1;
		idx += 1;
	for(int i=2;i<=n;i++)
	{
		if(tmp[i]<c) 
		{
			idx=-1;
			break;
		}
		c=tmp[i];
	}
	return idx;
}
int fz()
{
	int c=b[1],idx=n+1;
	for(int i=n;i>=1;i--)
	{
		if(b[i]<=c) c=b[i],idx=i;
		else break;
	}
	int j=0;
	for(int i=idx;i<=n;i++) tmp[++j]=b[i];
	for(int i=1;i<idx;i++) tmp[++j]=b[i];
	//判增
	c=tmp[1];
		idx=n-idx+1;
		idx+=1;
	for(int i=2;i<=n;i++)
	{
		if(tmp[i]<c) 
		{
			idx=-1;
			break;
		}
		c=tmp[i];
	}
	return idx;
}
int fzf()
{
	reverse(a+1,a+1+n);
	int c=a[1],idx=n+1;
	for(int i=n;i>=1;i--)
	{
		if(a[i]>=c) c=a[i],idx=i;
		else break;
	}
	int j=0;
	for(int i=idx;i<=n;i++) tmp[++j]=a[i];
	for(int i=1;i<idx;i++) tmp[++j]=a[i];
	reverse(tmp+1,tmp+1+n);
	//判增
	idx=n-idx+1;
	idx += 2;
	c=tmp[1];
	for(int i=2;i<=n;i++)
	{
		if(tmp[i]<c) 
		{
			idx=-1;
			break;
		}
		c=tmp[i];
	}
	return idx;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int flag=0,gx=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			b[i]=a[i];
			if(i>1)
			{
				if(gx==1&&a[i]<a[i-1]) flag=i;
				if(gx==2&&a[i]>a[i-1]) flag=i;
				if(!flag&&a[i]>a[i-1]) gx=1;
				if(!flag&&a[i]<a[i-1]) gx=2;
			}
		}
		reverse(b+1,b+1+n);
		/*
		转
		反
		反转
		转反
		反转反		
		*/
		if(flag)//非单调，仅仅反肯定不行了
		{
			//三种操作，取最小值或者输出-1
			int v1=z(),v2=zf(),v3=fzf(),v4=fz();
			if(v1!=-1||v2!=-1||v3!=-1) 
			{
				if(v1==-1) v1=0x3f3f3f3f;
				if(v2==-1) v2=0x3f3f3f3f;
				if(v3==-1) v3=0x3f3f3f3f;
				if(v4==-1) v4=0x3f3f3f3f;
				int ans=min(v1,v2);
				ans=min(v3,ans);
				ans =min(v4,ans);
				printf("%d\n",ans);
			}
			else printf("-1\n");
		}
		else
		{
			if(gx<=1) printf("0\n");
			else printf("1\n");
		}
	}
}

反思：要通过这次的D记住有时候单点不能确定的时候，要考虑能不能确定点所在的区间，通过F要记住凡是讨论一定要把所有情况都讨论完整。