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;
} 