Summary of training competition (Lao Li's collection of questions)

1. Lao Li intercepted a telegram , Telegrams consist of characters （ There may be spaces ）, He hopes to extract useful information from these strings .

for example ：a1b23c456d007890 We can extract 1, 23, 456, 7890 common 4 A digital .

Now? , He got a length up to 1000 String , Please help him extract all the numbers .

Input

There are many sets of data in this question .
Enter a string S.

Output

Output all the extracted numbers , Two adjacent numbers are separated by a space .

Output blank lines when no numbers are included

Be careful , You can't output a number with a leader 0.

 Input ：
u1s1qs
1a2b3c4d5e006d
a1b23c456d007890
2333
kur1su
alan0233
 Output ：
1 1
1 2 3 4 5 6
1 23 456 7890
2333
1
233

Ideas ： I first thought of string arrays , Then it's gone, and then it's saved when it comes to numbers , Pay attention to the lead 0( Note in the example that it must be a legal number ）

If there are other ideas, they can be found below “ Pat me ”（ Leaving a message. ）

Time complexity ：O（n^2)

c++ Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int nu(string s1)
{
	int x = 0;
	for(int i=0;i<s1.size();i++)x = x * 10 + (s1[i] - '0');
	return x;
}
int main()
{
	string s;
	while (cin >> s)
	{
		int i = 0, w = 0, j, count1 = 0;
		string a1[1000];
		for (i = 0; i <s.size(); i++)
		{
			if (s[i] >= '0' && s[i] <= '9')
			{
				string a;
				for (j = i; s[j] >= '0' && s[j] <= '9'; j++)a += s[j];
				i = j;
				a1[w++] = a;
			}
		}
		for (int i = 0; i < w; i++)
			cout << nu(a1[i]) << " ";
		cout << '\n';
	}
	return 0;
}

2.

describe

Lao Li saw that the monk was a rude man , I also know a few big characters . see ？ I was admitted to the monk . Lao Li gave the monk a string , Ask the monk to write the full arrangement of this string . The length of the string should not exceed 100.

Input

Multi group input . Enter one string at a time .

Output

Each input will output the full arrangement of the string .

Each character is separated by a space .

The output dictionary order is ASCII Code order .

 Examples ：
123 

 Output ：
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

Train of thought ：dfs+ enumeration

c++ Code ：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
string s;
char st[N];
bool used[N];
void dfs(int u)
{
    if(u>=n)// You can output the answer 
    {
        for(int i=0;i<n;i++)
        {
            printf("%c ",st[i]);
        }
        printf("\n");
        return ;
    }
    for(int i=0;i<n;i++)
    {
        if(!used[i])
        {
            st[u]=s[i];// Mark 
            used[i]=true;
            dfs(u+1);// Enumerate the next 
            st[u]='0';// recovery 
            used[i]=false;
        }
    }
}
int main()
{
    while(cin>>s)
    {
        sort(s.begin(),s.end());// Before enumerating, sort it to ensure that the order is from small to large 
        n=s.size();
        dfs(0);
    }
    return 0;
}

Train of thought two ：next_permutation+ enumeration

Overview and analysis ：
      STL Two algorithms for calculating permutation and combination relationship are provided , Namely next_permutation and prev_permutation. First of all, we have to understand what is “ next ” Permutation and combination , What is? “ Previous ” Permutation and combination . Consider a sequence of three characters {a,b,c}.

        This sequence has six possible permutations ：abc,acb,bac,bca,cab,cba. These permutations are based on less-than Operators do dictionary order (lexicographical) Sort . in other words ,abc Number one , Because every element is smaller than the following elements .acb This is a permutation and combination , Because it's fixed a( The smallest element in the sequence ) The new combination made later .

      In the same way , Those fixed b( The second smallest element in the sequence ) And make an arrangement , Will precede those fixed in order c And make an arrangement . With bac and bca For example ,bac stay bca Before , Because the order ac Less than sequence ca. face bca, We can say that the previous permutation is bac, And the next permutation is cab. Sequence abc No, “ Previous ” Permutation and combination ,cba No, “ After a ” Permutation and combination .
     next_permutation() Will get [first,last) The next permutation of the marked sequence , If there is no next permutation , Then return to false; Otherwise return to true. There are two versions of this algorithm . The commonly used version uses the less-than Operator to determine the next permutation .
c++ Code ：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string line;
    while(cin>>line)
    {
      sort(line.begin(),line.end());// Full Permutation 
      for(int i=0;i<line.size();i++)
      cout<<line[i]<<" ";
      puts("");
      while(next_permutation(line.begin(),line.end()))
      {
       for(int i=0;i<line.size();i++)
         cout<<line[i]<<" ";
         puts("");
      }
    }
    return 0;
}

