UPC 2022 summer personal training game 07 (part)

B: LH String... String ( String basis )

Carelessness ：

give n individual The length is d String , find n The length of the longest common string of strings

Ideas ：

Search all strings of a string , Length from large to small , Check whether the string appears in other strings

#include<bits/stdc++.h>
using namespace std;
   
#define fi first
#define se second 
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e6+10;
const int pp = 1e9 + 7;
typedef pair<int,int>PII;
  
int n,m;
string str;
string s[31];
int max1;
 
bool judge()
{
    
    for(int i=2;i<=n;i++)
    {
    
        if(s[i].find(str)==string::npos) return 0;
    }
    return 1;
}
 
int main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    int len=s[1].size();
     
    for(int i=0;i<len;i++)
    {
    
        for(int j=1;j<=len-i;j++)
        {
    
            str=s[1].substr(i,j);
            if(judge())
            {
    
                max1=max(max1,(int)str.size());
            }
        }
    }
     
    cout<<max1;       
}

D. Bloody vanguard (BFS)

Carelessness ：

Give some starting points , Each point can infect four adjacent points per second , Give some questions , Ask these questions about the earliest infection time

Ideas :

bfs Solve the minimum number of steps

#include<bits/stdc++.h>
using namespace std;
   
#define fi first
#define se second 
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e6+10;
const int pp = 1e9 + 7;
typedef pair<int,int>PII;
  
  
PII p;
int n,m,x,y;
int f[501][501];
bool f1[501][501];
int a,b;
int dir[4][2]={
    0,1,0,-1,1,0,-1,0};
queue<PII>qu;
  
int main()
{
    
    scanf("%d %d %d %d",&n,&m,&a,&b);
      
    for(int i=1;i<=a;i++)
    {
    
        scanf("%d %d",&p.fi,&p.se);
        qu.push(p);
        f1[p.fi][p.se]=1;
    }
      
    while(!qu.empty())
    {
    
        PII t=qu.front();
        qu.pop();
          
        for(int i=0;i<4;i++)
        {
    
            int xx=t.fi+dir[i][0];
            int yy=t.se+dir[i][1];
            if(xx<1||yy<1||xx>n||yy>m) continue;
            if(f1[xx][yy]) continue;
            f1[xx][yy]=1;
            f[xx][yy]=f[t.fi][t.se]+1;
            qu.push({
    xx,yy});
        }
    }
      
    for(int i=1;i<=b;i++)
    {
    
        scanf("%d %d",&x,&y);
        printf("%d\n",f[x][y]);
    }       
}

K: Swap Hats( thinking )

Carelessness :

Give the original three numbers and the exchanged three numbers , Ask exchange 1e18 Whether it can become the target sequence after times ;

Ideas :

There are only three cases when three numbers are changed to the target sequence , One exchange , Exchange twice and Exchange 0 Time , When swapped an even number of times (0,2) The remaining even operations can maintain this sequence , But if you need to exchange 1 Switch to the original sequence for the second time , The remaining odd operations cannot maintain the sequence ;

The number of exchanges listed is 1 A combination of

#include<bits/stdc++.h>
using namespace std;
   
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e6+10;
const int p = 1e9 + 7;
 
char a1,b1,c1;
char a2,b2,c2;
 
int main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
      
    cin>>a1>>b1>>c1>>a2>>b2>>c2; 
     
    if(a1==a2&&b1==c2&&c1==b2||b1==b2&&a1==c2&&c1==a2||c1==c2&&a1==b2&&b1==a2)
    {
    
        cout<<"No";
    }
    else
    {
    
        cout<<"Yes";
    } 
}

Q: Mooo Moo( Completely backpack )

Carelessness :

The original intention is very long , No more

Ideas :

We can first calculate the individual sound volume sequence of each pasture according to the given total sound volume sequence , Then the remaining problem turns into a complete knapsack problem , The sound of each type of cow is taken as the volume of the object ,1 As a contribution , Minimum number of cows per capacity

The recursive equation is given below
$dp[j]=min(dp[j],dp[j-w[i]]+1)$

