题目限制一览

题目 时间限制 空间限制
1. door 1000 MS 128 MB
2. escape 1000 MS 128 MB
3. graze 3000 MS 128 MB

1. 门卫（door.cpp）

Description

红美玲是红魔馆的门卫。最近红魔馆安保系统使用了新型的数据编码技术base64，可以

将数据转化为大小写字母、数字和+、/、=组成的字符串，具体方法如下：

首先将输入字符三个三个分为一组：如果没有剩余（即字符串长度为3的倍数），则直接调用主过程（见下方描述）；如果剩1个，则加两个“\0”字符（ASCII码为0），使总长度变为3的倍数，调用主过程，并且将主过程转化后的字符串最后两个字符改为“==”；如果剩2个，则加一个“\0”字符，使总长度变为3的倍数，调用主过程，并且将主过程转化后的字符串最后一个字符改为“=”。

主过程：输入一个长度为3k的字符串，输出一个长度为4k的字符串。（k为非负整数。）循环以下过程n次,每次转换三个字符成为四个字符，循环n次转换出的字符串连接起来，即为最终的字符串。

每次将三个字符转化成ascii码，再转成二进制，得到24个二进制位。将24个二进制位分成4组，每组6个二进制位，再分别转化成十进制。此时得到四个十进制数，并且小于 64（因为每个十进制数是由6个二进制位表示的）。接下来参照下表，将这四个数转化成字符，输出即可。

value char
0-25 A-Z
26-51 a-z
52-61 0-9
62 +
63 /

接下来是两个例子：

输入Man，长度为3的倍数，直接调用主过程

文本 M a n
ASCII 77 97 110
二进制 01001101 01100001 01101110

输出为：TWFu

输入A：

文本 A \0 \0
ASCII 65 0 0
二进制 01000001 00000000 00000000

输出为：QQAA => QQ==（最后两个字符被替换）

最终将转化后的字符串输出，每76个字符为一行，如果最后一行不满76个字符，也换一行。输出文件最后请输出一个空行。因为是逐字节比较，行末不能有多余空格，文末不能有多余空行（也就是说文件最后一行一定是空行，倒数第二行一定不是空行）。

你需要为红魔馆设计这个新型的编码技术，红美玲正在急着处理传输进来的信息，却不

知道红魔馆内已经有了入侵者……

Input

输入文件第一行是一个正整数n，表示原始字符串的长度。

第二行是一个字符串，长度为n。字符串由大小写字母，数字，符号，空格构成。

Output

若干行，表示转化后的字符串。每76个字符为一行，如果最后一行不满76个字符，也换一行。因为是逐字节比较，行末不能有多余空格，文末不能有多余空行（也就是说文件最后一行一定是空行，倒数第二行一定不是空行）。

Sample Input

1
2
2
BC

Sample Output

1
QkM=

Hint

对于30%的数据,n=3,字符串只由字母组成

对于50%的数据,n=12

对于70%的数据,n<=57

对于100%的数据,3<=n<=1000

分析

一道简单的字符串操作题，根据题意转化字符串，分行输出转化后的字符即可

这道题在考试时写的程序，在自己电脑上能 AC，但是交到老师的 Linux 下面去就不行了……

然而 NOIP 采用的就是标准的 Linux 环境，不知道该怎么办……

