CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7 [2020/08/04 21:04]
nikkukun 创建
+++ 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7 [2020/08/20 17:36] (当前版本)
nikkukun add CGIJ
@@ 行 11: / 行 11: @@
 ==== 题目描述 ====
+在半径为 $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% 的数据也太惨了吧。

CVBB ACM Team

用户工具

站点工具

页面工具