#include<bits/stdc++.h>
using namespace std;
   
#define fi first
#define se second 
typedef long long ll;
const int N = 1e5;
const int NN = 1e6+10;
const int pp = 1e9 + 7;
typedef pair<int,int>PII;
 
int m,n;
int w[31];
int a[101],b[101];
int dp[N+10];// Sound is consumption , Number is contribution 
// The cow is unlimited , Completely backpack 
ll sum;
 
int main()
{
    
    cin>>n>>m;
     
    for(int i=1;i<=m;i++) cin>>w[i];
     
     
    for(int i=1;i<=n;i++)
    {
    
        cin>>a[i];
        if(a[i-1]) b[i]=a[i]-(a[i-1]-1);
        else b[i]=a[i];
    }// Find out the single voice sequence 
     
     
    for(int i=1;i<=N;i++) dp[i]=1e9+10;//dp Array initialization 
     
    for(int i=1;i<=m;i++)
    {
    
        for(int j=w[i];j<=N;j++)
        {
    
            dp[j]=min(dp[j],dp[j-w[i]]+1);
        }
    }
     
     
    for(int i=1;i<=n;i++)
    {
    
        sum+=dp[b[i]];
    }
     
    cout<<sum;
     
}

V: Mismatched Socks( thinking )

Carelessness :

give n Kind of Socks with different styles , Every sock The number of k , Find out the maximum number of pairs of different socks

Ideas :

Since socks should be combined in pairs , We might as well divide socks into two categories , If the number of one kind of socks exceeds half of the total , So this kind of socks is the first kind , All other socks as the second category , It is necessary to pair with this kind of socks to ensure the maximum number of combinations , But if none of the socks is more than half the total , Half of our socks can be used as the first class , Half as the second kind , Different sock combinations with others , The contribution to the answer is sum/2;

#include<bits/stdc++.h>
using namespace std;
   
#define fi first
#define se second 
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e6+10;
const int pp = 1e9 + 7;
typedef pair<int,int>PII;
int n;
ll a[1001];
ll sum,max1,ans;
 
int main()
{
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i],max1=max(max1,a[i]);
    if(max1*2>=sum) ans=sum-max1;
    else ans=sum/2;
    cout<<ans;     
}

W: It Takes Three

Carelessness :

Give three rectangles , Ask if you can form a square ;

Ideas :

Look at examples :

8 2
1 6
7 6

It needs to meet that one side of the rectangle on the upper side is equal to the sum of the two sides on the lower side, and the sum of the sides is equal to the long side of the rectangle on the upper side

We just need to choose which rectangle is on the top (3), Confirm his status , Is it horizontal or vertical (2), Then determine the state of the following two rectangles (4), Can simulate all situations , The position of the following two rectangles does not affect the type of situation ;

So there is 24 In this case

Just try

#include<bits/stdc++.h>
using namespace std;
   
#define fi first
#define se second 
typedef long long ll;
const int N = 1e6+10;
const int NN = 1e6+10;
const int pp = 1e9 + 7;
typedef pair<int,int>PII;
 
ll n,m;
 
int a[4][2],b[4][2];
 
