Time 7：50 AM -> 11：15 AM

感覺今天考完后，我的內心是崩潰的

---

試題
考試包

---

T1：

首先看起來是個貪心，然而，然而，看到那個100%數據為n <= 2000整個人就虛了，發呆接近兩小時后意識到這個應該是個dp，然后開始考慮dp方程，腦殘把dp打成了n^3，果斷上天。。而且在轉移過程中推錯多打了一個-1，于是3個wa 1個ac 6個TLE ，10分滾粗

T1 dp 正解：

使用二維dp記錄當前狀態，dp[i][j]表示在前i個妖精中選擇了j個妖精的最小時間，轉移過程如下：

1、

如果dp[i-1][j] != inf dp[i][j] = min(dp[i][j], dp[i-1][j]);

2、

如果dp[i-1][j-1] != inf 即可以轉移，如果dp[i-1][j-1] < l[i] 那么dp[i][j] = min(dp[i][j], l[i] + t[i] -1)，否則dp[i][j] = min(dp[i][j], dp[i-1][j-1] + t[i]);最后逆序枚舉dp[n][i]輸出第一個小于inf的i值即為答案

#include <cstdio> #include <cstring> #include <algorithm>const int maxn = 2000 + 100;int dp[maxn][maxn]; int li[maxn], ri[maxn], ti[maxn]; int n;int main () {freopen("sanae.in", "r", stdin);freopen("sanae.out", "w", stdout);scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d %d %d", &li[i], &ri[i], &ti[i]);memset(dp, 127, sizeof(dp));for (int i = 0; i <= n; i++) dp[i][0] = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++) {if (dp[i-1][j] != 0x3f3f3f3f) {dp[i][j] = std :: min(dp[i][j], dp[i-1][j]);} if (dp[i-1][j-1] != 0x3f3f3f3f) {if (dp[i-1][j-1] < li[i]) dp[i][j] = std :: min(li[i] + ti[i] - 1, dp[i][j]);else {int cend = dp[i-1][j-1] + ti[i];if (cend <= ri[i]) {dp[i][j] = std :: min(dp[i][j], cend);}}}}for (int i = n; i >= 0; i--) if (dp[n][i] < 0x3f3f3f3f) {printf("%d", i);break;}return 0; }/* 7 3 12 6 7 13 6 9 14 3 13 22 7 13 24 5 16 24 3 16 26 6*/

T3

歷經一下午思考以及apt123大神講解，終于算是A了這道world final的B題。考試時看到數據范圍，果斷的寫了dfs，30分到手，也算是勉強彌補了一下第一題的坑
先來粘一下作者給的無比詳細(shi fen jian lue)的題解

我們將所有給出的三元環看做點，把所有邊也看成點。把三元環所對應的點與組成這個三元環的邊所對應的點連線，這樣我們就得到了一棵樹。問題轉化為：在這棵樹上取一棵有最多葉子結點的子樹，滿足：
1、 代表原三元環的點的所有連出的邊都可以選。
2、 代表原邊的點只能選兩條連出的邊。
樹形dp即可。

呵呵

再來看一下gcj給的題解

This proved to be the easiest problem in the finals for the experienced competitors.

We get some insight into the problem by noticing the graph resembles a tree. These graphs are actually called partial 2-trees. We can actually build a tree if we follow the way the graph is constructed. We build another graph that associates a node to each new added cycle of length this cycle shares an edge to an old cycle so we add an edge between the two respective nodes in the second graph. This way we have built the tree decomposition of these graphs. As on trees many problems that are hard to solve on general graphs have polynomial algorithms on this type of graphs.

Let's solve the related problem of finding the longest path in a tree. We can use dynamic programming and depth first search. We mark a node as a root. Every path in the tree has exactly one node that is closest to the root and this node splits the path in two downward paths. Now for each node in the tree we compute the longest downwards path that starts in it. To find the largest path in the tree we look at each node and at the two longest paths that start in it's children. This solves the problem in linear time.

The solution for our original problem is pretty similar. For each edge (x,y), we compute the cycle that contains it and and all the other nodes in the cycle have larger indexes. Let's call this a downward cycle since it goes the opposite direction of where the initial three nodes are. To find that number we have to look at all higher indexed nodes that were connected to this edge and try to use them as intermediary points in the cycle. So for a given intermediary point z we can build a cycle by looking at the longest downward cycle that contains the edge (x,z) and the longest downward cycle that contains the edge (z,y), use all the edges, add edge (x,y) and remove the edges (x,z) and (z,y).

