[NowCoder]牛客OI周赛1 题解

A.分组

首先，认识的人不超过3个，因此不存在无解的方案

考虑直接构造，先把所有点设为1，顺序扫一遍把有问题的点加入队列

每次取队头，将其颜色取反，再更新有问题的点

复杂度：考虑到每个点不会操作2次，所以是$O(N+M)$

到目前为止、AC的代码几乎都是因为数据水才AC的错误代码

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=(a);i<=(b);++i)

#define DEC(i,a,b) for(int i=(a);i>=(b);--i)

#define dbg(...) fprintf(stderr,__VA_ARGS__)

using namespace std;

template<typename T,typename U> inline bool smax(T&x,const U&y){return y>x?(x=y,1):0;}

template<typename T,typename U> inline bool smin(T&x,const U&y){return y<x?(x=y,1):0;}

typedef long long ll;

#define pb push_back

inline int read(){

    int w=0,p=0;char c;

    while(!isdigit(c=getchar()))if(c=='-')p=1;

    while(isdigit(c))w=(w<<1)+(w<<3)+(c^'0'),c=getchar();

    return p?-w:w;

}

const int n=read(),N=1e5+5;

vector<int>g[N];

int q[N<<2],l=1,r,c[N],s[N];

bool ins[N];

void solve(){

	REP(i,1,n)c[i]=1;

	REP(x,1,n){

		for(int y:g[x])if(c[x]==c[y])++s[x];

		if(s[x]>=2)q[++r]=x,ins[x]=1;

	}

	while(l<=r){

		int&x=q[l++];if(!ins[x])continue;ins[x]=0;

		c[x]^=3;s[x]=0;

		for(int y:g[x])if(c[x]==c[y]){

			++s[x],++s[y];

			if(s[y]>=2&&!ins[y])q[++r]=y,ins[y]=1;

		}else if(--s[y]<2)ins[y]=0;

	}

}

int main(){

	int m=read();

	while(m--){int x=read(),y=read();g[x].pb(y),g[y].pb(x);}

	solve();

	REP(i,1,n)printf("%d ",c[i]);

	return 0;

}

B.树

计数类问题,考虑计算以每个节点为下端点的合法方案数

设$s[x]$为子树大小，$d[x]$为x的深度，$son_x$为x的儿子集合

计算节点x时，显然两条路径的下端点都在x的不同子树内，方案数为

\[g[x]=\frac{s[x]\times(s[x]-1)}{2}-\sum_{y\in son_x}\frac{s[y]\times(s[y]-1)}{2}
\]

考虑上端点位置有几种不同情况

第一、分别在S1,S2（除了子树y的两个不同子树）

第二、分别在S1S2,S3S4

第三、在S到T路径上的点（两个端点相同，这个单独算上去即可）

(考试时候漏算了第一种，挂成30分。。)

因此，$$f[x]=\sum_{u\in S..T}(s[u]-s[son[u]])\times(n-s[u])+C_{s[u]-s[son[u]]}^2-\sum_{v\in son_u, v\ne son[u]}C_{s[v]}^2$$

\[Ans=\sum_xg[x]\times f[x]\times 2+(d[T]-d[S]+1)\times g[x]
\]

前缀和优化即可

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i(a);i<=(b);++i)

using namespace std;

typedef long long ll;

inline int read(){char c;int w;

    while(!isdigit(c=getchar()));w=c&15;

    while(isdigit(c=getchar()))w=w*10+(c&15);return w;

}

inline char smax(int&x,const int&y){return x<y?x=y,1:0;}

inline char smin(int&x,const int&y){return x>y?x=y,1:0;}

const int n=read(),l=read(),r=read(),N=2e5+5,p=1e9+7;

vector<int>g[N];

int a[N],dep[N];ll b[N],s[N],t[N],ans;

void go(int x,int f){

	dep[x]=dep[f]+1;s[x]=1;

	for(int y:g[x])if(y!=f)go(y,x),s[x]+=s[y],t[x]=(t[x]+s[y]*(s[y]-1)/2)%p;

	t[x]=(s[x]*(s[x]-1)/2-t[x]+p)%p;

}

inline void inc(ll&x,const ll&y){x+=y;if(x>=p)x-=p;;}

void dfs(int x,int f){

    const int&d=dep[x];a[d]=x;

    if(f)b[d-1]=(b[d-2]+t[f]+((s[f]-s[x])*((n-s[f]<<1)-s[x]-1+s[f])-s[f]*(s[f]-1)+s[x]*(s[x]-1)>>1))%p;

    if(d>l){

        const int top=max(1,d-r),down=d-l;

        inc(ans,(b[down]-b[top-1]+p)*(t[x]<<1|1)%p);

        inc(ans,(down-top+1)*t[x]%p);

    }

    for(int y:g[x])if(y!=f)dfs(y,x);

}

#define pb push_back

int main(){

    REP(i,2,n){int x=read(),y=read();g[x].pb(y),g[y].pb(x);}

    go(1,0);dfs(1,0);

    cout<<(ans%p+p)%p;

    return 0;

}

C.序列

注意到，如果交换一个序列的不同2个数，得到的F矩阵就是不同的

因此只需要求有序序列方案，再乘以斯特林数即可

这样转化为：x个不同的数，递增排列，相邻数相差不超过K，最大值最小值相差不超过M的方案数

设f[i][j]表示i个数，最大最小相差j的方案数，枚举最后两个数差值转移，然后前缀和优化一下即可

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i(a),i##_(b);i<=i##_;++i)

using namespace std;

const int N=2005,p=998244353;

int n,m,k,a[N][N],f[N][N],jc[N],s[N][N],ans;

int main(){

	cin>>n>>m>>k;a[0][0]=jc[0]=1;

	REP(i,1,n)jc[i]=1ll*jc[i-1]*i%p;

	REP(i,1,n)REP(j,1,i)a[i][j]=(a[i-1][j-1]+1ll*a[i-1][j]*j)%p;

	REP(i,0,m)s[1][i]=1;f[1][0]=1;

	REP(i,2,n)REP(j,1,m)

		f[i][j]=(f[i][j]+s[i-1][j-1]-(j-k>0?s[i-1][j-k-1]:0))%p,s[i][j]=(s[i][j-1]+f[i][j])%p;

	REP(i,1,n)ans=(ans+1ll*s[i][m]*a[n][i]%p*jc[i])%p;

	cout<<(ans+p)%p;

	return 0;

}

巴特西

[NowCoder]牛客OI周赛1 题解

A.分组

B.树

C.序列

最新文章

热门文章