欢乐赛小题解

stdCharly

2024-08-26 07:02:50

发布于：河南

33阅读

0回复

0点赞

众所周知我只会打广搜

感觉后面就两题难，但是还是入门题吧?

T7

原题链接
这道题我想了一会 ~~真的只有一会儿~~
突然被我发现了盲点，外围的数是一样的，也就是说步数(也就是赋值)到n-1的时候，停止就行
所以直接顺手打个广搜，真不会写深搜

#include<bits/stdc++.h>
using namespace std;
int n,vis[1001][1001];
int fx[4]={1,0,-1,0};
int fy[4]={0,1,0,-1};
struct node{
	int x,y,step;
};
queue<node>q;
int main(){
	memset(vis,-1,sizeof vis);
	cin>>n;
	q.push({n,n,0});
	vis[n][n]=0;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.step==n-1)continue;
      //如果数字到达n-1，结束
		for(int i=0;i<4;i++){
			int xx=t.x+fx[i];
			int yy=t.y+fy[i];
			if(vis[xx][yy]!=-1)continue;
			q.push({xx,yy,t.step+1});
			vis[xx][yy]=t.step+1;
		}
	}for(int i=1;i<=n*2-1;i++){
		for(int j=1;j<=n*2-1;j++){
			if(vis[i][j]==-1){
				cout<<"*";
              //如果vis[i][j]没走到，根据题目要求，输出*
			}else{
				cout<<vis[i][j];
			}
		}cout<<endl;
	}
}

T8

原题链接
暴力搜索直接过但是我还是爱打广搜
根据题目要求，先用埃式筛弄一张质数表
然后根据质数表直接搜索即可(再次顺手打个广搜)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000001],ans;
vector<int>v;
struct node{
	int x,sum,id;
};queue<node>q;
signed main(){
	cin>>n;
	for(int i=2;i<=1000000;i++){
		if(a[i]==0)v.push_back(i);
		for(int j=i*2;j<=1000000;j+=i){
			a[j]=1;
		}
	}q.push({1,0,0});
	while(!q.empty()){
		node t=q.front();
		q.pop();
		if(t.sum==0&&(v[t.id]*v[t.id]*v[t.id+1]*v[t.id+2]*v[t.id+2]>n||t.id>=v.size()-1-2))continue;
		if(t.sum==1&&(t.x*v[t.id]*v[t.id+1]*v[t.id+1]>n||t.id>=v.size()-1-1))continue;
		if(t.sum==2&&(t.x*v[t.id]*v[t.id]>n||t.id>=v.size()-1))continue;
      //标记边界，如果现在的值加上目前运行到的地方已经大于n
      //则直接跳过本次循环
		if(t.x>n)continue;
      //如果现在的值已经大于n，跳过本次循环，减少运行次数，防止TLE
		if(t.sum==3){
			ans++;
			continue;
		}
      //如果已经取了三个数，则答案++，因为上面已经判断t.x>n就跳过;
      //所以本处无需判断
		q.push({t.x,t.sum,t.id+1});
		if(t.sum==1)q.push({t.x*v[t.id],t.sum+1,t.id+1});
		else q.push({t.x*v[t.id]*v[t.id],t.sum+1,t.id+1});
      //将选择和不选择的两种情况加入队列
	}cout<<ans;
}