递推 | 矩阵 | SPFA | 模拟 | 数论 | 20190723考 试：解题报告

题目限制一览

题目	时间限制	空间限制
1. traffic	$1000$ MS	$128$ MB
2. paint	$1000$ MS	$512$ MB
3. airline	$1000$ MS	$128$ MB

1. 车流量（traffic.cpp）

Description

工人打算用一组传感器测量公路上的车流量，每个传感器被用来测量一小段路面上的车流量的数值。不幸的是，某一天装有传感器的盒子进了水，之后它们就不能精确的测量了。现在每个传感器只能输出一个可能结果的范围。例如，一个传感器可能会给出范围[7,13]，表示在这段路面上的车流量不小于7，并且不大于13。

高速路要测量的这一段长N英里，当然高速路都是单向的，从第1英里驶向第N英里。工人想要安装N个传感器——每个监测1英里长的路段。在其中某些路段上，有能够使得车辆进入高速公路的上匝道，在这样的路段上，工人会将传感器装在上匝道上，测量流入的车流量。在某些路段上有能够使得车辆离开高速公路的下匝道，在这样的路段上，工人会将传感器装在下匝道上。每一个路段包含至多一个匝道。如果在公路的一个路段上没有上匝道或下匝道，工人就将传感器装在高速公路的主路上。

给定N个传感器的读数，请求出在高速公路第1英里之前和第N英里之后车流量的最为准确的可能范围。这些范围应当与所有N个传感器的读数相一致。

Input

输入的第一行包含N（1≤N≤100）。余下N行每行按从第1英里至第N英里的顺序描述一段1英里长的路段。每行包含一个字符串，为”on”（如果这段路上有一个上匝道），”off”（如果这段路上有一个下匝道），或者是”none”（如果这段路上没有匝道），然后是两个范围为0…1000的整数，表示这段路上的传感器的读数所给出的下界、上界。至少一个高速公路路段的描述会是”none”。

Output

输出的第一行包含两个整数，为第1英里之前的车流量的最准确的可能范围。第二行包含两个整数，为第N英里之后的车流量的最准确的可能范围。输入保证存在符合要求的解。

Sample Input

4
on 1 1
none 10 14
none 11 15
off 2 3

Sample Output

10 13
8 12

Hint

在这个例子中，路段2和路段3的读数组合在一起告诉我们通过这两个路段的车流量为范围$[11,14]$之间的某个值，因为只有这个范围与两个读数$[10,14]$和$[11,15]$均一致。在第1英里，恰有1单位的车辆通过上匝道进入，所以在第1英里之前，车流量一定在范围$[10,13]$之内。在第4英里，2单位到3单位之间的车辆通过下匝道离开，所以这段路之后可能的车流量范围为$[8,12]$。

分析

简单的模拟，可以通过预处理把连续的且没有匝道的路段的 L，R 值取交集，把有匝道的连续路段合并起来计算影响流量可能的最大值和最小值

要计算 1 英里之前的流量，从前往后扫一遍，遇到有匝道的就计算和更新造成影响的最大值和最小值，遇到没有匝道的就与当前的答案取交集（此时要把影响加上去），对于 N 英里之后的流量，可以当作是反过来求 1 英里之前的流量，所以反着再扫一遍，把上下道造成的影响反过来计算即可

考试的时候因为没有全部扫一遍只得了 70 分……（我真是越来越弱了）

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 101
using namespace std;
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
struct node{
	int L,R;int k;
	// k=0,1,2 ==> on,none,off 
}a[maxn],road[maxn];
int n,cnt; char op[11];
node calc(node x,node y,int cnt){
	node z;
	if(cnt==1) z={max(x.L,y.L),min(x.R,y.R),cnt};
	else z={x.L+y.L,x.R+y.R,cnt};
	return z;
}
inline void init(){
	for(int i=1;i<=n;i++){
		node T=a[i];i++;
		while(a[i].k==T.k){
			T=calc(T,a[i],T.k);
			i++;
		} road[++cnt]=T;i--;
 	}
}
inline void solve(){
	node ansR=(node){-2139062143,2139062143},ansL=(node){-2139062143,2139062143};
	int deltaL=0,deltaR=0;
	// Get ansL 
	for(int i=1;i<=cnt;i++){
		if(road[i].k==0){
			deltaL+=road[i].L;
			deltaR+=road[i].R;
		}else if(road[i].k==1){
			ansL.L=max(ansL.L,road[i].L-deltaR);
			ansL.R=min(ansL.R,road[i].R-deltaL);
		}else{
			deltaL-=road[i].R;
			deltaR-=road[i].L;
		}
	} deltaL=0;deltaR=0;
	printf("%d %d\n",max(ansL.L,0),max(ansL.R,0));
	for(int i=cnt;i;i--){
		if(road[i].k==0){
			deltaL-=road[i].R;
			deltaR-=road[i].L;
		}else if(road[i].k==1){
			ansR.L=max(ansR.L,road[i].L-deltaR);
			ansR.R=min(ansR.R,road[i].R-deltaL);
		}else{
			deltaL+=road[i].L;
			deltaR+=road[i].R;
		}
	}
	printf("%d %d",max(ansR.L,0),max(ansR.R,0)); 
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("traffic.in","r",stdin);
	freopen("traffic.out","w",stdout);
	#endif
	fcin(n);
	for(int i=1;i<=n;i++){
		scanf("%s",op);fcin(a[i].L);fcin(a[i].R);
		if(op[1]=='n') a[i].k=0;
		else if(op[1]=='o') a[i].k=1;
		else a[i].k=2;
	} init();
	solve();
	return 0;
}

