前言
这次考试比较恶心，三道蓝题，一道不知难度的题，不过最后还是考了270，Rank5，运气有方面的好，有的方面坏。出的题都是我擅长的算法T1规律题，T2一道简单DP，T3一道分层图最短路，T4是一道比较难想但代码却很简单的玄学生成树题目。但代码中却出现了一些小错误，T3的dijkstra居然爆了，他T了，我打了一个假的dijkstra。T4脑壳发抽多加了两个if。
算法&难度
T1:推规律 难度：没有，应该是道绿的左右吧。 T2:线性DP题 难度：蓝题（应该是评错了吧，绿题做有难度） T3:分层图最短路 难度：蓝题 T4:有限制的最小生成树，kruskal 难度：蓝题
T1 数列问题
理想分数100，实际分数100
题目描述
思路：
首先看到都是输入一个数，输出一个数，让后再看到这个数据范围：1<=t<=1e4,1<=n<=1e9，这数据范围，O(tn),O(n+t),的算法都否认了，并且如果用数组来存储，一定会炸。于是就想到了推一下规律。我先打了一个dfs，将1-30的答案都搜了一遍，发现一个神奇的规律，每两组就加一个数，每一组数字就加一。如下：
f
[
1
]
=
0
,
f
[
2
]
=
1
,
f
[
3
]
=
2
,
f
[
4
]
=
2
,
f
[
5
]
=
3
,
f
[
6
]
=
3
,
f
[
7
]
=
4
,
f
[
8
]
=
4
,
f
[
9
]
=
4
,
f
[
10
]
=
5......
f[1] = 0,f[2]=1,f[3]=2,f[4]=2,f[5]=3,f[6]=3,f[7]=4,f[8]=4,f[9]=4,f[10] = 5......
f[1]=0,f[2]=1,f[3]=2,f[4]=2,f[5]=3,f[6]=3,f[7]=4,f[8]=4,f[9]=4,f[10]=5......你发现了什么，这个有规律。如果你还是发现不了规律，那么就打个暴力dfs吧，让后再一次输出来，傻子都能发现规律。。。 让后接下来的就很简单了，模拟一次它运行时的操作，时间复杂度
O
(
t
n
)
O(t\sqrt n)
O(tn
) 快的飞起，详细证明这儿就不给出了(作者不会),似乎要用均值不等式，可我还是一个数学差的爆炸的初中生，证明是数学竞赛的事，不是我的事，呵呵。。。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std
;
const int MAXN
= 1e7 + 5;
int t
,n
,pq
= 1,cnt
,step
;
int main() {
freopen("list.in","r",stdin);
freopen("list.out","w",stdout);
scanf("%d",&t
);
while(t
--) {
scanf("%d",&n
);
while(n
> 0) {
n
-= pq
;
cnt
++;
step
++;
if(cnt
== 2) cnt
= 0,pq
++;
}
printf("%d\n",step
- 1);
step
= 0,pq
= 1,cnt
= 0;
}
return 0;
}
T2 Teamwork G
理想分数100，实际分数100 题目描述 自认为是一道很简单的DP题目，考场上花了3min看题，5min想DP状态转移方程式，5min打出，0s过样例，5min构数据查错，一共二十分钟就过了这道题。感觉比第1题还水。
分析
一道很水的线性动态规划，设dp[i]表示前i个人最多能得到的技能水平之和，他对dp[min(i + k,n)]这个之前的有影响，而后面的又由后面k(j<=n)个的最大值得到，于是他就可以得到一个十分简单的状态转移方程
f
[
j
]
=
m
a
x
(
f
[
j
]
,
f
[
i
]
+
s
u
m
∗
(
j
−
i
)
)
f[j]=max(f[j],f[i]+sum*(j-i))
f[j]=max(f[j],f[i]+sum∗(j−i))当动态规划题目写出来了状态转移方程式，接下来还不简单吗？直接狂撸代码，反正代码量都只有这么小了。。。 先外层循环枚举结尾，循环0-n(1-n也行，就多在外面加个初始状态就可以了)。内层循环枚举后面会影响的从i到min(n,i + k)，一边存当前访问的最大值，一边更新当前的dp值，最后输出dp[n]，也就是1-n全部的技术值，时间复杂度
O
(
n
k
)
O(nk)
O(nk)，也是快的飞起
code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std
;
const int MAXN
= 1e4 + 5;
int n
,k
,a
[MAXN
],dp
[MAXN
];
int main() {
freopen("worker.in","r",stdin);
freopen("worker.out","w",stdout);
scanf("%d %d",&n
,&k
);
for(int i
= 1;i
<= n
;i
++)
scanf("%d",&a
[i
]);
for(int i
= 0;i
<= n
;i
++) {
int maxx
= 0;
for(int j
= i
+ 1;j
<= min(i
+ k
,n
+ 1);j
++) {
maxx
= max(maxx
,a
[j
]);
dp
[j
] = max(dp
[j
],dp
[i
] + maxx
* (j
- i
));
}
}
printf("%d",dp
[n
]);
return 0;
}
T3 [JLOI2011]飞行路线
期望100，实际60 我打dijkstra的时候傻了，dijkstra板子都背错了，我的vis呢？不见了！然后，考试结束，原地爆炸！！！ 题目描述
分析
本来是很简单的一道分层图最短路，看到有可以将价值变为0的东西，于是就分一下层，利用一下DP的思想。设dis[i][k]表示当前走到第i个点，用了k个能将权值变为0的“门票”，然后就用这个点来修改与它连过边的点，分成两种情况，用"门票"或者是不用"门票"，当用的"门票"大于了k，也就是将"门票"用光了时，第一种情况就跳过，直接执行第二种操作，这样就包含了所有的情况(两种情况)，想好这个思路了后就一切都交给dijkstra了，按着板子，一个一个都打了下去。最后的答案就存在了t点，也就是最后需要从起点到达的点，因为可以用k个"门票"，于是应该就在dis[n][k]中？但题目中没保证k<n，所以当k>n时这个就不对了了，答案就是最先赋值的0x3f极大值了，所以应该要从1-n遍历一遍寻找到最小值，来找到最后的答案。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std
;
const int MAXN
= 1e4 + 5;
int n
,m
,k
,s
,t
,dis
[MAXN
][20],minn
= 0x3f3f3f3f;
bool vis
[MAXN
][20];
struct node
{
int u
,w
;
node(){}
node(int U
,int W
){u
= U
,w
= W
;}
friend bool operator < (node x
,node y
){return x
.w
> y
.w
;}
};
struct data
{
int u
,w
,k
;
data(){}
data(int U
,int W
,int K
){u
= U
,w
= W
,k
= K
;}
friend bool operator < (data x
,data y
){return x
.w y
.w
;}
};
vector
<node
> vec
[MAXN
];
priority_queue
<data
> Q
;
void add(int u
,int v
,int w
) {
vec
[u
].push_back(node(v
,w
));
vec
[v
].push_back(node(u
,w
));
}
void dijkstra() {
memset(dis
,0x3f,sizeof(dis
));
dis
[s
][0] = 0;
Q
.push(data(s
,0,0));
while(!Q
.empty()) {
data f
= Q
.top();
Q
.pop();
int Size
= vec
[f
.u
].size();
int use
= f
.k
;
if(vis
[f
.u
][use
]) continue;
vis
[f
.u
][use
] = 1;
for(int i
= 0;i
< Size
;i
++) {
int to
= vec
[f
.u
][i
].u
;
int wei
= vec
[f
.u
][i
].w
;
if(dis
[to
][use
+ 1] > dis
[f
.u
][use
] && use
+ 1 <= k
&& !vis
[to
][use
+ 1]) {
dis
[to
][use
+ 1] = dis
[f
.u
][use
];
Q
.push(data(to
,dis
[to
][use
+ 1],use
+ 1));
}
if(dis
[to
][use
] > dis
[f
.u
][use
] + wei
&& !vis
[to
][use
]) {
dis
[to
][use
] = dis
[f
.u
][use
] + wei
;
Q
.push(data(to
,dis
[to
][use
],use
));
}
}
}
for(int i
= 0;i
<= k
;i
++)
minn
= min(minn
,dis
[t
][k
]);
printf("%d",minn
);
return;
}
int main() {
scanf("%d %d %d %d %d",&n
,&m
,&k
,&s
,&t
);
for(int i
= 1;i
<= m
;i
++) {
int u
,v
,w
;
scanf("%d %d %d",&u
,&v
,&w
);
add(u
,v
,w
);
}
dijkstra();
return 0;
}
T4 [HNOI2006]公路修建问题
期望20，实际10 没想到，居然在我的骗分代码上删了两个if后就A了，神奇？！！ 题目描述
分析
其实就是一个两次生成树，我考场上可能有一点问题居然想了kruskal+DP让后再想到了有限制的生成树等各种奇特的算法。因为看到必须要有k条生成树的边中是第一类，并且c1>=c2，所以直接先对c1进行排序，然后再对他求半棵生成树，一棵有k条边的生成树，然后再构成剩下n-k-1条边的半棵生成树，注意，此时的排序应该是c2的权值进行排序，应为此时构成的边是c2权值。让后就直接在求生成树的时候max一下，求一下最大的权值，让后输出，了事。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std
;
const int MAXN
= 2e4 + 5;
int n
,k
,m
,fa
[MAXN
];
struct node
{
int a
,b
,c1
,c2
;
}p
[MAXN
];
void Make_Set() {
for(int i
= 1;i
<= m
;i
++) fa
[i
] = i
;
}
int Find_Set(int x
) {
if(fa
[x
] == x
) return x
;
return fa
[x
] = Find_Set(fa
[x
]);
}
int Sum
;
bool cmp1(node x
,node y
){return x
.c2
< y
.c2
;}
bool cmp2(node x
,node y
){return x
.c1
< y
.c1
;}
void Kruskal() {
sort(p
+ 1,p
+ m
,cmp1
);
for(int i
= 1;i
< m
;i
++) {
int x
= Find_Set(p
[i
].a
),y
= Find_Set(p
[i
].b
);
if(x
== y
) continue;
fa
[x
] = y
;
Sum
= max(Sum
,p
[i
].c2
);
}
printf("%d",Sum
);
}
void kruskal() {
sort(p
+ 1,p
+ m
,cmp2
);
int q
= 0;
for(int i
= 1;i
< m
;i
++) {
int x
= Find_Set(p
[i
].a
);
int y
= Find_Set(p
[i
].b
);
if(x
== y
) continue;
fa
[x
] = y
;
Sum
= max(Sum
,p
[i
].c1
);
q
++;
if(q
== k
) break;
}
}
int main() {
scanf("%d %d %d",&n
,&k
,&m
);
for(int i
= 1;i
<= m
- 1;i
++)
scanf("%d %d %d %d",&p
[i
].a
,&p
[i
].b
,&p
[i
].c1
,&p
[i
].c2
);
Make_Set();
kruskal();
Kruskal();
return 0;
}
完结撒花~~
