AtCoder Grand Contest 040-526互联

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)\) 表示当前棋子的状态。操作可以分成三种：

将 \(x,d\) 同时加 \(1\)；
将 \(d\) 减少 \(1\)，为了确保不重复计算，确保 \(d\ge 2\)；
将 \(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;
}

atcoder contest grand 040

authentic atcoder contest grand

negative atcoder contest grand

atcoder contest radius grand

atcoder contest grand 022

atcoder contest grand 001

atcoder contest descent grand

histogram atcoder contest grand

atcoder contest grand 019

atcoder contest grand 017