Codes

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#define maxn 5005
using namespace std;
char src[maxn];
int bin[maxn],res[maxn];
char ref[maxn];
int n,cnt,rest;
void init(){
	for(int i='A';i<='Z';i++) ref[cnt++]=i;
	for(int i='a';i<='z';i++) ref[cnt++]=i;
	for(int i='0';i<='9';i++) ref[cnt++]=i;
	ref[cnt++]='+';ref[cnt++]='/';ref[cnt]='=';
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("door.in","r",stdin);
	freopen("door.out","w",stdout);
	#endif
	scanf("%d",&n);char ch;
	init();
	ch=getchar();
	for(int i=1;i<=n;i++){
		ch=getchar();
		src[i]=ch;
	}
	while(n%3!=0) src[++n]='\0',rest++;
	int offset,curch,ans;
	for(int i=1;i<=n;i+=3){
		memset(bin,0,sizeof(bin));
	 	curch=src[i];
		for(int j=7;j>=0;j--) bin[++bin[0]]=(curch>>j)&1;
		curch=src[i+1];
		for(int j=7;j>=0;j--) bin[++bin[0]]=(curch>>j)&1;
		curch=src[i+2];
		for(int j=7;j>=0;j--) bin[++bin[0]]=(curch>>j)&1;
		ans=0;
		for(int j=1;j<=bin[0];j++){
			ans=(ans<<1)|bin[j];
			if(j%6==0){res[++res[0]]=ans;ans=0;}
		}
	}
	for(int i=rest;i;i--) res[res[0]-i+1]=64;
	for(int i=1;i<=res[0];i++){
		putchar(ref[res[i]]);
		if(i%76==0) 
			putchar('\n');
	}putchar('\n');// 这里必须多打一个 putchar，不然不能换行……
	if(res[0]%76!=0) putchar('\n');
	return 0;
}

2. 逃跑（escape.cpp）

Description

因为门卫红美玲的失误，疏忽将入侵者放入了红魔馆。入侵者袭击了红魔馆的大小姐蕾米莉亚·斯卡雷特，大小姐在施放【必杀·斯卡雷特家绝技·抱头蹲防】无效后只好变成了好多蝙蝠，在红魔馆中分散开来。

现在的当务之急是找到二小姐芙兰朵露·斯卡雷特，并且与大小姐化身成的所有蝙蝠集合在一点。你的任务就是帮她们找一条最佳路线。

我们可以用一个无向图来表示红魔馆的地图。蝙蝠和二小姐走过任何一条边都要付出一定的代价。因为形态不同，蝙蝠和二小姐走同一条边付出的代价可能不同。但是如果某一只蝙蝠与二小姐碰面，那么二小姐由于蝙蝠的引导，以后的所有路程可以不支付代价。（也就是相当于二小姐和某只蝙蝠都走到某点，之后无视二小姐的存在。）现在已知所有蝙蝠，二小姐和目标集合点的位置，请你求出所有蝙蝠和二小姐行走代价的和的最小值。

Input

第一行是5个正整数，n，m，k，S，T，分别代表无向图点数，边数，蝙蝠的数量，二小姐所在起点的编号，目标点的编号。

第二行是k个正整数，分别代表大小姐每个蝙蝠所在的起点的编号。

接下来有m行，每行有4个正整数，u，v，q，p，分别是该边的起点、终点，蝙蝠通过该路花费的代价，二小姐通过该路花费的代价。

Output

第一行是5个正整数，n，m，k，S，T，分别代表无向图点数，边数，蝙蝠的数量，二小姐所在起点的编号，目标点的编号。

第二行是k个正整数，分别代表大小姐每个蝙蝠所在的起点的编号。

接下来有m行，每行有4个正整数，u，v，q，p，分别是该边的起点、终点，蝙蝠通过该路花费的代价，二小姐通过该路花费的代价。

Sample Input

1
2
3
4
5
6
7
5 5 2 3 4 
1 5 
1 2 3 5 
3 2 3 5 
2 4 4 9 
3 4 9 6 
5 4 1 1

Sample Output

1
14

Hint

【样例解释】

1号蝙蝠从1到2，花费3 二小姐从3到2，花费5，遇见蝙蝠，之后不计算费用

1号蝙蝠从2到4，花费4 2号蝙蝠从5到4，花费1 总计13

【数据规模】

其中30%：n<=200。

另有20%: 保证S=T。

另有20%：保证k<=5，n<=1000,m<=10000。

