====== 2020牛客暑期多校训练营（第七场） ======

[[https://ac.nowcoder.com/acm/contest/5672 | 比赛链接]]




===== A - Social Distancing =====

Solved by qxforever.

==== 题目描述 ====

在半径为 $r$ 的圆内选 $n$ 个整点，使两两距离平方的和最大，输出答案。 $n\le 8$, $r\le 30$, $T\le250$

==== 解题思路 ====

注意到 $n,r$ 的范围很小，输入最多有 $240$ 种情况，因此想到打表来解决此题。

首先所选的点一定在圆内整点形成的凸包上，如果不在凸包上，凸包上一定存在一点使答案更优。计算了一下 $r\in[1,30]$ 的凸包顶点数，发现最多为 $36$ 。在这些点中遍历答案即可，对每组 $(n,r)$，最多有 $\binom{36+8-1}{8}=1.45\times 10^8$ 种选择方案。本地需要 ~1 分钟可以打完。  

注意在凸包上顶点很多的时候，也是有可能两个点重合的。一开始为了效率进行了这样的剪枝，导致 +2 。

感觉这里用概率算法并不是很好。

打表代码:
<hidden><code cpp>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e4+23;

struct Point{
    int x,y;
    Point(int x=0,int y=0):x(x),y(y) {}
    bool operator < (const Point &b){
        return x<b.x||(x==b.x&&y<b.y);
    }
};
Point p[maxn],ch[maxn];int cnt;

typedef Point Vector;
Point operator + (Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
Point operator - (Point A,Point B) {return Point(A.x-B.x,A.y-B.y);}
Point operator * (Point A,double B) {return Point(A.x*B,A.y*B);}
Point operator / (Point A,double B) {return Point(A.x/B,A.y/B);}

int dot(Vector a,Vector b){
    return a.x*b.x+a.y*b.y;
}

int cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}

int length(Vector a){
	return a.x*a.x+a.y*a.y;
}

int ConvexHull(Point *p,int n,Point *ch){
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++){
        while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--){
        while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}

int a[maxn],n,r,sz,ans,vis[100];

void dfs(int p,int dep){
	if(dep==n){
		int sum=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<i;j++){
				int x=a[i],y=a[j];
				sum+=length(ch[y]-ch[x]);
			}
		}
		ans=max(ans,sum);
		return ;
	}
	for(int i=p+1;i<sz;i++){
		a[dep]=i;
		dfs(i,dep+1);
	}
}

void dfs2(int p,int dep){
	if(dep==n){
		int sum=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<i;j++){
				int x=a[i],y=a[j];
				sum+=length(ch[y]-ch[x]);
			}
		}
		ans=max(ans,sum);
		return ;
	}
	for(int i=p;i<sz;i++){
		a[dep]=i;
		dfs2(i,dep+1);
	}
}

void solve(int x,int y){
	n=x,r=y;
	ans=0;
	cnt=0;
	for(int i=0;i<=r;i++){
		for(int j=0;j<=r;j++){
			if(i*i+j*j<=r*r){
				p[cnt++]=Point(i,j);
				p[cnt++]=Point(-i,j);
				p[cnt++]=Point(i,-j);
				p[cnt++]=Point(-i,-j);
			}
		}
	}
	sz=ConvexHull(p,cnt,ch);
	dfs2(0,0);
	printf("ans[%d][%d]=%d;\n",n,r,ans);
}

int main(){
	// freopen("1.out","w",stdout);
	for(int i=1;i<=8;i++){
		for(int j=1;j<=30;j++) solve(i,j);
	}
}

</code></hidden>

\\




===== B - Mask Allocation =====

Solved by qxforever.

==== 题目描述 ====

将 $n\times m$ 个数分组，使得存在能选出 $n$ 组 $m$ 个的方案以及 $m$ 组 $n$ 个的方案，最小化组数，输出字典序最大的方案。

==== 解题思路 ====

将 $n,m$ 进行类似辗转相除的过程即可保证组数最小。






===== C - A National Pandemic =====

Upsolved by nikkukun.

==== 题目描述 ====

给一棵 $n$ 个结点的树，初始所有节点权值都为 $0$，接着有 $q$ 次操作：

  - 给定 $u$ 和 $w$，将树中所有节点 $v$ 的权值加上 $w - \mathrm{dis}(u, v)$；
  - 给定 $u$，将 $u$ 的权值与 $0$ 取最小值；
  - 给定 $u$，询问 $u$ 的权值。

==== 解题思路 ====

操作 2 实际就是一个单点加减，查询后记录一个变化量就行。

