Educational Codeforces Round 109 (Rated for Div. 2)

D. Armchairs

题目描述

点此看题

解法

很多贪心都是不行的，反例基本上都举得出来，我不知道模拟费用流能不能做。

话不多说，直接进入正解。这道题是一个不对等匹配的问题，但是我们所熟悉的模型是相等个数的东西来匹配，这个经典问题是可以排序解决的。那么我们可以考虑枚举 \(a_i=0\) 参与匹配的集合 \(S\)，然后依次匹配即可。

选出这个集合可以 \(dp\)，设 \(dp[i][j]\) 表示考虑到 \(i\) 已经匹配了 \(j\) 个 \(1\) 的最小花费，随便转移就可以 \(O(n^2)\)

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int M = 5005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;}
	while(c>=‘0‘ && c<=‘9‘) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[M],dp[M][M];vector<int> v;
int Abs(int x) {return x>0?x:-x;}
signed main()
{
	n=read();v.push_back(0);
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(a[i]) v.push_back(i);
	}
	memset(dp,0x3f,sizeof dp);
	dp[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<v.size();j++)
		{
			int x=v[j];
			dp[i][j]=min(dp[i][j],dp[i-1][j]);
			if(!a[i] && j>0)
				dp[i][j]=min(dp[i][j],dp[i-1][j-1]+Abs(i-v[j]));
		}
	}
	printf("%d\n",dp[n][v.size()-1]);
}

E. Assimilation IV

题目描述

点此看题

解法

我觉得我就是被概率洗脑了，有时候算算方案数也挺好的。

一看就是要求每个点的期望，对于点 \(i\) 我们考虑他怎么才算被覆盖，如果存在 \(p_j\leq n+1-a(j,i)\) 则合法。但是这个好像不是很好算，正难则反，我们考虑什么时候不合法，\(\forall p_j>n+1-a(j,i)\) 则不合法，拿 \(1\) 减去不合法的概率即可。

求不合法的概率可以求排列 \(p\) 的方案数除以总方案数，我们用 \(cnt\) 数组统计 \(n+1-a(j,i)\)，那么填第一个位置可以有 \(cnt[0]\) 种方案，填第二个位置有 \(cnt[1]+cnt[0]-1\) 种方案，填第三个位置有 \(cnt[2]+cnt[1]+cnt[0]-2\) 种方案 \(...\) 以此类推。

#include <cstdio>
#include <iostream>
using namespace std;
const int M = 50005;
const int MOD = 998244353;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;}
	while(c>=‘0‘ && c<=‘9‘) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,inv,ans,a[25][M],cnt[M];
int qkpow(int a,int b)
{
	int r=1;
	while(b>0)
	{
		if(b&1) r=r*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return r;
}
signed main()
{
	n=read();m=read();inv=1;
	for(int i=1;i<=n;i++)
		inv=inv*qkpow(i,MOD-2)%MOD;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=read();
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=n;j++) cnt[j]=0;
		for(int j=1;j<=n;j++) cnt[n+1-a[j][i]]++;
		int tmp=inv;
		for(int j=0,s=0;j<n;j++)
		{
			s+=cnt[j];
			tmp=tmp*s%MOD;
			s=max(0ll,s-1);
		}
		ans=(ans+1-tmp)%MOD;
	}
	printf("%lld\n",(ans+MOD)%MOD);
}

Educational Codeforces Round 109 (Rated for Div. 2)

原文：https://www.cnblogs.com/C202044zxy/p/14787374.html