AtCoder Grand Contest 028-526互联

A - Two Abbreviations

答案要么就是 \(\operatorname{lcm}(n,m)\) 要么就是 \(-1\)。判断下 \(\operatorname{lcm}(n,m)\) 是否合法就是了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m;
char s[N],t[N];
long long gcd(long long a,long long b)
{
	return b==0?a:gcd(b,a%b);
}
long long lcm(long long a,long long b)
{
	return a/gcd(a,b)*b;
}
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	scanf("%s",t+1);
	long long L=lcm(n,m);
	long long la=L/n,lb=L/m;
	long long d=lcm(la,lb);
	for(long long i=1;i<=L;i+=d)
		if(s[(i-1)/la+1]!=t[(i-1)/lb+1])
		{
			printf("-1");
			return 0;
		}
	printf("%lld",L);
	return 0;
}

B - Removing Blocks

将 \(a_i\) 分开计算贡献，如果删除 \(j\) 时有 \(a_i\) 的贡献当且仅当 \(j\) 是 \(i\sim j\) 之间最早被删除的，概率即为 \(\frac{1}{j-i+1}\)。答案即为

\[\begin{aligned}&\sum\limits_{i=1}^na_i \cdot n!\sum\limits_{j=1}^n\frac{1}{|j-i+1|} \\ =& \sum\limits_{i=1}^n a_i\cdot n!\left(\sum\limits_{j=1}^{n-i+1}\frac{1}{j}+\sum\limits_{j=1}^i\frac{1}{j}-1\right)\end{aligned} \]

前缀和优化一波就好了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
const int MOD=1000000007;
int n;
int a[N];
int inv[N];
int sum[N];
void init(int n=100000)
{
	inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
	for(int i=1;i<=n;i++)
		sum[i]=(sum[i-1]+inv[i])%MOD;
	return;
}
int main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int facn=1;
	for(int i=1;i<=n;i++)
		facn=1LL*facn*i%MOD;
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=(ans+1LL*(sum[n-i+1]+sum[i]-1)*facn%MOD*a[i]+MOD)%MOD;
	printf("%d",ans);
	return 0;
}

C - Min Cost Cycle

不妨令一个点 \(u\) 的贡献为两个 \(01\) 字符，表示 \(a_u,b_u\) 的是否有贡献，有情况：

若 \(a_u<b_{to},b_u<a_{from}\)，则贡献为 \(11\)。
若 \(a_u<b_{to},b_u>a_{from}\)，则贡献为 \(10\)。
若 \(a_u>b_{to},b_u<a_{from}\)，则贡献为 \(01\)。
若 \(a_u>b_{to},b_u>a_{from}\)，则贡献为 \(00\)。

哈密顿回路中一条边 \((u,v)\) 的贡献为 \(\min(a_u,b_v)\)，我们可以将这个条件转化为在 \(a_u,b_v\) 选取一个，可以发现多出来的那些不合法图都是不优的，不可能成为答案。

所以有：

在 \(01\) 和 \(11\) 后面必须接 \(01\) 或者 \(00\)；
在 \(00\) 和 \(10\) 后面必须接 \(10\) 或者 \(11\)；

不妨设有 \(x\) 个 \(01\)，\(y\) 个 \(10\)，\(z\) 个 \(11\)，\(z\) 个 \(00\)（\(11\) 和 \(00\) 的数量显然相等）

如果 \(z=0\)，要么 \(x=n\)，要么 \(y=n\)。

如果 \(z\ne 0\)，此时一定有解，一种构造方法就是先将 \(z\) 个 \(11\) 和 \(z-1\) 个 \(00\) 首尾依次交替合并成一个新的 \(11\)，然后在 \(11\) 前面接上所有的 \(10\)，后面接上所有的 \(01\)，最后用 \(00\) 把它们串起来。

也就是说我们除了都为 \(01\) 或 \(10\) 的情况，我们一定有一个位置为 \(11\)，这个可以贪心。

具体的说，将 \(a,b\) 排序，判下前 \(n\) 项是否合法。

