「题解」2019 ICPC Asia Nanchang Regional 解题报告

未完待续

A. 9102

题面翻译

题解

代码

B. A Funny Bipartite Graph

题意翻译

给定二分图,左右各 \(n\) 个结点,且仅当 \(i\leq j\) 时 \(L_i\) 和 \(R_j\) 才可能连边。每个左节点度数 \(\in\left[1,3\right]\)。

C. And and Pair

题意翻译

\(T\) 组数据,每组数据给你一个 \(n\)(以一个二进制字符串 \(S\) 给出,满足\(1\leq\left|S\right|\leq 10^5\)),求满足下列条件的数对 \((i,j)\) 的个数,答案对 \(10^9+7\) 取模:

  1. \[0\leq j\leq i\leq n\]
  2. \[i\And n=n\]
  3. \[i\And j=0\]

题解

考虑到假如 \(n\) 的某一位为 \(1\),那么可能存在方案满足 \(i\) 这一位为 \(1\)。

不妨设 \(\texttt{dp} _ {i,0/1}\),表示当前考虑到第 \(i\) 位,其中 \(\texttt{dp} _ {i,1}\) 第 \(i\) 位以及之前填过 \(1\) 的方案数,用 \(\texttt{dp} _ {i,0}\) 表示第 \(i\) 位及之前没有填过 \(1\) 的方案数。

那么我们有
\[
\begin{aligned}
\texttt{dp} _ {i,1}&=
\begin{cases}
3\texttt{dp} _ {i-1,1}+\texttt{dp} _ {i-1,0}&,n _ i=1\\
2\texttt{dp} _ {i-1,1}&,n _ i=0
\end{cases}\\
\texttt{dp} _ {i,0}&=\texttt{dp} _ {i-1,0}
\end{aligned}
\]

边界条件为 \(\texttt{dp} _ {0,0}=1\)。

