8.11 贝壳找房

1. 给个数组，需要移除k个数使得这个数组的最大公因数为1，求k，不存在输出-1。

答案只可能0或-1

#include <bits/stdc++.h>
using namespace std;
int n, m;
int ans;
int a[100005];

int gcd(int a, int b){
    if(b == 0)
        return a;
    return gcd(b, a%b);
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 0 ; i < n ; i++)
            scanf("%d", &a[i]);
        if(n < 2){
            printf("-1\n");
            continue;
        }
        int g = gcd(a[0], a[1]);
        for(int i = 2 ; i < n ; i++)
            g = gcd(g, a[i]);
        if(g == 1)
            ans = 0;
        else
            ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}

2. 求a mod x = b的解的个数。过了90%，超时了

#include <bits/stdc++.h>
using namespace std;
int n, m;
int ans;
int main()
{
    scanf("%d %d", &n, &m);
    if(n == m){
        printf("inf\n");
        return 0;
    }
    if(n < m){
        printf("0\n");
        return 0;
    }
    if(m == 0){
        for(int i = 1 ; i <= n ; i++){
            if(n % i == 0)
                ans++;
        }
        printf("%d\n", ans);
        return 0;
    }
    int p = n - m;
    for(int i = m ; i <= p ; i++){
        if(n % i == m)
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}

3. 给定矩阵地图，有不可行点。自己选择起点或终点，问最短路径的最大值为多少。

枚举起点bfs算最远距离

#include <bits/stdc++.h>
using namespace std;
int n, m;
int ans;
char s[100][100];
int vis[100][100];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void bfs(int p, int q){
    memset(vis, -1, sizeof(vis));
    queue<pair<int, int>> que;
    que.push(make_pair(p, q));
    vis[p][q] = 0;
    while(!que.empty()){
        int p = que.front().first;
        int q = que.front().second;
        que.pop();
        for(int i = 0 ; i < 4; i++){
            int x = p + dx[i];
            int y = q + dy[i];
            if(x<0||x>=n||y<0||y>=m) continue;
            if(s[x][y]=='#') continue;
            if(vis[x][y]>=0) continue;
            vis[x][y] = vis[p][q] + 1;
            ans = max(ans, vis[x][y]);
            que.push(make_pair(x,y));
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0 ; i < n ; i++)
        scanf("%s", s[i]);
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            if(s[i][j] == '#')
                continue;
            bfs(i, j);
        }
    }
    printf("%d\n", ans);
    return 0;
}

4. 4个人，每个人有一些音乐，给定所有音乐长度，选择若干首播放，并行播放时，最长结束时间和最短结束时间的差最小为多少。

n<=10，二进制枚举

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[5][20];
int b[5][2000];
int ans;

bool ok(int m){
    for(int k = 1 ; k < (1<<n) ; k++){
        for(int j = 0 ; j < 4 ; j++){
            int t = b[j][k];
            bool f = true;
            for(int i = 0; i < 4 ; i++){
                int p = lower_bound(b[i], b[i] + (1<<n), t) - b[i];
                int q = upper_bound(b[i], b[i] + (1<<n), t+m) - b[i];
                if(p == q){
                    f = false;
                    break;
                }
            }
            if(f)
                return true;
        }
    }
    return false;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0 ; i < 4 ; i++){
        for(int j = 0 ; j < n ; j++){
            scanf("%d", &a[i][j]);
        }
    }
    for(int k = 1 ; k < (1<<n) ; k++){
        for(int i = 0 ; i < 4 ; i++){
            int sum = 0;
            for(int j = 0 ; j < n ; j++){
                if(k & (1<<j))
                    sum += a[i][j];
            }
            b[i][k] = sum;
        }
    }
    for(int i = 0 ; i < 4 ; i++){
        sort(b[i], b[i]+ (1<<n));
    }
    int l = 0, r = 600*n;
    while(l < r){
        int mid = (l + r) / 2;
        if(ok(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

#笔试题目##贝壳找房#