2021-08-05
贪心训练。
活动安排&种树：贪心板子题
思维上没有太大难度。
#include<bits/stdc++.h>
using namespace std;
struct NODE
{
int start,end;
};
NODE action[1001];
inline bool COMPARE(NODE,NODE);
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>action[i].start>>action[i].end;
sort(action+1,action+n+1,COMPARE);
int time=action[1].end,answer=1;
for(int i=2;i<=n;i++)
if(action[i].start>=time)
{
answer++;
time=action[i].end;
}
cout<<answer<<endl;
return 0;
}
bool COMPARE(NODE x,NODE y)
{
return x.end<y.end;
}
#include <bits/stdc++.h>
#define maxn 100500
#define man 5500
using namespace std;
struct NODE
{
int l, r, val;
};
NODE e[man];
int n, m, mp[maxn];
inline bool CMP(NODE, NODE);
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
scanf("%d%d%d", &e[i].l, &e[i].r, &e[i].val);
sort(e, e + m, CMP);
for (int i = 0; i < m; ++i)
{
int sum = 0;
for (int j = e[i].l; j <= e[i].r; ++j)
sum += mp[j];
for (int j = e[i].r; sum < e[i].val; --j)
if (!mp[j])
{
mp[j] = 1;
sum++;
}
}
int ans = 0;
for (int i = 1; i <= n; ++i)
ans += mp[i];
printf("%d
", ans);
return 0;
}
inline bool CMP(NODE a, NODE b)
{
return a.r < b.r;
}
2021-08-03
树上莫队、回滚莫队。
树上莫队理解：
把树的括号序分块跑莫队，把树压成一维的。
Luogu P4074 糖果公园
给一棵每个点带有颜色的树，每次询问 (sum _c val_c sum ^{cnt_c} _{i = 1} w_i)。
val：该颜色的价值；
cnt：颜色出现的次数；
w：该颜色出现 i 次后的价值。
先把树变成序列，然后每次添加/删除一个点，这个点的对答案贡献 (val_c imes w_{cnt_{c + 1}})。
扫的过程中起点的子树里的点肯定会被扫两次，但贡献为0。
开一个vis数组，每次扫到点x，就把 (vis_x) 异或上 (1)。
(vis_x = 0) 时点贡献不计。
最后套上昨天的带修莫队。
#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int f[maxn], g[maxn], id[maxn], head[maxn], cnt, last[maxn], dep[maxn], fa[maxn][22], v[maxn], w[maxn],pos[maxn], col[maxn], app[maxn];
int block, index, n, m, q;
bool vis[maxn];
long long int ans[maxn], cur;
struct EDGE
{
int to, nxt;
};
EDGE e[maxn];
int cnt1 = 0, cnt2 = 0;
struct QUERY
{
int l, r, t, id;
bool operator<(const QUERY &b) const
{
return (pos[l] < pos[b.l]) || (pos[l] == pos[b.l] && pos[r] < pos[b.r]) || (pos[l] == pos[b.l] && pos[r] == pos[b.r] && t < b.t);
}
};
QUERY a[maxn], b[maxn];
inline void addEDGE(int x, int y)
{
e[++cnt] = (EDGE){
y, head[x]};
head[x] = cnt;
}
void dfs(int x)
{
id[f[x] = ++index] = x;
for (int i = head[x]; i; i = e[i].nxt)
{
if (e[i].to != fa[x][0])
{
fa[e[i].to][0] = x;
dep[e[i].to] = dep[x] + 1;
dfs(e[i].to);
}
}
id[g[x] = ++index] = x;
}
inline void swap(int &x, int &y)
{
int t;
t = x;
x = y;
y = t;
}
inline int lca(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
if (dep[x] != dep[y])
{
int dis = dep[x] - dep[y];
for (int i = 20; i >= 0; i--)
if (dis >= (1 << i))
dis -= 1 << i, x = fa[x][i];
}
if (x == y)
return x;
for (int i = 20; i >= 0; i--)
{
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
}
return fa[x][0];
}
inline void add(int x)
{
if (vis[x])
cur -= (long long)v[col[x]] * w[app[col[x]]--];
else
cur += (long long)v[col[x]] * w[++app[col[x]]];
vis[x] ^= 1;
}
inline void modify(int x, int t)
{
if (vis[x])
{
add(x);
col[x] = t;
add(x);
}
else
col[x] = t;
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= m; i++)
scanf("%d", &v[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (int i = 1; i < n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
addEDGE(x, y);
addEDGE(y, x);
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &last[i]);
col[i] = last[i];
}
dfs(1);
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
int block = pow(index, 2.0 / 3);
for (int i = 1; i <= index; i++)
{
pos[i] = (i - 1) / block;
}
while (q--)
{
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if (opt == 0)
{
b[++cnt2].l = x;
b[cnt2].r = last[x];
last[x] = b[cnt2].t = y;
}
else
{
if (f[x] > f[y])
swap(x, y);
a[++cnt1] = (QUERY){
lca(x, y) == x ? f[x] : g[x], f[y], cnt2, cnt1};
}
}
sort(a + 1, a + cnt1 + 1);
int L, R, T;
L = R = 0;
T = 1;
for (int i = 1; i <= cnt1; i++)
{
while (T <= a[i].t)
{
modify(b[T].l, b[T].t);
T++;
}
while (T > a[i].t)
{
modify(b[T].l, b[T].r);
T--;
}
while (L > a[i].l)
{
L--;
add(id[L]);
}
while (L < a[i].l)
{
add(id[L]);
L++;
}
while (R > a[i].r)
{
add(id[R]);
R--;
}
while (R < a[i].r)
{
R++;
add(id[R]);
}
int x = id[L], y = id[R];
int llca = lca(x, y);
if (x != llca && y != llca)
{
add(llca);
ans[a[i].id] = cur;
add(llca);
}
else
ans[a[i].id] = cur;
}
for (int i = 1; i <= cnt1; i++)
{
printf("%lld
", ans[i]);
}
return 0;
}
2021-08-02
主要学习带修莫队。
对带修莫队的大概理解：
在普通莫队上用于 DP 类似的思想强行加上一维表示操作时间，询问时也相应加上一维，由 ([l , r]) 变为 ([l , r , time])，坐标移动时也加一维变成
-
([l - 1 , r , time])
-
([l + 1 , r , time])
-
([l , r - 1 , time])
-
([l , r + 1 , time])
-
([l , r , time - 1])
-
([l , r , time + 1])
转移仍保持 (O(1))。
裸题 BZOJ 2120
#include <bits/stdc++.h>
#define N 200007
using namespace std;
struct ques
{
int l, r, num, tim;
} q[N];
int nn[N << 3], n, m, a[N], ans[N], bl[N];
inline bool CMP(ques, ques);
int cp[N], cx[N];
int main()
{
cin >> n >> m;
int cntq = 0, cntr = 0;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int size = pow(n, 2.0 / 3.0), bn = ceil((double)n / size);
char c[26];
for (int i = 1; i <= bn; i++)
for (int j = (i - 1) * size + 1; j <= i * size, j <= n; j++)
bl[j] = i;
for (int i = 1; i <= m; i++)
{
int x, y;
scanf("%s", c);
scanf("%d%d", &x, &y);
if (c[0] == 'Q')
q[++cntq].l = x, q[cntq].r = y, q[cntq].num = cntq, q[cntq].tim = cntr;
if (c[0] == 'R')
{
cp[++cntr] = x;
cx[cntr] = y;
}
}
sort(q + 1, q + 1 + cntq, CMP);
int l = 1, r = 0, time = 0, cnt = 0;
for (int i = 1; i <= cntq; i++)
{
int ql = q[i].l, qr = q[i].r, qt = q[i].tim;
while (l < ql)
{
nn[a[l]]--;
if (nn[a[l]] == 0)
cnt--;
l++;
}
while (l > ql)
{
l--;
nn[a[l]]++;
if (nn[a[l]] == 1)
cnt++;
}
while (r < qr)
{
r++;
nn[a[r]]++;
if (nn[a[r]] == 1)
cnt++;
}
while (r > qr)
{
nn[a[r]]--;
if (nn[a[r]] == 0)
cnt--;
r--;
}
while (time < qt)
{
time++;
int x = cp[time];
if (ql <= x && x <= qr)
{
nn[a[x]]--;
if (nn[a[x]] == 0)
cnt--;
}
swap(a[x], cx[time]);
if (ql <= x && x <= qr)
{
if (nn[a[x]] == 0)
cnt++;
nn[a[x]]++;
}
}
while (time > qt)
{
int x = cp[time];
if (ql <= x && x <= qr)
{
nn[a[x]]--;
if (nn[a[x]] == 0)
cnt--;
}
swap(a[x], cx[time]);
if (ql <= x && x <= qr)
{
if (nn[a[x]] == 0)
cnt++;
nn[a[x]]++;
}
time--;
}
ans[q[i].num] = cnt;
}
for (int i = 1; i <= cntq; i++)
printf("%d
", ans[i]);
}
inline bool CMP(ques a, ques b)
{
if (bl[a.l] != bl[b.l])
return bl[a.l] < bl[b.l];
else
{
if (bl[a.r] == bl[b.r])
return a.tim < b.tim;
else
{
if (bl[a.l] & 1)
return bl[a.r] < bl[b.r];
else
return bl[a.r] > bl[b.r];
}
}
}
另尝试解决 CodeForces 1396E（DP题），但只推导出 (minans = sum ^ n _{i =1} [i
ot = root] sz[i] pmod 2)
(maxans = sum ^n _{i = 1} [i
ot = root] sz[i])
没有思考出如何判断有解，爆零。
看了看题解，推不动如何证明答案有解的充分条件，就放弃了。
whk进度条 40/283
2021-07-31
- [CSP-S2019] 树的重心
题意可得树深度较浅，因此暴力换重儿子。
根据重心定义，对于一个点 (x)，若 (x) 不是重心，则中心要么在重儿子子树内，要么在父亲节点上。
第一次深搜求出儿子树与子树结点数。
第二次深搜换根，对于一条边，以下方的重心可以直接跳倍增，可以跳的条件为上方 (size le dfrac{sum}{2})
对于上方的重心，换根时记录信息，倍增方法相同。
#include <bits/stdc++.h>
#define N 300005
using namespace std;
struct NODE
{
int to, next;
};
int n, T, son[N], s[N], pr[N], son2[N], p[N][18], son3[N], f[N], h[N], cnt, s2[N];
long long int ans;
NODE w[N << 1];
inline int READ();
inline void ADD(int, int);
void DFS(int, int);
inline int JUDGE(int, int);
void DFS2(int, int);
int main()
{
freopen("centroid.in", "r", stdin);
freopen("centroid.out", "w", stdout);
T = READ();
while (T--)
{
memset(h, 0, sizeof(h));
memset(son, 0, sizeof(son));
memset(f, 0, sizeof(f));
memset(pr, 0, sizeof(pr));
cnt = 0, ans = 0, n = READ();
for (int i = 1; i < n; i++)
{
int x = READ(), y = READ();
ADD(x, y);
ADD(y, x);
}
DFS(1, 0);
memcpy(s2, s, sizeof(s2));
memcpy(son3, son, sizeof(son3));
memcpy(f, pr, sizeof(f));
DFS2(1, 0);
printf("%lld
", ans);
}
return 0;
}
inline int READ()
{
int data = 0, w = 1;
char ch = 0;
while (ch != '-' && (ch < '0' || ch > '9'))
ch = getchar();
if (ch == '-')
w = -1, ch = getchar();
while (ch >= '0' && ch <= '9')
data = (data << 1) + (data << 3) + (ch ^ 48), ch = getchar();
return data * w;
}
inline void ADD(int x, int y)
{
++cnt;
w[cnt].to = y;
w[cnt].next = h[x];
h[x] = cnt;
return;
}
void DFS(int x, int fa)
{
s[x] = 1;
pr[x] = fa;
for (int i = h[x]; i; i = w[i].next)
{
int y = w[i].to;
if (y == fa)
continue;
DFS(y, x);
s[x] += s[y];
if (s[y] > s[son[x]])
son2[x] = son[x], son[x] = y;
else if (s[y] > s[son2[x]])
son2[x] = y;
}
p[x][0] = son[x];
for (int i = 1; i <= 17; i++)
p[x][i] = p[p[x][i - 1]][i - 1];
return;
}
inline int JUDGE(int x, int sum)
{
return x * (max(s2[son3[x]], sum - s2[x]) <= sum / 2);
}
void DFS2(int x, int fa)
{
for (int i = h[x]; i; i = w[i].next)
{
int y = w[i].to;
if (y == fa)
continue;
s2[x] = s[1] - s[y];
f[y] = 0;
f[x] = 0;
if (son[x] == y)
son3[x] = son2[x];
else
son3[x] = son[x];
if (s2[fa] > s2[son3[x]])
son3[x] = fa;
p[x][0] = son3[x];
for (int j = 1; j <= 17; j++)
p[x][j] = p[p[x][j - 1]][j - 1];
int b = x;
for (int j = 17; j >= 0; j--)
if (s2[x] - s2[p[b][j]] <= s2[x] / 2)
b = p[b][j];
ans += JUDGE(son3[b], s2[x]) + JUDGE(b, s2[x]) + JUDGE(f[b], s2[x]);
b = y;
for (int j = 17; j >= 0; j--)
if (s2[y] - s2[p[b][j]] <= s2[y] / 2)
b = p[b][j];
ans += JUDGE(son3[b], s2[y]) + JUDGE(b, s2[y]) + JUDGE(f[b], s2[y]);
f[x] = y;
DFS2(y, x);
}
son3[x] = p[x][0] = son[x];
f[x] = pr[x];
for (int j = 1; j <= 17; j++)
p[x][j] = p[p[x][j - 1]][j - 1];
s2[x] = s[x];
return;
}
做题情况
-
Luogu P3943 100pts
-
Luogu P5666 100pts
-
JZYZOJ P3745 20pts