差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:20200801比赛记录 [2020/08/05 14:32]
zars19
+++ 2020-2021:teams:wangzai_milk:20200801比赛记录 [2020/08/05 21:19] (当前版本)
infinity37 [D - Fake News]
@@ 行 73: / 行 73: @@
 树链剖分可以搞，辅助一堆记录的登西。给所有点加距离即加上 $dep_x$ 和 $dep_{自己}$ ，然后需要减去 $dep_{lca}$ 这个是树剖的部分。我们从 $x$ 到根权值 $+1$ ，等到询问 $y$ 时查询 $y$ 到根的和即可。如果需要置零则查询一下，同样记录一个变量，减去当前的值。
+<hidden><code c++>
+#include <bits/stdc++.h>
+using namespace std;
+const int N = 5e4+5;
+typedef long long ll;
+int n,m;
+struct E {
+	int nxt,to;
+}e[N<<1];
+int head[N],tot;
+void add(int x,int y) {
+	e[++tot].to = y;e[tot].nxt = head[x];head[x] = tot;
+}
+ll tr[N<<2];
+int lazy[N<<2];
+ll decn[N];
+ll adding,times;
+void build(int p,int l,int r) {
+	tr[p] = 0;
+	lazy[p] = 0;
+	if (l==r)return;
+	int mid = (l+r)>>1;
+	build(p<<1,l,mid);
+	build(p<<1|1,mid+1,r);
+}
+void Push_Down(int p,int l,int r) {
+	if (l==r||!lazy[p])return;
+	int mid = (l+r)>>1;
+	tr[p<<1] += (ll)(mid-l+1)*lazy[p];
+	tr[p<<1|1] += (ll)(r-mid)*lazy[p];
+	lazy[p<<1]+=lazy[p];
+	lazy[p<<1|1]+=lazy[p];
+	lazy[p] = 0;
+}
+void Update(int p,int l,int r,int a,int b,int c) {
+	Push_Down(p,l,r);
+	if (l>=a && r<=b) {
+		tr[p] += (ll)(r-l+1)*c;
+		lazy[p] += c;
+		return;
+	}
+	int mid = (l+r)>>1;
+	if (a <= mid)Update(p<<1,l,mid,a,b,c);
+	if (b > mid)Update(p<<1|1,mid+1,r,a,b,c);
+	tr[p] = tr[p<<1]+tr[p<<1|1];
+}
+ll Getans(int p,int l,int r,int a,int b) {
+	Push_Down(p,l,r);
+	if (l>=a && r<=b) return tr[p];
+	ll ans = 0;
+	int mid = (l+r)>>1;
+	if (a <= mid)ans+=Getans(p<<1,l,mid,a,b);
+	if (b > mid)ans+=Getans(p<<1|1,mid+1,r,a,b);
+	return ans;
+}
+int size[N],son[N],w[N],top[N],fa[N],cnt,id[N],dpt[N];
+void dfs1(int x,int f) {
+	fa[x] = f;
+	size[x] = 1;
+	dpt[x] = dpt[f]+1;
+	son[x] = 0;
+	for (int i = head[x];i;i=e[i].nxt) {
+		if (e[i].to == f)continue;
+		dfs1(e[i].to,x);
+		size[x]+=size[e[i].to];
+		if (size[e[i].to] > size[son[x]])son[x] = e[i].to;
+	}
+}
+void dfs2(int x,int tp) {
+	top[x] = tp;
+	w[x] = ++cnt;
+	id[cnt] = x;
+	if (son[x])dfs2(son[x],tp);
+	for (int i = head[x];i;i=e[i].nxt)
+		if (e[i].to!=son[x] && e[i].to!=fa[x])
+			dfs2(e[i].to,e[i].to);
+}
+void update(int x,int y,int z)
+{
+    while (top[x]!=top[y])
+    {
+        if (dpt[top[x]]<dpt[top[y]])swap(x,y);
+        Update(1,1,n,w[top[x]],w[x],z);
+        x = fa[top[x]];
+    }
+    if (dpt[x]<dpt[y])swap(x,y);
+    Update(1,1,n,w[y],w[x],z);
+}
+ll getans(int x,int y)
+{
+	ll ans = 0;
+    while (top[x]!=top[y])
+    {
+        if (dpt[top[x]]<dpt[top[y]])swap(x,y);
+        ans+=Getans(1,1,n,w[top[x]],w[x]);
+        x = fa[top[x]];
+    }
+    if (dpt[x]<dpt[y])swap(x,y);
+    ans+=Getans(1,1,n,w[y],w[x]);
+    return ans;
+}
+ll getFx(int x) {
+	ll ans = decn[x]-(ll)times*dpt[x];
+	ans = ans+adding;
+	ans = ans+getans(1,x);
+	return ans;
+}
+void init() {
+	memset(head,0,sizeof(head));
+	memset(decn,0,sizeof(decn));
+	tot = cnt = 0;
+	adding = times = 0;
+}
+int main()
+{
+	int cas;
+	scanf("%d",&cas);
+	while(cas--) {
+		init();
+		scanf("%d%d",&n,&m);
+		int x,y;
+		for (int i = 1;i<n;i++) {
+			scanf("%d%d",&x,&y);
+			add(x,y);add(y,x);
+		}
+		build(1,1,n);
+		dfs1(1,0);
+		dfs2(1,1);
+		while (m--) {
+			int opt;
+			scanf("%d",&opt);
+			if (opt == 1) {
+				scanf("%d%d",&x,&y);
+				adding += y-dpt[x];
+				times++;
+				update(1,x,2);
+			} else if(opt == 2) {
+				scanf("%d",&x);
+				ll tmp = getFx(x);
+				if (tmp > 0) decn[x]-=tmp;
+			} else {
+				scanf("%d",&x);
+				printf("%lld\n",getFx(x));
+			}
+		}
+	}
+}
+</code></hidden>
+\\
 ===== D - Fake News =====
 满足 $1$ 到 $n$ 的平方和是完全平方数的只有 $1$ 和 $24$ ，打表之后可以猜得到。
+===== H - Dividing =====
+经过一顿推导之后可以发现对于同一个$k$，可能的$n$只有$k$的倍数和$k$的倍数$+1$，（包括1），所以要求的就是下面这个式子
+$N+\sum_{i=2}^{K}\lfloor \frac{N}{i}\rfloor +\lfloor\frac{N+1}{i}\rfloor+1$
+此公式针对$K\leq N$的情况，如果$K>N$，可以使$K=N$，最后答案中加$K-N$，因为对于大于$N$的$k$，每个$k$都仅有$1$这个数字可以作为一组。
+上面这个式子用数论分块可以直接求，另外要注意一些特殊情况。
+<hidden><code c++>
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+const ll mod = 1e9+7;
+ll getans(ll n,ll k) {
+	ll ans = 0;
+	for (ll l = 1,r;l<=k;l=r+1) {
+		r = min(k,n/(n/l));
+		ans += (r-l+1)*(n/l)%mod;
+		ans = ans%mod;
+	}
+	return ans;
+}
+int main()
+{
+	ll ans = 0;
+	ll n,k;
+	scanf("%lld%lld",&n,&k);
+	if (k >= n) {
+		ans += k-n+2;
+		k = n-1;
+	}
+	ans += getans(n,k)+getans(n-1,k)+k-n;
+	ans = (ans%mod+mod)%mod;
+	printf("%lld\n",ans);
+	return 0;
+}
+</code></hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具