「ZROI 2018」0820 暑假普转提模拟赛

题目列表

  1. 「Prefix Sum」
  2. 「Bead」
  3. 「Train」
  4. 「监视 G 房」

A. 「Prefix Sum」

很容易推出答案的式子 $C_{n+m-1}^{n-1}$

考虑证明答案的正确性:对于一个数,每次做前缀和时会对后面的数做出贡献,那么问题转化为:一个数向后跳 $m$ 次(做 $m$ 次前缀和),也可以不跳,总共要跳 $n$ 步(对后面所有数字做出贡献),求方案数。(当然也可以像我一样打表找规律)

则有 $\sum_{i=1}^m x_i=n\quad(x_i\geqslant 0)$,用插板法可以求解。如果暴力计算组合数,时间复杂度为 $O(m)$ 可以得到 $60$ 分。

其实正解只是优化了答案的式子。

上述式子的分子分母项数都是 $O(n)$ 级别的。

时间复杂度:$O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
const int N=5005;
const int P=998244353;
long long pow(long long x,long long p) {
long long res=1LL;
for(;p;p>>=1,x=(x*x)%P) if(p&1) res=(res*x)%P;
return res;
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
long long f1=1LL,f2=1LL;
for(int i=m+1;i<=n+m-1;++i) f1=(f1*i%P);
for(int i=1;i<n;++i) f2=(f2*i%P);
printf("%lld\n",f1*pow(f2,P-2)%P);
return 0;
}

B. 「Bead」

显然此题为动态规划,$f[i][j]$ 表示已经分了 $i$ 段,最后一次分割在 $j$ 的后面,状态转移方程为:

$f[i][j]=\min(f[i][j],f[k][j-1]+res[k+1][i])\quad(0\le k<i)$

其中 $res[i][j]$ 表示 $i\sim j$ 的价值。初始化为 $f[0][0]=0$ 其余为 $\infty$。

很显然状态已经无法优化了,考虑转移优化。其实这个状态转移方程满足决策单调性,因此我们可以整体二分求解。

记 $nl$ 和 $nr$ 为当前状态 $l$ 和 $r$ 的最优决策段,当 $l=r$ 时直接在 $f[k-1][nl\sim nr]$ 转移即可,否则求出 $mid=(l+r)/2$ 的在当前决策的最优决策点,接下来递归求解 $[l,mid-1]$ 和 $[mid+1,r]$。

时间复杂度:$O(n\log n)$

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=100005;
int n,k,a[N],c[N],f[25][N],t[N];
int L,R,ans;

int query(int l,int r) {
while(L>l) ans+=c[a[--L]]++;
while(R<r) ans+=c[a[++R]]++;
while(L<l) ans-=--c[a[L++]];
while(R>r) ans-=--c[a[R--]];
return ans;
}
void solve(int k,int l,int r,int nl,int nr) {
if(l>r) return;
if(l==r) {
for(int i=nl;i<=nr;++i) f[k][l]=std::min(f[k][l],f[k-1][i-1]+query(i,l));
return;
}
int mid=(l+r)>>1;
for(int i=nl;i<=nr;++i) t[i]=f[k-1][i-1]+query(i,mid);
int idx=0;
for(int i=nl;i<=nr;++i) if(!idx||t[i]<t[idx]) idx=i;
f[k][mid]=t[idx];
solve(k,l,mid-1,nl,idx);
solve(k,mid+1,r,idx,nr);
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
L=1; R=0;
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=k;++i) solve(i,1,n,1,n);
printf("%d\n",f[k][n]);
return 0;
}

C. 「Train」

对于每列火车,我们可以将其路线拆成 $x\rightarrow LCA\rightarrow y$。若我们在 $x\sim LCA$ 这部分上车,那么肯定不是最优的(在到达 $x$ 之前,$x\sim LCA$ 肯定都到达过)。故我们可以将所有线路变成 $LCA\rightarrow y$,即为许多向下的链。

我们又可以把线路转化为从 $1$ 出发到 $y$(虽然 $1\sim LCA$ 并不存在,但是这样方便排序),根据新的出发时间排序(如果时间相同则按照深度排序),如果当前时间是可达的则说明这列火车可以被乘坐,于是我们把 $LCA$ 到 $y$ 的点都标记为可达的。标记时从下到上标记,遇到已经标记过的点就退出(如果 $x$ 被标记,那么 $1\sim x$ 肯定都被标记了)。