100%：n<=10000，m<=100000，k<=10000，1<=S、T、u、v<=n，1<=p、q<=1000，不保证蝙蝠起点互不相等，数据中可能有重边和自环，保证所有点均能走到T点（即不存在无解情况）。

分析

局部分做法：SPFA + DFS（60分）

考试时写的解法，先预处理出终点到所有点的单源最短路径，然后统计所有蝙蝠到终点的最短路径距离和，如果题目给出的 S=T，则直接输出作为答案（这里有 20pts）

然后就是 DFS 标记每只蝙蝠通过最短路径到达终点时要经历的点，再做一次 SPFA，以二小姐的点为源点，计算每个被标记的点到新的源点的最短路径，再在其中取最小值，加上上一步算出的和即为答案，最终得分 60pts

正解：SPFA + 路径转化（100分）

很显然蝙蝠不一定要在最短路径上经过的点来接二小姐，因为二小姐到达这些点的花费通常比蝙蝠要高得多

枚举每个蝙蝠去接二小姐的点 $D$，设去接二小姐的蝙蝠为 $K_i$，那么这只蝙蝠需要的额外花费就为：

$dist[K_i][D]+dist[S][D]+dist[D][T]-dist[K_i][T]=delta$，也就是 $ans+=delta$

这样做的话，朴素做法需要预处理出每只蝙蝠，二小姐，终点到每个点的单源最短路径（如果会求多源最短路径的话到这一步就可以 AC 此题了），时间和空间都不能接受，考虑每个点的 $delta$ 值：

$delta(D)=min_{i=1}^n(dist[K_i,D]+dist[D][T]+dist[S][D]-dist[K_i][T])$

$ans=min{i=1}^ndelta(i)+\sum{i=1}^ndist[i][T]$

其中 $delta(D)$ 的表达式中可以提出常值表达式（即不会被当前计算所改变的表达式）：
$delta(D)=min_{i=1}^n(dist[K_i][D]-dist[K_i][T])-dist[S][K]+dist[D][T]$

变化的表达式值记作：$f(D)=delta(D)=min_{i=1}^n(dist[K_i][D]-dist[K_i][T])$

考虑新设源点 $S’$ ，把 $S’$ 与所有蝙蝠在的点 $Ki$ 连接一条权值为 $-dist[K_i][t]$ 的边，然后计算以这个点为源点的单源最短路径，发现表达式和 $f(D)$ 一致，那么我们就可以一次最短路求出 $f$ 数组，然后又枚举得出答案了

本题考查对最短路径表达式的理解，难点在于最后一步的新源点设置和转化，通过已知的目标表达式构造出能用最短路径求出的表达式从而解决问题

Codes

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#define maxn 10005
#define maxm 100005*8
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
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],nxt[maxm],head[maxn];
int wsis[maxm],wbf[maxm],tot;
int n,m,S,T,k;int pos[maxn];
int bf[maxn];
int dist[3][maxn];
inline void Eadd(int u,int v,int W1,int W2){
	to[++tot]=v;nxt[tot]=head[u];
	wbf[tot]=W1;wsis[tot]=W2;head[u]=tot;
}
struct cmp{bool operator ()(const pr a,const pr b){return a.second>b.second;}};
priority_queue<pr,vector<pr>,cmp> q;
void SPFA(int id,int src=-1){
	if(src!=-1) while(!q.empty()) q.pop();
	if(src!=-1) memset(dist[id],0x3f,sizeof(dist[id]));
	int hx,hy,val;
	if(src!=-1){
		dist[id][src]=0;
		q.push(make_pair(src,0));
	}
	while(!q.empty()){
		hx=q.top().first;
		hy=q.top().second;
		q.pop();
		if(dist[id][hx]!=hy) continue;
		for(int i=head[hx];i;i=nxt[i]){
			val=(id==0 || id==2)?wbf[i]:wsis[i];
			if(dist[id][to[i]]>dist[id][hx]+val){
				dist[id][to[i]]=dist[id][hx]+val;
				q.push(make_pair(to[i],dist[id][to[i]]));
			}
		}
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("escape.in","r",stdin);
	freopen("escape.out","w",stdout);
	#endif
	fcin(n);fcin(m);int a,b,c,d;
	fcin(k);fcin(S);fcin(T);
	for(int i=1;i<=k;i++) fcin(a),bf[a]++;
	for(int i=1;i<=m;i++){
		fcin(a);fcin(b);
		fcin(c);fcin(d);
		Eadd(a,b,c,d);Eadd(b,a,c,d);
	} 
	SPFA(0,T);SPFA(1,S); 
	ll ans=0;while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++){
		if(bf[i]){
			dist[2][i]=-dist[0][i];
			ans+=dist[0][i]*bf[i];
			q.push(make_pair(i,dist[2][i]));
		}else dist[2][i]=1<<28; 
	}
	SPFA(2);
	ll ret=1ll<<55;
	for(int i=1;i<=n;i++) ret=min(ret,ans+dist[2][i]+dist[0][i]+dist[1][i]);
	printf("%lld",ret);
	return 0;
}

