#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 500010;
int n, m;
LL w[N];
struct Node
{
int l, r;
LL sum;
LL d;
}tr[N << 2];
LL gcd(LL a, LL b)
{
return b? gcd(b, a % b) : a;
}
void pushup(Node& u, Node& l, Node& r)
{
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r)
{
LL b = w[r] - w[r - 1];
tr[u] = {l, r, b, b};
}
else
{
tr[u].l = l, tr[u].r = r;
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, LL v)
{
if (tr[u].l == x && tr[u].r == x)
{
LL b = tr[u].sum + v;
tr[u] = {x, x, b, b};
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
Node query(int u, int l, int r)
{
//if (l > r) return {0};
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);
build(1, 1, n);
char op[2];
int l, r;
LL v;
while (m -- )
{
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q')
{
auto left = query(1, 1, l);
Node right({0, 0, 0, 0});
if (l + 1 <= r) right = query(1, l + 1, r);
printf("%lld\n", abs(gcd(left.sum, right.d)));
}
else
{
scanf("%lld", &v);
modify(1, l, v);
if (r + 1 <= n) modify(1, r + 1, -v);
}
}
return 0;
}
活动打卡代码
AcWing 246. 区间最大公约数
活动打卡代码
AcWing 245. 你能回答这些问题吗
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 5e5 + 10;
int n, m, w[N];
struct Node
{
int l, r, sum, lsum, rsum, tsum;
}tr[N << 2];
void pushup(Node& u, Node& l, Node& r)
{
u.sum = l.sum + r.sum;
u.lsum = max(l.lsum, l.sum + r.lsum);
u.rsum = max(r.rsum, r.sum + l.rsum);
u.tsum = max(max(l.tsum, r.tsum), l.rsum + r.lsum);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
else
{
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = (tr[u].l + tr[u].r) >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
int k, x, y;
while (m -- )
{
scanf("%d%d%d", &k, &x, &y);
if (k == 1)
{
if (x > y) swap(x, y);
printf("%d\n", query(1, x, y).tsum);
}
else modify(1, x, y);
}
return 0;
}
活动打卡代码
AcWing 1275. 最大数
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
struct Node
{
int l, r, v;
}tr[N << 2];
int n, m, p, last;
void pushup(int u)
{
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) return;
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r)
{
int trl = tr[u].l, trr = tr[u].r;
if (l <= trl && trr <= r) return tr[u].v;
int mid = (trl + trr) >> 1;
int v = 0;
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
void modify(int u, int x, int v)
{
int trl = tr[u].l, trr = tr[u].r;
if (trl == x && trr == x) tr[u].v = v;
else
{
int mid = (trl + trr) >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
int main()
{
scanf("%d%d", &m, &p);
build(1, 1, m);
char op[2];
int x;
while (m -- )
{
scanf("%s%d", op, &x);
if (*op == 'Q')
{
last = query(1, n - x + 1, n);
printf("%d\n", last);
}
else
{
++ n;
modify(1, n, ((LL)last + x) % p);
}
}
return 0;
}
分享
$恰饭时刻题解$
思路
抽象一下题意 我们发现问题是：
把n拆分为两个正整数之积
使这两个正整数之和减2最小
$于是我们有了最初想法 O（n^2）$
//暴力枚举
for (i = 1 ~ n)
for (j = 1 ~ n)
if (i * j == n)
//操作
我们可以发现
只要找到n的第一个因数
那么第二个也随之确定
并且 我们发现
那个比较小的因数 一定<=sqrt(n)
(对于正整数n 大于sqrt_n的因数只有一个)
我们只需要枚举这个就可以
稳定$O(\sqrt{n})$
结论：最接近$O(\sqrt{n})$的两个因数之和最小
(接下来是数学证明 可以不看)
$设n = ab(a != b), n = c^2$
$(a + b)^2 - (2c)^2$
$= a^2 + 2ab + b^2 - 4c^2$
$= a^2 - 2ab + b^2$
$= (a - b)^2 >= 0$
$所以 (a + b)^ 2 >= (2c)^2$
$即 a + b >= 2c$
$这样 我们就证明了2个\sqrt{n}之和最小$
$因为 (a - b)^2 >= 0$
$所以 随着a与b差的增大 (a - b)^2单调递增（无论a, b怎么取）$
$即 a + b 越来越大 （c不变）$
证毕
$大概描述一下 当n确定时 横坐标为a, 纵坐标为a + b$
$样子大概是y = (x - \sqrt{n})^2 + 2\sqrt{n}那样$
但是要强调 并不是平方级增长 我只是描述这个趋势
最坏$O(\sqrt{n})$
AC代码
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n, ans;
int main()
{
scanf("%lld", &n);
LL sqrt_n = sqrt(n);
for (LL i = sqrt_n; i; -- i)
{
LL j = n / i;
if (i * j == n)
{
ans = i + j - 2;
break;
}
}
printf("%lld\n", ans);
return 0;
}
活动打卡代码
AcWing 238. 银河英雄传说
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 30010;
int m;
int p[N], d[N], cnt[N];
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
scanf("%d", &m);
for (int i = 1; i < N; i ++ )
{
p[i] = i;
cnt[i] = 1;
}
while (m -- )
{
char op[2];
int a, b;
scanf("%s%d%d", , &a, &b);
if (op[0] == 'M')
{
int pa = find(a), pb = find(b);
if (pa != pb)
{
d[pa] = cnt[pb];
p[pa] = pb;
cnt[pb] += cnt[pa];
}
}
else
{
int pa = find(a), pb = find(b);
if (pa == pb) printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
else puts("-1");
}
}
return 0;
}
活动打卡代码
AcWing 237. 程序自动分析
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <unordered_map>
using namespace std;
const int N = 2000010;
int n, m, T;
int p[N];
unordered_map<int, int> S;
struct Query
{
int x, y, e;
}query[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int get(int x)
{
if (!S.count(x)) S[x] = ++ n;
return S[x];
}
int main()
{
scanf("%d", &T);
while (T -- )
{
n = 0;
S.clear();
scanf("%d", &m);
for (int i = 1; i <= m; i ++ )
{
int x, y, e;
scanf("%d%d%d", &x, &y, &e);
query[i] = {get(x), get(y), e};
}
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 1; i <= m; i ++ )
if (query[i].e)
{
int pa = find(query[i].x), pb = find(query[i].y);
p[pa] = pb;
}
bool success = true;
for (int i = 1; i <= m; i ++ )
if (!query[i].e)
{
int pa = find(query[i].x), pb = find(query[i].y);
if (pa == pb)
{
success = false;
break;
}
}
if (success) puts("YES");
else puts("NO");
}
return 0;
}
活动打卡代码
AcWing 1252. 搭配购买
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 10010;
int n, m, k;
int p[N], v[N], w[N], f[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d%d", &n, &k, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);
while (k -- )
{
int a, b;
scanf("%d%d", &a, &b);
int pa = find(a), pb = find(b);
if (pa != pb)
{
v[pb] += v[pa];
w[pb] += w[pa];
p[pa] = pb;
}
}
for (int i = 1; i <= n; i ++ )
if (p[i] == i)
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d\n", f[m]);
return 0;
}
活动打卡代码
AcWing 1250. 格子游戏
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 40010;
int p[N];
int n, m, res;
int get(int a, int b)
{
return a * n + b;
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n * n; i ++ ) p[i] = i;
for (int i = 1; i <= m; i ++ )
{
int x, y;
char d;
cin >> x >> y >> d;
-- x, -- y;
int a = get(x, y), b;
if (d == 'D') b = get(x + 1, y);
else b = get(x, y + 1);
int pa = find(a), pb = find(b);
if (pa == pb)
{
res = i;
break;
}
p[pa] = pb;
}
if (res) printf("%d\n", res);
else puts("draw");
return 0;
}
活动打卡代码
AcWing 368. 银河
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 100010, M = 600010;
int n, m;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], timestamp;
int id[N], scc_cnt, siz[N];
int stk[N], top, dist[N];
bool in_stk[N];
typedef long long LL;
void add(int h[], int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], low[j]);
}
if (dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
siz[scc_cnt] ++ ;
id[y] = scc_cnt;
in_stk[y] = false;
} while (y != u);
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(hs, -1, sizeof hs);
for (int i = 1; i <= n; i ++ ) add(h, 0, i, 1);
while (m -- )
{
int t, a, b;
scanf("%d%d%d", &t, &a, &b);
if (t == 1) add(h, a, b, 0), add(h, b, a, 0);
else if (t == 2) add(h, a, b, 1);
else if (t == 3) add(h, b, a, 0);
else if (t == 4) add(h, b, a, 1);
else add(h, a, b, 0);
}
tarjan(0);
bool success = true;
for (int i = 0; i <= n; i ++ )
{
for (int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if (a == b)
{
if (w[j] > 0)
{
success = false;
break;
}
}
else add(hs, a, b, w[j]);
}
if (!success) break;
}
if (success)
{
for (int i = scc_cnt; i; i -- )
for (int j = hs[i]; ~j; j = ne[j])
{
int k = e[j];
dist[k] = max(dist[k], dist[i] + w[j]);
}
LL res = 0;
for (int i = 1; i <= scc_cnt; i ++ ) res += (LL)dist[i] * siz[i];
printf("%lld\n", res);
}
else puts("-1");
return 0;
}
活动打卡代码
AcWing 1175. 最大半连通子图
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <unordered_set>
using namespace std;
const int N = 100010, M = 2000010;
int n, m, mod;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int id[N], scc_cnt, siz[N];
int stk[N], top;
bool in_stk[N];
int f[N], g[N];
typedef long long LL;
void add(int h[], int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], low[j]);
}
if (low[u] == dfn[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
siz[scc_cnt] ++ ;
id[y] = scc_cnt;
in_stk[y] = false;
} while (y != u);
}
}
int main()
{
scanf("%d%d%d", &n, &m, &mod);
memset(h, -1, sizeof h);
memset(hs, -1, sizeof hs);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(h, a, b);
}
for (int i = 1; i <= n; i ++ )
if (!dfn[i]) tarjan(i);
unordered_set<LL> S;
for (int i = 1; i <= n; i ++ )
for (int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
LL hash = a * 1000000ll + b;
if (a != b && !S.count(hash))
{
add(hs, a, b);
S.insert(hash);
}
}
for (int i = scc_cnt; i; i -- )
{
if (!f[i])
{
f[i] = siz[i];
g[i] = 1;
}
for (int j = hs[i]; ~j; j = ne[j])
{
int k = e[j];
if (f[k] < f[i] + siz[k])
{
f[k] = f[i] + siz[k];
g[k] = g[i];
}
else if (f[k] == f[i] + siz[k])
g[k] = (g[k] + g[i]) % mod;
}
}
int maxf = 0, sum = 0;
for (int i = 1; i <= scc_cnt; i ++ )
if (f[i] > maxf)
{
maxf = f[i];
sum = g[i];
}
else if (f[i] == maxf) sum = (sum + g[i]) % mod;
printf("%d\n", maxf);
printf("%d\n", sum);
return 0;
}
