20190922 「HZOJ NOIP2019 Round #7」20190922模拟

综述

这次是USACO2019JAN Gold的题目。

\(\mathrm{Cow Poetry}\)

题解

因为每句诗的长度一定是\(k\)，所以自然而然想到背包。

设\(opt[i][j]\)代表到第\(i\)位时，结尾为\(j\)的方案数。

背包，注意\(\mathrm{DP}\)顺序为先枚举\(i\)，后枚举单词。（Debug了一小时就因为这个）

然后乘法原理统计答案即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

void read(int &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

void fr(int &x){

	char ch=1;

	while(!(ch>='A'&&ch<='Z')) ch=getchar();

	x=ch-'A'+1;

}

const int mod=1000000007;

const int maxn=5003;

const int maxm=100100;

int n,m,k;

int s[maxn],c[maxn];

int e[maxn];

int opt[maxn][maxn],sum[maxm];

void Init(){

	read(n);read(m);read(k);

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

		read(s[i]);read(c[i]);

	}

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

		fr(e[i]);

	}

}

void dp(){

	sum[0]=1;

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

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

			if(i<s[j]) continue;

			opt[i][c[j]]=(opt[i][c[j]]+sum[i-s[j]])%mod;

			sum[i]=(sum[i]+sum[i-s[j]])%mod;

		}

	}

}

int tot,cnt[27];

int ksm(long long x,int p){

	long long ret=1;

	while(p){

		if(p&1) ret=ret*x%mod;p>>=1;

		x=x*x%mod;

	}

	return ret;

}

void Work(){

	dp();

	long long ans=0,sum=1;

	for(int i=1;i<=m;i++) ++cnt[e[i]];

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

		if(!cnt[i]) continue;

		ans=0;

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

			if(!opt[k][j]) continue;

			ans=(ans+ksm(opt[k][j],cnt[i]))%mod;

		}

		sum=sum*ans%mod;

	}

	printf("%lld\n",sum);

}

int main(){

	freopen("poetry.in","r",stdin);freopen("poetry.out","w",stdout);

	Init();Work();

	fclose(stdin);fclose(stdout);

	return 0;

}

\(\mathrm{Sleepy Cow Sorting}\)

题解

树状数组。

设\(c[i]\)代表\([1,i]\)中归位数。

显然最终的目的是将整个序列排序为一个上升序列，于是倒序枚举，先把最后有序的插入。

剩下来前面无序的就是要操作的，于是直接输出操作次数。

接下来方案很容易构造。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

void read(int &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

const int maxn=100000+7;

#define lowbit(pos) (pos&(-pos))

int c[maxn],n,a[maxn];

void change(int pos,int k){

	while(pos<=n){

		c[pos]+=k;pos+=lowbit(pos);

	}

}

int query(int pos){

	int ret=0;

	while(pos){

		ret+=c[pos];pos-=lowbit(pos);

	}

	return ret;

}

int ans,cnt;

int main(){

	freopen("sleepy.in","r",stdin);freopen("sleepy.out","w",stdout);

	read(n);

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

	for(int i=n;i>=1;i--){

		ans++;--cnt;change(a[i],1);

		if(a[i-1]>a[i]) break;

	}

	cnt+=n;

	printf("%d\n",cnt);

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

		--cnt;printf("%d ",query(a[i])+cnt);

		change(a[i],1);

	}

	fclose(stdin);fclose(stdout);

	return 0;

}

\(\mathrm{Shortcut}\)

题解

最短路树。

显然奶牛的路径就是从\(1\)走到各个草地，于是从\(1\)跑最短路，构建最短路树。

为了保证字典序，从\(1\)到\(n\)依次枚举每个结点，构建。

显然，用贪心的思想，这条边一定是从某个结点\(x\)联向\(1\)的。

然后深度遍历这棵最短路树，在每个结点处处理答案即可。

注意需要long long

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template<typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

#define int long long

const int maxn=10000+7;

const int maxm=100000+7;

const int INF=0x3f3f3f3f3f3f3f3fLL;

int n,m,t;

int cows[maxn];

int u[maxm],Head[maxn],Next[maxm],to[maxm],w[maxm],tot=1;

struct node{

	int id,dis;

	bool operator <(node a)const{

		return dis>a.dis;

	}

};

void add(int x,int y,int z){

	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z,u[tot]=x;

}

int Jead[maxn],Mext[maxm],of[maxm],fork=1;

void fafa(int x,int y){

	of[++fork]=y,Mext[fork]=Jead[x],Jead[x]=fork;

}

int dis[maxn];

bool vis[maxn];

void dijkstra(){

	for(int i=2;i<=n;i++) dis[i]=INF;

	priority_queue<node>q;

	q.push(node{1,0});dis[1]=0;

	while(!q.empty()){

		int x=q.top().id;q.pop();

		if(vis[x]) continue;vis[x]=1;

		for(int i=Head[x];i;i=Next[i]){

			int y=to[i];

			if(dis[y]>dis[x]+w[i]){

				dis[y]=dis[x]+w[i];

				q.push((node){y,dis[y]});

			}

		}

	}

}

bool exist[maxn];

void build(){

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

		for(int i=Head[x];i;i=Next[i]){

			int y=to[i];

			if(!exist[y]&&dis[y]==dis[x]+w[i]){

				fafa(x,y);fafa(y,x);exist[y]=1;

			}

		}

	}

}

bool ins[maxn];

int size[maxn],ans;

void dfs(int x){

	ins[x]=1,size[x]=cows[x];

	for(int i=Jead[x];i;i=Mext[i]){

		int y=of[i];

		if(!ins[y]){

			dfs(y);size[x]+=size[y];

		}

	}

	ans=max(ans,size[x]*(dis[x]-t));

}

void Init(){

	read(n);read(m);read(t);

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

	for(int i=1,x,y,z;i<=m;i++){

		read(x);read(y);read(z);

		add(x,y,z);add(y,x,z);

	}

}

void Work(){

	dijkstra();

	build();

	dfs(1);

	printf("%lld\n",ans);

}

signed main(){

	freopen("shortcut.in","r",stdin);freopen("shortcut.out","w",stdout);

	Init();Work();

	fclose(stdin);fclose(stdout);

	return 0;

}

巴特西

20190922 「HZOJ NOIP2019 Round #7」20190922模拟

综述

\(\mathrm{Cow Poetry}\)

题解

\(\mathrm{Code}\)

\(\mathrm{Sleepy Cow Sorting}\)

题解

\(\mathrm{Code}\)

\(\mathrm{Shortcut}\)

题解

\(\mathrm{Code}\)

最新文章

热门文章