Codeforces Round #660 (Div. 2) A. Captain Flint and Crew Recruitment、Captain Flint and a Long Voyage

题目链接：Captain Flint and Crew Recruitment

题意：

t组输入，每一组输入一个n。这里我们说一下题目定义的近似质数概念：

“如果可以将正整数x表示为p⋅q，则将其定义为近似质数，其中1 <p <q，p和q是质数。例如，整数6和10几乎是质数（因为2⋅3= 6和2⋅5= 10），但整数1、3、4、16、17不是。”

这里我们把n分成四个数的和，你需要使这四个数中的至少三个数都是近似质数，且要保证这四个数互不相等

如果能找出来这四个数就输出，否则输出NO

题解：

因为只需要三个数都是近似质数就行，那么最小的三个近似质数是6，10，14那么n的大小最小要等于31才可以有解

这里要注意，题目要求四个数要互不相等，那么我们就需要特判一下36，40，44

代码：

 1 #include<stack>

 2 #include<queue>

 3 #include<map>

 4 #include<cstdio>

 5 #include<cstring>

 6 #include<iostream>

 7 #include<algorithm>

 8 #define fi first

 9 #define se second

10 using namespace std;

11 typedef long long ll;

12 const int maxn=1e5+10;

13 const int mod=1e9+7;

14 const double eps=1e-8;

15 int a[maxn],b[maxn];

16 int main()

17 {

18     int t;

19     scanf("%d",&t);

20     while(t--)

21     {

22         int n;

23         scanf("%d",&n);

24         if(n==36)

25         {

26             printf("YES\n");

27             printf("5 6 10 15\n");

28         }

29         else if(n==40)

30         {

31             printf("YES\n");

32             printf("15 6 10 9\n");

33         }

34         else if(n==44)

35         {

36             printf("YES\n");

37             printf("6 7 10 21\n");

38         }

39         else if(n>6+10+14)

40         {

41             printf("YES\n");

42             printf("6 10 14 ");

43             printf("%d\n",n-30);

44         }

45         else

46         {

47             printf("NO\n");

48         }

49     }

50     return 0;

51 }

题目链接：Captain Flint and a Long Voyage

题意：

t组输入，每组数据给你一个n，代表数x的长度，这个x是你需要找到的一个整数。你把x的每一位数转化成二进制形式后就是k

例如 x=729，那么 k=111101001 (因为 7=111, 2=10, 9=1001).

然后你把k的末尾n个二进制数删除，就是最后的结果，例如上面的例子删除之后就变成了111101

你要使这个结果尽可能的大，所以给你一个n，让你求能使最后结果尽可能大的最小的那个x是多少，然后输出x

题解：

你会发现整数8、9转化成二进制都是4位，所以我们的x肯定是由8、9构成的，那么什么时候用8什么时候用9呢？

比较来看8、9的二进制形式也就只有最后一位不同

题目又说输出那个最小的x，题目的x转化成k之后，还要删除末尾的n个二进制数。删除这n个二进制数由8这个整数构成才可以使得x最小

所以x的最后n/4+(n%4!=0)位输出8，剩下的输出9

代码：

 1 #include<stack>

 2 #include<queue>

 3 #include<map>

 4 #include<cstdio>

 5 #include<cstring>

 6 #include<iostream>

 7 #include<algorithm>

 8 #define fi first

 9 #define se second

10 using namespace std;

11 typedef long long ll;

12 const int maxn=1e5+10;

13 const int mod=1e9+7;

14 const double eps=1e-8;

15 int a[maxn],b[maxn];

16 int main()

17 {

18     int t;

19     scanf("%d",&t);

20     while(t--)

21     {

22         int n;

23         scanf("%d",&n);

24         int ans=n/4;

25         if(n%4)

26             ans++;

27         for(int i=1;i<=n-ans;++i)

28             printf("9");

29         for(int i=1;i<ans;++i)

30             printf("8");

31         printf("8\n");

32     }

33     return 0;

34 }

巴特西

Codeforces Round #660 (Div. 2) A. Captain Flint and Crew Recruitment、Captain Flint and a Long Voyage

最新文章

热门文章