NOMURA Programming Competition 2020-526互联

A - Study Scheduling

先算出总时间，然后在减去 \(K\) 就好了。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int h1,m1,h2,m2,k;
int main()
{
	scanf("%d%d%d%d%d",&h1,&m1,&h2,&m2,&k);
	int ansh=h2-h1,ansm=m2-m1;
	if(ansm<0) ansm+=60,ansh--;
	if(ansh<0) ansh+=24;
	int t=ansh*60+ansm;
	t-=k;
	printf("%d",max(t,0));
	return 0;
}

B - Postdocs

可以发现，将所有的 P 换成 D 答案肯定不会更劣，将所有 ? 换成 D 就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200005;
int n;
char s[N];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
		if(s[i]=='?') s[i]='D';
	printf("%s",s+1);
	return 0;
}

C - Lamps

考虑从下往上做，预处理出第 \(i\) 层满足第 \(n\) 行肯定有 \(a_n\) 个点的最大值 \(g_i\)；再从上往下做，第 \(1\) 行有 \(1\) 个点，预处理出第 \(i\) 层满足第 \(1\) 行有 \(1\) 个点的最大值 \(f_i\)，每层的答案就是取个最小值。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
int n;
int a[N];
long long f[N],g[N];

int main()
{
	scanf("%d",&n);
	for(int i=0;i<=n;i++)
		scanf("%d",&a[i]);
	if(a[0]>1)
	{
		printf("-1");
		return 0;
	}
	g[n]=a[n];
	for(int i=n-1;i>=0;i--)
		g[i]=g[i+1]+a[i];
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		f[i]=min((f[i-1]-a[i-1])*2,g[i]);
		if(a[i]>f[i])
		{
			printf("-1");
			return 0;
		}
	}
	long long ans=0;
	for(int i=0;i<=n;i++)
		ans+=f[i];
	printf("%lld",ans);
	return 0;
}

D - Urban Planning

考虑如果 \(p_i\neq -1\)，将 \(i\) 向 \(p_i\) 连边，可以发现，最后的肯定是基环树森林，答案就是 \(n\) 减环数。考虑计算所有的环数，然后再用总数 \(n(n-1)^k\) 减去就是答案，一个环的贡献就是 \((n-1)^k\)。

考虑加入了 \(p_i=-1\)，图中多出了树的情况。我们考虑一个环，它的大小为 \(a_1,a_2,\cdots a_m\) 的树构成的，它对答案的贡献即为 \((\prod a_i)(m-1)!(n-1)^{k-m}\)（注意特判 \(1\) 的情况）。

考虑计算贡献，令 \(f_{i,j}\) 表示前 \(i\) 棵树，选了 \(j\) 个树的 \(\sum (\prod a_k)\)，然后枚举选的树的数量加入答案中就好了。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=5005;
const int MOD=1000000007;
int n,k;
int p[N];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
vector<int>G[N];
bool vis[N];
int cnt,tot;
bool flag;
int a[N],m;
void dfs(int u,int father)
{
	if(vis[u])
	{
		if(!flag) cnt++;
		flag=true;
		return;
	}
	vis[u]=true;
	tot++;
	for(int v:G[u])
	{
		if(v==father) continue;
		dfs(v,u);
	}
	return;
}
long long fac[N];
void init(int n=5000)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	return;
}
long long dp[N][N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		if(p[i]==-1) k++;
		else G[i].push_back(p[i]),G[p[i]].push_back(i);
	}
	for(int u=1;u<=n;u++)
		if(!vis[u])
		{
			flag=false;
			tot=0;
			dfs(u,0);
			if(!flag) a[++m]=tot;
		}
	long long ans=n*ksm(n-1,k)%MOD;
	ans=(ans-cnt*ksm(n-1,k)%MOD+MOD)%MOD;
	dp[0][0]=1;
	for(int i=1;i<=k;i++)
	{
		dp[i][0]=1;
		for(int j=1;j<=i;j++)
			dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*a[i]%MOD)%MOD;
	}
	init();
	if(k>=1) ans=(ans-(dp[k][1]-k)*ksm(n-1,k-1)%MOD+MOD)%MOD;
	for(int i=2;i<=k;i++)
		ans=(ans-dp[k][i]*fac[i-1]%MOD*ksm(n-1,k-i)%MOD+MOD)%MOD;
	printf("%lld",ans);
	return 0;
}

