差别

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

--- 2020-2021:teams:wangzai_milk:20200527比赛记录 [2020/06/02 00:39]
wzx27
+++ 2020-2021:teams:wangzai_milk:20200527比赛记录 [2020/06/07 00:35] (当前版本)
zars19 [E-Eureka]
@@ 行 3: / 行 3: @@
 ===== 比赛情况 =====
-^题号 	^A 	^B 	^C 	^D 	^E 	^F 	^G 	^H 	^I 	^J 	^K 	|^L 	|^M 	|
+^题号 	^A 	^B 	^C 	^D 	^E 	^F 	^G 	^H 	^I 	^J 	^K 	^L 	^M 	|
 ^状态 	|O 	|- 	|- 	|- 	|O 	|O 	|- 	|- 	|O	|-	|O	|Ø      |-      |
@@ 行 14: / 行 14: @@
 **提交记录**
+''A: Accepted 2020-05-27 13:28:13''
 ''K: Accepted 2020-05-27 13:33:18''
@@ 行 29: / 行 30: @@
 ===== 题解 =====
+==== A-Acperience ====
+solved by Zars19
+给定向量$W=(w_1,w_2,...,w_n)$，有$B=(b_1,b_2,...,b_n)~(b_i\in\{+1,−1\}),~\alpha\ge0$，使得$∥W−\alpha B∥^2$最小，求这个最小值。
+题解：发现应该是$w_i\geq0$时$b_i$取$+1$，否则$-1$，然后保留$\alpha$为变量可以列出$∥W−\alpha B∥^2$式，二次函数求最值即可。
+code:
+<hidden>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<cassert>
+#include<cstdlib>
+#include<cmath>
+#include<vector>
+#include<algorithm>
+#define LL long long
+const int N=1e5+5;
+using namespace std;
+int read()
+{
+	int x=0,f=1;char c=getchar();
+	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
+	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
+	return x*f;
+}
+LL gcd(LL a,LL b){return a?gcd(b%a,a):b;}
+LL w[N];
+int main()
+{
+	int T=read();
+	while(T--)
+	{
+		int n=read();
+		LL a=0,b=0,c=0;
+		for(int i=1;i<=n;i++)
+		{
+			w[i]=read();
+			if(w[i]>=0)b-=2*w[i];
+			else b+=2*w[i];
+			c+=w[i]*w[i],a++;
+		}
+		LL p=4*a*c-b*b,q=4*a;
+		LL g=gcd(p,q);
+		printf("%lld/%lld\n",p/g,q/g);
+	}
+	return 0;
+}
+</code>
+</hidden>
+\\
+==== E-Eureka ====
+solved by Zars19
+二维平面上给出$n$个点的坐标。一个有$\text{best pair}$的集合是最好的$\text{best set}$，$f(u,v)=\sqrt{(x_u−x_v)^2+(y_u−y_v)^2}$，$g(u,v,w)=\frac{f(u,v)+f(v,w)+f(w,u)}2$，当$u,v$对集合中所有$w$满足$f(u,v)≥g(u,v,w)$，它们是$\text{best pair}$。求$\text{best set}$数量。
+题解：对着那个柿子稍微化简一下会发现是求平面上在一条直线上的点集的数量，本来写了$O(n\log^2n)$极角排序，但卡常失败非常痛苦。后来用''map<pair<LL,LL>,int>''记录每个角度的点的个数，''pair<LL,LL>''利用gcd避免精度问题，map写法比较微妙，不用多次排序常数好了很多。细节上需要一点排列组合处理。
+code:
+<hidden>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<map>
+#include<cstdlib>
+#include<cmath>
+#include<vector>
+#include<algorithm>
+#define ex(x) ((pow2[d[x].num]-1+Mod)%Mod)
+#define sqr(x) ((x)*(x))
+#define eps 1e-8
+#define LL __int64
+#define pll pair<LL,LL>
+const int N=1e3+5;
+const LL Mod=1e9+7;
+using namespace std;
+inline int read()
+{
+	int x=0,f=1;char c=getchar();
+	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
+	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
+	return x*f;
+}
+struct Point
+{
+	LL x,y;
+	int num;
+	Point(LL x=0,LL y=0):x(x),y(y){}
+	Point operator + (Point a){return Point(x+a.x,y+a.y);}
+	Point operator - (Point a){return Point(x-a.x,y-a.y);}
+	bool operator == (Point a){return x==a.x&&y==a.y;}
+}d[N],cp[N],p;
+typedef Point Vector;
+inline LL Cross(Vector v1,Vector v2){return v1.x*v2.y-v1.y*v2.x;}
+inline LL dissqr(Point p1,Point p2){return sqr(p1.x-p2.x)+sqr(p1.y-p2.y);}
+inline int dcmp(double x){return x<-eps?-1:(x>eps);}
+inline bool cmp(Point p1, Point p2)
+{
+	if(p1.x==p2.x)return p1.y<p2.y;
+	return p1.x<p2.x;
+}
+LL pow2[N];
+map<pll,int>mp;
+void init()
+{
+	pow2[0]=1;
+	for(int i=1;i<N;i++)pow2[i]=(pow2[i-1]<<1)%Mod;
+}
+LL gcd(LL a,LL b){return a?gcd(b%a,a):b;}
+void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
+{
+    if(!b)d=a,x=1,y=0;
+    else exgcd(b,a%b,d,y,x),y-=x*(a/b);
+}
+LL inv(LL a,LL p)
+{
+    LL d,x,y;exgcd(a,p,d,x,y);
+    return (x+p)%p==0?p:(x+p)%p;
+}
+int main()
+{
+	init();
+	int T=read();
+	while(T--)
+	{
+		int n=read(),m=0;
+		LL res=0;
+		for(int i=0;i<n;i++)d[i].x=read(),d[i].y=read(),d[i].num=1;
+		sort(d,d+n,cmp);
+		for(int i=0;i<n;i++)
+		if(d[i]==d[i+1]&&i!=n-1)d[i+1].num+=d[i].num;
+		else cp[m++]=d[i],res+=(pow2[d[i].num]-1-d[i].num+Mod)%Mod;
+		for(int i=0;i<m;i++)d[i]=cp[i];
+		for(int i=0;i<m;i++)
+		{
+			mp.clear();
+			for(int j=i+1;j<m;j++)
+			{
+				LL u=d[j].x-d[i].x,v=d[j].y-d[i].y;
+				LL g=gcd(u,v);
+				if(g<0)g*=-1;
+				if(g)u/=g,v/=g;
+				LL t=pow2[mp[make_pair(u,v)]]*ex(i)%Mod*ex(j)%Mod;
+				res=(res+t)%Mod;
+				mp[make_pair(u,v)]+=d[j].num;
+			}
+		}
+		cout<<res<<endl;
+	}
+	return 0;
+}
+</code>
+</hidden>
+\\
+==== F - Fantasia ====
+=== 题目大意 ===
+给定一个无向图$G$，定义$G_i$为该图去掉$i$点后的权重，图的权重定义如下
+如果图连通，那么图的权重就是所有点权重的乘积
+如果图不连通，那么图的权重就是图中若干连通块权重的加和。
+现在求所有的$G_i$
+=== 数据范围 ===
+$n\leq 10^5$，$m\leq 2\times 10^5$
+=== 题解 ===
+意识到对于一个无向图，之后删除割点的时候才会产生新的连通块，那么我们可以对所有点双联通分量缩点，在森林上进行dp和处理即可。
+这样写起来比较麻烦，据说官方题解是block forest data，可以等有时间了学习一手。
+=== 代码 ===
+<hidden code>
+<code cpp>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <vector>
+#include <algorithm>
+using namespace std;
+typedef long long ll;
+const ll mod = 1e9+7;
+const int N = 1e5+5;
+const int M = 2e5+5;
+vector<int>edge[N];
+vector<int>son[N];
+void add(int x,int y) {
+	edge[x].push_back(y);
+	edge[y].push_back(x);
+}
+int n,m;
+int w[N];
+int dfn[N],low[N];
+ll val[N],treeval[N];
+int tree[N],root[N];
+ll ans,ans1,ans2;
+int treecount,clock;
+ll quick_pow(ll x,ll y) {
+	ll ans = 1;
+	x = x%mod;
+	while (y) {
+		if (y&1)
+			ans = ans*x%mod;
+		y >>= 1;
+		x = x*x%mod;
+	}
+	return ans;
+}
+ll Inv(ll x) {
+	return quick_pow(x,mod-2);
+}
+int tarjan(int x,int fa) {
+	int lowx = dfn[x] = clock++;
+	tree[x] = treecount;
+	ll sum = w[x];
+	int sz = edge[x].size();
+	for (int i = 0;i < sz;i++) {
+		int to = edge[x][i];
+		if (!dfn[to]) {
+			int lowto = tarjan(to,x);
+			lowx = min(lowx,lowto);
+			son[x].push_back(to);
+			sum = sum*val[to]%mod;
+		} else {
+			lowx = min(lowx, dfn[to]);
+		}
+	}
+	val[x] = sum;
+	return low[x] = lowx;
+}
+void init() {
+	clock = 1;
+	memset(dfn,0,sizeof(dfn));
+	memset(root,0,sizeof(root));
+	treecount = 0;
+	scanf("%d%d",&n,&m);
+	for (int i = 1;i <= n;i++)scanf("%d",&w[i]);
+	for (int i = 1;i <= n;i++) {
+		edge[i].clear();
+		son[i].clear();
+	}
+	int x,y;
+	for (int i = 1;i <= m;i++) {
+		scanf("%d%d",&x,&y);
+		add(x,y);
+	}
+}
+int main()
+{
+	int cas;
+	scanf("%d",&cas);
+	while (cas--) {
+		init();
+		for (int i = 1;i<= n;i++) {
+			if (!dfn[i]) {
+				treecount++;
+				tarjan(i,-1);
+				treeval[treecount] = val[i];
+				root[i] = 1;
+			}
+		}
+		ll sum = 0;
+		for (int i = 1;i <= treecount;i++)
+			sum+= treeval[i];
+		ans = 0;
+		for (int i = 1;i<= n;i++) {
+			ans2 = 0;
+			ans1 = treeval[tree[i]];
+			ll othersum = sum-ans1;
+			ans1 = ans1*Inv(w[i])%mod;
+			int sz = son[i].size();
+			for (int j = 0;j < sz;j++) {
+				int to = son[i][j];
+				if (low[to] >= dfn[i]) {
+					ans1 = ans1*Inv(val[to])%mod;
+					ans2 = (ans2+val[to])%mod;
+				}
+			}
+			if (root[i]) ans1--;
+			(ans += (ans1 + ans2 + othersum)%mod*i%mod)%=mod;
+		}
+		printf("%lld\n",ans);
+	}
+}
+</code>
+</hidden>
+\\
+==== I - It's All In The Mind ====
+=== 题目大意 ===
+假设有这样一个序列，其长度为$n$，满足下述三个条件
+.对于任意的$i$，有$0\leq a_i\leq 100$
+.序列是不上升的，$a_n \leq a_{n-1} \leq $……$\leq a_2 \leq a_1$
+.序列的和不为0
+现在让你来构造这样一个序列，使得$\frac{a_1+a_2}{\sum_{i=1}^na_i}$最大
+=== 数据范围 ===
+$n\leq 100$
+=== 题解 ===
+贪心构造就好，$a_1$和$a_2$尽量大，余下的数字尽量小。
+=== 代码 ===
+<hidden code>
+<code cpp>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <algorithm>
+using namespace std;
+const int N = 105;
+int a[N];
+int gcd(int x,int y) {
+	if (y == 0) { return x; }
+	return gcd(y,x%y);
+}
+int main()
+{
+	int cas;
+	scanf("%d",&cas);
+	while (cas--) {
+		int n,m;
+		scanf("%d%d",&n,&m);
+		for(int i = 1;i<= n;i++)a[i] = -1;
+		int x,y;
+		for (int i = 1;i<= m;i++) {
+			scanf("%d%d",&x,&y);
+			a[x] = y;
+		}
+		int sum = 0;
+		int ans = 0;
+		for(int i = n;i>= 3;i--) {
+			if (a[i] == -1)
+				a[i] = ans;
+			else
+				ans = a[i];
+			sum+=a[i];
+		}
+		ans = 100;
+		for (int i = 1;i<= 2;i++) {
+			if (a[i] == -1)
+				a[i] = ans;
+			else
+				ans = a[i];
+			sum+=a[i];
+		}
+		int q = gcd(a[1]+a[2],sum);
+		printf("%d/%d\n",(a[1]+a[2])/q,sum/q);
+	}
+	return 0;
+}
+</code>
+</hidden>
+\\
 ==== K-Keep on Movin ====
@@ 行 78: / 行 448: @@
 </code>
 </hidden>
+\\
 ==== L-La Vie en rose ====
-给两个长度分别为 $n$ 和 $m$ 的串 $s,p$，问对于$1\le i\le n$ $p$ 在经过某种变换之后是否能完全匹配 $s_i s_{i+1}...s_{i+m-1}$ 。这种变换定义为，任选 $1,2,..,m$ 中 $k$ 个不相邻的下标 $i_k$，交换 $p_{i_k}$ 和 $p_{i_k+1}$。
+给两个长度分别为 $n$ 和 $m$ 的串 $s,p$，问对于$1\le i\le n$ $p$ 在经过某种变换之后是否能完全匹配 $s_i s_{i+1} ... s_{i+m-1}$ 。这种变换定义为，任选 $1,2,..,m$ 中 $k$ 个不相邻的下标 $i_k$，交换 $p_{i_k}$ 和 $p_{i_k+1}$。
 本来暴力 $nm=5e8$ 可以过的，好像这个赛后加强了数据，得用 $\text{bitset}$ 优化一下才能过。

CVBB ACM Team

用户工具

站点工具

差别

页面工具