2022年第十三届CC++ B组第一场蓝桥杯省赛题解

解析：这道题就是模拟找规律，有三种情况，分别是第一、二、三次走到目标位置灌木长的高度，在这三种情况中取最大值。

code:

#include
using namespace std;
const int M=1e5+5,mod=1e9+7;
typedef long long LL;
int a[M], b[M], w[M];  
int n;
int Ma, Mb;
LL mul[M];  
int A, B;
int main()
{
    int n,Ma,Mb;
    cin>>n;
    cin>>Ma;
    for(int i=Ma;i>=1;i--) cin>>a[i];
    cin>>Mb;
    for(int i=Mb;i>=1;i--) cin>>b[i];
    int M=max(Ma,Mb);
    for(int i=M;i>=1;i--)
    {
        int t=max(a[i],b[i]);
        w[i]=max(2,t+1);
    }
    mul[1]=1;
    for(int i=2;i<=M;i++)
    {
        mul[i]=mul[i-1]*w[i-1]%mod;
    }
    for(int i=Ma;i>=1;i--)
    A=(A+a[i]*mul[i])%mod;
    
    for(int i=Mb;i>=1;i--)
    B=(B+b[i]*mul[i])%mod;
    
    cout<<(A-B+mod)%mod;
    
    return 0;
}

解析：这道题用贪心就可以很简单的解决这道题。数的每位都选用对A和B来说合理的进制最小但不低于2的进制，A-B的值最小。就比如第i位，A的数为3，B的数为4，对A来说进制最小为4，对B来说进制最小为5，那么对A和B来说该位合理的进制最小为5。每位的进制得出来后，再算出每位的权值。在这里要注意在算权值时是会爆int的，两个int值相乘会爆int，即使取模，在取模前就爆了，所以权值要用long long来存，但算A和B时，是不会爆int的，因为会分别取模，两个在1e9+7范围内的数相加是不会爆int的，这个要注意！如果你不想那么麻烦，也可以全都用long long来存，答案不会变，就是耗时长一点。

code:

#include
using namespace std;
const int N=5e2+10;
int a[N][N];
int main()
{
    int n,m,k;
    long long ans=0;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=i;j<=m;j++)
        {
            for(int s=1,t=1;t<=n;t++)
            {
                while(s<=t&&a[t][j]-a[t][i-1]-a[s-1][j]+a[s-1][i-1]>k) s++;
                if(s<=t) ans+=t-s+1;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

解析：这道题要用前缀和双指针的知识。
以下为示意图：

s和t是能动的指针，i和j固定。我们在做的时候遍历i和j，然后在循环内遍历t，s往下动的条件是s<=t&&a[t][j]-a[t][i-1]-a[s-1][j]+a[s-1][i-1]>k，这里要用while循环，直道s>t或里面的数之和小于或等于k，如果是小于或等于k的情况就是我们想要的答案了，ans+=t-s+1，为什么是加t-s+1呢？因为s往下都是符合条件的答案。接着t++，再一次循环遍历上述流程。

code:

#include
using namespace std;
const int mod=1e9+7;
long long f[2][3];
int main()
{
    int n;
    scanf("%d",&n);
    f[1][0]=1;
    f[1][1]=2;
    f[1][2]=1;
    for(int i=2;i<=n;i++)
    {
        f[i&1][0]=(f[i-1&1][0]+f[i-1&1][2])%mod;
        f[i&1][1]=(f[i-1&1][0]*2+f[i-1&1][1])%mod;
        f[i&1][2]=(f[i-1&1][0]+f[i-1&1][1])%mod;
    }
    printf("%lld",f[n&1][0]);
    return 0;
}

解析：这道题咋一看是不是有点像蒙德里安的梦想这道状压DP题，但其实比那道题简单多了，因为这里规定了长度为2，那么表示状态就好表示多了，用线性DP就可以解决。
规定f[i][j]:前i列已填满，第i+1列填了j个方块，那么答案就是f[n][0]。在这里要注意n的取值最大可为10的7次方，数组空间会超的，但我们都是相邻两列进行比较，所以我们可以用滚动数组来做。

code:

#include
using namespace std;
const int N=5e4+10,M=1e6+7,X=1e9+1;
struct node{
	int x,y,r;
}b[N];
typedef long long ll;
ll h[M];
int id[M],res;
bool st[N];
ll get_hs(int x,int y)
{
	return (ll)x*X+y;
}
int find(int x,int y)
{
	ll hs=get_hs(x,y);
	int key=(hs%M+M)%M;
	while(h[key]!=-1&&h[key]!=hs)
	{
		key++;
		if(key==M) key=0;
	}
	return key;
}
bool check(int x1,int y1,int r,int x,int y)
{
	int d=(x1-x)*(x1-x)+(y1-y)*(y1-y);
	return d<=r*r;
}
void bfs(int pos)
{
	queue q;
	q.push(pos);
	st[pos]=1;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		int x=b[t].x,y=b[t].y,r=b[t].r;
		for(int xx=x-r;xx<=x+r;xx++)
		{
			for(int yy=y-r;yy<=y+r;yy++)
			{
				int key=find(xx,yy);
				if(id[key]&&!st[id[key]]&&check(x,y,r,xx,yy))
				{
					int pos=id[key];
					st[pos]=1;
					q.push(pos);
				}
			}
		}
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	memset(h,-1,sizeof(h));
	int x,y,r;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y>>r;
		b[i].x=x,b[i].y=y,b[i].r=r;
		int key=find(x,y);
		if(h[key]==-1) h[key]=get_hs(x,y);
		if(!id[key]||b[id[key]].r>x>>y>>r;
		for(int xx=x-r;xx<=x+r;xx++)
		{
			for(int yy=y-r;yy<=y+r;yy++)
			{
				int key=find(xx,yy);
				if(id[key]&&!st[id[key]]&&check(x,y,r,xx,yy)) bfs(id[key]);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		int key=find(b[i].x,b[i].y);
		int pos=id[key];
		if(pos&&st[id[key]]) res++;
	}
	cout<

#include
using namespace std;
const int N=105,mod=1e9+7;
int f[N][N][N];
int n,m;
int main()
{
    cin>>m>>n;
    f[0][0][2]=1;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k0)
                {
                    f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%mod;
                }
                if(j>0&&k%2==0)
                {
                    f[i][j][k]=(f[i][j][k]+f[i][j-1][k/2])%mod;
                }
            }
        }
    }
    cout<

#include
using namespace std;
int n,m;
long long num;
int mod=1e9+7;
int ans=0;
string s="";
void dfs(int k)
{
	if(k>n+m)
	{
			num=2;
			//cout<0)
					num=num-1;
					else break;
				}
				if(s[i]=='1') {
					b++;
					num=num*2;
				}
				
			}
			if((num==0)&&(i==n+m)&&a==m&&b==n){
				
				ans++;
				ans=ans%mod;	
			} 
			
			return;
	}
	s+='0';
	dfs(k+1);
	if(s.length()!=1)
	s=s.substr(0,k-1);
	else s="";
	s+='1';
	dfs(k+1);
}
int main()
{
	cin>>n>>m;
	dfs(1);
	cout<

#include
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N];
vector b[N];
int n;
ll change(ll x)
{
    return sqrt(x/2+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        while(a[i]>1)
        {
            int flag=0;
            for(ll j:b[i-1])
            {
                if(a[i]==j)
                {
                    flag=1;
                    break;
                }
            }
            if(!flag) res++;
            b[i].push_back(a[i]);
            a[i]=change(a[i]);
        }
    }
    printf("%d",res);
    return 0;
}