注意到三天没有博客。
[DAY 12]
复习板子
[DAY 13]
[T1]
数位DP / 二分
[T3]
网络流 + 人类智慧建图
[T2]
加强版的 SCOI2016 萌萌哒
[DAY 14]
哇啊啊啊啊啊啊别样的保龄球大战。
啊啊啊啊我不会数论。
[T1]
不是您家提高模拟赛 T1 放网络流。
考虑拆成 n + m 个点。
由源点到左部点连 (S, i, 2, 0)，由右部点向汇点连 (n + i, T, 2, 0)，中间部分对于 (i, j) 这个格子，连 (i, n + j, 1, w_{i, j})。
跑最大费用最大流，注意如果 cost<0 就不用再跑了，否则会导致费用不优。
#include<bits/stdc++.h>
using namespace std;
const int N = 70, M = 100005, INF = 1e8;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], w[M], idx;
int q[N], d[N], pre[N], incf[N], st[N];
void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++;
}
int spfa()
{
int hh = 0, tt = 1;
memset(d, 0x3f, sizeof d);
memset(incf, 0, sizeof incf);
q[0] = S, d[S] = 0, incf[S] = INF;
while(hh != tt)
{
int u = q[hh ++];
if(hh == N)hh = 0;
st[u] = 0;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(f[i] && d[j] > d[u] + w[i])
{
d[j] = d[u] + w[i];
pre[j] = i;
incf[j] = min(f[i], incf[u]);
if(!st[j])
{
q[tt ++] = j;
if(tt == N)tt=0;
st[j] = 1;
}
}
}
}
return incf[T] > 0 && d[T] < 0;
}
void EK(int &flow, int &cost)
{
flow = cost = 0;
while(spfa())
{
int t = incf[T];
flow += t;
cost += t * d[T];
for(int i = T; i != S; i = e[pre[i] ^ 1])
{
f[pre[i]] -= t;
f[pre[i] ^ 1] += t;
}
}
}
int main()
{
freopen("pick.in", "r", stdin);
freopen("pick.out", "w", stdout);
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
S = 0, T = n + m + 1;
for (int i = 1; i <= n; i ++)add(S, i, 2, 0);
for (int i = 1; i <= n; i ++)
{
for (int j = 1, x; j <= m; j ++)
{
scanf("%d", &x);
add(i, n + j, 1, -x);
}
}
for (int i = 1; i <= m; i ++)add(n + i, T, 2, 0);
int flow, cost;
EK(flow, cost);
printf("%d", -cost);
return 0;
}
[T2]
我不会数论（冷静。
算了推一下：
$\sum{i = 1}^n \sum{d | i} \gcd(d, \frac{i}{d})$
$ = \sum{i = 1}^n \sum{j = 1}^n \gcd(i, j) [ij \leq n]$
由欧拉函数性质2，有：
$= \sum{i = 1}^n \sum{j = 1}^n \sum_{d|i, d|j} \varphi(d) [ij \leq n]$
交换枚举顺序，并令 i \leftarrow \frac{i}{d}, j \leftarrow \frac{j}{d}
$= \sum{d = 1}^n \varphi(d) \sum{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} [ijd ^ 2 \leq n]$
考虑对于固定 i, d，答案应该是什么。
$= \sum{d = 1}^n \varphi(d) \sum{i = 1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{n}{id^2} \rfloor$
这个枚举范围太大了，注意到 i>\sqrt n 的时候，后面没有任何贡献。
于是最终的柿子： $= \sum{d = 1}^{\sqrt n} \varphi(d) \sum{i = 1}^{\lfloor \frac{n}{d ^ 2} \rfloor} \lfloor \frac{n}{id^2} \rfloor$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 320005;
LL n, res;
int primes[N], phi[N], cnt;
bool st[N];
void init(LL n)
{
phi[1] = 1;
for (int i = 2; i <= n; i ++)
{
if (!st[i])
{
primes[cnt ++] = i;
phi[i] = i - 1;
}
for (int j = 0; j < cnt && primes[j] <= n / i; j ++)
{
st[primes[j] * i] = 1;
if (!(i % primes[j]))
{
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
}
int main()
{
freopen("gcd.in", "r", stdin);
freopen("gcd.out", "w", stdout);
scanf("%lld", &n);
LL sqn = sqrt(n);
init(sqn);
for (LL d = 1; d <= sqn; d ++)
{
LL ans = 0;
for (LL l = 1, r; l <= (n / (d * d)); l = r + 1)
{
r = (n / (n / (l * d * d))) / (d * d);
ans += 1LL * (r - l + 1) * (n / (l * d * d));
}
res += 1LL * phi[d] * ans;
//printf("%lld\n", d);
}
printf("%lld", res);
return 0;
}
[T3]
被骗去写块状链表没写出来。
实际上线段树就能做。
注意两个 tag 的顺序，先加减，后取 \max， 而且拥有加减 tag 加入 \max 的 tag 的时候注意 max tag 同时加减。
主要就是这点，还有就是记得下放。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1e9;
struct node
{
int Min, st, add_tag, max_tag;
}tr[N << 2];
void pushup(int u)
{
tr[u].Min = min(tr[u << 1].Min, tr[u << 1 | 1].Min);
tr[u].st = tr[u << 1].st && tr[u << 1 | 1].st;
}
void pushA(int u, int v)
{
tr[u].Min += v;
tr[u].add_tag += v;
if (tr[u].max_tag != -INF)tr[u].max_tag += v;
}
void pushM(int u, int v)
{
if (v > tr[u].Min)
{
tr[u].Min = v;
tr[u].max_tag = v;
}
}
void pushdown(int u)
{
if (tr[u].add_tag)
{
pushA(u << 1, tr[u].add_tag);
pushA(u << 1 | 1, tr[u].add_tag);
tr[u].add_tag = 0;
}
if (tr[u].max_tag != -INF)
{
pushM(u << 1, tr[u].max_tag);
pushM(u << 1 | 1, tr[u].max_tag);
tr[u].max_tag = -INF;
}
}
int n, m, I;
void build(int u, int l, int r)
{
if (l == r)
{
tr[u] = {I, 1, 0, -INF};
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify_add(int u, int l, int r, int L, int R, int v)
{
if (L <= l && r <= R)
{
if (tr[u].Min + v > 0)
{
pushA(u, v);
return;
}
else if (l == r)
{
tr[u].Min = INF;
tr[u].st = 0;
return;
}
tr[u].st = 0;
}
pushdown(u);
int mid = l + r >> 1;
if (L <= mid)modify_add(u << 1, l, mid, L, R, v);
if (mid < R)modify_add(u << 1 | 1, mid + 1, r, L, R, v);
pushup(u);
}
void modify_max(int u, int l, int r, int L, int R, int v)
{
if (L <= l && r <= R)
{
pushM(u, v);
return;
}
pushdown(u);
int mid = l + r >> 1;
if (L <= mid)modify_max(u << 1, l, mid, L, R, v);
if (mid < R)modify_max(u << 1 | 1, mid + 1, r, L, R, v);
pushup(u);
}
int query(int u, int l, int r, int L, int R)
{
if (L <= l && r <= R)return tr[u].st;
pushdown(u);
int mid = l + r >> 1, res = 1;
if (L <= mid)res = res && query(u << 1, l, mid, L, R);
if (mid < R)res = res && query(u << 1 | 1, mid + 1, r, L, R);
return res;
}
int main()
{
freopen("road.in", "r", stdin);
freopen("road.out", "w", stdout);
scanf("%d%d%d", &n, &m, &I);
build(1, 1, n);
int res = 0;
while (m --)
{
int op, l, r, v;
scanf("%d%d%d%d", &op, &l, &r, &v);
if (op == 1 && query(1, 1, n, l, r))
{
modify_add(1, 1, n, l, r, -v);
res ++;
}
else if (op == 2)modify_add(1, 1, n, l, r, v);
else if (op == 3)modify_max(1, 1, n, l, r, v);
}
printf("%d", res);
return 0;
}