---

2. 刷墙（paint.cpp）

Description

Todobe要把她的寝室弄得漂漂酿酿，所以她管Yashem66要了一些墙纸。

Todobe有一面墙，可分为n块，Yashem66提供的所有墙纸都是统一规格的，均只可覆盖连续k块完整的墙面，但是有m种不同的颜色的墙纸，每种颜色的墙纸都有无限张。Todobe要用这些墙纸把墙贴满，墙纸不可以裁剪，墙纸与墙纸之间可以有重叠部分。当墙纸重叠时，只能看到最外层的墙纸颜色。

Todobe想知道她以不同的方式贴墙纸，共能贴出多少种不同配色方案的墙面，两种方案不同当且仅当两种方案中至少有一块墙面的颜色不同。

Input

输入一行3个整数n,m,k。

Output

输出一行一个整数代表方案数量，答案取模1e9+7。

Sample Input #1

3 2 2

Sample Output #1

6

Sample Input #2

10 4 3

Sample Output #2

371740

Hint

对于样例输入1，我们假设两种颜色分别是A,B

那么6种方案分别是：AAA，AAB，ABB，BAA，BBA，BBB

【数据范围与约定】

对于0%的数据，与样例数据相同;

对于20%的数据，n<=10,m<=5;

对于另20%的数据n<=500;

对于另20%的数据n<=10^5;

对于100%的数据n<=2^31-1,m<=10^5，k<=100。

分析

应该是考试中最难的题了，这道题正向思考不好想，可以逆向考虑一下，每种墙纸都能覆盖连续 $k$ 块墙，它们之间又可以相互覆盖，可以知道，不管墙纸之间的覆盖关系如何，一定存在一种颜色看起来连续覆盖了 $k$ 块墙面，一旦满足这个条件，剩下的 $n-k$ 块墙面形成的任何的颜色和顺序都是可以通过覆盖得到的合法方案，所以想到合法的方案数应该是所有方案数减去不合法的方案数

由于 $n$ 块墙，每块墙都有可能涂上 $1\to m$ 的颜色，总的方案数应该为 $m^n$ 种（不考虑连续 $k$ 块为同一种颜色），设 $f[i]$ 表示涂到第 $i$ 块墙都没有连续 $k$ 块墙是一种颜色的方案数， 则 $ans=m^n-f[n]$，考虑怎么递推得到 $f[n]$

可以发现此处 $f[n]$ 的定义和 核电站问题 中的 $f[n]$ 定义很相似，考虑 核电站问题 中的 $f[n]$ ，要使得前 $n$ 个反应堆不爆炸，若在 $n$ 位置不放反应堆，那么只需 $n-1$ 位置不爆炸即可，若在 $n$ 位置放反应堆而不在 $n-1$ 位置放，则需要 $n-2$ 位置不爆炸，以此类推到 $n-k$ 位置，那么就得到：

$f[n]=\sum_{i=n-k}^{n-1}f[i]$，特别地，当 $n<k$ 时，$f[n]=2^n$

那么这个题在 $n\geq k$ 时和 核电站问题 非常相似，在 $n<k$ 时可以选择的有 $m-1$ 种颜色（除了自己之外），那么递推方程为：

$f[n]=\left(\sum_{i=n-k}^{n-1}f[i]\right)\times (m-1)$，特别地，当 $n<k$ 时，$f[n]=m^n$

得到了这个方程还没完，由于 $n\leq 2^{31}-1$，直接计算显然会超时，考虑用矩阵加速计算：

设：$F(k)=\begin{bmatrix}f(k)&f(k-1)&f(k-2)&…&f(1)\end{bmatrix}$

则：$F(k+1)=\begin{bmatrix}f(k+1)&f(k)&f(k-1)&…&f(2)\end{bmatrix}$

考虑 $F(k) \times A=F(k+1)$，演算得到 $A$ 的表达式为：

