JZTXT

AtCoder Grand Contest 040

发布时间 2023-09-27 19:00:14作者: Zhou_JK

A - ><

将所有的连续段缩起来，如果这个区间为 <，则左端点为 \(0\)，依次递增；如果这个区间为 >，则右端点为 \(0\)，分界点取个左右的 \(\max\) 就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=500005;
int n;
char s[N];
int a[N];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1,j=1;i<=n;i=j)
	{
		while(j<=n&&s[i]==s[j]) j++;
		if(s[i]=='<')
		{
			int l=-1;
			a[i-1]=max(a[i-1],++l);
			for(int k=i;k<j;k++)
				a[k]=max(a[k],++l);
		}
		else if(s[i]=='>')
		{
			int l=-1;
			for(int k=j-1;k>=i;k--)
				a[k]=max(a[k],++l);
			a[i-1]=max(a[i-1],++l);
		}
	}
	long long ans=0;
	for(int i=0;i<=n;i++)
		ans+=a[i];
	printf("%lld",ans);
	return 0;
}

B - Two Contests

对于一种集合中只选一个，另一个选剩下的情况先计算进答案中。

剩下的情况可以将所有区间先按左端点排序，再按右端点排序。那么两个集合选的一定是一个前缀和后缀，枚举分界点计算贡献即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
struct Seg
{
	int l,r;
}s[N];
int pre[N],nxt[N];
int main()
{
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&s[i].l,&s[i].r);
	sort(s+1,s+n+1,[=](const Seg &a,const Seg &b){return a.l==b.l?a.r<b.r:a.l<b.l;});
	pre[0]=1e9;
	for(int i=1;i<=n;i++)
		pre[i]=min(pre[i-1],s[i].r);
	nxt[n+1]=1e9;
	for(int i=n;i>=1;i--)
		nxt[i]=min(nxt[i+1],s[i].r);
	for(int i=1;i<n;i++)
		ans=max(ans,max(pre[i]-s[i].l+1,0)+max(nxt[i+1]-s[n].l+1,0));
	int L=s[n].l,R=pre[n];
	for(int i=1;i<=n;i++)
		ans=max(ans,s[i].r-s[i].l+1+max(R-L+1,0));
	printf("%d",ans);
	return 0;
}

C - Neither AB nor BA

每个位置的奇偶性是不变的，那么就可以将偶数位置上的 A 看做 B，B 看做 A 来处理，问题就变成了 AA 和 BB 不能选。

