当前位置:网站首页>Yugu p1012 spelling +p1019 word Solitaire (string)
Yugu p1012 spelling +p1019 word Solitaire (string)
2022-07-06 13:51:00 【zjsru_ Beginner】
Topic 1 ( Spell numbers )
Equipped with nn A positive integer a_1 \dots a_na1…an, Join them in a row , Adjacent numbers end to end , Make up the largest integer .
Input format
The first line has an integer , Represents the number of numbers nn.
The second line has nn It's an integer , Indicates the given nn It's an integer a_iai.
Output format
A positive integer , Represents the largest integer
I/o sample
Input
3 13 312 343
Output
34331213
Input
4 7 13 4 246
Output
7424613
Their thinking
The question is relatively simple , It is a problem of string splicing to get the largest integer . Change the code bool cmp Judgment is important , The judgment is a+b and b+a String size , instead of a and b The size of the string , Because judging alone a and b The number spliced by the size of may not be the maximum ( for example 521 and 52), And then main In the function sort Sort , Output results .
The code is as follows
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n;
string s[20];
bool cmp(string a, string b) {
return a + b > b + a;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
sort(s+1, s + n+1 , cmp);
for (int i = 1; i <= n; i++){
cout << s[i];
}
return 0;
}
The operation results are as follows :
Topic two ( The word chain )
The word Solitaire is a game similar to the idiom Solitaire we often play , Now we know a set of words , And given a starting letter , Ask for the longest beginning with this letter “ dragon ”( Every word is at most “ dragon ” There are two times ), When two words are connected , The overlapping parts are combined into one part , for example beast
and astonish
, If connected into a dragon, it becomes beastonish
, In addition, two adjacent parts cannot have a containment relationship , for example at
and atide
Can't be connected .
Input format
The first line of input is a single integer nn Indicates the number of words , following nn Each line has a word , The last line of input is a single character , Express “ dragon ” The first letter . You can assume that “ dragon ” There must be .
Output format
Just output the longest... Starting with this letter “ dragon ” The length of .
I/o sample
Input
5 at touch cheat choose tact a
Output
23
Their thinking
This question should pay attention to three points :1. Use each word twice at most
2. Words can be left unfinished , The longer the length, the better
3. The less overlap, the better , The longer the Dragon
There are two functions in the following code , among xianjie Function the connection of two strings , from 1 Start , Connect the two shortest strings , Returns the length of the smallest overlap , stay solve Search in function , Get the maximum string length .
The code is as follows
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a[20];
int n,length=0;
string s[20];
int xianjie(string s1,string s2){
for(int i=1;i<min(s1.length(),s2.length());i++){ // Length of overlap
int flag=1;
for(int j=0;j<i;j++)
if(s1[s1.length()-i+j]!=s2[j]) // Check whether the strings are equal
flag=0;
if(flag==true)
return i;
}
return 0;
}
void solve(string str,int length1){
length=max(length1,length); // Maximum length
for(int i=0;i<n;i++){
if(a[i]>=2) // The number of uses must be less than 2
continue;
int c=xianjie(str,s[i]); // Length of overlap
if(c>0){ // To search
a[i]++;
solve(s[i],length1+s[i].length()-c);
a[i]--;
}
}
}
int main(){
cin>>n;
for(int i=0;i<=n;i++){
a[i]=0;
cin>>s[i];
}
solve(' '+s[n],1); //xianjie The overlap of the function needs to be less than the shortest length -1, So add a meaningless full length from the front ‘ ’. This is mandatory xianjie The function compares the last bit
cout<<length;
}
The operation results are as follows
big data 201 tyx
边栏推荐
- Miscellaneous talk on May 27
- Have you encountered ABA problems? Let's talk about the following in detail, how to avoid ABA problems
- Wei Pai: the product is applauded, but why is the sales volume still frustrated
- The latest tank battle 2022 full development notes-1
- Difference and understanding between detected and non detected anomalies
- Nuxtjs quick start (nuxt2)
- [the Nine Yang Manual] 2020 Fudan University Applied Statistics real problem + analysis
- 实验四 数组
- 【九阳神功】2022复旦大学应用统计真题+解析
- Implementation of count (*) in MySQL
猜你喜欢
C language to achieve mine sweeping game (full version)
SRC挖掘思路及方法
1. First knowledge of C language (1)
Cookie和Session的区别
Poker game program - man machine confrontation
canvas基础1 - 画直线(通俗易懂)
记一次猫舍由外到内的渗透撞库操作提取-flag
[au cours de l'entrevue] - Comment expliquer le mécanisme de transmission fiable de TCP
[during the interview] - how can I explain the mechanism of TCP to achieve reliable transmission
[面試時]——我如何講清楚TCP實現可靠傳輸的機制
随机推荐
Thoroughly understand LRU algorithm - explain 146 questions in detail and eliminate LRU cache in redis
MySQL中count(*)的实现方式
[面試時]——我如何講清楚TCP實現可靠傳輸的機制
Leetcode.3 无重复字符的最长子串——超过100%的解法
7-3 构造散列表(PTA程序设计)
Safe driving skills on ice and snow roads
C语言入门指南
3. C language uses algebraic cofactor to calculate determinant
FAQs and answers to the imitation Niuke technology blog project (III)
Miscellaneous talk on May 27
SRC mining ideas and methods
6. Function recursion
【毕业季·进击的技术er】再见了,我的学生时代
Programme de jeu de cartes - confrontation homme - machine
使用Spacedesk实现局域网内任意设备作为电脑拓展屏
【黑马早报】上海市监局回应钟薛高烧不化;麦趣尔承认两批次纯牛奶不合格;微信内测一个手机可注册俩号;度小满回应存款变理财产品...
7-7 7003 组合锁(PTA程序设计)
The latest tank battle 2022 - Notes on the whole development -2
[中国近代史] 第九章测验
. Net6: develop modern 3D industrial software based on WPF (2)