模拟赛

1.魔法部落

题意分析

就是求30+31+……+3n

解题思路

快速幂+逆元
首先将30+31+……+3n *3
变成31+32+……+3n+3n+1
用第二个式子-第一个式子
得 (3n+1-30)/2=(3n+1-1)/2
用快速幂求出3n+1
再用玄学逆元/2

AC代码

#include<cmath>
#include<cstdio>
using namespace std;
const long long MOD=1000000007;
long long n;
long long ksm(long long x,long long y)//快速幂
{
   
	long long z=1;
	while(y)
	{
   
		if(y&1)z=z*x%MOD;
		x=x*x%MOD;
		y>>=1;
	}
	return z;
}
int main()
{
   
	scanf("%lld",&n);
	printf("%lld",(ksm(3,n+1)-1)*(MOD+1)/2%MOD);//逆元求和
 	return 0; 
}

2.圆盘

解题思路

等比数列+最小表达法
最小表达法

AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,p,ok,ans,a[505],c[505],b[505][1005];
int zxbsf(int z[])//最小表达法
{
   
	int x=1,y=2,k=0;
	while(x<=2*m&&y<=2*m)
	{
   
		for(k=0;k<=2*m&&z[x+k]==z[y+k];k++);
		if(k==2*m)break;
		if(z[x+k]<z[y+k])
		{
   
		 	x+=k+1;
		 	if(x==y)x++;
		} 
		else
		{
   
		 	y+=k+1;
		 	if(x==y)y++;
		}
	}
	return min(x,y);
}
int main()
{
   
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)
	{
   
	 	for(int j=1;j<=m;j++) 
	  	 scanf("%d",&a[j]);
	  	sort(a+1,a+m+1);
		for(int j=1;j<=m-1;j++)//先复制一遍
		{
   
			b[i][j]=abs(a[j+1]-a[j]);
			b[i][j+m]=b[i][j];
		}
		b[i][m]=b[i][m+m]=a[1]+p-a[m];
		c[i]=zxbsf(b[i]); //最小表达法
	}
	for(int i=1;i<=n;i++)//比较
	 for(int j=i+1;j<=n;j++)
	 {
   
	 	ok=1;
	 	int x=c[i],y=c[j];
	 	for(int k=1;k<=m;k++)//一一比较
	 	 if(b[i][x+k-1]!=b[j][y+k-1])
	 	 {
   
		 	ok=0;
			break; 
	 	 }
	  	if(ok==1)ans++;
	 }
	printf("%d",ans);
	return 0;  
}

3.棋盘行走

题意分析

就是找出一个环

解题思路

用dfs暴力
因为形成一个环后，字母个数一定是>=4的
所以不用判断字母个数

AC代码

#include<cstdio>
#include<iostream>
#include<cstring> 
using namespace std;
int n,m,a[55][55],c[55][55];//数组开小点，看清题目范围
int dx[4]={
   1,-1,0,0};
int dy[4]={
   0,0,1,-1};
bool check(int x,int y)//判断
{
   
	if(x>=1&&x<=n&&y>=1&&y<=m)return true;
	return false;  
}
void dfs(int x,int y,int xx,int yy)//x、y为当前点坐标，xx、yy为上一个点坐标
{
   
	if(c[x][y]){
   printf("Yes");exit(0);}//如果有环就退出
	c[x][y]=1;//标记
	for(int i=0;i<4;i++)//4个方位
	{
   
		int x1=x+dx[i],y1=y+dy[i];
		if(check(x1,y1))
		 if(a[x1][y1]==a[x][y]&&(x1!=xx||y1!=yy))
		  dfs(x1,y1,x,y);
	}
}
int main()
{
   
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
   
	 string s;
	 cin>>s; 
	 for(int j=0;j<m;j++)a[i][j+1]=s[j]-'A'+1;
	} 
	for(int i=1;i<=n;i++)//每个点遍历一遍
	 for(int j=1;j<=m;j++)
	 {
   
		memset(c,0,sizeof(c));
	    dfs(i,j,0,0);
	 }
	printf("No");
	return 0;
}

4.走方格

解题思路

看到求和
我们就可以用前缀和或后缀和来做
我们先看一组地址

1 2 3 4 5 6 7 8 9
如果删除 5 ，变成
1 2 3 4   5 6 7 8

我们不难发现
5前面的数没变，就可以用前缀和求和
5后面的数奇偶数对调，就可以用后缀和求和
最后再比较一下
就OK了

AC代码

#include<cstdio>
using namespace std;
int n,ans,a[200005],sum1[200005][3],sum2[200005][3];
int main()
{
   
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	 scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)//求前缀和
	 if(i%2==1)sum1[i][1]=sum1[i-2][1]+a[i];
	 else sum2[i][1]=sum2[i-2][1]+a[i];
	for(int i=n;i>=1;i--)//求后缀和
	 if(i%2==1)sum1[i][2]=sum1[i+2][2]+a[i];
	 else sum2[i][2]=sum2[i+2][2]+a[i];
	for(int i=1;i<=n;i++)//枚举每一个点
	 if(i%2==1)//判断奇偶情况
	 {
    
	  	if((sum1[i-2][1]+sum2[i+1][2])==(sum2[i-1][1]+sum1[i+2][2]))//判断是否相等
	 	ans++;
	 }
	 else 
	 {
   
	 	if((sum1[i-1][1]+sum2[i+2][2])==(sum2[i-2][1]+sum1[i+1][2]))//判断是否相等
	 	ans++;
	 }
	printf("%d",ans);//输出
	return 0;
}

谢谢