可以发现，合法的情况为 A 和 B 的个数均 \(\leq \frac{n}{2}\)，否则删到最后肯定会有两个相同的 A 或 B。A 和 B 的个数均 \(\ge \frac{n}{2}\) 的情况不好算，考虑容斥，计算 A 的个数 \(\ge \frac{n}{2}\) 的情况。枚举 A 的个数 \(i\)，剩下的位置可以随便填，方案数为 \(C_n^i \cdot 2^{n-i}\)，B 的个数 \(\ge \frac{n}{2}\) 的情况同理。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=10000005;
const int MOD=998244353;
int n;
long long pw2[N],pw3[N];
long long fac[N],inv[N];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
void init(int n=10000000)
{
	pw2[0]=1;
	for(int i=1;i<=n;i++)
		pw2[i]=pw2[i-1]*2%MOD;
	pw3[0]=1;
	for(int i=1;i<=n;i++)
		pw3[i]=pw3[i-1]*3%MOD;
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%MOD;
	return;
}
long long C(int n,int m)
{
	if(m>n) return 0;
	else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main()
{
	init();
	scanf("%d",&n);
	long long ans=pw3[n];
	long long res=0;
	for(int i=n/2+1;i<=n;i++)
		res=(res+C(n,i)*pw2[n-i]%MOD)%MOD;
	for(int i=n/2+1;i<=n;i++)
		res=(res+C(n,i)*pw2[n-i]%MOD)%MOD;
	ans=(ans-res+MOD)%MOD;
	printf("%lld",ans);
	return 0;
}

D - Balance Beam

考虑一种固定的排列方法，对于 Snuke 能赢的情况的 Ringo 的位置为一段区间，区间的左端点为 \(0\)，我们要使得区间的长度最长即右端点最大。

令 \(sa_i=\sum\limits_{j=1}^i a_j\)，\(sb_i=\sum\limits_{j=1}^i b_j\)。将 \(sa\) 和 \(sb\) 的图像绘制出来，这是两条折线。对于 Ringo 的不同起点，相当于是将 \(sb\) 的折线平移，起点为折线与 \(x\) 轴的交点的情况。我们要确保 \(sa\) 和 \(sb\) 有交点的情况下起点尽量靠右。

考虑新的一条折线，从起点出发，走 \(sb\) 到 \(sa\) 与 \(sb\) 的交点后走 \(sa\) 到 \((n,sa_n)\)。要使起点尽量靠右，我们就要让尽量快的到达 \((n,sa_n)\)，可以发现一个块的最大的贡献为 \(\max(a_i,b_i)\)，可以证明这个上界是可以达到的。

枚举当前的起点所在的块 \(p\)，注意起始块的贡献为 \(b_p\)，我们需要选择最少的块使得 \(\sum \max(a_i,b_i)\ge p-b_p\)，这个可以排序后二分实现。可以发现，在交点处可能可以向下移动一部分，相似算一下就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
struct Node
{
	int a,b;
}p[N];
long long sum[N];
struct Fraction
{
	long long p,q;
	bool operator<(const Fraction &b)const
	{
		return (double)p/q<(double)b.p/b.q;
	}
};
long long gcd(long long a,long long b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&p[i].a,&p[i].b);
	sort(p+1,p+n+1,[=](const Node &x,const Node &y){return max(x.a,x.b)<max(y.a,y.b);});
	for(int i=n;i>=1;i--)
		sum[i]=sum[i+1]+max(p[i].a,p[i].b);
	long long to=0;
	for(int i=1;i<=n;i++)
		to+=p[i].a;
	Fraction ans=(Fraction){0,1};
	for(int i=1;i<=n;i++)
	{
		int pos=n+1;
		int l=1,r=n;
		auto check=[=](int x){return sum[x]-(x<=i?max(p[i].a,p[i].b):0)>=to-p[i].b;};
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(check(mid)) l=mid+1,pos=mid;
			else r=mid-1;
		}
		if(pos>n) continue;
		long long ret=sum[pos]-(pos<=i?max(p[i].a,p[i].b):0)-(to-p[i].b);
		Fraction res=(Fraction){1LL*(pos-1-(pos>i))*p[i].b+min(ret,(long long)p[i].b),1LL*p[i].b*n};
		ans=max(ans,res);
	}
	long long d=gcd(ans.p,ans.q);
	ans.p/=d,ans.q/=d;
	printf("%lld %lld",ans.p,ans.q);
	return 0;
}

E - Prefix Suffix Addition

考虑如果只有 1 操作，答案就为 \(\sum\limits_{i=1}^{n-1} [a_i> a_{i+1}]\)。

考虑加入 2 操作，不妨令 1 操作对 \(x_i\) 的贡献为 \(c_i\)，此时的答案为

\[\sum\limits_{i=1}^{n-1} ([c_i> c_{i+1}]+[a_i-c_i< a_{i+1}-c_{i+1}]) \]

我们需要确定 \(c_i\) 使得上式最小。

考虑 DP，令 \(f_{i,j}\) 表示前 \(i\) 位，\(c_i=j\) 时的最小操作次数。第 \(i\) 位对答案新产生的贡献为

\[[c_{i-1}> c_{i}]+[a_{i-1}-c_{i-1}< a_i-c_i] \]

转化一下，可以得到：