若不合法，也就是此时每个点都为 \(01\) 或 \(10\)，删掉排序后第 \(n\) 项，加入排序后第 \(n+1\) 项，判断是否合法。

如果还不合法，也是说排序后第 \(n\) 项和排序后第 \(n+1\) 项属于同一个点，有两种方法:

去掉排序后第 \(n-1\) 项，加上排序后第 \(n\) 项；
去掉排序后第 \(n+1\) 项，加上排序后第 \(n+2\) 项；

发现这两种方法一定合法，取个最小值即可。

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int a[N],b[N];
vector<pair<int,int>>val;
bool vis[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]);
	long long suma=0,sumb=0;
	for(int i=1;i<=n;i++)
		suma+=a[i],sumb+=b[i];
	for(int i=1;i<=n;i++)
		val.emplace_back(a[i],i),val.emplace_back(b[i],i);
	sort(val.begin(),val.end());
	long long sum=0;
	bool flag=false;
	for(int i=0;i<n;i++)
	{
		auto [v,p]=val[i];
		sum+=v;
		if(vis[p]) flag=true;
		else vis[p]=true;
	}
	if(flag)
	{
		printf("%lld",min(sum,min(suma,sumb)));
		return 0;
	}
	sum-=val[n-1].first;
	vis[val[n-1].second]=false;
	sum+=val[n].first;
	if(vis[val[n].second]) flag=true;
	else vis[val[n].second]=true;
	if(flag) printf("%lld",min(sum,min(suma,sumb)));
	else printf("%lld",min(min(sum-val[n-2].first+val[n-1].first,sum-val[n].first+val[n+1].first),min(suma,sumb)));
	return 0;
}

D - Chords

可以将问题转化成一个序列上的问题，如果 \([l_1,r_1]\) 和 \([l_2,r_2]\) 相交但不包含，在圆上他们就是相交的。

考虑对于每个连通块计算贡献。

令 \(f_{l,r}\) 表示只在区间 \([l,r]\) 内部连，\(l\) 和 \(r\) 连通的方案数。再令 \(g_x\) 表示 \(x\) 个点的环任意连边的方案数，\(c_i\) 表示 \([1,i]\) 中还没确定连边情况的点的个数，这两个都可以预处理出来。

转移可以用区间内的点任意连边的方案数减去 \(l\) 和 \(r\) 不连通的方案数。计算 \(l\) 和 \(r\) 不连通的方案数可以枚举和 \(l\) 联通的点 \(k\) 然后容斥：

\[f_{l,r}=g_{c_r-c_{l-1}}-\sum\limits_{i=l+1}^{r-1}f_{l,i}\cdot g_{c_r-c_i} \]

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=605;
const int MOD=1000000007;
int n,k;
int match[N];
int c[N];
int f[N][N];
int g[N];
int dfs(int l,int r)
{
	if(l>r) return 0;
	if((r-l+1)%2!=0) return 0;
	if(f[l][r]!=-1) return f[l][r];
	for(int i=l;i<=r;i++)
		if(match[i])
		{
			if(match[i]<l||match[i]>r) return f[l][r]=0;
		}
	int res=g[c[r]-c[l-1]];
	for(int i=l+1;i<=r-1;i++)
		res=(res-1LL*dfs(l,i)*g[c[r]-c[i]]%MOD+MOD)%MOD;
	return f[l][r]=res;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		match[a]=b;
		match[b]=a;
	}
	n=n*2;
	for(int i=1;i<=n;i++)
		c[i]=c[i-1]+(match[i]==0);
	g[0]=1;
	for(int i=2;i<=n;i+=2)
		g[i]=1LL*g[i-2]*(i-1)%MOD;
	memset(f,-1,sizeof(f));
	int ans=0;
	for(int l=1;l<=n;l++)
		for(int r=l+1;r<=n;r++)
			ans=(ans+1LL*dfs(l,r)*g[c[n]-(c[r]-c[l-1])])%MOD;
	printf("%d",ans);
	return 0;
}

E - High Elements

考虑按位确定，考虑判断一个状态是否合法。