E - Binary Programming

考虑一种贪心，肯定是先删 \(0\) 再删 \(1\)，显然奇数位置的 \(0\)，然后再从后往前删。

考虑将连续的一段缩起来一起考虑，对于一段长度为偶数的连续的 \(1\)，可以发现贡献是固定的，对于一段长度为奇数的连续的 \(1\)，我们只需要考虑多出来的那个 \(1\) 的贡献，这个贪心一下就好了。

这时候只剩下了 \(1\)，这个直接算一下就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200005;
int n;
char s[N];
char a[N];
int len[N],l[N];
int m;
int sum[N][2];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1,j=1;i<=n;i=j)
	{
		while(j<=n&&s[i]==s[j]) j++;
		m++,a[m]=s[i],len[m]=j-i;
	}
	for(int i=1;i<=m;i++)
	{
		sum[i][0]+=sum[i-1][0];
		sum[i][1]+=sum[i-1][1];
		sum[i][a[i]-'0']+=len[i];
		l[i]=l[i-1]+len[i];
	}
	long long ans=0;
	for(int i=1;i<=m;i++)
	{
		if(a[i]=='1')
		{
			if(len[i]&1)
			{
				ans+=(sum[i][0]+l[i]%2)/2;
				ans+=sum[m][0]-sum[i][0];
				int t=len[i]/2;
				ans+=sum[i][0]*t;
				ans+=(sum[m][0]-sum[i][0])*t;
			}
			else
			{
				int t=len[i]/2;
				ans+=sum[i][0]*t;
				ans+=(sum[m][0]-sum[i][0])*t;
			}
		}
	}
	for(int i=0;i<=sum[m][1];i++)
	{
		int s=sum[m][1]-i;
		ans+=(s+1)/2;
	}
	printf("%lld",ans);
	return 0;
}

F - Sorting Game

可以发现，如果 \(a\) 合法，对于某一位，如果这一位上 \(a_i=1,a_j=0\)，则 \(a_i,a_j\) 的更低位肯定相同。

令 \(f_{i,j}\) 表示当前填到第 \(i\) 层，总共有 \(j\) 个数的方案数。

考虑当前层填什么，

如果填 \(0\ldots 01 \ldots1\)，这层的填数方案有 \(j+1\) 种，转移为：\(f_{i-1,j}\cdot j\to f_{i,j}\)。
如果填 \(0\ldots 0 \mathbf{1x\ldots x0} 1\ldots 1\)，不妨看成是在 \(0\ldots 01\ldots 1\) 中插入 \(\mathbf{x\ldots x0}\)，这个的方案数即为 \(\sum\limits_{k=1}^{j-1} f_{i-1,k}\cdot k\cdot 2^{j-k-1}\)。

直接转移是 \(O(NM^2)\) 的，前缀和优化一波就是 \(O(NM)\) 的了。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
const int MOD=1000000007;
int n,m;
long long dp[N][N];
long long sum[N][N];
long long Pw[N],inP[N];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
void init(int n=5000)
{
	Pw[0]=1;
	for(int i=1;i<=n;i++)
		Pw[i]=Pw[i-1]*2%MOD;
	inP[n]=ksm(Pw[n],MOD-2);
	for(int i=n;i>=1;i--)
		inP[i-1]=inP[i]*2%MOD;
	return;
}
int main()
{
	init();
	scanf("%d%d",&n,&m);
	for(int j=1;j<=m;j++)
		dp[0][j]=1,sum[0][j]=(sum[0][j-1]+dp[0][j]*j%MOD*inP[j]%MOD)%MOD;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j]*(j+1)%MOD;
			dp[i][j]=(dp[i][j]+sum[i-1][j-1]*Pw[j-1]%MOD)%MOD;
			sum[i][j]=(sum[i][j-1]+dp[i][j]*j%MOD*inP[j]%MOD)%MOD;
		}
	printf("%lld",dp[n][m]);
	return 0;
}

competition programming nomura 2020

competition programming planning nomura

programming competition 1914f cf

programming competition原则1914f

programming keyence contest 2020

nomura

competition

hamburger_competition

hamburger_competition competition hamburger

competition codeforces summarize divide