3. 擦蛋（graze.cpp）

Description

大小姐和二小姐汇合以后，大小姐从蝙蝠变回人形。这个时候入侵者发现了她们，二小姐看见了新的玩具，十分兴奋，使用了禁忌【四重存在】。此时密集的弹幕飞了过来，二小姐与她的分身该怎样躲过这一阵袭击呢？

四重存在 == 分身有4个

我们假设对战场地是一条长度为n格的路，开始时二小姐与所有分身都在路的最左端第一格，而目标在路的最右端，也就是第n格。二小姐需要将分身都移动到路的最右一格，然后给予敌人致命一击。因为分身难以操纵，所以二小姐每单位时间只能操作1个分身向右移动一格。显然，二小姐需要4n-4的时间使得所有分身处于道路最右端。

我们已知从开始4n-4时间内每时刻，道路的某一格内的弹幕数。对于每个分身分别计算，如果在第t时刻,该分身位于第i格，那么则会：1.受到该时刻第i格内弹幕数量的伤害，称为miss数（指走位失误的数量）。2.如果该分身上一时刻在第i-1格，得到该时刻i-1格内弹幕数量的分数，称为graze数（指擦弹数）。（如果该分身此回合没有移动，不计算擦弹数。）

总miss就是这4n-4时间段内所有分身所有miss之和，总graze数是这4n-4时间段内所有分数的graze数之和。现在想知道miss数最小的情况下，graze数最大为多少。输出这个miss数和graze数。

Input

第一行是1个正整数n，代表道路长度。

接下来有4n-4行，每行n个整数，第i行第j个数代表在i时刻（开始为0时刻）在第j格内受到的伤害。

Output

两个整数，用空格隔开，分别代表最小的miss数，和在miss数最小的情况下最大的graze 数。

Sample Input

1
2
3
4
5
2
1 2
2 2
3 2
4 2

Sample Output

1
30 10

Hint

【样例解释 】

只有一种走法。

第一回合：第一格3分身，第二格1分身，miss5，graze1。

第二回合：第一格2分身，第二格2分身，miss8，graze2。第三回合：第一格1分身，第二格3分身，miss9，graze3。

第四回合：第一格0分身，第二格4分身，miss8，graze4。

【数据约定 】

其中30%数据:n<=3 其中50%数据:n<=10 其中70%数据:n<=30

100%数据:n<=100,每时刻每格中弹幕数均为正数且小于1000

分析

30分做法：搜索

朴素的搜索算法，考试时还想着剪枝优化，结果发现剪了枝和没剪没什么区别……

100分做法：DP+各种优化

1级 DP

设 $f[t][i][j][k][l]=(miss,\;graze)$ 表示在 $t$ 时刻，四个分身位于 $i,\;j,\;k,\;l$ 四个位置时的最小 $miss$ 值以及最大 $graze$ 值，按照题意 $miss$ 值小的优先，这点可以在重载运算符时实现，然后转移方程也比较好想：

