本文共 1974 字，大约阅读时间需要 6 分钟。

D. Armchairs

题目描述

解法

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

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

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

#include 
   
    #include 
    
     #include 
     
      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
      
        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
       
        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 
   
    #include 
    
     using namespace std;const int M = 50005;const int MOD = 998244353;#define int long longint 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