每日总结3.27

蓝桥刷题

1.
团建
（树+dfs）
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N],b[N];
int ans;
map<int,vector<int>>m1,m2;
void dfs(int x,int y,int count)
{
  if(a[x]!=b[y])
  {return;}
  ans=max(ans,count+1);
  for(int i=0;i<m1[x].size();i++)
  {
    for(int j=0;j<m2[y].size();j++)
    {
      int a1=m1[x][i];
      int b1=m2[y][j];
      dfs(a1,b1,count+1);
    }
  }
}
signed main()
{
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {cin>>a[i];}
  for(int i=1;i<=m;i++)
  {cin>>b[i];}
  for(int i=0;i<n-1;i++)
  {
    int u,v;
    cin>>u>>v;
    m1[u].push_back(v);
  }
  for(int i=0;i<m-1;i++)
  {
    int u,v;
    cin>>u>>v;
    m2[u].push_back(v);
  }
  dfs(1,1,0);
  cout<<ans;
  return 0;
}

2.
反倍数
#include <iostream>
using namespace std;
#define int long long
signed main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,a,b,c;
  int ans=0;
  cin>>n>>a>>b>>c;
  for(int i=1;i<=n;i++)
  {
    if(i%a!=0&&i%b!=0&&i%c!=0)
    {
      ans++;
    }
  }
  cout<<ans;
  return 0;
}

3.
迷宫

#include<bits/stdc++.h>
using namespace std;
//typedef long long LL;
//const int N = 100010;
char mp[15][15]; //地图存放 
bool vis[15][15];//判断该路是否走过 
int cnt = 0;     //记录走出人数 
void dfs(int x, int y){//从(x,y)点出发的人 
    if(x<1 || x>10 || y < 1 || y > 10){ //如果超出范围，则走出 
        cnt=cnt+1;//走出的人数加一 
        return;
    }
    
    if(vis[x][y]) return;//如果该点走过则返回，用以判断是否绕圈 
    vis[x][y] = 1;       //没走过则标记走过 
    
    if(mp[x][y] == 'U'){
        int dx = x - 1;
        int dy = y;
        dfs(dx,dy);
    }else if(mp[x][y] == 'D'){
        int dx = x + 1;
        int dy = y;
        dfs(dx,dy);
    }else if(mp[x][y] == 'L'){
        int dx = x;
        int dy = y - 1;
        dfs(dx,dy);
    }else if(mp[x][y] == 'R'){
        int dx = x;
        int dy = y + 1;
        dfs(dx,dy);
    }
}

int main(){
    for(int i = 1; i <= 10; i++){
        for(int j = 1; j <= 10; j++){
            cin >> mp[i][j];
        }
    }
    for(int i = 1; i <= 10; i++){
        for(int j = 1; j <= 10; j++){
            dfs(i,j); //枚举每个点作为起点 
            memset(vis,0,sizeof vis);//换起点时初始化vis数组 
        }
    }
    cout << cnt;
return 0;}

4.全部都有的子序列
（哈希表）

#include <bits/stdc++.h> 
using namespace std;
set<int> p;
int a[100005];
int st[100005];
int num=100005;
signed main()
{
  int n;
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    p.insert(a[i]);
  }
  int len=p.size();
  for(int i=0;i<n;i++)
  {
    int ans=0;
    memset(st,0,sizeof(st));
    for(int j=i;j<n;j++)
    {
      if(st[a[j]]++==0)
      {
        ans++;
      }
      if(ans==len)
      {
        num=min(num,j-i+1);
        break;
      }
    }
  }
  cout<<num;
  return 0;
}

力扣刷题

300.
最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int dp[10100];
        dp[0]=1;
        int cnt=1;
        for(int i=1;i<nums.size();i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                    cnt=max(dp[i],cnt);
                }
            }
        }
        return cnt;
        
         }
};