递推 | 矩阵 | 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;
}