$A=\begin{bmatrix}m-1&1&0&0&0&0&…&0\\ m-1&0&1&0&0&0&…&0\\ m-1&0&0&1&0&0&…&0\\ m-1&0&0&0&1&0&…&0\\ m-1&0&0&0&0&1&…&0\\ …&…&…&…&…&…&…&…\\ m-1&0&0&0&0&0&…&1\end{bmatrix}$，然后找规律，发现一共有 $k-1$ 行，$k$ 列，且第一列的数都为 $m-1$，除去第一列的矩阵对角线上为 $1$ ，其他地方为 $0$

此时 $F(n)=F(k)\times A^{n-k}$ ，用 矩阵快速幂 就可以提高运算的速度了

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 110
using namespace std;
typedef long long ll;
ll mod=(ll)1e9+7;
struct mat{ 
    ll val[maxn][maxn];
    int row,col; // 行 列  
    mat(int n=-1,int m=-1,int __sourceval=0){
        if(n==-1 && m==-1) return;
        row=n; col=m;
        for(int i=1;i<=row;i++)
            for(int j=1;j<=col;j++) 
                val[i][j]=__sourceval;
    }
    inline void put(){
        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++) cout<<val[i][j]<<' ';
            cout<<'\n';
        }
    }
    inline void get(int n,int m){  
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) cin>>val[i][j];
        row=n;col=m;
    }
    inline void get(){
        for(int i=1;i<=row;i++)
            for(int j=1;j<=col;j++) cin>>val[i][j];
    }
    mat operator *(const mat &obj)const{ 
        // 矩阵乘法   
        mat ret(row,obj.col,0);
        for(int i=1;i<=row;i++)
            for(int j=1;j<=obj.col;j++)
                for(int k=1;k<=col;k++)
                    ret.val[i][j]+=val[i][k]*obj.val[k][j];
        ret.row=row;
        ret.col=obj.col;
        return ret;
    }
    mat mul(mat B,ll md){
        // 矩阵 a*b % p 
        mat ret(row,B.col,0);
        for(int i=1;i<=row;i++)
            for(int j=1;j<=B.col;j++)
                for(int k=1;k<=col;k++)
                    (ret.val[i][j]+=
                    val[i][k]*B.val[k][j])%=md;
        ret.row=row;
        ret.col=B.col;
        return ret;
    }
};
ll m,n,k,ans;
ll Quickpow(ll b,ll p,ll K){
	ll sol=1;
	while(p>0){
		if(p%2==1) sol=(sol*b)%K;
		b=(b*b)%K;
		p/=2;
	} return sol;
}
mat Fastpow(mat A,ll b,ll p){
    // 矩阵快速幂 
    mat res(A.row,A.col);
    for(int i=1;i<=res.row;i++) res.val[i][i]=1;
    while(b>0){
        if(b&1) res=res.mul(A,p);
        A=A.mul(A,p);
        b>>=1;
    }
    return res;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("paint.in","r",stdin);
	freopen("paint.out","w",stdout);
	#endif
	cin>>n>>m>>k;k--;
	ans=Quickpow(m,n,mod);
	mat A(1,k),T(k,k+1,0);
	A.val[1][k]=m;
	for(int i=k-1;i;i--) A.val[1][i]=(A.val[1][i+1]*m%mod);
	for(int i=1;i<=k;i++) T.val[i][1]=m-1;
	for(int i=1;i<=k;i++) T.val[i][i+1]=1;
	T=Fastpow(T,n-k,mod);A=A.mul(T,mod);
	ans=(ans-A.val[1][1]+mod)%mod;cout<<ans;
	return 0;
}

---

3. 航线（airline.cpp）

Description

Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000)，编号为1到T。这些城镇之间通过R条道路 (1 <= R <= 50,000，编号为1到R) 和P条航线 (1 <= P <= 50,000，编号为1到P) 连接。每条道路i或者航线i连接城镇Ai (1 <= Ai <= T)到Bi (1 <= Bi <= T)，花费为Ci。对于道路，0 <= Ci <= 10,000；然而航线的花费很神奇，花费Ci可能是负数(-10,000 <= Ci <= 10,000)。道路是双向的，可以从Ai到Bi，也可以从Bi到Ai，花费都是Ci。然而航线与之不同，只可以从Ai到Bi。事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：如果有一条航线可以从Ai到Bi，那么保证不可能通过一些道路和航线从Bi回到Ai。由于FJ的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

Input

第1行：四个空格隔开的整数: T, R, P, and S

第2到R+1行：三个空格隔开的整数（表示一条道路）：Ai, Bi 和 Ci

第R+2到R+P+1行：三个空格隔开的整数（表示一条航线）：Ai, Bi 和 Ci

Output

第1到T行：从S到达城镇 i 的最小花费，如果不存在输出”NO PATH”。

Sample Input

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

Sample Output

NO PATH
NO PATH
5
0
-95
-100

