20190423模拟赛

侯爷爷的场

A

现在给定n个数 ,找一个非空子集,使得这个子集的平均数减去中位数最大, $n \leq 2e5$

请先思考后再展开

显然枚举中位数,然后显然长度是单峰的,选择方案显然是「中位数左边第一个往左若干,n往左若干」

说些小trick:

  1. 如果考虑集合大小为偶数的情况,那么一定左右两边第一个数都会被选;考虑反证,把中位数右边那个往左移,平均数的变化量一定比中位数的变化量小
  2. 其实既然想到上面这个,类似地可以发现,只有奇数个是有用的;考虑反证,把中位数右边那个丢掉,同上;而且这两个都让ln的上限增大了(选择更多)

实现直接二分变化量即可,时间复杂度为 $O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ll a[MAX_N],sum[MAX_N];int n;
ll getsum(int l,int r){return sum[r]-sum[l-1];}
double getf(int i,int ln){return 1.0*(getsum(i-ln,i)+getsum(n-ln+1,n))/(2*ln+1);}
void main()
{
n=qread();for(int i=1;i<=n;i++) a[i]=qread();sort(a+1,a+n+1);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
double mx=0;
for(int i=1;i<=n;i++)
{
int l=0,r=min(i-1,n-i);
while(l<=r)
{
int mid=(l+r)>>1;
double x=getf(i,mid);mx=max(mx,x-a[i]);if(l==r) break;
double y=getf(i,mid+1);mx=max(mx,y-a[i]);
if(x<=y) l=mid+1;
else r=mid-1;
}
}
printf("%.5lf",mx);
}

B

有两个长度为n的数组和2n个数,每个数可以填在第一个数组的ai处,也可以填在第二个数组的bi处,数组上每
个位置只能填一个数。求最小代价(两个数组的和的差的绝对值),如果无解(不能填满)输出-1。 $n \leq 3e4,num\leq 15$

请先思考后再展开

建棵2n个点的基环树,然后假设树边是直接得到的,环上就只有两个方向,考虑对A-B的贡献(不考虑绝对值),就是X和-X,直接背包

背包有两种选择,直接分治fft、根号背包(套路已更新);然后第二种常数更小,随机数据飞快,第一种会被卡常

C

给出一个 $n \times m$ 的矩形,每个位置可以填上 $[1,c]$ 中的任意一个数,要求填好后任意两行不完全相等,任意两列不完全相等,求方案数

$n,m,c \leq 5e3$

请先思考后再展开

经典套路题
$g(m)表示保证行合法=(c^m)^{\underline n}$
f(m)表示都合法,考虑用f表示g
设有k组本质不同的列,那么相当于只有k列要求满足行的条件
$g(m)=\sum_{k=0}^m S2(m,k)f(k)$
反演得$f(m)=\sum\limits_{i=0}^m(-1)^{m-i}\begin{bmatrix}m\i \end{bmatrix}g(i)$

D

给定一个n个点m条边的有向图,将这个图复制成e份,任意两份之间没有连边,求复制得到的图的补图的哈密顿路径条数%998244353。$n \leq 14,e \leq 5e4$

请先思考后再展开

初看感觉极不可做,会觉得哈密顿这种东西只能指数级搞;但细看数据范围发现n很小,那估计就是利用复制这个性质去搞。

问题等价于e种颜色,每种n个球,相邻不同色或同色无边的排列方案数

考虑容斥,通常我们都会希望设一个f为恰好g为至少,然后希望转移系数带有组合数什么的便于反演

$g(n)=\sum_{i=n}^N C_i^n f(i)$

那么假设某个方案有恰好k段连续的非法边(其实这里思路清奇),那么我们要假装没看到一部分来产生组合的贡献

每个连通块是相同的,直接卷起来,若总共固定了成k段连续的块,方案数为可重集即 $\frac{k!}{\prod k_t!}$,此处时间为 $O(nelog)$

考虑得到之后如何统计答案,k段则有ne-k条边,系数为 $(-1)^{ne-k}$

现在考虑同色无边这个限制,n很小直接状压dp求出生成函数的系数即可,此处时间为 $O(2^nn^3)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
//#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
const int MOD=998244353;
void add(ll &x,ll y){x+=y;if(x>=MOD)x-=MOD;if(x<=-MOD)x+=MOD; }
ll qpower(ll x,int e)
{
ll ans=1;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv(ll x){return qpower(x,MOD-2);}
const int MAX_N=4e6+10;
int bin[50];ll fac[MAX_N];
struct NTT
{
int R[MAX_N];void preR(int ln){for(int i=1;i<ln;i++)R[i]=(R[i>>1]>>1)|( (i&1)*bin[(int)log2(ln)-1] ); }
ll w[2][MAX_N];
void prew(int ln)
{
ll now0=qpower(3,(MOD-1)/ln),now1=inv(now0);w[0][0]=w[1][0]=1;
for(int i=1;i<ln;i++) w[0][i]=w[0][i-1]*now0%MOD,w[1][i]=w[1][i-1]*now1%MOD;
}
void DFT(ll A[],int n,int f)
{
for(int i=1;i<n;i++) if(i>R[i]) swap(A[i],A[R[i]]);
for(int ln=1;ln<=n/2;ln*=2) for(int st=0;st<n;st+=2*ln) for(int k=0;k<ln;k++)
{
ll x=A[st+k],y=w[f][k*(n/ln/2)]*A[st+ln+k]%MOD;
A[st+k]=(x+y)%MOD;A[st+ln+k]=(x-y)%MOD;
}
}
}ntt;
ll A[MAX_N];
void solve(int e,int n)
{
for(int k=0;k<=n;k++) A[k]=A[k]*inv(fac[k])%MOD;
int ln=1;while(ln<=n) ln*=2;ntt.preR(ln);ntt.prew(ln);
ntt.DFT(A,ln,0);
for(int i=0;i<ln;i++) A[i]=qpower(A[i],e);
ntt.DFT(A,ln,1);
ll ans=0;
for(int k=0,t=(n&1)?-1:1;k<=n;k++,t=-t) add(ans,A[k]*inv(ln)%MOD*t*fac[k]%MOD);
write((ans+MOD)%MOD);
}
const int MAX_M=15;
int mp[MAX_M][MAX_M];
ll f[1<<MAX_M][MAX_M][MAX_M];//f(S,k,lst)
void dp(int n)
{
for(int i=0;i<n;i++) f[bin[i]][1][i]=1;
for(int S=0;S<bin[n];S++) for(int k=0;k<=n;k++) for(int lst=0;lst<n;lst++) if(f[S][k][lst])
for(int j=0;j<n;j++) if((S&bin[j])==0)
{
add(f[S|bin[j]][k+1][j],f[S][k][lst]);
if(mp[lst][j]) add(f[S|bin[j]][k][j],f[S][k][lst]);
}
for(int k=0;k<=n;k++) for(int lst=0;lst<n;lst++) add(A[k],f[bin[n]-1][k][lst]);
}
void main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=fac[i-1]*i%MOD;
int e=qread(),n=qread(),m=qread();
while(m--){int x=qread()-1,y=qread()-1;mp[x][y]=1;}
dp(n);solve(e,e*n);
}
};
signed main()
{
//freopen("a.in","r",stdin);
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/13ef.html
转载请注明出处,谢谢!