题目链接： 鉴于估计bzoj活不久了，以后都尽量不贴bzoj的链接了 T1 数列 T2 游走 T3 切糕
代码在本文末尾
数列
主要考察：数学推导能力与转换能力算法：数学推导突破口：考虑每一个差分序列对答案的贡献正确思路：发现m的限制不能用组合→考虑差分数列
发现该题如果使用组合数，则无法满足相邻两天的差不超过M这个限制，而数据范围不允许使用容斥，所以排除组合数的可能
发现题目中有一句容易被认为是鸡肋的东西并且这些参数满足
M(K−1)<N
M
(
K
−
1
)
<
N
，本着出题人不会没事干去保证数据满足什么无用性质的想法，觉得这点应该是有用的
然后发现如果要满足相邻两天的差不超过M的话，维护差分数组是很简单的，于是向下深入
设差分数组为
{ai|i∈[1,k−1]}
{
a
i
|
i
∈
[
1
,
k
−
1
]
}
发现对于一个差分数组，满足差分后得到该数组的原数组有
n−∑k−1i=1a[i]
n
−
∑
i
=
1
k
−
1
a
[
i
]
个，所以总答案为
∑所有不一样的差分数组a[](n−∑i=1k−1a[i])
∑
所
有
不
一
样
的
差
分
数
组
a
[
]
(
n
−
∑
i
=
1
k
−
1
a
[
i
]
)
由于
M(K−1)<N
M
(
K
−
1
)
<
N
，所以总共有
mk−1
m
k
−
1
种不同的差分数组
提出
n
n
后，得到项n∗mk−1n∗mk−1
再考虑右边的项，总共
mk−1
m
k
−
1
个数组，每个里有
k−1
k
−
1
个元素，每个数字平均分布，每个出现
mk−1(k−1)m=mk−2(k−1)
m
k
−
1
(
k
−
1
)
m
=
m
k
−
2
(
k
−
1
)
次，使用求和公式求和即可
所以总答案为
n∗mk−1−mk−2∗(k−1)∗n(n+1)2
n
∗
m
k
−
1
−
m
k
−
2
∗
(
k
−
1
)
∗
n
(
n
+
1
)
2
游走
主要考察：转换能力算法：贪心+期望+高斯消元突破口：贪心，每条边分别考虑，且由点转移正确思路：每条边分别考虑→贪心→由点推边→高斯消元
这题先看数据范围
n≤500
n
≤
500
，肯定不是什么高端的诡异算法，目测时间复杂度在
O(n2logn)
O
(
n
2
log
n
)
到
O(n3)
O
(
n
3
)
左右
个人一看觉得像高斯消元，但发现有两种未知数（每个点的期望和每条边的权值）于是转换：不直接求点的期望答案，而是求边的期望，按照期望大小次序给定边权，再给边权赋值
但是求边的期望又可以由边两边的点的期望得到，只是这回求点的期望是求访问的期望，不是权值的期望，所以不用考虑边的权值，高斯消元即可
所以总流程为：
高斯消元求出每个点被访问到的期望
↓
根据点的期望反推每条边被访问到的期望
↓
按照每条边的期望大小排序贪心给定权值
↓
统计每条边的权值乘期望的和
Tips:这题转化了两次，而且是点→边→点的思维，思维难度比较大，需要耐心思考
切糕
主要考察：建图能力算法：网络流突破口：考虑网络流正确思路：转化网络流→加边以满足相邻两点的距离差条件
发现这题每一列仅取一点，显然最小割模型
然后思考如何满足相邻两点的距离不超过D的限制
在草稿纸上画两笔就知道对于每个点
(x,y,z)
(
x
,
y
,
z
)
往四个方向上高度为
z±D
z
±
D
的点连一条
INF
I
N
F
的边即可
代码部分
数列
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll n,m,k,p;
ll qpow(ll A,ll B){
A%=p;
ll ans=
1;
while(B){
if(B&
1)ans=ans*A%p;
A=A*A%p;
B>>=
1;
}
return ans;
}
int main(){
cin>>n>>k>>m>>p;n%=p;
if(k==
1){
printf(
"%llu\n",n);
return 0;}
ll ans=((n*qpow(m,k-
1))%p-qpow(m,k-
2)*(k-
1)%p*((m*(m+
1)>>
1)%p)%p+p)%p;
printf(
"%llu\n",ans);
return 0;
}
游走
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
#define cl(x) memset(x,0,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))
#define eps (1e-10)
template <
typename _Tp>
inline _Tp read(_Tp&x){
rg
char c11=getchar(),ob=
0;x=
0;
while(c11^
'-'&&!
isdigit(c11))c11=getchar();
if(c11==
'-')c11=getchar(),ob=
1;
while(
isdigit(c11))x=x*
10+c11-
'0',c11=getchar();
if(ob)x=-x;
return x;
}
const int N=
505,M=
505005;
struct Edge{
int v,nxt;}e[M<<
1];
double tot[N],a[N][N],f[M];
int head[N],l[M],r[M],_=
0,n,m;
inline char cmp(
const double aa,
const double bb){
return aa-bb>eps;}
inline void add(
int u,
int v){
++tot[u],++tot[v];
e[++_].v=v,e[_].nxt=head[u],head[u]=_;
e[++_].v=u,e[_].nxt=head[v],head[v]=_;
}
int main(){
read(n),read(m);
for(rg
int i=
0;i<m;++i)
add(read(l[i]),read(r[i]));
a[
1][n]=-
1.0;
for(rg
int i=
1;i<n;++i){
a[i][i]=-
1.0;
for(rg
int j=head[i];j;j=e[j].nxt)
if(e[j].v!=n)
a[i][e[j].v]=
1.0/tot[e[j].v];
}
for(rg
int i=
1;i<n;++i){
int ex=i;
double ma=-
1.0;
for(rg
int j=i;j<n;++j)
if(
fabs(a[j][i])-ma>eps)
ma=
fabs(a[ex=j][i]);
if(ex!=i)
for(rg
int j=
1;j<=n;++j)swap(a[i][j],a[ex][j]);
double t=a[i][i];
for(rg
int j=
1;j<=n;++j)a[i][j]/=t;
for(rg
int j=
1;j<n;++j)
if(j!=i){
t=a[j][i];
for(rg
int k=
1;k<=n;++k)
a[j][k]-=t*a[i][k];
}
}
for(rg
int i=
0;i<m;++i)f[i]=a[l[i]][n]/tot[l[i]]+a[r[i]][n]/tot[r[i]];
sort(f,f+m,cmp);
double ans=
0;
for(rg
int i=
0;i<m;++i)ans+=f[i]*(i+
1);
printf(
"%.3lf\n",ans);
return 0;
}
切糕
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define qi(x,y) ((x&1)^(y&1))
#define get(x,y) ((x-1)*n+y)
#define cl(x) memset(x,0,sizeof(x))
#define cl1(x) memset(x,-1,sizeof(x))
#define clm(x) memset(x,0x3f3f3f3f,sizeof(x))
#define min(x,y) ((x)<(y)?(x):(y))
#define rg register
#define inf 0x3f3f3f3f
template <
typename _Tp>
inline void read(_Tp&x){
char c11=getchar();x=
0;
bool booo=
0;
while(c11!=
'-'&&!
isdigit(c11))c11=getchar();
if(c11==
'-'){booo=
1;c11=getchar();}
while(
isdigit(c11)){x=x*
10+c11-
'0';c11=getchar();}
if(booo)x=-x;
}
const int MD=
800050,ME=
800050;
struct node{ll v,w,nxt;}a[ME];
ll head[MD],cur[MD],p=
0;
const int mx[]={
0,
0,
1,-
1},my[]={
1,-
1,
0,
0};
int id[
42][
42][
42];
ll n,m,s,t,d,h;
ll dis[MD];
ll sum=
0,ans=
0;
inline void add(ll,ll,ll);
inline void ADD(ll,ll,ll);
void init();
bool bfs(){
queue <int> q;
q.push(s);
cl1(dis);
dis[s]=
0;
while(!q.empty()){
int x=q.front();
q.pop();
for(rg
int i=head[x];~i;i=a[i].nxt)
if(dis[a[i].v]==-
1&&a[i].w>
0)
{dis[a[i].v]=dis[x]+
1;q.push(a[i].v);
if(a[i].v==t)
break;}
}
return dis[t]!=-
1;
}
ll dfs(ll x,ll low){
if(x==t||low==
0)
return low;
ll res=
0,temp;
for(rg
int i=cur[x];~i;i=a[i].nxt){
cur[x]=i;
if(dis[a[i].v]==dis[x]+
1)
if((temp=dfs(a[i].v,min(low-res,a[i].w)))>
0){
a[i].w-=temp;
a[i^
1].w+=temp;
res+=temp;
if(res==low)
return low;
}
}
if(!res)dis[x]=-
1;
return res;
}
void work(){
while(bfs()){
for(rg
int i=
1;i<=t;++i)cur[i]=head[i];
ans+=dfs(s,inf);
}
printf(
"%lld\n",ans);
return ;
}
int main(){
init();
work();
return 0;
}
void init(){
read(n);read(m);read(h);read(d);
cl1(head);
int cnt=
0,A;
for(rg
int i=
1;i<=n;++i)
for(rg
int j=
1;j<=m;++j)
for(rg
int k=
1;k<=h+
1;++k)
id[i][j][k]=++cnt;
s=++cnt;t=++cnt;
for(rg
int i=
1;i<=n;++i)
for(rg
int j=
1;j<=m;++j){
ADD(s,id[i][j][
1],inf);
ADD(id[i][j][h+
1],t,inf);
}
for(rg
int k=
1;k<=h;++k)
for(rg
int i=
1;i<=n;++i)
for(rg
int j=
1;j<=m;++j){
read(A);
ADD(id[i][j][k],id[i][j][k+
1],A);
}
for(rg
int k=d+
1;k<=h+
1;++k)
for(rg
int i=
1;i<=n;++i)
for(rg
int j=
1;j<=m;++j)
for(rg
int o=
0;o<
4;++o)
if(i+mx[o]>
0&&i+mx[o]<=n&&j+my[o]>
0&&j+my[o]<=m)
ADD(id[i][j][k],id[i+mx[o]][j+my[o]][k-d],inf);
return ;
}
inline void add(ll u,ll v,ll w){
a[p].v=v;
a[p].w=w;
a[p].nxt=head[u];
head[u]=p++;
}
inline void ADD(ll x,ll y,ll z){add(x,y,z);add(y,x,
0);
return ;}