3.

describe

In order to improve the shooting accuracy of the whole army , A shooting competition was held , Use four grades （ copper , silver , gold , Platinum ） To measure the accuracy of soldiers , Those who perform well in the competition can be promoted . All new contestants start with the bronze medal Group , As long as they get perfect results in the game , They will be promoted to the next higher group . You can even promote participants many times in the same competition .

Tell you the number of people at each level at the beginning of the game and the number of people at each level after the game , Ask for a silver medal in this game , gold medal , How many people have platinum promoted .

Input

Input consists of four lines , Each row contains 0..1,000,000 Two integers in the range . The first row specifies the number of bronze medals before and after the competition .

The second row specifies the number of silver medals before and after the competition . The third row specifies the number of gold medal participants before and after the competition . The last row specifies the number of platinum before and after the competition .

Output

Please output three lines , Each line contains an integer . The first line should include the number of participants who have been promoted from bronze to silver .

The second line should contain the number of participants who were promoted from silver to gold . The last line should contain the number of participants who were promoted from gold to platinum .

 Examples ：
1 2
1 1
1 1
1 2
 Output ：
1
1
1

Ideas ：

c++ Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int bef[4],aft[4];
int main(){
	for(int i=0;i!=4;++i)cin>>bef[i]>>aft[i];
	cout<<aft[1]+aft[2]+aft[3]-bef[1]-bef[2]-bef[3]<<endl<<aft[2]+aft[3]-bef[2]-bef[3] 
    <<endl<<aft[3]-bef[3]<<endl;
	return 0;
}

4.

describe

Lao Li plays games with his old friend Chu Yunfei （ It's rare not to fight ）, Their initial integral is 1.

The winner can multiply his score by (K The square of ), And the loser can also multiply K.

They had a great time , So I forgot how long I played , even to the extent that K How much is it and the number of rounds of the game N Forgot to .

Now give them their final points a,b, Is there a positive integer K、N Satisfy such integral , Judge whether their game results are credible .

Input

Enter an integer in the first line T（ Represents the number of samples ）

Next T Group example

One row for each sample , Enter two positive integers a,b（0<a,b<=1e9）

Output

Output T That's ok

Output the results corresponding to one sample line

If the result is credible , Output Yes

otherwise , Output No

 Examples ：
6
2 4
75 45
8 8
16 16
247 994
1000000000 1000000
 Output ：
Yes
Yes
Yes
No
No
Yes

Ideas ： Each round of the game will be multiplied by k^3  simulation