时间复杂性:$O(m\log n)$

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
inline char in() {
static char buf[1000001],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template <class Tp> void read(register Tp &s) {
s=0;
register bool neg=0;
register char c=in();
while(c<'0'||c>'9') {if(c=='-')neg=1;c=in();}
while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+c-48,c=in();
s=(neg?-s:s);
}
template <class Tp> void write(register Tp x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}


const int N=300005;
int n,m,tot,hd[N],dep[N],f[N][21];
long long dis[N];
bool vis[N];
struct Edge {
int to,nxt,w;
}e[N<<1];
struct Train {
int u,v;
long long st;
bool operator < (const Train &b) const {
return st==b.st?dep[u]<dep[b.u]:st<b.st;
}
}tr[N];

void add(int u,int v,int w) {
e[++tot].to=v;
e[tot].nxt=hd[u];
e[tot].w=w;
hd[u]=tot;
}
void dfs(int u,int fa) {
f[u][0]=fa; dep[u]=dep[fa]+1;
for(int i=1;(1<<i)<=dep[u];++i) f[u][i]=f[f[u][i-1]][i-1];
for(int i=hd[u];i;i=e[i].nxt) {
int v=e[i].to;
if(v!=fa) {
dis[v]=dis[u]+e[i].w;
dfs(v,u);
}
}
}
int lca(int x,int y) {
if(dep[x]>dep[y]) swap(x,y);
for(int i=20;i>=0;--i) if(dep[y]-(1<<i)>=dep[x]) y=f[y][i];
if(x==y) return x;
for(int i=20;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int main() {
read(n); read(m);
for(int u,v,w,i=1;i<n;++i) {
read(u); read(v); read(w);
add(u,v,w); add(v,u,w);
}
dfs(1,0);
for(int u,v,t,i=1;i<=m;++i) {
read(u); read(v); read(t);
int x=lca(u,v);
Train tmp;
tmp.u=x; tmp.v=v; tmp.st=t+dis[u]-2*dis[x];
tr[i]=tmp;
}
sort(tr+1,tr+m+1);
vis[1]=1;
for(int i=1;i<=m;++i) {
if(vis[tr[i].u]) {
int x=tr[i].v;
while(!vis[x]) vis[x]=1,x=f[x][0];
}
}
int ans=0;
for(int i=1;i<=n;++i) ans+=vis[i];
printf("%d\n",ans);
for(int i=1;i<=n;++i) if(vis[i]) printf("%d ",i);
puts("");
return 0;
}

D. 「监视 G 房」

树形 $\text{DP}$,记 $f[i][0,1,2]$ 分别表示第 $i$ 个结点 只有父亲、只有儿子、只有自己 放摄像头的最小数量,$g[i][0,1,2]$ 为其方案数。

对于树形 $\text{DP}$ 的具体实现见下方代码(虽然没有注释,但是所有代码的含义都是字面意思)。

时间复杂度:$O(n)$

代码

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
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=100005;
const int P=1000000007;
int n,tot,hd[N],f[N][3],g[N][3];
// 0:father 1:son 2:itself
struct Edge {
int to,nxt;
}e[N<<1];

void add(int u,int v) {
e[++tot].to=v;
e[tot].nxt=hd[u];
hd[u]=tot;
}
void update(int &x,int val) {
((x+=val)>=P)&&(x-=P);
}
void dfs(int u,int fa) {
f[u][1]=(1<<20); f[u][2]=1;
g[u][0]=g[u][1]=g[u][2]=1;
for(int i=hd[u];i;i=e[i].nxt) {
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);

int res=0;
int mn=min(f[v][0],min(f[v][1],f[v][2]));
if(f[v][0]==mn) update(res,g[v][0]);
if(f[v][1]==mn) update(res,g[v][1]);
if(f[v][2]==mn) update(res,g[v][2]);
f[u][2]+=mn;
g[u][2]=1LL*g[u][2]*res%P;

res=0;
mn=min(f[u][1]+min(f[v][1],f[v][2]),f[u][0]+f[v][2]);
if(f[u][1]+f[v][1]==mn) update(res,g[v][1]);
if(f[u][1]+f[v][2]==mn) update(res,g[v][2]);
f[u][1]=mn;
g[u][1]=1LL*res*g[u][1]%P;

if(f[u][0]+f[v][2]==mn) update(g[u][1],1LL*g[u][0]*g[v][2]%P);
f[u][0]+=f[v][1];
g[u][0]=1LL*g[u][0]*g[v][1]%P;
}
}
int main() {
scanf("%d",&n);
for(int u,v,i=1;i<n;++i) {
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs(1,0);
if(f[1][1]<f[1][2]) printf("%d\n%d\n",f[1][1],g[1][1]);
else if(f[1][1]>f[1][2]) printf("%d\n%d\n",f[1][2],g[1][2]);
else printf("%d\n%d\n",f[1][1],(g[1][1]+g[1][2])%P);
return 0;
}
0%