序言：

有史以来，第一次第一名。

被质疑。。。被某些人又开始找我的茬。。

然后我写篇题解来澄清我并没有抄话说重启两次再加拔U盘，怎么会被说是抄的。。。再说即使是做过那也不得重打吗？

---

数列问题：

思路 ： 一道公式题。

当$n=1$的时候，f[1] = 0;

当$n=2$的时候，f[2] = 1;

当$n=3$的时候，f[3] = 2;

当$n=4$的时候，f[4] = 2;

当$n=5$的时候，f[5] = 3;

当$n=6$的时候，f[6] = 3;

当$n=7$的时候，f[7] = 4;

当$n=8$的时候，f[8] = 4;

当$n=9$的时候，f[9] = 4;

当$n=10$的时候，f[10] = 5;

当$n=11$的时候，f[11] = 5;

当$n=12$的时候，f[12] = 5;

当$n=13$的时候, f[13] = 6;

当$n=14$的时候, f[14] = 6；

当$n=15$的时候, f[15] = 6；

当$n=16$的时候, f[16] = 6；

当$n=17$的时候, f[17] = 7；

当$n=18$的时候, f[18] = 7；

当$n=19$的时候, f[19] = 7；

当$n=20$的时候, f[20] = 7；

当$n=21$的时候, f[21] = 8；

$$.......$$

到这里就可以看出来规律了。。。。 一个循环，如果$a_i$ * $a_i$大于$n$的话就把$a_i$赋值给一个变量，跳出循环。

---

code ：

#include <algorithm> #include <cstring> #include <cstdio> using namespace std; long long T, n; long long temp_a; int main() { // freopen("list.in", "r", stdin); // freopen("list.out", "w", stdout); scanf("%lld", &T); while(T --) { scanf("%lld", &n); for(int i = 1;i <= n;i ++){ if(i * i >= n) { temp_a = i; break; } } if(temp_a * (temp_a - 1) >= n) { printf("%lld\n", temp_a - 2 + temp_a - 1); } else{ printf("%lld\n", temp_a - 1 + temp_a - 1); } } return 0; }

这道题，就是靠推嘛。。看样例都可以有些启发吧。

---

Teamwork：

思路： 因为题面已经说了是连续的， 所以就可以用一个线性的dp。

设dp[i]以$i$结尾的包装能力之和的最大值。

设一个sum为dp[i]~dp[j]`包装能力的最大值。

然后状态转移方程就是： $$dp[j]=Max(dp[j],dp[i-1]+(j-i+1)\ast sum);$$

---

code：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10005; int dp[maxn] , s[maxn]; int sum; int n , k; int Max(int x, int y) { return x > y ? x : y; } 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", &s[i]); } for(int i = 1;i <= n;i ++) { sum = 0; for(int j = i;j < min(i + k , n + 1);j ++) { sum = Max(s[j] , sum);//求出最高的 dp[j] = Max(dp[j] , dp[i - 1] + (j - i + 1) * sum);//更新 } } printf("%d", dp[n]); return 0; } }

---

飞行路线：

思路： 一道最短路的题。。。

分层最短路的板子。。。

对于图中的所有节点$u$，他可以拆成$k+1$个节点$u_j$，而且j$\in$[0,k]。

分别表示当使用 $j$ 次免费通行权限后到达 $u$ 号节点的状态。

对于，样例来说那个图的话（脑补）加工中。

list[i][j]为到达i用了j次免费机会的最小花费。

vis[i][j]为到达i用了j次免费机会的情况是否出现过。

对于某些路径，我们可以选择使用机会，也可以选择不使用机会。

之后就分两种情况 ：

void spfa() { int head = 1; int tail = 2; memset(list, 0 ,sizeof(list)); list[1][0] = ks; list[1][1] = 0; while(head != tail) { int x = list[head][0]; int c = list[head][1]; for(int k = last[x];k;k = a[k].next) { int y = a[k].y; if(f[x][c] + a[k].dis < f[y][c]) { f[y][c] = f[x][c] + a[k].dis; if(vis[y][c] == false) { vis[y][c] = true; list[tail][0] = y; list[tail][1] = c; tail ++; if(tail == a_b) { tail = 1; } } } if(f[x][c] < f[y][c + 1] && c < d_k) { f[y][c + 1] = f[x][c]; if(vis[y][c + 1] == false) { vis[y][c + 1] = true; list[tail][0] = y; list[tail][1] = c + 1; tail ++; if(tail == a_b){ tail = 1; } } } } head ++; if(head == a_b) { head = 1; } vis[x][c] = false; } }

---

公路修建问题:

思路： 一道最小生成树。。。

这道题读了题感觉还好吧。。。

总共二次排序，

一次是因为一级公路有K条，所以先把一级公路的花费排一个序，然后就把剩下的公路由二级公路的花费再排一个序，

还有些细节在代码里。 code:

sort(a + 1 , a + 1 + m , cmp); int len = 0 , ans = 0; for(int i = 1;i <= m;i ++) {//第一级 if(find_set(a[i].a) != find_set(a[i].b)) { ans = max(ans , a[i].way); make_set(a[i].a , a[i].b); _ans[++ len].ans = 1; vis[a[i].num] = true; _ans[len].t = a[i].num; } if(len == k) { break; } } sort(a + 1 , a + 1 + m , cmp1); for(int i = 1;i <= m;i ++) {//第二级 if(!vis[a[i].num] && find_set(a[i].a) != find_set(a[i].b)) { ans = max(ans , a[i].way_2); make_set(a[i].a , a[i].b); vis[a[i].num] = true; _ans[++ len].ans = 2; _ans[len].t = a[i].num; } if(len == n - 1) { break; }

---

总结：

最后一道题，确实暑假的时候做过。。我能打出来，但是说不出某行代码什么意思，就说别人抄的，真的有意思吗？