CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » wangzai_milk » educational_codeforces_round_93_rated_for_div._2_zars19
2020-2021:teams:wangzai_milk:educational_codeforces_round_93_rated_for_div._2_zars19

目录

A. Bad Triangle

选前两根和最后一根判断两边之和大于第三边。

点击以显示 ⇲

点击以隐藏 ⇱ 

#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 int N=5e4+10;
int a[N];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		if(a[1]+a[2]<=a[n])printf("1 2 %d\n",n);
		else puts("-1");
	}
	return 0;
}


B. Substring Removal Game

轮流选当前最长的一段 $1$ 取走。

点击以显示 ⇲

点击以隐藏 ⇱ 

#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 int N=105;
char s[N];
vector<int>v;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s);
		for(int i=0;s[i];i++)
		{
			if(s[i]=='1')
			{
				int cnt=1;
				while(s[i+1]=='1')i++,cnt++;
				v.pb(cnt);
			}
		}
		sort(v.begin(),v.end(),[&](int x,int y){return x>y;});
		int res=0;
		for(int i=0;i<v.size();i+=2)res+=v[i];
		printf("%d\n",res);
		vector<int>().swap(v);
	}
	return 0;
}


C. Good Subarrays

统计区间和等于区间长度的区间有多少，处理前缀和后两位置 $pre_i-i$ 相等意味着某区间满足条件。

点击以显示 ⇲

点击以隐藏 ⇱ 

#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 int N=2e6+10,M=1e5;
int a[N],b[N];
char s[N];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;ll res=0;
		scanf("%d%s",&n,s+1);
		b[M]++;
		for(int i=1;i<=n;i++)
		{
			a[i]=s[i]-'0'+a[i-1];
			int t=a[i]-i+M;
			res+=b[t],b[t]++;
		}
		printf("%lld\n",res);
		b[M]=0;
		for(int i=1;i<=n;i++)b[a[i]-i+M]=0;
	}
	return 0;
}


D. Colored Rectangles

三种颜色各有若干小棍，给出长度，每次从两个不同颜色中各选一个将二者长度的乘积计入结果，问能得到的最大答案。

明显每次只能从每种颜色最大长度的小棍里选两个，排序dp一下。

点击以显示 ⇲

点击以隐藏 ⇱ 

#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>
#define pll pair<ll,ll>
using namespace std;
const int N=202;
int r[N],g[N],b[N];
ll dp[N][N][N];
int main()
{
	int R,G,B;
	scanf("%d%d%d",&R,&G,&B);
	for(int i=1;i<=R;i++)scanf("%d",&r[i]);
	for(int i=1;i<=G;i++)scanf("%d",&g[i]);
	for(int i=1;i<=B;i++)scanf("%d",&b[i]);
	sort(r+1,r+1+R),sort(b+1,b+1+B),sort(g+1,g+1+G);
	for(int i=0;i<=R;i++)
	for(int j=0;j<=G;j++)
	for(int k=0;k<=B;k++)
	{
		if(i&&j)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+r[i]*g[j]);
		if(j&&k)dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+g[j]*b[k]);
		if(i&&k)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+r[i]*b[k]);
	}
	printf("%lld\n",dp[R][G][B]);
	return 0;
}


E. Two Types of Spells

每条咒语有一个力量值，有两种咒语，其中一条闪电咒可以将排在它后面的一条咒语力量翻倍，动态增删一些咒语，每次问最大力量值。

显然每条咒语的力量值至少会被计入答案一次，而我们要考虑的是哪些咒语的力量值会被计入两次，如果闪电咒 $x$ 条，那计入两次的力量值是 $x$ 条或 $x-1$ 条，我们必然选力量值最大的若干条，如果前 $x$ 条全部为闪电咒我们去除一条最小的闪电咒替换为最大的火咒，如果没有火咒则仅取 $x-1$ 条翻倍。离散化上线段树。

点击以显示 ⇲

点击以隐藏 ⇱ 

