CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/04 13:58]
zars19 [1383D - Rearrange]
+++ 2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/05 15:24] (当前版本)
zars19 [1332E - Height All the Same]
@@ 行 529: / 行 529: @@
 	for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=m;j++)
 	printf("%d ",b[i][j]);
+	return 0;
+}
+</code></hidden>
+\\
+====== 1388E - Uncle Bogdan and Projections ======
+给 $x$ 轴以上的若干水平线段。现可以指定一个向量让所有线段沿该方向投影到 $x$ 轴上，投影不可以重叠，宽度定义为投影最右端横坐标减去最左端横坐标，问可能的最小宽度。
+如果纵坐标全部相同，直接垂直投影即可。否则我们可以在使得某个投影与投影相切的时候取到最小宽度。对任意两个纵坐标不同的线段，我们可以算出两个投影相切的角度，从而得到一段不可行的区间。扫描线得出全局的可行投影角度区间。
+而要在合理时间内得到取若干角度时投影的最大最小横坐标，可以用一个叫Convex Hull Trick的做法。设 $\theta$ 为投影线与 $x$ 轴正方向的夹角， $(x,y)$ 投影在横坐标 $x-\frac y{tan(\theta)}$ 的位置。以 $-\frac 1{tan(\theta)}$ 为自变量，则 $y_i$ 为斜率， $x_i$ 为截距。若干直线只会在一个凸包上取得最大值，我们先求出这个凸包，之后对于每个 $-\frac 1{tan(\theta_i)}$ 可以二分。最小值同理。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define fi first
+#define se second
+#define mp make_pair
+#define pb push_back
+#define pii pair<int,int>
+using namespace std;
+const int N=2005;
+const double pi=acos(-1.0);
+const double eps=1e-10;
+const double inf=1e20;
+int l[N],r[N],y[N],tot1,tot2,top1,top2;
+int dcmp(double x){return x<-eps?-1:x>eps;}
+vector<double>v1,v2;
+double num[N*N*2],res=inf,x1[N*2],x2[N*2];
+struct line{int k,b;}s[N*2],st1[N*2],st2[N*2];
+double getInt(line l1,line l2){return (l2.b-l1.b)*1.0/(l1.k-l2.k);}
+void getMax(double x)
+{
+	int ll=1,rr=top1;double maxn;
+	while(ll<=rr)
+	{
+		int mid=(ll+rr)>>1;
+		double pl=x1[mid-1],pr=x1[mid];
+		if(x>=pl&&x<=pr){maxn=st1[mid].k*x+st1[mid].b;break;}
+		else if(x>pr)ll=mid+1;
+		else rr=mid-1;
+	}
+	ll=1,rr=top2;double minn;
+	while(ll<=rr)
+	{
+		int mid=(ll+rr)>>1;
+		double pl=x2[mid-1],pr=x2[mid];
+		if(x>=pl&&x<=pr){minn=st2[mid].k*x+st2[mid].b;break;}
+		else if(x>pr)ll=mid+1;
+		else rr=mid-1;
+	}
+	res=min(res,maxn-minn);
+}
+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;
+}
+int main()
+{
+	int n=read();
+	double maxt=-inf,mint=inf;
+	bool f=true;
+	for(int i=1;i<=n;i++)
+	{
+		l[i]=read(),r[i]=read(),y[i]=read();
+		maxt=max(maxt,1.0*r[i]),mint=min(mint,1.0*l[i]);
+		s[++tot2]=line{y[i],l[i]};
+		s[++tot2]=line{y[i],r[i]};
+		for(int j=1;j<i;j++)
+		if(y[i]!=y[j])
+		{
+			int a=i,b=j;f=false;
+			if(y[a]<y[b])swap(a,b);
+			int u=y[a]-y[b],p=r[a]-l[b],q=l[a]-r[b];
+			int g1=abs(__gcd(u,p)),g2=abs(__gcd(u,q));
+			double ang1=atan2(u/g1,p/g1);
+			double ang2=atan2(u/g2,q/g2);
+			v1.pb(ang1),v2.pb(ang2);
+			num[++tot1]=ang1,num[++tot1]=ang2;
+		}
+	}
+	if(f){printf("%.10lf\n",maxt-mint);return 0;}
+	sort(num+1,num+1+tot1),sort(v1.begin(),v1.end()),sort(v2.begin(),v2.end());
+	sort(s+1,s+1+tot2,[&](line l1,line l2){return l1.k==l2.k?l1.b>l2.b:l1.k<l2.k;});
+	for(int i=1;i<=tot2;i++)
+	{
+		if(top1&&st1[top1].k==s[i].k)continue;
+		while(top1>=2&&dcmp(getInt(s[i],st1[top1])-x1[top1-1])<=0)top1--;
+		st1[++top1]=s[i];
+		if(top1>=2)x1[top1-1]=getInt(st1[top1],st1[top1-1]);else x1[top1-1]=-inf;
+	}
+	x1[top1]=inf;
+	sort(s+1,s+1+tot2,[&](line l1,line l2){return l1.k==l2.k?l1.b<l2.b:l1.k>l2.k;});
+	for(int i=1;i<=tot2;i++)
+	{
+		if(top2&&st2[top2].k==s[i].k)continue;
+		while(top2>=2&&dcmp(getInt(s[i],st2[top2])-x2[top2-1])<=0)top2--;
+		st2[++top2]=s[i];
+		if(top2>=2)x2[top2-1]=getInt(st2[top2],st2[top2-1]);else x2[top2-1]=-inf;
+	}
+	x2[top2]=inf;
+	for(int i=1,j=0,k=0,cnt=0;i<=tot1;i++)
+	{
+		while(k<v2.size()&&dcmp(v2[k]-num[i])<=0)k++,cnt--;
+		if(!cnt)getMax(-1.0/tan(num[i]));
+		while(j<v1.size()&&dcmp(v1[j]-num[i])<=0)j++,cnt++;
+	}
+	printf("%.10lf\n",res);
+	return 0;
+}
+</code></hidden>
+\\
+====== 1332E - Height All the Same ======
+ $n\times m$ 的网格，位置 $(i,j)$ 上有 $a_{i,j}$ 个方块，每次操作可以在某位置加两个方块，或者在两个相邻位置各加一个方块，目标是使得所有位置高度一致。问在 $a_{i,j}\in[l,r]$ 的条件下，能达成目标的方案有多少。
+一个观察是重要的只是所有位置上方块数量的奇偶性，同一个位置加两个方块这一操作不改变奇偶性，而使得所有位置奇偶性一致后必能用这个操作达成目标。
+另一个观察是，我们必能改变且仅改变任意一对格子的奇偶性（这是因为两个位置间必有一条路径，沿路径每次翻转相邻两个就好）。
+当有偶数个奇数或偶数个偶数个时，可以把它们两两配对改变奇偶性达成目标，否则不可以。
+  * 当 $n\times m$ 为奇数时，必然是偶数个奇数奇数个偶数/偶数个偶数奇数个奇数，答案是总数 $\mathrm{total}=(r-l+1)^{nm}$ 。
+  * 当 $n\times m$ 为偶数时，奇偶都是偶数个可以，奇偶都是奇数个不行。pikmike提供了一个直觉法：
+  * 当 $r-l+1$ 为偶数时，答案是 $\frac{\mathrm{total}}2$
+  * 当 $r-l+1$ 为奇数时，可行将会比不可行多 $1$ 。这是因为 $[l,r]$ 中必定有 $k\in[l,r]且 k\oplus1\notin[l,r]$ 。每一种方案，我们可以选第一个不为 $k$ 的位置给 $a_{i,j}$ 异或 $1$ ，这样可以使可行方案与不可行方案两两配对，除了全部为 $k$ 的一个方案可行。答案 $\frac{\mathrm{total}+1}{2}$
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define fi first
+#define se second
+#define mp make_pair
+#define pb push_back
+#define pii pair<int,int>
+using namespace std;
+const ll mod=998244353;
+ll n,m,l,r;
+ll qpow(ll a,ll b)
+{
+	ll res=1;
+	while(b)
+	{
+		if(b&1)res=res*a%mod;
+		a=a*a%mod,b>>=1;
+	}
+	return res;
+}
+int main()
+{
+	scanf("%lld%lld%lld%lld",&n,&m,&l,&r);
+	ll tot=qpow(r-l+1,n*m);
+	if((n*m)&1)printf("%lld\n",tot);
+	else if((r-l+1)&1)printf("%lld\n",(tot+1)%mod*qpow(2,mod-2)%mod);
+	else printf("%lld\n",tot*qpow(2,mod-2)%mod);
 	return 0;
 }
 </code></hidden>
 \\

CVBB ACM Team

用户工具

站点工具

页面工具