4245

Scaramouche
WNx
cjh2023
UNIT

yxc的小迷妹
6666633
InsiApple

Paul_8

2010

Cfpl_Lmd

YzWait2-4YsZth
Henry1

## 简证

假设cnt < n



## 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 5010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[N];
int d[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u, int faside)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u;

for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j, i);
low[u] = min(low[u], low[j]);
if (dfn[u] < low[j])
is_bridge[i] = is_bridge[i ^ 1] = true;
}
else if (i != (faside ^ 1)) low[u] = min(low[u], dfn[j]);
}

if (dfn[u] == low[u])
{
++ dcc_cnt;
int y;
do {
y = stk[top -- ];
id[y] = dcc_cnt;
} while (y != u);
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
}

tarjan(1, -1);

for (int i = 0; i < idx; i ++ )
if (is_bridge[i])
d[ id[ e[i] ] ] ++ ;

int cnt = 0;
for (int i = 1; i <= dcc_cnt; i ++ )
if (d[i] == 1)
cnt ++ ;

printf("%d\n", (cnt + 1) >> 1);

return 0;
}


#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 5010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[N];
int d[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u, int faside)
{
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u;

for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j, i);
low[u] = min(low[u], low[j]);
if (dfn[u] < low[j])
is_bridge[i] = is_bridge[i ^ 1] = true;
}
else if (i != (faside ^ 1)) low[u] = min(low[u], dfn[j]);
}

if (dfn[u] == low[u])
{
++ dcc_cnt;
int y;
do {
y = stk[top -- ];
id[y] = dcc_cnt;
} while (y != u);
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
}

tarjan(1, -1);

for (int i = 1; i < idx; i ++ )
if (is_bridge[i])
d[ id[ e[i] ] ] ++ ;

int cnt = 0;
for (int i = 1; i <= dcc_cnt; i ++ )
if (d[i] == 1)
cnt ++ ;

printf("%d\n", (cnt + 1) >> 1);

return 0;
}


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


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


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


## 思路

抽象一下题意 我们发现问题是：



$于是我们有了最初想法 O（n^2）$

//暴力枚举
for (i = 1 ~ n)
for (j = 1 ~ n)
if (i * j == n)
//操作

我们可以发现

(对于正整数n 大于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}那样$

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


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


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


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


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