#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>
#define pll pair<ll,ll>
using namespace std;
const int N=2e5+10;
ll tp[N],d[N],num[N],tot,sz[N<<2],cnt[2][N<<2],sum[N<<2];
void modify(int idx,int l,int r,int pos,int a,int b)
{
	if(l==r){sz[idx]+=a,cnt[b][idx]+=a,sum[idx]+=num[l]*a;return;}
	int mid=(l+r)>>1;
	if(pos<=mid)modify(idx<<1,l,mid,pos,a,b);
	else modify(idx<<1|1,mid+1,r,pos,a,b);
	sz[idx]=sz[idx<<1]+sz[idx<<1|1];
	cnt[b][idx]=cnt[b][idx<<1]+cnt[b][idx<<1|1];
	sum[idx]=sum[idx<<1]+sum[idx<<1|1];
}
ll query1(int idx,int l,int r,int k)
{
	if(l==r)return k*num[l];
	int mid=(l+r)>>1;
	if(sz[idx<<1]<k)return sum[idx<<1]+query1(idx<<1|1,mid+1,r,k-sz[idx<<1]);
	else return query1(idx<<1,l,mid,k);
}
bool query2(int idx,int l,int r,int k)
{
	if(l==r)return cnt[1][idx]>=k;
	int mid=(l+r)>>1;
	if(sz[idx<<1]<k)return (cnt[1][idx<<1]==sz[idx<<1])?query2(idx<<1|1,mid+1,r,k-sz[idx<<1]):0;
	else return query2(idx<<1,l,mid,k);
}
ll query3(int idx,int l,int r,int k)
{
	if(l==r)return num[l];
	int mid=(l+r)>>1;
	if(sz[idx<<1]<k)return query3(idx<<1|1,mid+1,r,k-sz[idx<<1]);
	else return query3(idx<<1,l,mid,k);
}
ll query4(int idx,int l,int r)
{
	if(l==r)return num[l];
	int mid=(l+r)>>1;
	if(cnt[0][idx<<1])return query4(idx<<1,l,mid);
	else return query4(idx<<1|1,mid+1,r);
}
bool cmp(int x,int y){return x>y;}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&tp[i],&d[i]),num[++tot]=abs(d[i]);
	sort(num+1,num+1+tot,cmp);
	tot=unique(num+1,num+1+tot)-num-1;
	ll tmp=0;
	for(int i=1;i<=n;i++)
	{
		tmp+=d[i];
		int t=lower_bound(num+1,num+1+tot,abs(d[i]),cmp)-num;
		ll ans=tmp;
		if(d[i]>0)modify(1,1,tot,t,1,tp[i]);
		else modify(1,1,tot,t,-1,tp[i]);
		if(cnt[1][1])
		{
			ans+=query1(1,1,tot,cnt[1][1]);
			if(query2(1,1,tot,cnt[1][1]))
			{
				ans-=query3(1,1,tot,cnt[1][1]);
				if(cnt[0][1])ans+=query4(1,1,tot);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}


F. Controversial Rounds

给出带?的 $01$ 串（?可做任意指定）。连续的 $x$ 个位置相同可以被计入答案一次（不能重叠），对于每个 $x\in[1,n]$ 回答答案最多是多少。

可以预处理 $a[i][0],a[i][1]$ 分别为位置 $i$ 左边（包含自己）最近的 $0,1$ 所在位置。 $a[i-1][j]==a[i+x-1][j]$ 意味着 $[i,i+x-1]$ 可以计入一次，之后i+=x。否则，我们使i=min(a[i+x-1][0],a[i+x-1][1])+1;即该区间内最靠右一段的段首。可以证明这样跳复杂度是 $O(n\log n)$

点击以显示 ⇲

点击以隐藏 ⇱ 

#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>
#define pll pair<ll,ll>
using namespace std;
const int N=1e6+10;
char s[N];
int a[N][2];
int main()
{
	int n;
	scanf("%d%s",&n,s+1);
	for(int i=1;s[i];i++)
	{
		if(s[i]=='0')a[i][0]=i;else a[i][0]=a[i-1][0];
		if(s[i]=='1')a[i][1]=i;else a[i][1]=a[i-1][1];
	}
	for(int i=1;i<=n;i++)
	{
		int res=0;
		for(int j=1;j+i-1<=n;)
		{
			if(a[j+i-1][0]==a[j-1][0]||a[j+i-1][1]==a[j-1][1])j+=i,res++;
			else j=min(a[j+i-1][0],a[j+i-1][1])+1;
		}
		printf("%d ",res);
	}
	puts("");
	return 0;
}


G. Running Competition

在二维平面上有

  • two horizontal segments: one connecting the points $(0,0)$ and $(x,0)$ , the other connecting the points $(0,y)$ and $(x,y)$
  • $n+1$ vertical segments, numbered from $ 0 $ to $n$ . The i-th segment connects the points $(a_i,0)$ and $(a_i,y)$ ; $0=a_0 < a_1 < a_2 < \ldots < a_{n-1} < a_n=x$

给出若干 $l_i$ 问能选出的矩形周长 $L|l_i$ 最大为多少。

矩形周长其实是 $2(a_i-a_j+y)$ 。用两个多项式 $A(x)=\sum\limits_{i=0}^{n} x^{a_i},B(x)=\sum\limits_{i=0}^{n} x^{-a_i}$ 相乘，系数不为零的正指数项则意味着可以有这样的 $a_i-a_j$ ，至于每个 $l_i$ 最大的可行因子可以一次性处理完成。

点击以显示 ⇲

点击以隐藏 ⇱ 

#include<bits/stdc++.h>
using namespace std;
const int M=8e5+10;
const int N=1e6+10;
const double pi=acos(-1.0);
typedef complex<double> cp;
int rev[M],t[M],ans[N];
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;
}
void fft(cp* x,int l,int on)
{
    for(int i=0;i<l;i++)if(i<rev[i])swap(x[i],x[rev[i]]);
	for(int i=1;i<l;i<<=1)
	{
		cp wn(cos(pi/i),on*sin(pi/i));
		for(int j=0;j<l;j+=2*i)
		{
			cp w(1,0);
			for(int k=j;k<j+i;k++)
			{
				cp u=x[k],v=w*x[k+i];
				x[k]=u+v,x[k+i]=u-v,w*=wn;
			}
		}
	}
	if(on==-1)for(int i=0;i<l;i++)x[i]/=l;
}
cp a[M],b[M];
int main()
{
	int n=read(),x=read(),y=read();
	for(int i=0;i<=n;i++){t[i]=read(),a[t[i]]=b[x-t[i]]=1;}
    int l=2,bit=1;
	while(l<2*x+1)l<<=1,bit++;
	for(int i=0;i<l;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    fft(a,l,1);fft(b,l,1);
    for(int i=0;i<l;i++)a[i]*=b[i];
    fft(a,l,-1);
	memset(ans,-1,sizeof(ans));
	for(int i=1;i<l;i++)
	{
		if((int)(a[x+i].real()+0.5)!=0)
		for(int j=2*(i+y);j<N;j+=2*(i+y))ans[j]=2*(i+y);
	}
	int q=read();
	for(int i=1;i<=q;i++){int p=read();printf("%d ",ans[p]);}
    return 0;
}


2020-2021/teams/wangzai_milk/educational_codeforces_round_93_rated_for_div._2_zars19.txt · 最后更改: 2020/08/21 16:17 由 zars19

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3