Hint

【样例输入解释】

一共六个城镇。在1-2，3-4，5-6之间有道路，花费分别是5，5，10。同时有三条航线：3->5，

4->6和1->3，花费分别是-100，-100，-10。FJ的中心城镇在城镇4。

【样例输出解释】

FJ的奶牛从4号城镇开始，可以通过道路到达3号城镇。然后他们会通过航线达到5和6号城镇。

但是不可能到达1和2号城镇。

分析

这个题看似是 SPFA 的裸题（实际上也差不多），但是根据 USACO 的尿性，一定会出几个稠密图的测试点来卡 SPFA，因此需要设计一些优化算法

做法一：SPFA + SLF 优化

SPFA 的 SLF 优化（Small Label First）

优化思路：将原队列改成双端队列，对要加入队列的点 $p$，如果 $dist[p]$ 小于队头元素 $u$ 的 $dist[u]$，将其插入到队头，否则插入到队尾。

实现：

void SPFA(int s){
    deque<int> q;
  	...
    if(!vis[to[i]]){
        if(!q.empty && dist[to[i]]<dist[q.front()]) q.push_front(to[i]);
        else q.push_back(to[i]);
    }
}

SPFA 的 LLL 优化（Large Label Last）

优化思路：对每个要出队的队头元素 $u$，比较 $dist[u]$ 和队列中点的 $dist$ 的平均值，如果 $dist[u]$ 更大，将其弹出放到队尾，然后取队首元素进行相同操作，直到队头元素的 $dist$ 小于等于平均值。

实现：

void SPFA(int s){
    deque<int> q;
    while(dist[q.front()]*cnt>sum){
        x=q.front();
        q.pop_front();q.push_back(x);
    }...
}

讲道理这 2 个优化方式互不干扰，结合使用应该效果会更好的，但是实际测试却是：

优化方式	通过测试点数目（/16）	得分（/100）
SPFA	13	87
SPFA + SLF + LLL	13	87
SPFA + SLF	16	100

做法二：SPFA + 强连通分量缩点 优化

根据题意可以发现图中不可能存在负环的情况（无向边构成的环一定是正环），而且通过 $A\to B$ 后就不可能再回到 $A$ 了，结合题目中存在有向边，可以发现原图非常像一个有向无环 DAG 图，只要把所有构成环的无向边缩点，就可以在新的图上跑 SPFA 了

对于 $dist[u]$，若 $u$ 和 $s$ 处在同一个连通分量内，则直接在里面 SPFA，否则就先预处理出 $dist[p]$ 的值，其中 $p$ 是连通分量的代表，然后设 $S$ 代表 $s$ 所处的连通分量（缩点后的新点），则 $dist[u]=dist[p]+dist’[S]$

Codes

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#define maxn 25001
#define maxm 150001
using namespace std;
template<typename t>inline void fcin(t &x){
	int sign=1; x=0; char op=getchar();
	while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
	while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
	x*=sign;
}
int to[maxm],w[maxm],nxt[maxm];
int head[maxn],tot,dist[maxn];
int T,R,P,S;bool vis[maxn];
struct PAIR{
	int dis,node;
	bool operator <(const PAIR &obj)const{
		return dis<obj.dis;
	}
};
inline void Eadd(int u,int v,int W){
	to[++tot]=v;nxt[tot]=head[u];
	w[tot]=W;head[u]=tot;
}

void SPFA(int s){
	// advanced by SLF 
	memset(dist,127,sizeof(dist));
	deque<int> q; int x=0,cnt=1,sum=0;
	q.push_back(s);dist[s]=0;vis[x]=true;
	while(!q.empty()){
		x=q.front();
		q.pop_front();
		for(int i=head[x];i;i=nxt[i])
			if(dist[to[i]]>dist[x]+w[i]){
				dist[to[i]]=dist[x]+w[i];
				if(!vis[to[i]]){
					vis[to[i]]=true;cnt++;sum+=dist[to[i]];
					if(!q.empty() && dist[to[i]]>=dist[q.front()]) q.push_back(to[i]);
					else q.push_front(to[i]);
				}
			}
		vis[x]=false;
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("airline.in","r",stdin);
	freopen("airline.out","w",stdout);
	#endif
	int x,y,z;
	fcin(T);fcin(R);fcin(P);fcin(S);
	for(int i=1;i<=R;i++){
		fcin(x);fcin(y);fcin(z);
		Eadd(x,y,z);Eadd(y,x,z);
	}
	for(int i=1;i<=P;i++){
		fcin(x);fcin(y);fcin(z);
		Eadd(x,y,z);
	} SPFA(S);
	for(int i=1;i<=T;i++){
		if(dist[i]==2139062143) printf("NO PATH");
		else printf("%d",dist[i]);
		putchar('\n');
	} 
	return 0;
}