首页 > Necklace
头像 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 基本思路: 分情况构造:如果宝石个数中有两个以上的奇数,那么结果一定为,随便输出一个串即可。如果宝石个数中仅有一个奇数,那么结果为所有数的,构造考虑输出个回文串,奇数个数的宝石 展开全文
头像 BJUT071010
发表于 2020-12-17 17:50:44
如果有两种颜色的珠子个数是奇数个,那么魅力值就是0,任意输出一个串就可以。否则,魅力值一定是颜色个数的最大公约数。 代码如下: #include<bits/stdc++.h> #define lalala printf("lalala\n"); #define N 3 展开全文
头像 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(&quo 展开全文

等你来战

查看全部