B、华华对月月的忠诚
辗转相减法（更相减损术），gcd与斐波那契数列的关系。
先介绍下辗转相除法之外的辗转相减法。gcd(a,b)如果a>b那么会等于gcd(a-b,b)。如果b>a那么会等于gcd(a,b-a)，如果a，b相等此时就是gcd。
还有一个结论就是 gcd(2a,2b) = 2gcd(a,b)
多用于高精度，代替复杂的取模运算。
先给结论 题目要求的答案 证明如下：
import math a,b,n = map(int,input().split()) print(math.gcd(a,b))
C、Game
给定n，每次可以把n拆分成两个数相乘，第二个人对拆分出来的数操作，谁最先不能操作，也就是集合内全是素数，就输了。
那么题目意思很简单，就是问你这个数，分解成若干素数相乘的形式，无论你是这么拆分，最后分解出来一定是同一个素数积。
所以直接对素数分解即可，遇到一个素数拆分一次。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int ans[N];
bool isprime(int x) {
if (x < 2) return false;
for (int i = 2; i <= sqrt(x); ++i) {
if (x % i == 0) return false;
}
return true;
}
int countprime(int x) {
int ret = 0;
for (int i = 2; i <= sqrt(x); ++i) {
if (isprime(i) && x % i == 0) {
ret = 1 + ans[x / i];
break;
}
}
return ret;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 4; i <= n; ++i) {
ans[i] = countprime(i);
}
//printf("%d\n", ans[n]);
if (ans[n] & 1) puts("Johnson");
else puts("Nancy");
return 0;
}
D、挖沟
……迪杰斯特拉模板题，真就全模板，一点都没改，如果还不会就是数据结构没认真听课或者还没学图，最小生成树还是要会滴。
具体证明网上很多，这就不展开。
//kruskal 适用于稀疏图 O(n+m*log2(m))
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 1e5 + 7; //节点
const int M = 5e5 + 7; //路径数
int n, m;
struct Edge {
int u, v, w;
bool operator <(const Edge tmp) const {
return w < tmp.w;
}
}edge[M];
int father[N];
ll ans = 0; //最小生成树的花费和
int find(int root) {
int son = root;
while (root != father[root])
root = father[root];
while (son != root) { //路径压缩
int temp = father[son];
father[son] = root;
son = temp;
}
return root;
}
void kruskal() {
for (int i = 1; i <= m; i++) {
int u = edge[i].u, v = edge[i].v;
int x = find(u), y = find(v);
if (x != y) {
father[x] = y;
ans += edge[i].w;
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++i)
father[i] = i;
for (int i = 1; i <= m; ++i)
edge[i].u = read(), edge[i].v = read(), edge[i].w = read();
sort(edge + 1, edge + 1 + m);
kruskal();
printf("%lld\n", ans);
return 0;
} E、签到题
和我一样一开始照着出题人描述补函数的举起爪子，我最后TLE吐了，才发现，如果按照他思路，时间爆炸了……
直接改掉函数，模拟就行了，其实也可以用线段树，当然更快，模拟更轻松一点就是了。）看来被set大常数卡的不轻，当然也感谢出题人仁慈没给极限数据……
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
int a[maxn];
int opt, x, y;
set<pair<int, int> >P;
int main(){
int n, L;
cin >> n >> L;
int ans = 0;
while (n--){
cin >> opt >> x >> y;
if (opt == 1){
if (P.find(make_pair(x, y)) != P.end()) continue;
P.insert(make_pair(x, y));
for (int i = x; i <= y; i++){
a[i]++;
if (a[i] == 1) ans++;
}
}
else if (opt == 2){
if (P.find(make_pair(x, y)) == P.end()) continue;
P.erase(make_pair(x, y));
for (int i = x; i <= y; i++){
a[i]--;
if (a[i] == 0) ans--;
}
}
else{
cout << ans << endl;
}
}
return 0;
}
E正解、线段树写法
区间更新，区间查询，如果区间值大于1，正解求区间长度即可。否则就要去左右子树累加区间值大于1的区间长度，线段树操作
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
const int MAXN = 100010;
struct Node {
int l, r;
//ll lazy;
ll sum;
} segTree[MAXN << 2];
void build(int i, int l, int r) {
segTree[i].l = l;
segTree[i].r = r;
if (l == r) {
//scanf("%lld", &segTree[i].sum);
return;
}
int mid = l + r >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
//segTree[i].sum = segTree[i << 1].sum + segTree[i << 1 | 1].sum;
}
void push_up(int i) {
ll tmp = min(segTree[i << 1].sum, segTree[i << 1 | 1].sum);
segTree[i].sum += tmp;
segTree[i << 1].sum -= tmp;
segTree[i << 1 | 1].sum -= tmp;
}
void push_down(int i) {
if (segTree[i].sum) {
segTree[i << 1].sum += segTree[i].sum;
segTree[i << 1 | 1].sum += segTree[i].sum;
segTree[i].sum = 0;
}
}
void add(int i, int l, int r, ll v) {
if (segTree[i].l >= l && segTree[i].r <= r) {
segTree[i].sum += v;
return;
}
push_down(i);
int mid = segTree[i].l + segTree[i].r >> 1;
if (mid >= l) add(i << 1, l, r, v);
if (mid < r) add(i << 1 | 1, l, r, v);
push_up(i);
}
ll query(int i, int l, int r) {
ll res = 0;
if (segTree[i].l >= l && segTree[i].r <= r)
if (segTree[i].sum > 0)
res += r - l + 1;
else if (l != r) {
int mid = segTree[i].l + segTree[i].r >> 1;
push_down(i);
res += query(i << 1, l, mid);
res += query(i << 1 | 1, mid + 1, r);
push_up(i);
}
return res;
}
int main() {
int n, m, op;
scanf("%d%d", &n, &m);
build(1, 1, m);
int l, r;
while (n--) {
op = read(), l = read(), r = read();
if (op == 1)
add(1, l, r, 1);
else if (op == 2)
add(1, l, r, -1);
else
printf("%lld\n", query(1, 1, m));
}
return 0;
} 
京公网安备 11010502036488号