c++ Code ：

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    long long a,b;
    cin>>n;
    while(n--)
   {
        cin>>a>>b;
        long long t=cbrt(a*b);
        long long x=a/t;
        long long y=b/t;
        if((x*x*y==a)&&(x*y*y==b))// It needs a good understanding 
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

5.

as everyone knows , Lao Li robbed the equipment of Chu Yunfei's three battalions during the war . Brother Yunfei didn't come here less . Lao Li had to play a trick , Claimed to have distributed all the equipment n A soldier , Let Chu Yunfei go and get back by himself . Yama likes to see , It's hard for a kid to get around . The soldier gave Chu Yunfei the equipment only after he met his requirements . Yes n Individuals in x On the shaft , Everyone's coordinate is an integer , Chu Yunfei shuttles on the axis , There is only one commodity to exchange , Everyone has a demand or supply for this kind of material , If delta[i] Positive number , It means that this person wants to supply delta[i] The number of , If it's a negative number , It means that this person needs −delta[i] Goods and materials , Guarantee delta The sum of is nonnegative , At first Chu Yunfei was 0 Location , There is no material in hand , Every second he can go left or right 1 Unit distance , If he is in the same position with someone , Can meet his requirements （ This process does not take time ）, The number of each transaction is determined by Chu Yunfei , Of course, he can't give more than the amount of materials in his hand , Chu Yunfei can hold as many materials as he wants during walking , To a person's position , You can also choose not to trade with it , Finally, Chu Yunfei needs to meet the following two points

1: Chu Yunfei must meet everyone's needs

2: It must end in the last person's position .

Ask how much time it will take at least .

Input

Enter an integer in the first line n (1 ≤ n ≤ 300)

Second line input n Elements pos[i]( 1 ≤ pos[i] ≤ 1050), Indicates everyone's position

In the third line, enter n Elements delta[i](-1050≤ delta[i] ≤ 1050) Express everyone's needs

Guarantee pos Monotone increasing ,delta The sum of is nonnegative

Output

Output an integer indicating the minimum time required

 Examples ：
5
3 14 15 92 101
-3 2 3 -3 1
 Output ：
143;

Ideas ： simulation + enumeration

res Represents the current material status ,res+delta[i] Represents the next material status ,ans It means spending time

If res<0,res+delta[i]>=0 It means that the current material is insufficient to meet the current needs , Materials must be added , And the materials at the next location can supply the needs , We need to fill the gap in the front , Once in a while , Take both the journey and the time 2;

If res<0,res+delta[i]<0 It means that materials are in great need at present , Materials must be added , The materials at the next location are insufficient , Just keep going ;

If res>=0,res+delta[i]<0 It means that the current material is enough , But the next location needs a lot , You need to mark the value of the next location , Because the material in the next place is very scarce ;

Time complexity ：O(n^2)

c++ Code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n,ans;
int pos[N],delta[N];
int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ )cin>>pos[i];
    for (int i = 1; i <= n; i ++ )cin>>delta[i];
    int res=0,x=0;
    for (int i = 1; i <= n; i ++ )
    {
        if(res<0&&res+delta[i]>=0)ans+=(pos[i]-x)*2;
        if(res>=0&&res+delta[i]<0)x=pos[i];
        ans+=pos[i]-pos[i-1];
        res+=delta[i];
    }
    return cout<<ans,0;
}

6.

The war ahead is tight , Lao Li has a new plan , Prepare to ask the brigade commander for instructions . The telegram of Lao Li and the brigade commander adopts a kind of password encryption , Now please complete one of the links . Give me two strings A,B. find B For the first time in A The position in the string .

Input

Multi group input .

Enter two strings for each group A,B, The string does not contain spaces and will not be longer than 1000.

Output

Output a number , Table is B String in A The position subscript of the first occurrence of the string .

If it does not match, output -1.

 Examples ：
123
3
123
4
 Output 
2
-1

Ideas ：KMP string matching

Time complexity ：o(n^2)

c++ Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10, M = 3e6 + 10;
int n, m;
char p[N], s[M];
int ne[N];

int main()
{
    std::ios::sync_with_stdio(false);
    while (cin >> s + 1 >> p + 1)
    {
        bool flag = true;
        int n = strlen(p + 1), m = strlen(s + 1);
        for (int i = 2, j = 0; i <= n; i++)
        {
            while (j && p[i] != p[j + 1])j = ne[j];
            if (p[i] == p[j + 1])j++;
            ne[i] = j;
        }
        for (int i = 1, j = 0; i <= m; i++)
        {
            while (j && s[i] != p[j + 1])j = ne[j];
            if (s[i] == p[j + 1])j++;
            if (j == n)
            {
                flag = false;
                printf("%d\n", i - n);
                break;
            }
        }
        if (flag)printf("-1\n");
    }
    return 0;
}

