题目限制一览
| 题目 |
时间限制 |
空间限制 |
| 1. trapped |
1000 MS |
128 MB |
| 2. array |
1000 MS |
128 MB |
| 3. travel |
1000 MS |
128 MB |
1. 陷阱（trapped.cpp）
Description
FJ将N(1<=N<=100000)堆干草放在了一条平直的公路上。第j堆干草的大小为Sj，坐标为Pj。奶牛贝茜位于一个没有干草堆的点B。
奶牛Bessie可以在路上自由移动，甚至可以走到某个干草堆上，但是不能穿过去。如果她朝同一个方向跑了D个单位的距离，那么她就有足够大的速度去击碎任何大小严格小于D的干草堆。当然，在这之后她就可以获得了更大的活动空间，以尝试击碎更多干草堆。
约翰可以指定某堆干草，并增大它的大小，他想知道他最少需要 增大多少，才能把奶牛贝茜困住（即在第一堆干草和最后一堆干草之间），或者根本不可能。
第一行两个整数，分别表示N和B
接下来N行，每行两个整数S,J ，描述了干草堆的大小和坐标
Output
输出一个整数，表示FJ需要增加的最小值。如果不可能阻止Bessie，则输出-1
1
2
3
4
5
6
| 5 7
8 1
1 4
3 8
12 15
20 20
|
Sample Output
Hint
所有干草堆的位置和大小都属于[1,10^9]
分析
做法一：暴力枚举（50分）
将所有干草堆按照Bessie的起点位置分成左右两个部分，然后每个部分内按照位置坐标升序排序
设 $f[i]$ 表示将Bessie阻挡在第 $i$ 堆干草块前最少需要在这堆干草上加的干草高度，于是可以得到：
$f[i]=min\lbrace abs(pos[j]-pos[i]-siz[i])\; \lvert\; pos[j]\geq abs(pos[j]-pos[i])\; \rbrace$
这样枚举寻找满足条件的 $j$ 的过程中，若遇到 $siz[i]\geq \lvert pos[j]-pos[i] \rvert$ 可以直接输出 0,复杂度接近 $O(n^2)$
做法二：近似贪心（100分）
我们可以指定Bessie往一个方向突破（左或者右），然后考虑花费最少的干草高度堆在某一个Bessie突破方像的干草堆上使得她不能出去
这样做的前提就是左边的干草堆必须能够承受Bessie的撞击，假设当前考虑突破到右边的第 $i$ 个干草堆，那么左边就必须存在干草堆 $j$ 使得 $\lvert pos[j]-pos[i] \rvert\leq siz[j]$ 然后我们才能放心的在这个右边的干草堆上面堆草
那么Bessie往左边突破的时候同理分析，最后类似贪心的做法能在近似 $O(n)$ 的时间复杂度内得到答案
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stack>
#define maxn 100005
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 siz,pos;
bool operator <(const node &x)const{
return pos<x.pos;
}
}dl[maxn],dr[maxn];
int n,st,cl,cr;
bool l[maxn],r[maxn],del[maxn];
int f[maxn];int sign;
void dp(){
}
int main(){
#ifndef ONLINE_JUDGE
freopen("trapped.in","r",stdin);
freopen("trapped.out","w",stdout);
#endif
fcin(n);fcin(st);
int x,y;
for(int i=1;i<=n;i++){
fcin(x);fcin(y);
if(y<st) dl[++cl]=(node){x,y};
else dr[++cr]=(node){x,y};
}sort(dl+1,dl+cl+1);sort(dr+1,dr+cr+1);
int ans=-1,sign=cl;
for(int i=1;i<=cr && sign;i++){
while(sign && abs(dr[i].pos-dl[sign].pos)>dl[sign].siz) sign--;
if(!sign) break;
if(abs(dr[i].pos-dl[sign].pos)<=dr[i].siz) return printf("0"),0;
else if(ans<0) ans=abs(dr[i].pos-dl[sign].pos)-dr[i].siz;
else ans=min(ans,abs(dr[i].pos-dl[sign].pos)-dr[i].siz);
}sign=1;
for(int i=cl;i&&sign<=cr;i--){
while(sign<=cr && abs(dl[i].pos-dr[sign].pos)>dr[sign].siz) sign++;
if(sign>cr) break;
if(abs(dr[sign].pos-dl[i].pos)<=dl[i].siz) return printf("0"),0;
else if(ans<0) ans=abs(dr[sign].pos-dl[i].pos)-dl[i].siz;
else ans=min(ans,abs(dr[sign].pos-dl[i].pos)-dl[i].siz);
}printf("%d",ans);
return 0;
}
|
2. 数列（array.cpp）
Description
有两个位置分别对应的序列A、B，长度为n，两序列都为n的一个排列。当Ai == Bj时，上下会连一条边。
你可以选择序列A或者序列B进行旋转任意K步，
如 3 4 1 5 2 旋转两步为 5 2 3 4 1。
求旋转后最小的相交的线段的对数。
第一行是N
接下来N行,每行一个整数，表示A[i]
再接下来N行,每行一个整数，表示B[i]
Output
输出最小的相交的线段对数
Sample Output
Hint
1≤N≤100,000
分析
题目所说的 “两个数列相交的线段最小” 其实就是尽可能多的将 a 数列中的数与 b 数列中的数一一对应，进一步的，如果将 b 数列中的元素在 a 数列中出现的位置做成新的一个序列（例如样例的序列为 3 4 5 1 2）所谓的最小的相交线段数就是这个序列的最少的逆序对数
由于 a 数列可以旋转，那么对应出来的新的序列也是可以旋转的，但是我们不用每次旋转之后计算新的逆序对数，只需要记录最开始的逆序对数为 $ans$，那么假设当前新序列的末尾元素为 $p[i]$，它被旋转到了第一位，那么序列中减少的逆序对数就是原来比 $p[i]$ 大的元素个数，增加的逆序对数就是原来比 $p[i]$ 小的元素个数，由于题目给出的序列是 $[1,\;n]$ 的一个全排列，那么新的逆序对数 $ans’=ans-(n-p[i])+p[i]-1$，那么从尾到头把序列扫描一遍取最小值即可
P.S. 由于题目中说两个数列都可以旋转，所以上述操作要对 $(b\leftarrow a)$ 和 $(a\leftarrow b)$ 各自做一遍，取最小值
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stack>
#define maxn 100005
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
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 n;ll T[maxn];
int a[maxn],b[maxn];
int vis[maxn],f[maxn];
void updata(int p,int d){
for(int i=p;i<=n;i+=lowbit(i))
T[i]+=1ll*d;
return;
}
ll sum(int p){
ll ans=0;
for(int i=p;i;i-=lowbit(i))
ans+=T[i];
return ans;
}
ll init(int ref[maxn],int op[maxn]){
memset(f,0,sizeof(f));
memset(T,0,sizeof(T));
for(int i=1;i<=n;i++) vis[ref[i]]=i;
for(int i=1;i<=n;i++) f[i]=vis[op[i]];
ll ans=0,tmp,res;
for(int i=n;i;i--){
ans+=sum(f[i]);
updata(f[i],1);
}res=ans;
for(int i=n;i>=2;i--){
tmp=ans-(n-f[i])+f[i]-1;
res=min(res,tmp);
ans=tmp;
}
return res;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
#endif
fcin(n);
for(int i=1;i<=n;i++) fcin(a[i]);
for(int i=1;i<=n;i++) fcin(b[i]);
printf("%lld",min(init(a,b),init(b,a)));
return 0;
}
|
3. 旅游（travel.cpp）
Description
某城市有N个旅游胜地（1≤N≤1000），编号为1…N，每个旅游胜地都有一个愉悦度Q。如果去i胜地旅游，可以获得Qi单位的愉悦度。每块胜地最多和10块胜地有相连的道路，在相连的两个胜地之间走动需要消耗E单位的愉悦度（1≤E≤1,000,000)。你可以从任意一个胜地开始旅游，并且想要在获得了最多愉悦度的时候停止。你是一个挑剔的旅行者，一旦去过某个胜地，她就不会再去愉悦度相同或更低的胜地！但是你可以路过某些胜地，而不停下来享受旅游（从而不获得该圣地的愉悦度）。实际上，如果路过一块高愉悦度的胜地，等一下返回再去享受旅游，有时会更有利！请计算你能够获得的愉悦度的最大值。
第1行：包含两个整数N和E。
接下来N行：每行描述一块胜地，首先两个整数Q和D，分别表示该胜地的愉悦度（范围1…1,000,000）和相连的其他胜地的数量。然后紧接着D个整数表示相连的胜地编号。
Output
输出你能够获得的愉悦度的最大值。
1
2
3
4
5
6
| 5 2
4 1 2
1 3 1 3 4
6 2 2 5
5 2 2 5
2 2 3 4
|
Sample Output
Hint
NO HINT
分析
做法：BFS（或SPFA）+ DP
由于题目中限制了在旅游完一个景点之后只能去比它愉悦度更高的景点，那么我们可以根据愉悦度从大到小给每个景点排序，设 $f[i]$ 表示以 $i$ 号旅游景点为起点能得到的最大愉悦度
那么显然，若以 $i$ 号景点为起点，我们只能去 $[1,\;i-1]$ 号旅游景点旅游（不是路过），并且还要减去路上的花销，由于题目中的边权值是一样的，所以对于每个点直接 BFS 一次就可以到得到它到每个点的边权和，所以转移方程为：
$f[i]=max(f[i],\; f[j]+Q[id[i]]-dist[id[i]][id[j]])$，这里的 $id$ 表示排序后的数组对应到原来的旅游景点的编号
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stack>
#define maxn 5005
#define maxm 10005
using namespace std;
typedef long long ll;
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 tot,n,costE,q[maxn];
bool vis[maxn]; int cost[maxn][maxn];
ll f[maxn];int id[maxn];
inline void Eadd(int u,int v){
to[++tot]=v;nxt[tot]=head[u];
head[u]=tot;
}
void bfs(int src){
memset(cost[src],0x3f,sizeof(cost[src]));
memset(vis,false,sizeof(vis));queue<int> q;
q.push(src);vis[src]=true;cost[src][src]=0;
int hx;
while(!q.empty()){
hx=q.front();q.pop();
for(int i=head[hx];i;i=nxt[i])
if(!vis[to[i]]){
vis[to[i]]=true;
q.push(to[i]);
cost[src][to[i]]=cost[src][hx]+costE;
}
}
}
bool cmp(int x,int y){
return q[x]>q[y];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
#endif
fcin(n);fcin(costE);
int x,y;
for(int i=1;i<=n;i++){
fcin(q[i]);fcin(x);
id[i]=i;
for(int j=1;j<=x;j++){
fcin(y);
Eadd(i,y);
}
}
for(int i=1;i<=n;i++)
bfs(i);
sort(id+1,id+n+1,cmp);ll ans=0;
for(int i=1;i<=n;i++){
f[i]=q[id[i]];
for(int j=1;j<i;j++) f[i]=max(f[i],q[id[i]]+f[j]-cost[id[i]][id[j]]);
ans=max(ans,f[i]);
}printf("%lld",ans);
return 0;
}
|
