Educational Codeforces Round 129 (Rated for Div. 2)(A-D)题解

A. Game with Cards

题目链接：Problem - A - Codeforces

题意：Alice和Bob打牌，两人分别有n和m张牌，每个人出的牌必须比前一张牌大，不然就输了，A输出两人分别先后手的情况。

思路：每人直接打出最大的牌，比较两人最大牌的大小，如果两人的最大牌相同，那么先手必赢。

代码实现：

#include
#define ll long long 
using namespace std;
const int maxn=1e3+10;
const int inf=0x3f3f3f3f;
int a[maxn],b[maxn];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int maxa=0;
		int maxb=0;
		int n,m;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			maxa=max(maxa,x);//寻找Alice的最大牌 
		}
		cin>>m;
		for(int i=1;i<=m;i++)
		{
			int x;
			cin>>x;
			maxb=max(maxb,x);//寻找Bob的最大牌 
		}
		if(maxa>=maxb)//Alice先手，最大牌相同Alice也能赢 
		cout<<"Alicen";
		else
		cout<<"Bobn";
		if(maxa>maxb)//Alice后手 
		cout<<"Alicen";
		else
		cout<<"Bobn";
	}
	return 0;
}

B. Card Trick

题目链接：Problem - B - Codeforces

题意：有n张牌的牌组，从上到下大小分别为a1,a2...an,进行m次洗牌，第i次洗牌将顶部bj张牌洗到底部。问第m次洗牌后最顶端的牌的大小

思路：如果直接模拟洗牌那么就太复杂了，我们只需要关注最顶端的牌，在未洗牌的状态，顶端为a1，将顶部x张牌放入底端，当前顶端为a[1+x],以此类推，最顶端的牌可以表示为a[(1+x)%n]。

代码实现：

#include
#define ll long long 
using namespace std;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
int a[maxn],b[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n;
		int top=1;//记录最顶端的下标 
		for(int i=1;i<=n;i++)
		cin>>a[i];
		cin>>m;
		for(int i=1;i<=m;i++)
		{
			int x;
			cin>>x;
			top+=x;
			top%=n;
		}
		if(top==0)//因为n%n==0，所以没有这步会输入a[0](就是0) 
		top=n;
		cout<

C. Double Sort

题目链接：Problem - C - Codeforces

题意：给两个长度为n的数列，有如下操作，将两个数列的第i个元素同时与各自的第j个元素交换，问有没有可能将两个数列变成非递减数列，如果能，就输出其中一种做法，如果没有输出-1。

思路：假设如果两个数列没有重复元素，那么两个数列的各元素大小关系必须相同才可以排序，也就是说两数组第i大的数必须在同一位置。但是这题有重复数字，前面这种类似于离散化（大概？）的做法不能成立，相同的数字排序之后肯定连在一起，而另外一个数组在这段连续的区间必须满足非递减关系。把两个数组看成一个整体，先按照第一个数组排序，相同数字的地方根据第二个数组大小关系排序，排完后第一个数组肯定排好了，但第二数组只保证了在第一个数组相同数字的一块满足非递减，所以此时检查第二数组是否排好就可以验证。难点在于判断，排序的话可以随便。

代码实现：

#include
#define ll long long 
using namespace std;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
struct node{
	int x,y;
}a[maxn],b[maxn],ans[maxn];
 
bool cmp1(const node a,const node b)
{
	if(a.x!=b.x)//先按第一个数组排 
	return a.x>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)//输入第一个数组 
		{
		cin>>a[i].x;
		b[i].x=a[i].x;	
		}
		for(int i=1;i<=n;i++)//输入第二个数组 
		{
		cin>>a[i].y;
		b[i].y=a[i].y;	
		}
		sort(a+1,a+1+n,cmp1);
		bool f=1;
		for(int i=1;i<=n-1;i++)
		if(a[i].y>a[i+1].y)//如果第二个数组不是非递减 
		{
			f=0;
			break;
		}
		if(f)
		{
			int s=0;
			for(int i=1;i<=n;i++)
			{
				int min=i;
				for(int j=i+1;j<=n;j++)
				{
					if(b[min].x>=b[j].x&&b[min].y>=b[j].y)
					min=j;//寻找第i小的数(第i次循环中最小的数) 
				}
				if(min!=i)
				{
					ans[++s].x=min;
					ans[s].y=i;
				node temp=b[min];//交换 
				b[min]=b[i];
				b[i]=temp;	
				}
			}
			cout< 
D. Required Length
 
题目链接：Problem - D - Codeforces
 
题意：给一个数字n和x，n代表长度，x每次操作可以乘以自己十进制形式出现的数，（比如12可以乘1或2），问x最少几次操作可以变成长度为n的数，如果不可以输出-1。
 
思路：n的大小为[2,19]，可以使用BFS，队列存储的是x分别乘以（除了0）自己各位上的数后的结果，因为要记录每一位上的数，所以用string表示就很方便，同时string还能记录长度，用一个map记录是否入队并且记录转换成该数字所需要的操作数，当队列首元素长度为n是，即查找成功。
 
代码实现：
 
#include
#define ll long long
#define ull unsigned long long
using namespace std;
//unsigned long long可以表示10的19次方的数,样例n最大为19 
int main()
{   
    int n;
    cin >> n;
    ull x;
    cin >> x;
    queue q;
    map mp;//记录到达该数的操作数 
    mp[x]=0;
    q.push(x);
    int ans=-1;
    while(!q.empty())
    {
        ull p=q.front();//取出队列首元素 
        q.pop();
        string s="";
        ull temp=p;
        while(temp)//获取倒过来的p，实际上不影响，因为只需要知道长度和每位的数 
        {
        	s+=temp%10+'0';
        	temp/=10;
		}
        if(s.size()==n)//如果长度找到了 
        {
           ans=mp[p];
           break;
        }
        for(int i=0;i