Train of thought two ：STL Method

#include <bits/stdc++.h>
using namespace std;

int main()
{
  std::ios::sync_with_stdio(false);
    string s1,s2;
    while(cin>>s1>>s2)
    {
        int index=s1.find(s2);
        if(index<=s1.size())
        cout<<index<<endl;
        else cout<<"-1"<<endl;
    }
    return 0;
}

7.

describe

The war between the two armies has reached a white hot stage , The enemy drove out the tanks . As a senior general trained by Huangpu Military Academy , Chu Yunfei certainly knows how to deal with , He let his men set up an anti tank array . It is a kind of sharp tower pile .

Input

Multi group input .

Enter two lines at a time .

The first line is the character of the tower , The second row represents the height of the tower .

Output

See Example .

 Input ：
*
4
 Output ：
    *
   * *
  * * *
 * * * *

Time complexity ：O(n^2)

c++ Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
  std::ios::sync_with_stdio(false);
   char c;
   int num;
   while(cin>>c>>num)
   {
       for(int i=0;i<num;i++)
       {
            for(int j=i;j<num-1;j++)cout<<" ";
            for(int k=0;k<=i;k++) cout<<" "<<c;
            cout<<endl;
       }
   }
}

8.

describe

Although Lao Li didn't go to school , But it still counts , Now give Lao Li some figures , Let Lao Li judge the size .

Input

A single set of inputs .

Every time you enter several data , The number of data will not exceed 100 individual , Each data does not exceed 2 Of 32 Power .

Each data is separated by a newline .

Output

Output one line .

If the sum of all the previous numbers is smaller than the last number , Please export <

If the sum of all the previous numbers is greater than the last number , Please export >

If the sum of all the previous numbers is equal to the last number , Please export =

 Examples ：
1 2 3
 Output 
=

Time complexity ：o(n)

c++ Code

#include <bits/stdc++.h>

using namespace std;
double a[110],b[110];
int x=0;
char c;
int main()
{

     while(cin>>a[x])x++;
        for(int i=0; i<x; i++)
        {
            b[i]=a[i]+b[i-1];
        }

    if(b[x-2]==a[x-1])puts("=");
    else if(b[x-2]<a[x-1])puts("<");
    else puts(">");

    return 0;
}

9.

The Eighth Route Army and the Japanese who had a good life were fighting on the front . Both sides laid mines , The equipment of the Eighth Route Army is relatively backward , So the mines they laid were relatively small , use 'o' Express , In contrast, the enemy's mines are used 'O' Express , Two small mines can produce the power of a big one , But it won't explode directly , When two big mines are placed in the attachment, they will explode . Lao Li is the commander , Now he wants to know the final situation of mines in a row , As Lao Li's doge Military division , Can you work it out ？
Input

Multi group input .

Enter one string at a time . The string length is less than 100.

Each set of input is only made up of 'O' and 'o' form .

Output

Output the final result .

 Examples ：
ooooOOOoOoo
 Output ;
Oo

Ideas ： simulation

Time complexity ：O(n)

c++ Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
typedef long long ll;
stack<char> p;
int main()
{
    string s;
    while(cin>>s)
    { 
        char s1[N];int xx=0;
        for (int i = 0; i < s.size(); i ++ )
        {
            if(p.empty())p.push(s[i]);
            else
            {
                if(s[i]=='o'&&p.top()=='o')
                {
                    p.pop();
                    s[i]='O';
                    i--;
                }
                else if(s[i]=='O'&&p.top()=='O')p.pop();
                else p.push(s[i]);
            }
        }
       while(p.size())
       {
           s1[xx++]=p.top();
            p.pop();
       }
       for(int i=xx-1;i>=0;i--)
       printf("%c",s1[i]);
       printf("\n");
    }
    return 0;
}

java The code will be changed later

It's too late today. , If you have any questions, please leave a message below

Ouch, ouch