首页 > 试题广场 >

冰冻青蛙

[编程题]冰冻青蛙

热度指数：442 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 在女仆长紧张修建红魔馆的同时，雾之湖附近却也不安宁。

$\hspace{15pt}$ 在雾之湖的岸边，有 $n$ 只青蛙排成一排，编号依次为 $1$ 到 $n$ 。冰之妖精琪露诺（⑨）和她的好朋友大妖精正在练习冰冻魔法！每一轮施展魔法的规则如下：
$\hspace{23pt}\bullet\,$ 如果一个青蛙的编号为 $x$ ，满足 $\gcd(x,\underbrace{999\,999\,999}_{9 \text { 个 } 9})\neq 1$ ，则可以一次性冻结它以及它左右相邻的青蛙（如果存在）；
$\hspace{23pt}\bullet\,$ 被冻结的青蛙可以再次被选中并冻结。
$\hspace{15pt}$ 现在，你作为琪露诺的好朋友大妖精，可以提前帮助琪露诺，将这些青蛙进行重新排序。如果排序后可以使得琪露诺通过施展任意多次魔法、最终冻结所有的青蛙，她会夸你和她一样聪明。否则，琪露诺会气呼呼的说你是 $\textrm{Baka!}$ 。当然，你也需要骂回去。

$\hspace{15pt}$ $\gcd$ ，即最大公约数，指两个整数共有约数中最大的一个。例如， $12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此 $\gcd(12,30)=6$ 。‌

输入描述:

在一行上输入一个整数  代表青蛙数量。

输出描述:

如果不存在任何一种排序，使得琪露诺可以冻结所有青蛙，直接输出 。否则，在一行上输出  个不同的整数 ，代表重新排序后的青蛙编号。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

输出

1 3 2

说明

在这个样例中，，所以琪露诺可以冻结第二只青蛙，这会一并使得第一只和第三只青蛙被冻结。因此，琪露诺可以冻结所有青蛙。

示例2

输入

输出

Baka!

算法知识视频讲解

Xuan2333

发表于 2025-12-10 18:58:14

正当我百思不得其解时，一看题解，竟然还没人写？？？那没办法了，我来写一篇:-D思路及对题目的理解一只能被冰冻的青蛙可以把相邻的两个冻住，那么根据贪心（的思想），肯定是要冻住两只不能冻住别的青蛙的青蛙那么我们首先得判断这种能冰冻别的青蛙的青蛙的数量是否够，不够的话就Baka了（）够了的话，就用就用队列展开全文

周康禧

发表于 2025-12-12 16:32:10

#include <bits/stdc++.h> using namespace std; using ll = long long int; using ld = long double; using PII=pair<ll,ll>; using PIII=pair< 展开全文

悠零

发表于 2025-12-21 16:51:22

#include <iostream> using namespace std; void solve() { int x; cin>>x; if (x<36 && x%3!=0) { cout << 展开全文

yiIst

发表于 2026-01-16 16:04:12

我认为本题难点不在gcd上面，而是如何放置青蛙。下面我把可以冰冻其他青蛙的称作冰冻青蛙，其他的称为普通青蛙。我发现用双端队列deque实现起来比较方便。大致思路规划在序列中用尽量少的冰冻青蛙让所有青蛙被冰冻，下面我们用1和0表示冰冻青蛙和普通青蛙 010010010···很明显这样是用最少的1 展开全文

游云吞鲸

发表于 2026-01-19 17:35:25

//首先找出质因子很重要啊，而且有个3就非常好啊,这使得我们其实只需要讨论两段就够了 #include <bits/stdc++.h> using namespace std; #define int long long signed main() { int n;cin> 展开全文

Drink0318

发表于 2025-12-19 12:34:04

import sys import math n = int(input()) other=list()#存储其他元素 frozen=list()#存储冰冻元素 N=999999999 temp=0 for i in range(1,n+1): if(math.gcd(i,N)!=1): 展开全文

问题信息

难度：

1条回答 4收藏 62浏览

热门推荐

相关试题

冰冻青蛙

扫描二维码，关注牛客网
意见反馈
下载牛客APP，随时随地刷题

扫一扫，把题目装进口袋

求职之前，先上牛客: 扫描二维码，进入QQ群



扫描二维码，关注牛客公众号

公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
牛客科技© All rights reserved admin@nowcoder.com
京ICP备14055008号-4 增值电信业务经营许可证营业执照人力资源服务许可证
京公网安备 11010502036488号