[数据结构与算法]蓝桥杯·寒假百校真题大联赛（研究生/大学A组）（第1期） 蓝桥

题目1:

思路分析：

没必要想什么bfs dfs 直接暴力就行

代码实现：

int ch(int x,int y){
  if(x==0||x==11) return 1;
  if(y==0||y==11) return 1;
  return 0;
}
void solve(){
    char a[11][11];
      int n=10;
      for(int i=1;i<=n;i++){
        for(int j=1;j<=10;j++){
          cin>>a[i][j];
        }
      }
      int vis[11][11];
      int ans=0;
      for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
          memset(vis,0,sizeof vis);
            int x=i;int y=j;
          while(1){
          if(ch(x,y))  {ans++;break;}
          if(vis[x][y]) break;
          vis[x][y]=1;
          if(a[x][y]=='U'){
            x--;
          }
          else if(a[x][y]=='D'){
            x++;
          }
          else if(a[x][y]=='L'){
            y--;
          }
          else if(a[x][y]=='R'){
            y++;
          }
          }
        }
      }
      cout<<ans<<endl;
}

?题目2:

思路分析：

一道简单的bfs暴搜的题目 状态可以通过字符串模拟可达?

int ans=0;
void solve(){
    int d[4]={-2,-1,1,2};
    string s="12345678 ";
    string ss="87654321 ";
    queue<string>q;
    set<string>st;
    q.push(s);
    st.insert(s);
    while (!q.empty()) {
        ans++;
        int t=q.size();
        for(int i=0;i<t;i++){
            string now=q.front();
            q.pop();
            if(now==ss){return;}
            int pos=now.find(" ");
            for(int i=0;i<4;i++){
                string now1=now;
                swap(now1[pos],now1[(pos+d[i]+9)%9]);
                if(st.count(now1)){continue;}
                else {
                    st.insert(now1);
                    q.push(now1);
                }
            }
        }
    }
}

题目3:

?

?思路分析：

其实就是一个动态规划吧orz

#include <stdio.h>
#include <string.h>
#include<math.h>
#define N 256
int f(const char* s1, const char* s2)
{
    int a[N][N];
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int i,j;
    
    memset(a,0,sizeof(int)*N*N);
    int max = 0;
    for(i=1; i<=len1; i++){
        for(j=1; j<=len2; j++){
            if(s1[i-1]==s2[j-1]) {
                a[i][j] =a[i-1][j-1]+1; 
                if(a[i][j] > max) max = a[i][j];
            }
        }
    }
    
    return max;
}

int main()
{
    printf("%d\n", f("abcdkkk", "baabcdadabc"));
    printf("%d\n", f("aaakkkabababa", "baabababcdadabc"));
    printf("%d\n", f("abccbaacbcca", "ccccbbbbbaaaa"));    
    printf("%d\n", f("abcd", "xyz"));
    printf("%d\n", f("ab", "ab"));
    return 0;
}

题目4

?

思路分析：

括号问题可以栈模拟也可以dfs?

int ans=0;string s;
int pos=0;
int dfs(){
    int cnt=0;
    while (pos<s.length()) {
        if(s[pos]=='('){
            pos++;
            cnt+=dfs();
        }
        else if(s[pos]=='|'){
            ans=max(ans,cnt);
            cnt=0;
            pos++;
        }
        else if(s[pos]==')'){
            pos++;
            break;
        }
        else {
            cnt++;
            pos++;
        }
    }
    ans=max(ans,cnt);
    return ans;
}
void solve(){
    cin>>s;
    ans=dfs();
    cout<<ans<<endl;
    
}

?题目5:

思路分析：

如果n个数的最大公约数不为1那么就为inf

一个完全背包的板子题?

代码实现：

int a[maxn];
void solve(){
    int n;cin>>n;
    cin>>a[1];int f=a[1];
    for(int i=2;i<=n;i++) {cin>>a[i];f=_gcd(a[i],f);}
    if(f!=1) cout<<"INF";
    else{
        int dp[10005];memset(dp,0,sizeof dp);dp[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j+a[i]<10005;j++){
                if(dp[j]) dp[j+a[i]]=1;
            }
        }
        int ans=0;
        for(int i=1;i<=10000;i++){
            if(!dp[i]) {ans++;}
        }
        cout<<ans<<endl;
    }
}

?题目6:

?思路分析：

一个简单的二分法

int n,k;int h[maxn];int w[maxn];
int ch(int x){
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=(h[i]/x*w[i]/x);
    }
    return ans>=k;
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>h[i]>>w[i];
    int l=0;
    int r=10000000;
    while(l<r){
        int mid=l+r+1>>1;
        if(ch(mid)){
            l=mid;
        }
        else r=mid-1;
    }
    cout<<r<<endl;
}

?