专栏文章

P11229 [CSP-J 2024] 小木棍(官方数据)题解

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir4snk4
此快照首次捕获于
2025/12/04 15:45
3 个月前
此快照最后确认于
2025/12/04 15:45
3 个月前
查看原文

题目介绍

用小木棍摆 090 \sim 9,组成一个正整数,满足如下条件:
  • 拼出这个数恰好使用 nn 根小木棍;
  • 拼出的数没有前导 00
  • 在满足以上两个条件的前提下,这个数尽可能小。
如果无解,输出 1-1

原题链接

100pts 思路讲解

算法:贪心(找规律)

时间复杂度:O(n)O(n)

首先发现数字 88 使用的小木棍数最多,想让最后的数最小,首先位数要最少,要位数最少所以要多选 88,剩下多余的小木棍用来做小数字。

注:在木棍少的时候取 88 不划算,记得特判。

代码+注释

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
		cin>>n;
		if(n==1)
		{
			cout<<"-1\n";
		}
		else if(n==2)
		{
			cout<<"1\n";
		}
		else if(n==3)
		{
			cout<<"7\n";
		}
		else if(n==4)
		{
			cout<<"4\n";
		}
		else if(n==5)
		{
			cout<<"2\n";
		}
		else if(n==6)
		{
			cout<<"6\n";
		}
		else if(n==7)
		{
			cout<<"8\n";
		}
		else if(n==10)
		{
			cout<<"22\n";
		}
		else if(n%7==0)
		{
			for(int i=1;i<=n/7;i++)
			{
				cout<<"8";
			}
			cout<<"\n";
		}
		else if(n%7==1)
		{
			cout<<"10";
			for(int i=1;i<=(n-8)/7;i++)
			{
				cout<<"8";
			}
			cout<<"\n";
		}
		else if(n%7==2)
		{
			cout<<"1";
			for(int i=1;i<=(n-2)/7;i++)
			{
				cout<<"8";
			}
			cout<<"\n";
		}
		else if(n%7==3)
		{
			cout<<"200";
			for(int i=1;i<=(n-17)/7;i++)
			{
				cout<<"8";
			}
			cout<<"\n";
		}
		else if(n%7==4)
		{
			cout<<"20";
			for(int i=1;i<=(n-11)/7;i++)
			{
				cout<<"8";
			}
			cout<<"\n";
		}
		else if(n%7==5)
		{
			cout<<"2";
			for(int i=1;i<=(n-5)/7;i++)
			{
				cout<<"8";
			}
			cout<<"\n";
		}
		else if(n%7==6)
		{
			cout<<"6";
			for(int i=1;i<=(n-6)/7;i++)
			{
				cout<<"8";
			}
			cout<<"\n";
		}
	}
    return 0;
}

100pts 记录

评论

0 条评论,欢迎与作者交流。

正在加载评论...