Yugu p1012 spelling +p1019 word Solitaire (string)

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