\(Day_1T_1\) 铺设道路 （Link）
这个题的数据范围比较的大，\(1 ≤ n ≤ 100000,0 ≤ d_i ≤ 10000\)。观察发现时间复杂度应该限制在\(O(N)\)或者\(O(NlogN)\)以内，当然如果可以\(O(logN)\)更好，但这个好像是无法实现的。
\(O(NlogN)\)：这个是笔者在考场上想出来的，五分钟敲完发现秒了大样例就走了。用的方法是一个二分。我们发现你选择的这个区间的限制不在于\(Deep[i]_{Max}\)，而在于\(Deep[i]_{Min}\)。什么意思呢。比如这个区间\(\{4~ 3~ 2~ 5~ 3~ 5 \}\)。
我们肯定首先要整体切两次。因为整个区间内的最小值为\(2\)，然后区间变为\(\{2~ 1~ 0~ 3~ 1~ 3 \}\)出现了\(0\)，我们再考虑做其他的事情。
于是我们发现了算法流程：
\(1.\)对于区间\([L, R]\)，寻找到区间最小的点的位置\(Pos\)
\(2.\)\(Ans += Deep[Pos]\)
\(3.\)二分\([L, Pos - 1]\), \([Pos + 1, R]\)。
遍历\([L, R]\)总时间复杂度是\(O(N)\)，二分的时间复杂度是\(O(logN)\)，总时间复杂度\(O(NlogN)\)。也算是卡着过去了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
const int MAXN = 100010 ;
const int Inf = 0x7fffffff ;
LL N, Data[MAXN], Tag[MAXN], Max[MAXN][23], Ans ;
inline LL Read() {
LL X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-') ? - 1 : 1, ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline void Erfen(int L, int R, int T) {
if (L == R) {
Ans += Data[L] - T ;
return ;
} LL Min = Inf, Pos = 0 ;
for (int i = L ; i <= R ; i ++)
Pos = Min > Data[i] ? i : Pos, Min = Min > Data[i] ? Data[i] : Min ;
Min -= T ; Ans += Min ;
if(Pos > L) Erfen(L, Pos - 1, T + Min) ;
if(Pos < R) Erfen(Pos + 1 , R, T + Min) ;
return ;
}
int main() {
N = Read() ;
for (int i = 1 ; i <= N ; i ++) Data[i] = Read() ;
int L = 1, R = N ; LL Min = Inf, Pos = 0 ;
for (int i = 1 ; i <= N ; i ++)
Pos = Min > Data[i] ? i : Pos, Min = Min > Data[i] ? Data[i] : Min ;
Ans += Min ;
if (Pos > 1) Erfen(1, Pos - 1, Min) ;
if (Pos < N) Erfen(Pos + 1, N, Min) ;
printf("%lld", Ans) ;
fclose(stdin) ; fclose(stdout) ;
return 0 ;
}\(O(N)\)：如果你愿意在考场上多花一点时间思考一下以保证\(AC\)的话，你可以发现这其实就是一个贪心，你发现对于两个相邻的数\(Deep[i]\)和\(Deep[i + 1]\)，如果\(Deep[i] > Deep[i + 1]\)，那么我们肯定会要把两个坑都填上，这时如果我们选择了区间[i, i + 1]，你发现根本就不需要加上\(Deep[i + 1]\)所要耗费的次数，因为他一定会被\(i\)点顺带着填掉。那么我们发现贪心的规律：对于每一个\(i\), 如果\(Deep[i] > Deep[i + 1]\)（当然也可以是小于，没有分别），\(Ans += Deep[i] - Deep[i + 1]\)。
复杂度\(O(N)\)，没有什么问题；
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;
typedef long long LL ;
const int MAXN = 100010 ;
const int Inf = 0x7fffffff ;
LL N, Deep[MAXN], Ans ;
inline LL Read() {
LL X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-') ? - 1 : 1, ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
int main() {
N = Read() ;
for (int i = 1 ; i <= N ; i ++) {
Deep[i] = Read() ;
Ans += (Deep[i] > Deep[i - 1]) ? (Deep[i] - Deep[i - 1]) : 0 ;
} printf("%lld", Ans) ; return 0 ;
}\(Day_1T_2\) 货币系统（Link）
实际上这到题考的就是一个完全背包。我们分析样例
\(4\)
\(3~ 19~ 10~ 6\)
可以发现，这里面的\(6\)可以被两个\(3\)表示，因此它无用，\(19\)可以被一个\(10\)和\(3\)个\(3\)表示，因此它也无用。所以得出答案就是2种。
于是我们发现，如果有一种面值是可以被其余的面值表示出来的，那么它就可以被筛掉。于是我们找到了算法流程：
\(1.\)从大到小排序。并且我们知道最小的面值一定要选。
\(2.\)对于每一个\(Data[i]\)，如果它已经被标记，那么\(continue\)。
\(3.\)计数器\(Ans++\)，标记\(F[Data[i]] = 1\)
\(4.\)从当前的\(Data[i]\)开始循环足够多的数，如果\(F[j - Data[i]] = 1\)，那么代表加上\(Data[i]\)之后还是可以被筛掉，那么\(F[j] = 1\)。
\(Over\)，时间复杂度为\(O(25000TN)\)算一算发现没有超时。完美。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long LL ;
const int MAXN = 10010 ;
const int MAXM = 25000 ;
int N, M, Data[MAXN], T, F[MAXM], Total ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline bool CMP(int X, int Y) { return X < Y ; }
int main() {
T = Read() ; while (T --) {
N = Read() ; Total = 0 ;
memset(Data, 0, sizeof(Data)) ;
memset(F, 0, sizeof(F)) ;
for (int i = 1 ; i <= N ; i ++)
Data[i] = Read(), M = max(M, Data[i]) ;
sort(Data + 1 , Data + N + 1, CMP) ;
for (int i = 1 ; i <= N ; i ++) {
if (F[Data[i]]) continue ;
Total ++ ; F[Data[i]] = 1 ;
for (int j = Data[i] ; j <= M ; j ++)
if (F[j - Data[i]]) F[j] = 1 ;
} printf("%d\n", Total) ;
} return 0 ;
}\(Day_2T_1\) 旅行（Link）
\(Subtask_1 ~ M = N - 1\)
这显然是一个树，我们显然要从\(1\)号节点出发，然后每一次选择与他相连的子节点中最小的点，那么我们可以对每一个点连接的点进行一个从小到大的排序，然后进行一遍\(Dfs\)就可以了。思考难度接近\(0\)，但是占了\(60\)的高分，这大概也就是为什么它的难度排在了\(Day_2T_1\)。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long LL ;
const int MAXN = 5050 ;
const int MAXM = 5050 ;
int N, M, Tot, H[MAXN], SF, ST, Ans[MAXN], Cnt ;
int E[MAXN][MAXN], Edge[MAXN][2], L[MAXN] ;
bool Vis[MAXN] ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
if (ch == '-') return -X;
return X;
}
inline void Doit(int Now, int Fa) {
printf("%d ", Now) ;
sort(E[Now] + 1, E[Now] + H[Now] + 1) ;
for (int i = 1 ; i <= H[Now] ; i ++)
if (E[Now][i] != Fa) Doit(E[Now][i], Now) ;
}
int main() {
N = Read() ; M = Read() ;
for (int i = 1 ; i <= M ; i ++) {
int X = Read(), Y = Read() ;
E[X][++ H[X]] = Y ; E[Y][++ H[Y]] = X ;
Edge[i][0] = X ; Edge[i][1] = Y ;
}
if (M == N - 1) Doit(1, 0) ;
return 0 ;
}\(Subtask_2 ~ M = N\)
这个就有一点难度了，起码不是那种让人一眼瞧出来的那种。我们发现这种图就是比一棵树多了一条边，那么我们知道它肯定会构成一个环并且仅会构成一个环，所以我们知道这是个基环树。
题目要求的是走完所有的点，则只可能走\(N - 1\)条边，也就是时候不论怎么走都会剩下一条边没走，那么我们就可以采取暴力手段，每次选取一条边把他删掉，确切的来说是记录下来，然后\(Dfs\)的时候如果碰到这条边就不走，然后对于每次的方案取最优即可。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long LL ;
const int MAXN = 5050 ;
const int MAXM = 5050 ;
int N, M, Tot, H[MAXN], SF, ST, Ans[MAXN], Cnt ;
int E[MAXN][MAXN], Edge[MAXN][2], L[MAXN] ;
bool Vis[MAXN] ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
if (ch == '-') return -X;
return X;
}
inline void Doit(int Now, int Fa) {
printf("%d ", Now) ;
sort(E[Now] + 1, E[Now] + H[Now] + 1) ;
for (int i = 1 ; i <= H[Now] ; i ++)
if (E[Now][i] != Fa) Doit(E[Now][i], Now) ;
}
inline void Dfs(int Now, int Fa) {
L[++ Cnt] = Now ; Vis[Now] = 1 ;
for (int i = 1 ; i <= H[Now] ; i ++) {
if(! Vis[E[Now][i]] && ! ((Now == SF && E[Now][i] == ST) ||(Now == ST && E[Now][i] == SF)))
Dfs(E[Now][i], Now) ;
}
}
inline bool Judge() {
for (int i = 1 ; i <= N ; i ++)
if (Ans[i] != L[i]) return Ans[i] > L[i] ;
return false ;
}
inline void WORK() {
memset(Ans, 127, sizeof(Ans)) ; memset(Vis, 0, sizeof(Vis)) ;
for (int i = 1 ; i <= N ; i ++) sort(E[i] + 1, E[i] + H[i] +1) ;
//把每一条边连接的点都排序
for (int i = 1 ; i <= M ; i ++) { Cnt = 0 ;
memset(L, 0, sizeof(L)) ; memset(Vis, 0, sizeof(Vis)) ;
SF = Edge[i][0], ST = Edge[i][1] ;
Dfs(1, 0) ;
if (Judge() && Cnt == N)
for (int i = 1 ; i <= N ; i ++)
Ans[i] = L[i] ;
}
for (int i = 1 ; i <= N ; i ++) printf("%d ", Ans[i]) ;
}
int main() {
N = Read() ; M = Read() ;
for (int i = 1 ; i <= M ; i ++) {
int X = Read(), Y = Read() ;
E[X][++ H[X]] = Y ; E[Y][++ H[Y]] = X ;
Edge[i][0] = X ; Edge[i][1] = Y ;
}
if (M == N - 1) Doit(1, 0) ;
else WORK() ; return 0 ;
}其实仔细想一想这道题也并不是特别的难，如果只停留在暴力删边的方法上的话。这里直接爆删是没法通过所有的测试点的，但是\(88\)分的成绩也不错了，加上在\(Dfs\)的过程中的一些最优性剪枝和玄学优化的话是可以卡过去的。然而还有一种十分玄的做法是边删边维护以做到\(O(N)\)，就不再说了（懒
以及可以扩展到不限制\(M\)的情况下在仙人掌图上做，可是我不会~~~