差别

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

--- 2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/02 20:35]
zars19 创建
+++ 2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/05 15:24] (当前版本)
zars19 [1332E - Height All the Same]
@@ 行 300: / 行 300: @@
 		puts("");
 	}
+	return 0;
+}
+</code></hidden>
+\\
+====== 1326E - Bombs ======
+给出长度为 $n$ 的两个排列 $p,q$ ，按照顺序从 $1$ 到 $n$ ，把 $p_i$ 加入集合，如果位置 $i$ 有炸弹则从集合中取出一个最大值，结果是最后集合中的最大值。第 $i$ 个答案回答的是 $q_1,q_2,\ldots q_{i-1}$ 处有炸弹时的结果。
+一个比较厉害的转换思维。我们观察到答案是单调不上升的，如果答案至多为 $x$ ，我们就需要让 $x+1,x+2,\ldots,n$ 都被炸掉，条件就是对于每个位置右边大于 $x$ 的 $p_i$ 的数量都不多于右边的炸弹数量。可以线段树维护 $右面不小于当前答案的p_i的数量-右面炸弹数量$ ，如果小于等于 $ 0 $ 则减小当前答案。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define pii pair<int,int>
+#define mp make_pair
+#define fi first
+#define se second
+#define pb push_back
+using namespace std;
+const int N=3e5+10;
+int p[N],q[N],maxn[N<<2],lz[N<<2],pos[N];
+void pushdown(int idx)
+{
+	int t=lz[idx];
+	lz[idx]=0,lz[idx<<1]+=t,lz[idx<<1|1]+=t;
+	maxn[idx<<1]+=t,maxn[idx<<1|1]+=t;
+}
+void add(int idx,int l,int r,int a,int b,int x)
+{
+	if(a<=l&&b>=r){lz[idx]+=x,maxn[idx]+=x;return;}
+	int mid=(l+r)>>1;
+	pushdown(idx);
+	if(b<=mid)add(idx<<1,l,mid,a,b,x);
+	else if(a>mid)add(idx<<1|1,mid+1,r,a,b,x);
+	else add(idx<<1,l,mid,a,b,x),add(idx<<1|1,mid+1,r,a,b,x);
+	maxn[idx]=max(maxn[idx<<1],maxn[idx<<1|1]);
+}
+int main()
+{
+	int n;
+	scanf("%d",&n);
+	for(int i=1;i<=n;i++)scanf("%d",&p[i]),pos[p[i]]=i;
+	for(int i=1;i<=n;i++)scanf("%d",&q[i]);
+	int res=n;
+	add(1,1,n,1,pos[n],1);
+	for(int i=1;i<=n;i++)
+	{
+		printf("%d ",res);
+		if(i==n)break;
+		add(1,1,n,1,q[i],-1);
+		while(maxn[1]<=0)--res,add(1,1,n,1,pos[res],1);
+	}
+	puts("");
+	return 0;
+}
+</code></hidden>
+\\
+====== 1373F - Network Coverage ======
+ $a_i $代表第 $i $处的需求量， $b_i $代表第 $i $处的资源， $i $处资源只可以供给 $i $和 $i+1 $（ $n $则可以供给 $n $和 $1 $），问是否可以满足全部需求。
+神秘的单调性与神秘的二分。我们发现只要确定某一处提供给自己的资源量就可以确定整个状态，这里我们选择 $1 $， $1 $提供给自己的量越少（即提供给 $2 $越多），后面 $2 $到 $n $的需求越可能得到满足。我们二分这个能使 $2 $到 $n $的需求得以满足的 $1 $能提供给自己最多的量，最后判断这种情况下首尾相接后 $1 $能否得到满足即可。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define pii pair<int,int>
+#define mp make_pair
+#define fi first
+#define se second
+#define pb push_back
+using namespace std;
+const int N=1e6+10;
+ll read()
+{
+	ll 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 n,a[N],b[N],c[N];		//a 需要 b 可分配
+bool judge(int k)
+{
+	for(int i=0;i<n;i++)c[i]=0;
+	c[0]=k,c[1]=b[0]-k;		//c 已经得到
+	for(int i=1;i<n;i++)
+	{
+		int t=max(0,a[i]-c[i]);
+		if(b[i]<t)return false;
+		c[(i+1)%n]+=b[i]-t;
+	}
+	return true;
+}
+int main()
+{
+	int t=read();
+	while(t--)
+	{
+		n=read();
+		for(int i=0;i<n;i++)a[i]=read();
+		for(int i=0;i<n;i++)b[i]=read();
+		int l=0,r=b[0],res=-1;
+		while(l<=r)
+		{
+			int mid=(l+r)>>1;
+			if(judge(mid))l=mid+1,res=mid;
+			else r=mid-1;
+		}
+		if(res!=-1&&judge(res)&&c[0]>=a[0])puts("YES");
+		else puts("NO");
+	}
+	return 0;
+}
+</code></hidden>
+\\
+====== 1373E - Sum of Digits ======
+ $f(x) $是 $x $的数位和，给定 $n,k $构造 $x $使得 $\sum\limits_{i=0}^kf(x+i)=n $。
+数据范围很小甚至可以打表。观察到 $k\le9 $，所以至多进位 $1 $次。事实上手玩一下发现是这样， $n $在进位情况下是 $x99\ldots998y $的形式，不进位情况下是 $x99\ldots999y $的形式，枚举 $x,y $和长度 $l $就好。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define pii pair<int,int>
+#define mp make_pair
+#define fi first
+#define se second
+#define pb push_back
+using namespace std;
+char s1[55],s2[55];
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n,k,f=0;
+		scanf("%d%d",&n,&k);
+		for(int i=0;i<9;i++)
+		for(int l=0;l<20;l++)
+		for(int j=0;j<10;j++)
+		{
+			int tmp=(i+l*9+j)*(k+1)+(1+k)*k/2;
+			if(j+k>=10)tmp-=9*(j+k-9);
+			if(j+k>=10&&l)tmp-=k+1;
+			if(tmp==n)
+			{
+				int cnt=0;
+				if(i)s2[cnt++]=i+'0';
+				for(int ii=1;ii<=l;ii++)
+				{
+					if(ii==l&&j+k>=10)s2[cnt++]='8';
+					else s2[cnt++]='9';
+				}
+				s2[cnt++]=j+'0',s2[cnt]='\0';
+				if(!f||strlen(s1)>strlen(s2)||(strlen(s1)==strlen(s2)&&strcmp(s1,s2)>0))
+				strcpy(s1,s2);
+				f=1;
+			}
+		}
+		if(!f)printf("%d\n",-1);
+		else printf("%s\n",s1);
+	}
+	return 0;
+}
+</code></hidden>
+\\
+====== 1383D - Rearrange ======
+给 $n\times m $的矩阵，其中元素是 $1 $到 $n\times m $的排列。现要求构造同样用 $1 $到 $n\times m $的排列填充的 $n\times m $矩阵，使得：
+  * 每一行、每一列都是单峰的。
+  * 行最大值的集合与给定矩阵相同，列最大值的集合与给定矩阵相同。
+一个想法是数字由大到小填，这样当填下某个数字时就可以确定某行或某列的最大值。官方提供了这样一种构造方法：
+初始待填充矩阵 $ 0  $行 $ 0  $列。
+ $\mathtt{for}\;num\;\mathtt{in}\;n\times m\;..\;1 $
+如果有行最大值为 $num $，增加行；有列最大值为 $num $，增加列。 $num $为某个最大值就直接填在右下角，如果是行最大值，将左边的一整行由近到远加入队列；是列最大值，将上边的一整列由近到远加入队列。 $num $不是最大值则从队列中取一个位置出来放在该位置。
+随便想一下就发现这样能够保证单峰性（峰值即那些行列最大值）。
+<hidden><code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define pii pair<int,int>
+#define mp make_pair
+#define fi first
+#define se second
+#define pb push_back
+using namespace std;
+const int N=255;
+int a[N][N],b[N][N],r[N],c[N];
+queue<pii>q;
+int main()
+{
+	int n,m;
+	scanf("%d%d",&n,&m);
+	for(int i=0;i<n;i++)for(int j=0;j<m;j++)
+	scanf("%d",&a[i][j]),r[i]=max(r[i],a[i][j]),c[j]=max(c[j],a[i][j]);
+	sort(r,r+n),sort(c,c+m);
+	int x=0,y=0,i=n-1,j=m-1;
+	for(int num=n*m;num;num--)
+	{
+		if(r[i]==num)x++;
+		if(c[j]==num)y++;
+		if(r[i]==num||c[j]==num)b[x][y]=num;
+		else b[q.front().fi][q.front().se]=num,q.pop();
+		if(r[i]==num)
+		{
+			for(int k=y-1;k;k--)q.push(mp(x,k));
+			i--;
+		}
+		if(c[j]==num)
+		{
+			for(int k=x-1;k;k--)q.push(mp(k,y));
+			j--;
+		}
+	}
+	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

用户工具

站点工具

差别

页面工具