对于前缀的一个状态，令当前两个序列的最大值分别为 \(m_A,m_B\)，前缀最大值个数分别为 \(c_A,c_B\)。对于剩下的数，安排序列 \(a_1,a_2,\cdots, a_x\) 和 \(b_1,b_2,\cdots ,b_y\)，满足

\(m_a\lt a_1 \lt a_2\lt \cdots \lt a_x\)
\(m_b\lt b_1 \lt b_2\lt \cdots \lt b_y\)
\(x+c_A=y+c_B\)

可以发现，\(A\) 或 \(B\) 中肯定有一个序列的数全为原序列中的前缀最大值。否则你可以将两边的不为原序列中的前缀最大值的数交换，它在原序列中不为前缀最大值的那个数一定在另一个序列中，所以两边都会少掉一个前缀最大值。

不妨设 \(A\) 全为原序列中的最大值，\(B\) 同理。

令剩下的数里面原序列前缀最大值个数为 \(q\)，有 \(k\) 个被放到 \(B\) 里面了，\(B\) 中还有 \(p\) 个新的前缀最大值，需要满足：

\[c_A+q-k=c_B+p+k \]

即为：

\[2k+p=c_A-c_B+q \]

这个可以看作是将原序列前缀最大值的位置权值看作 \(2\)，其他位置看作 \(1\)，判断是否能找到一个上升子序列使得权值为 \(c_A-c_B+q\)。

可以发现如果 \(v\) 能凑出来则 \(v-2\) 也能凑出来。令 \(f_{i,0/1}\) 表示以 \(i\) 开始，权值和为偶数/奇数的上升子序列的权值和最大值，线段树优化转移即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
const int INF=1061109567;
int n;
int p[N];
int a[N];
int suf[N];
int f[N][2];
char s[N];
struct Segment_Tree
{
	struct Node
	{
		int l,r;
		int mx;
	}tree[N<<2];
	void push_up(int i)
	{
		tree[i].mx=max(tree[i*2].mx,tree[i*2+1].mx);
		return;
	}
	void build(int i,int l,int r)
	{
		tree[i].l=l,tree[i].r=r;
		if(l==r)
		{
			tree[i].mx=-INF;
			return;
		}
		int mid=(l+r)/2;
		build(i*2,l,mid);
		build(i*2+1,mid+1,r);
		push_up(i);
		return;
	}
	void modify(int i,int u,int v)
	{
		if(tree[i].l==tree[i].r)
		{
			tree[i].mx=v;
			return;
		}
		if(u<=tree[i*2].r) modify(i*2,u,v);
		else modify(i*2+1,u,v);
		push_up(i);
		return;
	}
	int query(int i,int l,int r)
	{
		if(l>r) return -INF;
		if(l<=tree[i].l&&tree[i].r<=r) return tree[i].mx;
		int res=-INF;
		if(l<=tree[i*2].r) res=max(res,query(i*2,l,r));
		if(r>=tree[i*2+1].l) res=max(res,query(i*2+1,l,r));
		return res;
	}
}T[2];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	int mx=0;
	for(int i=1;i<=n;i++)
		if(p[i]>mx) a[i]=2,mx=p[i];
		else a[i]=1;
	T[0].build(1,1,n);
	T[1].build(1,1,n);
	for(int i=1;i<=n;i++)
		f[i][a[i]%2]=a[i],f[i][(a[i]%2)^1]=-INF;
	for(int i=n;i>=1;i--)
	{
		for(int j=0;j<2;j++)
			f[i][j]=max(f[i][j],T[(j-a[i]+2)%2].query(1,p[i]+1,n)+a[i]);
		for(int j=0;j<2;j++)
			T[j].modify(1,p[i],f[i][j]);
	}
	for(int i=n;i>=1;i--)
		suf[i]=suf[i+1]+(a[i]==2);
	int cnta=0,cntb=0;
	int mxa=0,mxb=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<2;j++)
			T[j].modify(1,p[i],-INF);
		auto check=[=](int ca,int cb,int ma,int mb)
		{
			int v=ca-cb+suf[i+1];
			if(v<0) return false;
			int mx=T[v%2].query(1,mb+1,n);
			if(v%2==0) mx=max(mx,0);
			return mx>=v;
		};
		if(check(cnta,cntb+(p[i]>mxb),mxa,max(mxb,p[i]))||check(cntb+(p[i]>mxb),cnta,max(mxb,p[i]),mxa)) s[i]='0',cntb+=(p[i]>mxb),mxb=max(mxb,p[i]);
		else if(check(cnta+(p[i]>mxa),cntb,max(mxa,p[i]),mxb)||check(cntb,cnta+(p[i]>mxa),mxb,max(mxa,p[i]))) s[i]='1',cnta+=(p[i]>mxa),mxa=max(mxa,p[i]);
		else
		{
			printf("-1");
			return 0;
		}
	}
	for(int i=1;i<=n;i++)
		printf("%c",s[i]);
	return 0;
}