\[[c_i-c_{i-1}< 0]+[c_i-c_{i-1}< a_i-a_{i-1}] \]

可以发现，对于 \(f_{i,j}\) 相等的情况，只有当 \(j\) 最小时才有用，其他可以舍去。因为 \(j\) 越小可以使得后面转移的代价更小。对于 \(f_{i,k}> f_{i,j}+2\) 的 \(k\) 也是没用的，因为后面转移时肯定不如用 \(j\) 去转移来的优。

那么就可以写出另一个 DP，令 \(f_{i,j}\) 表示前 \(i\) 位，代价为 \(j\) 时最小的 \(c_i\) 为多少，用 map 转移，转移时分成三种情况讨论一下就好了。

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int N=200005;
int n;
int a[N];
map<int,int>f[N];
void update(map<int,int>&f,int j,int v)
{
	if(!f.count(j)) f[j]=v;
	else f[j]=min(f[j],v);
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	f[1][0]=a[1],f[1][1]=0;
	for(int i=2;i<=n;i++)
	{
		int vl=min(0,a[i]-a[i-1]),vr=max(0,a[i]-a[i-1]);
		for(auto [v,j]:f[i-1])
		{
			if(f[i-1].begin()->first<v-2) break;
			if(j+vl>0) update(f[i],v+2,0);
  	  		if(j+vl<=a[i]) update(f[i],v+1,max(j+vl,0));
  	  		if(j+vr<=a[i]) update(f[i],v,max(j+vr,0));
		}
	}
	int ans=1e9;
	for(auto [v,j]:f[n])
		ans=min(ans,v+(j>0));
	printf("%d",ans);
	return 0;
}

F - Two Pieces

考虑用一个二元组 \((x,d)\) 表示当前棋子的状态。操作可以分成三种：

  1. 将 \(x,d\) 同时加 \(1\)；
  2. 将 \(d\) 减少 \(1\)，为了确保不重复计算，确保 \(d\ge 2\)；
  3. 将 \(d\) 设为 \(0\)。

考虑只有两种操作，第一种操作会进行 \(B\) 次，枚举第二种操作的次数。将第一种操作看做 \(+1,+1\)，第二种操作看做 \(+1,-1\)。可以看做在 \((0,0)\) 到 \((B+i,B-i)\) 的方案数，且不能到 \(x=1\) 以下，直接折线计数即可。

如果 \(k+B=n\)，这个直接算就是了。

考虑 \(k+B< n\)，考虑插入第三种操作，需要满足：

  • 最后的纵坐标需要到 \(B-A\)；
  • 插入的位置的纵坐标 \(d\) 必须为后缀最小值，否则就会不合法。

可以发现，最后插入的位置的纵坐标 \(d\) 需要满足 \(B-i-d=B-A\)，即 \(d=A-i\)。可以发现对于前面的 \(d=0,1,2\cdots A-i-1\) 的位置中的某个都可以成为后缀最小值，那么就在其中放入 \(n-B-k\) 个三操作就是了，用隔板法计算一下即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=20000005;
const int MOD=998244353;
int n,A,B;
long long fac[N],inv[N];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
void init(int n=20000000)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2);
	for(int i=n;i>=1;i--)
		inv[i-1]=inv[i]*i%MOD;
	return;
}
long long C(int n,int m)
{
	if(m>n) return 0;
	else return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
long long Catalan(int n,int m)
{
	return (C(n+m,n)-C(n+m,n+1)+MOD)%MOD;
}
int main()
{
	init();
	scanf("%d%d%d",&n,&A,&B);
	if(B==0)
	{
		printf("1");
		return 0;
	}
	long long ans=0;
	for(int k=0;B+k<n&&k<=A;k++)
		ans=(ans+Catalan(B-1,k)*C(n-B-k-1+A-k,A-k)%MOD)%MOD;
	if(A+B==n) ans=(ans+Catalan(B-1,A))%MOD;
	printf("%lld",ans);
	return 0;
}