首页
比赛
题库
课程
竞赛讨论区
登录
/
注册
去牛客
首页
>
Necklace
7条解析
开通博客写题解
Kur1su
发表于 2020-12-18 12:33:31
Description 给一堆字母的使用次数,判断能否构成一个环,使得断环成链后能够成为回文串的节点尽可能多。 Solution 首先思考回文串的定义,显然如果有两个以上奇数存在是不可能构成回文串的。接着画个图,给出几组数据 3 2 4 2 2 2 2 2 2 3不难看出,按照我们的构造方法,答
展开全文
hnust_yangyanjun
发表于 2020-12-18 19:29:54
题意:给你n种珠子,每种珠子ai颗,用全部珠子组成一条项链,项链最多有多少个切点为美丽的,美丽的为切完后为回文串,并输出其中的一种方案。 思路:由于我们需要的是回文串,如果有两种珠子个数为奇数则一定不能构成回文串,否则一定存在回文串,切点个数等于ai的最大公约数,具体构造参考代码。 代码: #inc
展开全文
ExcaIibur
发表于 2020-12-18 20:06:45
构造一个环使其成为回文串的切割数最大。 当超过两种颜色的数量为奇数时无法构造出回文串,直接输出。 根据切割的特点,容易想到构造回文串形式的单位循环节,则答案为循环节的数量,其中循环节的最大数量为各颜色数量的 gcd。 这里需要分类讨论一下(记各颜色数量的GCD为 d):(1)循环节中存在奇数数量颜色
展开全文
熠丶
发表于 2020-12-17 21:39:13
思路: 1.如果存在两个奇数,不可能找到回文字符串2.如果能找到回文串,最多能找到他们的最大公因数3.然后分不存在奇数和存在一个奇数分类讨论即可 代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #
展开全文
sunsetcolors
发表于 2020-12-17 22:00:06
Necklace 题目地址: https://ac.nowcoder.com/acm/problem/111227 基本思路: 分情况构造:如果宝石个数中有两个以上的奇数,那么结果一定为,随便输出一个串即可。如果宝石个数中仅有一个奇数,那么结果为所有数的,构造考虑输出个回文串,奇数个数的宝石
展开全文
BNDSBilly
发表于 2020-12-17 17:50:44
如果有两种颜色的珠子个数是奇数个,那么魅力值就是0,任意输出一个串就可以。否则,魅力值一定是颜色个数的最大公约数。 代码如下: #include<bits/stdc++.h> #define lalala printf("lalala\n"); #define N 35 using na
展开全文
Trkly
发表于 2020-12-21 12:31:30
参考代码: #include<bits/stdc++.h> using namespace std; typedef long long ll; int a[205]; char b[1000005]; int main() { int n; scanf("%d"
展开全文
查看本题
查看本题讨论
等你来战
查看全部
牛客小白月赛91
报名截止时间:2024-04-19 21:00
牛客练习赛124
报名截止时间:2024-04-26 21:30
武汉工程大学第六届ACM程序设计竞赛(同步赛)
报名截止时间:2024-04-29 16:00
2024牛客五一集训派对day1
报名截止时间:2024-05-01 17:00
2024牛客五一集训派对day2
报名截止时间:2024-05-02 17:00
2024牛客五一集训派对day3
报名截止时间:2024-05-03 17:00
2024牛客五一集训派对day4
报名截止时间:2024-05-04 17:00
2024牛客五一集训派对day5
报名截止时间:2024-05-05 17:00
牛客周赛 Round 41
报名截止时间:2024-05-05 21:00
第四届上海理工大学程序设计全国挑战赛
报名截止时间:2024-05-12 17:00
牛客周赛 Round 42
报名截止时间:2024-05-12 21:00
扫描二维码,关注牛客
意见反馈
下载牛客APP,随时随地刷题