设 $cost[i]$ 为 $i$ 位置在当前时刻 $t$ 的弹幕数量，则：

$f[t][i][j][k][l]=min\begin{cases} f[t-1][i-1][j][k][l]+(cost[i+j+k+l],\;cost[i-1])\\f[t-1][i][j-1][k][l]+(cost[i+j+k+l],\;cost[j-1])\\f[t-1][i][j][k-1][l]+(cost[i+j+k+l],\;cost[k-1])\\f[t-1][i][j][k][l-1]+(cost[i+j+k+l],\;cost[l-1]) \end{cases}$

这一个转移方程的控件和时间复杂度都达到了 $O((4n-4)\times n^4)$，可以过 50% 的数据

2级 DP

由于每时刻只能操作一个分身向前移动一格，所以 $t$ 也就是所有分身的位置总和（设 0 为起点，n-1 为终点），那么只需要枚举前三个 $i,\;j,\;k$ 就能确定剩下的 $l$ ，复杂度为 $O((4n-4)\times n^3)$ ，可以过掉 70 pts

3级DP

首先，$f[t]$ 的状态只和 $f[t-1]$ 有关，所以可以用滚动数组优化，降低空间复杂度

其次，考虑互换每个分身的位置，我们发现由于分身是一样的，所以将任一时刻的分身随意互换位置对计算的答案毫无影响，于是可以规定 $i>j>k>l$ ，从而减少枚举的状态，过 100pts 的数据点

Codes

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#define maxn 125
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 miss,graze;
	bool operator <(const node &x)const{
		if(miss!=x.miss) return miss<x.miss;
		else return graze>x.graze;
	}
	node operator +(const node &x){
		return (node){miss+x.miss,graze+x.graze}; 
	}
	node& operator +=(const node &x){
		miss+=x.miss;graze+=x.graze;
		return *this;
	}
}f[2][maxn][maxn][maxn];
int n,cost[maxn];
void calc(node &x,node y[maxn][maxn][maxn],int p1,int p2,int p3,int p4,int delta){
	if(p1<p2) swap(p1,p2);
	if(p2<p3) swap(p2,p3);
	if(p3<p4) swap(p3,p4);
	node cur=y[p1][p2][p3];
	cur.graze+=delta;
	if(cur.miss<x.miss || (cur.miss==x.miss && cur.graze>x.graze)) x=cur;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("graze.in","r",stdin);
	freopen("graze.out","w",stdout);
	#endif
	fcin(n);
	int curStat=1;
	memset(f[curStat],0x3f,sizeof(f[curStat]));
	f[1][0][0][0]=(node){0,0};
	for(int i=1;i<=4*(n-1);i++){
		curStat=!curStat;
		for(int p=0;p<n;p++) fcin(cost[p]);
		for(int x=min(n-1,i);x>=0;x--)
		for(int y=min(x,i-x);3*y+x>=i&&y>=0;y--)
		for(int z=min(y,i-x-y);2*z+y+x>=i&&z>=0;z--){
			int w=i-x-y-z;
			f[curStat][x][y][z]=(node){1<<28,1<<28};
			if(x) calc(f[curStat][x][y][z],f[1-curStat],x-1,y,z,w,cost[x-1]);
			if(y) calc(f[curStat][x][y][z],f[1-curStat],x,y-1,z,w,cost[y-1]);
			if(z) calc(f[curStat][x][y][z],f[1-curStat],x,y,z-1,w,cost[z-1]);
			if(w) calc(f[curStat][x][y][z],f[1-curStat],x,y,z,w-1,cost[w-1]);
			f[curStat][x][y][z].miss+=cost[x]+cost[y]+cost[z]+cost[w];
		}
	}
	node ans=f[curStat][n-1][n-1][n-1];
	printf("%d %d",ans.miss,ans.graze);
	return 0;
}