2021.07.16【普及组】模拟赛 C 组总结

文章目录

2021.07.16【普及组】模拟赛 C 组总结

一.前言

今天的比赛，有点简单，但是我只得了一百多分，是因为我到了考试时把知识点的打法忘了，比如说，忘了快速幂怎么打。

二.题解思路

T 1：花生采摘

先说思路，本来想着 dfs 或者 bfs 来实现寻找，但想到 dfs 可能会 TLE ，然后 bfs 不会打（忘了），就没有打。谁知道？比赛结束后一讲题，便知道了原来不用搜索，啊啊啊啊啊啊啊啊啊啊…真正的解法便是暴力！！！！！先输入，输入到这个点有花生，用4个数组储存这个点的数据，分别储存此地花生数、此地的 X 坐标，此地 Y 坐标， back 数组（用来暴力是回到上一步）。接着，用 sort 排序，最好用快排，用选择排序或冒泡也行。最后~~“公开处刑”~~（暴力）。

先看看暴力部分的代码：

	int time=back[1]+1;
	for(int i=2;i<=tot;i++)
	{
		time+=1+max(x[i-1],x[i])-min(x[i-1],x[i])+max(y[i-1],y[i])-min(y[i-1],y[i]);
		if(back[i]>k-time)
		{
			printf("%d",ans);
			return 0;
		}
		else
			ans+=hs[i];
	}
	printf("%d",ans);

话说回来，为啥在鲁宾逊的岛上会有不是他自己写的纸条？

T 2： FBI 树

同上一样，先说思路，先输入，把 01 串分开放在树的每个叶节点上，再算出叶节点上的数是 B 还是 I 。然后在往根节点上推，全 0 则 B ，全 1 则 I，混合则 F 。最后按照 DFS 的后序遍历输出，非常 NICE 。

让我们康康 dfs 函数：

void bt(long long t,long long r)
{
	if(t==n)
	{
		if(Map[r]==0)
			FBI[r]='B';
		else	
			FBI[r]='I';
		bz[r]=1;
		cout<<FBI[r];
		return ;
	}
	if(r<=s)
	{
		bt(t+1,r*2);bt(t+1,r*2+1);
		if(FBI[r*2]!=FBI[r*2+1]||FBI[r*2]=='F'||FBI[r*2+1]=='F')
			FBI[r]='F';
		else
		{
			if(FBI[r*2]=='B')
				FBI[r]='B';
			else
				FBI[r]='I';
		}
		if(bz[r*2]==1&&bz[r*2+1]==1)
		{
			bz[r]=1;
			cout<<FBI[r];
		}
	}

}

T 3：火星人

同上，先讲思路，一眼看，感觉像全排列，仔细一看，这就是全排列！！！不过，有一个全排列的好东西，那就是——康托展开，康托展开对全排列非常的好用，因为康托可以计算出全排列在序列中的位置，用了康托，还要加树优化。然后就 AC 了！

T 4：麦森数

这不是快速幂加高精度吗？直接上主程序：

void ksm(int a,long long n)
{
    if(n==0)
		return ;
    ksm(2,n/2);
    if(n%2==0)
	{
        for(int i=1;i<=500;i++)
            for(int j=1;j<=500;j++)
                g[i+j-1]=g[i+j-1]+out[i]*out[j];
    }
    if(n%2==1)
	{
        for(int i=1;i<=500;i++)
            for(int j=1;j<=500;j++)
                g[i+j-1]=g[i+j-1]+out[i]*out[j]*2;
    }
    for(int i=1;i<=500;i++)
	{
        out[i]=g[i]%10;
        g[i+1]=g[i+1]+g[i]/10;
    }
    memset(g,0,sizeof(g));
}