普及组T3样例不输出

问题讨论区 普及段
1

image
image994×632 99 KB

代码

#include<bits/stdc++.h>
using namespace std;
int t,n;
bool zs(int x){
	if(x==2){
		return 1;
	}
	for(int i=1;i<=sqrt(x);i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}
struct node{
	int sum;
	string s;
};
void bfs(int sum,string s){
	queue<node>q;
	q.push({sum,s});
	while(!q.empty()){
		node now=q.front();
		q.pop();
		if(now.sum>n){
			continue;
		}
		if(now.sum==n){
			cout<<s;
			return;
		}
		
		if(sum==0){
			
			q.push({sum+2,s+"1"});
			q.push({sum+5,s+"2"});
			q.push({sum+5,s+"3"});
			q.push({sum+4,s+"4"});
			q.push({sum+5,s+"5"});
			q.push({sum+6,s+"6"});
			q.push({sum+3,s+"7"});
			q.push({sum+7,s+"8"});
			q.push({sum+6,s+"9"});
		}else{
			q.push({sum+6,s+"0"});
			q.push({sum+2,s+"1"});
			q.push({sum+5,s+"2"});
			q.push({sum+5,s+"3"});
			q.push({sum+4,s+"4"});
			q.push({sum+5,s+"5"});
			q.push({sum+6,s+"6"});
			q.push({sum+3,s+"7"});
			q.push({sum+7,s+"8"});
			q.push({sum+6,s+"9"});
		}
		
		
		
	}
}
int main(){
//    freopen("sticks.in","r",stdin);
//    freopen("sticks.out","w",stdout);
    cin>>t;
    while(t--){
    	cin>>n;
    	if(n==1){
    		cout<<-1;
    		continue;
		}
		if(zs(n)&&n>=7){
			cout<<-1;
			continue;
		}
		string s="";
		bfs(0,s);
	}
    return 0;
}
蒟蒻求调
2 个赞
2

啊？和质数有什么关系吗？

1 个赞
3

我不知道考场上瞎打的

1 个赞
4

我只想知道为什么不输出

1 个赞
5

我现在一看见“普及T3”就会想起我痛苦的回忆……

1 个赞
6

HA!发现同类

1 个赞
7

看我头像和用户名就知道了。

1 个赞
8

还有我的帖子：

1 个赞
9

这道题可以使用贪心，即选尽量多的 8 ，位数会更少。
但这样过不了，还需要特判。
核心代码如下：

if(n==1) cout<<-1<<endl;
else if(n==3) cout<<7<<endl;
else if(n==4) cout<<4<<endl;
else if(n==10) cout<<22<<endl; 
else{
    int mod=n%7,ans=n/7;
	if(mod==1) cout<<10,ans-=1;
	else if(mod==2) cout<<1;
	else if(mod==3) cout<<200,ans-=2;
	else if(mod==4) cout<<20,ans-=1;
	else if(mod==5) cout<<2;
	else if(mod==6) cout<<6;
	for(int i=1;i<=ans;i++) cout<<8;
    cout<<endl;
}

给个解决方案作为我 T3 爆 0 的安慰，求求了

1 个赞
10

好的，谢谢解法

1 个赞
11

@肖宇睿 你是那个肖宇睿吗？

12

哪个肖宇睿，我是西林那个

1 个赞
13

@肖宇睿 是你没错了，我知道你，我是上上届六年级的

14

啊哈，学长

2 个赞
15
16

跟你做法一样

2 个赞