[LOJ #2473] [九省联考2018] 秘密袭击coat

题目链接

LOJ,LOJ机子是真的快

Solution

我直接上暴力了...\(O(n^2k)\)洛谷要\(O2\)才能过...loj平均单点一秒...

直接枚举每个点为第\(k\)大的点，然后\(dp\)出方案数统计答案就好了。

\(f[i][j]\)\(dfs\)下去的时候表示考虑到\(i\)，有\(j\)个大于\(i\)的点的方案数，此时没有考虑儿子。

然后回溯的时候从叶子节点把儿子的影响加回来就好了。

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define ll long long 

const int maxn = 1700+10;

const int inf = 1e9;

const lf eps = 1e-8;

const int mod = 64123;

int val[maxn],f[maxn][maxn],head[maxn],tot,n,k,w,ans,rt;

struct edge{int to,nxt;}e[maxn<<1];

void Add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}

void ins(int u,int v) {Add(u,v),Add(v,u);}

int add(int x,int y) {return x+y>mod?x+y-mod:x+y;}

void dfs(int x,int fa) {

	if(val[x]>val[rt]||(val[x]==val[rt]&&x>rt))

		for(int i=2;i<=k;i++) f[x][i]=add(f[x][i],f[fa][i-1]);

	else for(int i=1;i<=k;i++) f[x][i]=add(f[x][i],f[fa][i]);

	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) dfs(e[i].to,x);

	if(fa) for(int i=1;i<=k;i++) f[fa][i]=add(f[fa][i],f[x][i]);

}

int main() {

	read(n),read(k),read(w);

	for(int i=1;i<=n;i++) read(val[i]);

	for(int i=1,x,y;i<n;i++) read(x),read(y),ins(x,y);

	for(int i=1;i<=n;i++) {

		int cnt=1;rt=i;

		for(int j=1;j<=n;j++) cnt+=val[j]>val[i]||(val[j]==val[i]&&j>i);

		if(cnt<k) continue;

		for(int j=1;j<=n;j++)

			for(int t=0;t<=k;t++) f[j][t]=0;

		f[i][1]=1;for(int j=head[i];j;j=e[j].nxt) dfs(e[j].to,i);

		ans=add(ans,1ll*f[i][k]*val[i]%mod);

	}

	write(ans);

	return 0;

}

巴特西

[LOJ #2473] [九省联考2018] 秘密袭击coat

题目链接

Solution

最新文章

热门文章