时间复杂度为 \(\Theta(\left|S\right|)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int p=1e9+7;
const int MAXSIZE=1e5+5;

char S[MAXSIZE];

inline int add(reg int a,reg int b){
	reg int sum=a+b;
	return sum>=p?sum-p:sum;
}

inline int mul(reg int a,reg int b){
	return 1ll*a*b%p;
}

int dp[MAXSIZE][2];

int main(void){
	reg int T=read();
	while(T--){
		scanf("%s",S+1);
		reg int n=strlen(S+1);
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(reg int i=1;i<=n;++i){
			if(S[i]=='1')
				dp[i][1]=add(dp[i][1],add(mul(3,dp[i-1][1]),dp[i-1][0]));
			else
				dp[i][1]=add(dp[i][1],mul(2,dp[i-1][1]));
			dp[i][0]=dp[i-1][0];
		}
		printf("%d\n",add(dp[n][0],dp[n][1]));
	}
	return 0;
}

E. Bob’s Problem

题意翻译

给定一个有 \(n\) 个点 \(m\) 条边的无向图 \(G\),选不超过 \(k\) 条边使得图联通且边权值最大。

题解

因为权值都为正整数,所以黑边全选,白边求最大生成树即可,剩余白边用堆处理。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=5e4+5;
const int MAXM=5e5+5;

namespace UnionFind{
	int fa[MAXN];
	inline void Init(reg int n){
		for(reg int i=1;i<=n;++i)
			fa[i]=i;
		return;
	}
	inline int find(reg int x){
		if(x==fa[x])
			return x;
		else
			return fa[x]=find(fa[x]);
	}
	inline void merge(reg int a,reg int b){
		reg int ra=find(a),rb=find(b);
		if(ra!=rb)
			fa[rb]=ra;
		return;
	}
	inline bool search(reg int a,reg int b){
		return find(a)==find(b);
	}
}

struct Edge{
	int u,v,w;
	inline Edge(reg int u=0,reg int v=0,reg int w=0):u(u),v(v),w(w){
		return;
	}
	inline bool operator<(const Edge& a)const{
		return w>a.w;
	}
};

int n,m,k;
Edge W[MAXM],B[MAXM];

int main(void){
	reg int T=read();
	while(T--){
		n=read(),m=read(),k=read();
		reg int totB=0,totW=0;
		for(reg int i=1;i<=m;++i){
			static int u,v,w,c;
			u=read(),v=read(),w=read(),c=read();
			if(c)
				W[++totW]=Edge(u,v,w);
			else
				B[++totB]=Edge(u,v,w);
		}
		UnionFind::Init(n);
		reg ll ans=0;
		reg int cnt=0;
		for(reg int i=1;i<=totB;++i){
			ans+=B[i].w;
			if(!UnionFind::search(B[i].u,B[i].v)){
				++cnt;
				UnionFind::merge(B[i].u,B[i].v);
			}
		}
		//sort(B+1,B+totB+1);
		sort(W+1,W+totW+1);
		priority_queue<int> Q;
		for(reg int i=1;i<=totW&&k;++i)
			if(!UnionFind::search(W[i].u,W[i].v)){
				++cnt,--k;
				ans+=W[i].w;
				UnionFind::merge(W[i].u,W[i].v);
			}
			else
				Q.push(W[i].w);
		if(cnt==n-1){
			while(k&&!Q.empty()){
				--k;
				ans+=Q.top();
				Q.pop();
			}
			printf("%lld\n",ans);
		}
		else
			puts("-1");
	}
	return 0;
}

G. Eating Plan

题意翻译

给定 \(n\) 和排列 \(\{a_n\}\),有 \(m\) 组询问,每组询问给出 \(k\),设 \(l,r\in\left[1,n\right]\)。

求最小的 \(r-l+1\),满足:
\[\sum^r_{i=l}(a_i!)\bmod t\geq k\]

其中 \(t=998857459\)。

题解

看到奇怪的模数,首先打开 \(\texttt{factor}\),发现
\[t=998857459=461\times 773\times 2803\]

所以说大于等于 \(2804\) 的数的阶乘全部为 \(0\),所以直接删去 \(0\) 即可,又因为 \(a\) 是 \(n\) 的排列,所以有效数字不超过 \(2803\) 个,直接暴力即可。

时间复杂度为 \(\Theta(\omega^2)\),其中 \(\omega=2803\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int t=461*773*2803;

const int MAXN=1e5+5;
const int MAXM=1e4+5;
const int MAXSIZE=3e3+5;

inline int add(reg int a,reg int b){
	reg int sum=a+b;
	return sum>=t?sum-t:sum;
}

int n,m;
int a[MAXN];
int fac[MAXN];

inline void Init(reg int n){
	fac[0]=1;
	for(reg int i=1;i<=n;++i)
		fac[i]=1ll*fac[i-1]*i%t;
	return;
}

int f[MAXN];
int sum[MAXN];

struct querys{
	int k,id;
	inline querys(reg int k=0,reg int id=0):k(k),id(id){
		return;
	}
	inline bool operator<(const querys& a)const{
		return k<a.k;
	}
};

vector<int> V;
querys q[MAXM];
int ans[MAXM];

int main(void){
	Init(3e3);
	n=read(),m=read();
	for(reg int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i){
		a[i]=fac[a[i]];
		f[1]=max(f[1],a[i]);
		sum[i]=add(sum[i-1],a[i]);
		if(a[i])
			V.push_back(i);
	}
	for(reg int i=0,size=V.size();i<size;++i)
		for(reg int j=i+1;j<size;++j)
			f[V[j]-V[i]+1]=max(f[V[j]-V[i]+1],add(sum[V[j]],t-sum[V[i]-1]));
	for(reg int i=1;i<=m;++i){
		static int k;
		k=read();
		q[i]=querys(k,i);
	}
	sort(q+1,q+m+1);
	reg int j=1;
	for(reg int i=1;i<=n;++i)
		while(j<=m&&q[j].k<=f[i]){
			ans[q[j].id]=i;
			++j;
		}
	for(reg int i=1;i<=m;++i)
		printf("%d\n",ans[i]?ans[i]:-1);
	return 0;
}

J. Summon

题意翻译

在一个长度为 \(n\) 的环上填 \(0,1,2,3\),有 \(m\) 个长度为 \(4\) 的连续的顺时针的字段不能出现。在旋转之后相同的方案算是同一种。问最终有多少种不同的填法。