We also compute the largest downward cycle which contains these two nodes but doesn't contain this edge, this is a union of the cycle that goes through these nodes and the second largest path from which we remove the edge (x,y).

呵呵

好吧我們開始自食其力

T3題解 以及 我對T3的理解：

很顯然這張圖不是一般的圖（廢話），我們不難發現這張圖實際上是由若干個小三角形組成的（即題解中所說的三元組），那么對于

這種形狀的圖來說，我們只能從中選取兩個三角形來進行操作，從而推知，對于任意一條邊，最多只有兩個與之相連三角形被選取，因此，可以選擇從四周向中間的123轉移
設a數組記錄了每個點連出去的兩個點，用每個后加入點的標號表示三角形的標號，b數組代表從其余兩個方向遞推過來時的最大值，

即圖中的7 -> 5 和 6 -> 5，c數組表示通過1、2、3邊的最大值，為保證轉移正確在讀入時直接保證a[i][0] < a[i][1]，之后每一步根據轉移目標是否為123的三角形進行分情況討論并轉移，注意每一步需要嘗試更新ans值， ans值并不一定會在123三角形中取得。注意轉移細節，詳見代碼。

#include <cstdio> #include <algorithm> #include <cstring>const int maxn = 100000 + 100; int a[maxn][2]; int b[maxn][2]; int c[100][100]; int n; int ans = 0;int main () {freopen("aya.in", "r", stdin);freopen("aya.out", "w", stdout);scanf("%d", &n);for (int i = 4; i <= n; i++) {scanf("%d %d", &a[i][0], &a[i][1]);if (a[i][0] > a[i][1]) {int t = a[i][0];a[i][0] = a[i][1];a[i][1] = t;}}for (int i = n; i >= 4; i--) {if (a[i][1] < 4) {ans = std :: max(ans, c[a[i][0]][a[i][1]] + b[i][1] + b[i][0] + 3);c[a[i][0]][a[i][1]] = std :: max(c[a[i][0]][a[i][1]], b[i][1] + b[i][0] + 1);} else {if (a[a[i][1]][0] == a[i][0]) {ans = std :: max(ans, b[a[i][1]][0] + b[i][0] + b[i][1] + 3);b[a[i][1]][0] = std :: max(b[a[i][1]][0], b[i][0] + b[i][1] + 1);} else {ans = std :: max(ans, b[a[i][1]][1] + b[i][1] + b[i][0] + 3);b[a[i][1]][1] = std :: max(b[a[i][1]][1], b[i][0] + b[i][1] + 1);}}}ans = std :: max(ans, c[1][2] + c[2][3] + c[1][3] + 3);printf("%d", ans);return 0; }

以及R神的pascal代碼

var n,i,j,ans:longint; a,b:array[1..100000,1..2]of longint; bb:array[1..3,1..3]of longint; function max(a,b:longint):longint; beginif a>b then exit(a);exit(b); end; beginassign(input,'aya.in');reset(input);assign(output,'aya.out');rewrite(output);readln(n);for i:=4 to n dobeginreadln(a[i,1],a[i,2]);if a[i,1]>a[i,2] thenbeginj:=a[i,1];a[i,1]:=a[i,2];a[i,2]:=j;end;end;for i:=n downto 4 dobeginif a[i,2]<4 thenbeginans:=max(ans,bb[a[i,1],a[i,2]]+b[i,1]+b[i,2]+3);bb[a[i,1],a[i,2]]:=max(bb[a[i,1],a[i,2]],b[i,1]+b[i,2]+1);endelsebeginif a[a[i,2],1]=a[i,1] thenbeginans:=max(ans,b[a[i,2],1]+b[i,1]+b[i,2]+3);b[a[i,2],1]:=max(b[a[i,2],1],b[i,1]+b[i,2]+1);endelsebeginans:=max(ans,b[a[i,2],2]+b[i,1]+b[i,2]+3);b[a[i,2],2]:=max(b[a[i,2],2],b[i,1]+b[i,2]+1);end;end;end;ans:=max(ans,bb[1,2]+bb[1,3]+bb[2,3]+3);writeln(ans);close(input);close(output); end.

完

轉載于:https://www.cnblogs.com/CtsNevermore/p/6000243.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的2016 10 26考试 NOIP模拟赛 杂题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。