F - Reachable Cells

从大往小枚举 \((i,j)\)，求出所有能到达的点的权值和 \(s_{i,j}\)。计算 \(s_{i,j}\) 可以考虑容斥，用 \(s_{i+1,j}+s_{i,j+1}\) 减去两个点都能到达的点的权值和。

令 \(minn_{i,j,k}\) 和 \(maxn_{i,j,k}\) 表示 \((i,j)\) 能到达的点中，第 \(k\) 行纵坐标最小和最大的，对于 \((i,j+1)\) 和 \((i+1,j)\) 都能到的行 \(k\) 有 \(minn_{i+1,j,k}\leq minn_{i,j+1,k}\)，\(maxn_{i+1,j,k}\leq maxn_{i,j+1,k}\)。可以发现如果第 \(k\) 行有 \((i,j+1)\) 和 \((i+1,j)\) 都能到的点，那么必然可以都能到 \((k,minn_{i,j+1,k})\)。\((i,j+1)\) 和 \((i+1,j)\) 都能到的点是若干个 \(minn_{i,j+1,k}\) 可达点集的并，且这些点集所占据的行和列不相交，我们可以每次找到一个没有算过的 \(k\) 的减掉 \(s_{k,minn_{i,j+1,k}}\)。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1505;
int n;
char s[N][N];
int sum[N][N],r[N][N];
int minp[2][N][N],maxp[2][N][N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	int cur=0;
	long long ans=0;
	for(int i=n;i>=1;i--)
	{
		cur^=1;
		for(int j=n;j>=1;j--)
			if(s[i][j]!='#')
			{
				sum[i][j]=sum[i][j+1]+sum[i+1][j]+s[i][j]-'0';
				r[i][j]=max(max(r[i][j+1],r[i+1][j]),i);
				minp[cur][j][i]=j;
				for(int k=i+1;k<=r[i+1][j];k++)
					minp[cur][j][k]=minp[cur^1][j][k];
				for(int k=max(r[i+1][j],i)+1;k<=r[i][j+1];k++)
					minp[cur][j][k]=minp[cur][j+1][k];
				maxp[cur][j][i]=j;
				for(int k=i;k<=r[i][j+1];k++)
					maxp[cur][j][k]=maxp[cur][j+1][k];
				for(int k=max(r[i][j+1],i)+1;k<=r[i+1][j];k++)
					maxp[cur][j][k]=maxp[cur^1][j][k];
				for(int k=i+1;k<=min(r[i][j+1],r[i+1][j]);k++)
					if(maxp[cur^1][j][k]>=minp[cur][j+1][k]) sum[i][j]-=sum[k][minp[cur][j+1][k]],k=r[k][minp[cur][j+1][k]];
				ans+=(s[i][j]-'0')*(sum[i][j]-(s[i][j]-'0'));
			}
	}
	printf("%lld",ans);
	return 0;
}

atcoder contest grand 028

authentic atcoder contest grand

negative atcoder contest grand

atcoder contest radius grand

atcoder contest grand 022

atcoder contest grand 001

histogram atcoder contest grand

atcoder contest grand 019

atcoder contest grand 017

atcoder contest grand 039