bool solve()
{
    
    // 1  Make the top rectangle  1  cross 
     
    if(a[1][0]==a[2][0]+a[3][0]&&a[1][0]==a[1][1]+a[2][1]&&a[2][1]==a[3][1]) return 1;//aaa
    if(a[1][0]==b[2][0]+b[3][0]&&a[1][0]==a[1][1]+b[2][1]&&b[2][1]==b[3][1]) return 1;//abb
    if(a[1][0]==a[2][0]+b[3][0]&&a[1][0]==a[1][1]+a[2][1]&&a[2][1]==b[3][1]) return 1;//aab
    if(a[1][0]==a[2][0]+a[3][0]&&a[1][0]==a[1][1]+b[2][1]&&b[2][1]==a[3][1]) return 1;//aba
     
     // 1  Make the top rectangle  1  vertical 
     
    if(b[1][0]==a[2][0]+a[3][0]&&b[1][0]==b[1][1]+a[2][1]&&a[2][1]==a[3][1]) return 1;//baa
    if(b[1][0]==b[2][0]+b[3][0]&&b[1][0]==b[1][1]+b[2][1]&&b[2][1]==b[3][1]) return 1;//bbb
    if(b[1][0]==a[2][0]+b[3][0]&&b[1][0]==b[1][1]+a[2][1]&&a[2][1]==b[3][1]) return 1;//bab
    if(b[1][0]==b[2][0]+a[3][0]&&b[1][0]==b[1][1]+b[2][1]&&b[2][1]==a[3][1]) return 1;//bba
     
    // 2  Make the top rectangle  2  cross 
     
    if(a[2][0]==a[1][0]+a[3][0]&&a[2][0]==a[2][1]+a[1][1]&&a[1][1]==a[3][1]) return 1;// aaa
    if(a[2][0]==b[1][0]+b[3][0]&&a[2][0]==a[2][1]+b[1][1]&&b[1][1]==b[3][1]) return 1;// bab
    if(a[2][0]==a[1][0]+b[3][0]&&a[2][0]==a[2][1]+a[1][1]&&a[1][1]==b[3][1]) return 1;// aab
    if(a[2][0]==b[1][0]+a[3][0]&&a[2][0]==a[2][1]+b[1][1]&&b[1][1]==a[3][1]) return 1;// baa
	
	// 2  Make the top rectangle  2  vertical  
	
    if(b[2][0]==a[1][0]+a[3][0]&&b[2][0]==b[2][1]+a[1][1]&&a[1][1]==a[3][1]) return 1;// aba
    if(b[2][0]==b[1][0]+b[3][0]&&b[2][0]==b[2][1]+b[1][1]&&b[1][1]==b[3][1]) return 1;// bbb
    if(b[2][0]==a[1][0]+b[3][0]&&b[2][0]==b[2][1]+a[1][1]&&a[1][1]==b[3][1]) return 1;// abb
    if(b[2][0]==b[1][0]+a[3][0]&&b[2][0]==b[2][1]+b[1][1]&&b[1][1]==a[3][1]) return 1;// bba
     
   // 3  Make the top rectangle  3  cross  
     
    if(a[3][0]==a[2][0]+a[1][0]&&a[3][0]==a[3][1]+a[2][1]&&a[2][1]==a[1][1]) return 1;// aaa
    if(a[3][0]==b[2][0]+b[1][0]&&a[3][0]==a[3][1]+b[2][1]&&b[2][1]==b[1][1]) return 1;// bba
    if(a[3][0]==a[2][0]+b[1][0]&&a[3][0]==a[3][1]+a[2][1]&&a[2][1]==b[1][1]) return 1;// baa
    if(a[3][0]==b[2][0]+a[1][0]&&a[3][0]==a[3][1]+b[2][1]&&b[2][1]==a[1][1]) return 1;// aba
     
     // 3  Make the top rectangle  3  vertical 
     
    if(b[3][0]==a[2][0]+a[1][0]&&b[3][0]==b[3][1]+a[2][1]&&a[2][1]==a[1][1]) return 1;// aab
    if(b[3][0]==b[2][0]+b[1][0]&&b[3][0]==b[3][1]+b[2][1]&&b[2][1]==b[1][1]) return 1;// bbb
    if(b[3][0]==a[2][0]+b[1][0]&&b[3][0]==b[3][1]+a[2][1]&&a[2][1]==b[1][1]) return 1;// bab
    if(b[3][0]==b[2][0]+a[1][0]&&b[3][0]==b[3][1]+b[2][1]&&b[2][1]==a[1][1]) return 1;// abb
     
     
    return 0;
}
 
int main()
{
    
    for(int i=1;i<=3;i++)
    {
    
        cin>>a[i][0]>>a[i][1];
        b[i][0]=a[i][1];
        b[i][1]=a[i][0];    
    }
     
    if(solve()) cout<<"1";
    else cout<<"0";
}