洛谷100题DAY8

36.P1416 攻击火星

此题找出规律即可

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{cin >> n;cout << max(0, n - 2);return 0;
}

37.P1551 亲戚

并查集模板题目

两个人如果使亲戚就合并建立联系，最后进行查找即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, q, x, y, p[N];
int find(int x)
{if(p[x] != x)p[x] = find(p[x]);return p[x];
}
int main()
{cin >> n >> m >> q;for(int i = 1; i <= N; i ++)p[i] = i;for(int i = 1; i <= m; i ++){cin >> x >> y;p[find(x)] = find(y);}for(int i = 1; i <= q; i ++){cin >> x >> y;if(find(x) == find(y))cout << "Yes" << '\n';else cout << "No" << '\n';}return 0;
}

38.P1579 哥德巴赫猜想（升级版）

对于此题而言，使用普通的质数判断每一个数会超时，故使用埃氏筛法（将质数倍数的数全部筛去），一共只有三个数，我们循环枚举两个数，第三个数用和确定下即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> prime;
int n;
bool vis[N];
int main()
{cin >> n;vis[0] = vis[1] = true;for(int i = 2; i <= n; i ++){if(!vis[i]){for(int j = 2 * i; j <= n; j += i){vis[j] = true;}}}for(int i = 2; i <= n; i ++){if(!vis[i])prime.push_back(i);}for(auto i : prime){for(auto j : prime){int k = n - i - j;if(k > 0 && !vis[k]){cout << i << ' ' << j << ' ' << k;return 0;}}}
}

39.P1604 B进制星球

使用高精度加法等转化即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2009;
int B, a[N], b[N];
char s[N];
const char ch[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main()
{cin >> B;cin >> s + 1;int n = strlen(s + 1);for(int i = 1; i <= n; i ++){if('0' <= s[i] && s[i] <= '9')a[i] = s[i] - '0';else a[i] = s[i] - 'A' + 10;}reverse(a + 1, a + 1 + n);cin >> s + 1;int m = strlen(s + 1);for(int i = 1; i <= m; i ++){if('0' <= s[i] && s[i] <= '9')b[i] = s[i] - '0';else b[i] = s[i] - 'A' + 10;}reverse(b + 1, b + 1 + m);for(int i = 1; i <= max(n, m) + 1; i ++){a[i] += b[i];if(a[i] >= B){a[i + 1] += a[i] / B;a[i] %= B;}}bool flag = false;//删去前导0for(int i = max(n, m) + 1; i >= 1; i --){if(a[i])flag = true;if(flag)cout << ch[a[i]];} return 0;
}        

40.P1599 结算日

分析出最优的方法为一旦金额足够就去还债这样走的步数最小

#include<bits/stdc++.h>
using namespace std;
int n, x, sum, pos;
int main()
{cin >> n;int ans = n;for(int i = 1; i <= n; i ++){cin >> x;sum += x;if(sum >= 0 && pos){ans += (i - pos) * 2;pos = 0; }else if(sum < 0 && !pos){pos = i;}}cout << ans;return 0;
}