对于操作 1，$w - \mathrm{dis}(u, v) = w - \mathrm{dep}(u) - \mathrm{dep}(v) + 2 \cdot \mathrm{dep}(\mathrm{lca}(u, v))$，其中前三项都可以通过全局记录一个变化量维护，关键在后者。这里考虑一个很 tricky 的技巧，每次将 $u$ 到根的路径全部加 $2$，那么查询 $v$ 到根的路径和时，获得的就是 $2 \cdot \mathrm{dep}(\mathrm{lca}(u, v))$，树剖做一下即可。

树上两点路径相关的东西，可以先考虑固定其中一个点到根的路径，然后在走另一个点到根的路径上维护相关信息，它们第一次相遇的位置正是 LCA。例如 [[https://atcoder.jp/contests/agc047/tasks/agc047_d|AGC047 D - Twin Binary Trees]] 和本题就是这样的思路。








===== D - Fake News =====

前缀平方和是完全平方数的正整数只有 $1$ 和 $24$ 







===== G - Topo Counting =====

Upsolved by nikkukun.

==== 题目描述 ====

{{.:drg-example.png}}

给一个以参数 $n \leq 5\ 000$ 控制的烤肉架图（如上图），求它的拓扑序个数模一个给定的质数 $P$ 的值。

==== 解题思路 ====

题解和[[https://blog.nowcoder.net/n/67dd005e3ff4477aab7b75b2bc028883|这篇博客]]讲得非常清楚了，实际就是根据不同状态下烤肉架由哪些位置的点控制得到转移关系，进而计算即可。





===== H - Dividing =====

Solved by nikkukun & qxforever.

==== 题目描述 ====

定义 Legeng Tuple 如下，

  - $(1, k)$ 是
  - 如果 $(n, k)$ 是，那么 $(n + k, k)$ 也是
  - 如果 $(n, k)$ 是，那么 $(nk, k)$ 也是

给定 $N,K$ ，问对任意 $1\le n\le N,1\le k \le K$ 一共有多少 Legeng Tuple。 $N,K\le 10^{12}$

==== 解题思路 ====

分两种情况考虑

  - 进行过 $\times k$ 操作，那么可以表示为 $p \times k$ 
  - 没有进行过 $\times k$ 操作，那么可以表示为 $p \times k + 1$ 

答案是 $\sum_{i=1}^{k}(\lfloor\frac{n-1}{i}\rfloor+\lfloor\frac{n}{i}\rfloor +1)$ ，可以平方分块，也可以暴力算到 $\sqrt n$ ，后面就是一些 $0$ 和 $1$ 。








===== I - Valuable Forest =====

Upsolved by nikkukun.

==== 题目描述 ====

给定质数 $P$，接着 $q \leq 5\ 000$ 次询问，每次询问求 $n \leq 5\ 000$ 个点的森林中，每个点度数的平方和模 $P$ 的值。

==== 解题思路 ====

首先显然所有点地位相同，只要随便算一个点再让结果乘 $n$ 即可。和度数相关的东西可以想到 [[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:i_dont_know_png:nikkukun:pruefer-sequences|Prufer 序列]]，令 $f(n)$ 表示 $n$ 个点的树中，1 号点对答案的总贡献，则有

$$
f(n) = \sum_{d=1}^n d^2 \binom {n-2}{d-1} (n-1)^{(n-2) - (d-1)}
$$

实际就是钦定序列中哪 $d-1$ 个位置是 1 号点，其他点随便放。记 $g(n)$ 为 $n$ 个点的带标号森林个数，枚举 1 号点所在连通块的大小，则总答案为

$$
\sum _{i=1}^n f(i) \cdot g(n-i)
$$

现在考虑如何计算 $g(n)$。记 $h(n)$ 为 $n$ 个点的带标号树个数，由 Cayley 定理有 $h(n) = n^{n-2}$，故类似地枚举森林中 1 号点所在连通块的大小，有

$$
g(n) = \sum _{i=1}^n h(i) \cdot g(n-i)
$$

综上，总时间复杂度为 $O(\sum n^2)$。





===== J - Pointer Analysis =====

Upsolved by nikkukun.

==== 题目描述 ====

很长，摸了，请参考原题。

==== 解题思路 ====

暴力记录每个指针能指向的变量分别都有啥，每次都用所有赋值关系更新至无法更新即可。

赛场上写麻烦了，而且最后只过了 99.04% 的数据也太惨了吧。






===== 赛后总结 =====

==== nikkukun ====

==== qxforever ====

==== Potassium ====