NOIP2019普及組複賽第4題文化之旅

1樓：yoki颯

滿分搜尋的話，按理用下面幾個剪枝就可以了.

1、最優性剪枝（ans < nowdist + mindist）（nowdist當前走過的路程，mindist至少還要走多遠）.

2、刪去所有影響終點的城市（不可能走到的……）3、倒搜

說實話給 pj 組的寫 std 時是這麼寫的……ac過了.

雖然怎麼說倒搜似乎有些說不過.

另把倒搜換成下面的剪枝也是可以過的.

設定一個x，從終點向外拓展x層.

每走一個城市看是否這x層中的任意一層被封鎖.

上述的確有些鬱悶，因為x取小作用不大，取大又降低了程式執行速度.

可以考慮將所有拓展層全部求出來.每2、3層跳躍一次.

100個點的圖如果想卡人的話，層數不會太多的，最多10層左右.

不過後面的沒有實現了.std x 取1就可以過.

程式在學校的說……明天中午發過來》_<~

2樓：倩女筠筠

4文化之旅 (culture.cpp/c/pas) 【問題描述】普及組有一位使者要遊歷各國他每到一個國家都能學到一種文化但他不願意學習任何一種文化超過一次即如果他學習了某種文化則他就不能到達其他有這種文化的國家。不同的國家可能有相同的文化。

不同文化的國家對其他文化的看法不同有些文化會排斥外來文化即如果他學習了某種文化則他不能到達排斥這種文化的其他國家。現給定各個國家間的地理關係各個國家的文化每種文化對其他文化的看法以及這位使者遊歷的起點和終點在起點和終點也會學習當地的文化國家間的道路距離試求從起點到終點最少需走多少路。【輸入】輸入檔案 culture.

in。第一行為五個整數 nkmst每兩個整數之間用一個空格隔開依次代表國家個數國家編號為 1 到 n文化種數文化編號為 1 到 k道路的條數以及起點和終點的編號保證 s 不等於 t 第二行為 n 個整數每兩個整數之間用一個空格隔開其中第 i 個數 ci表示國家 i 的文化為 ci。接下來的 k 行每行 k 個整數每兩個整數之間用一個空格隔開記第 i 行的第 j 個數為 aijaij= 1 表示文化 i 排斥外來文化 ji 等於 j 時表示排斥相同文化的外來人aij= 0 表示不排斥注意 i 排斥 j 並不保證 j 一定也排斥 i。

接下來的 m 行每行三個整數 uvd每兩個整數之間用一個空格隔開表示國家 u 與國家 v 有一條距離為 d 的可雙向通行的道路保證 u 不等於 v兩個國家之間可能有多條道路。【輸出】輸出檔名為 culture.out。

輸出只有一行一個整數表示使者從起點國家到達終點國家最少需要走的距離數如果無解則輸出-1。【輸入輸出樣例 1】 culture.in 2 2 1 1 2 1 2 0 1 1 0 1 2 10 【輸入輸出樣例說明】 culture.

out -1 由於到國家 2 必須要經過國家 1而國家 2 的文明卻排斥國家 1 的文明所以不可能到達國家 2。【輸入輸出樣例 2】 culture.in 2 2 1 1 2 1 2 0 1 0 0 1 2 10 【輸入輸出樣例說明】路線為 1 -> 2。

【資料範圍】對於 20%的資料有 2≤n≤8k≤5 對於 30%的資料有 2≤n≤10k≤5 對於 50%的資料有 2≤n≤20k≤8 對於 70%的資料有 2≤n≤100k≤10 culture.out 10 普及組對於 100%的資料有 2≤n≤1001≤k≤1001≤m≤n 21≤ki≤k1≤u, v≤n1≤d≤1000 s≠t1 ≤s, t≤n。

跪求noip2012初賽試卷！我要進複賽！進了複賽就能拿一等獎！謝了，誰知道今年noip題目，哪怕一道也行！ 10

3樓：神道

10分換題？？1000分都換不到哦

4樓：匿名使用者

我有，如果想要就聯絡

noip2012完善程式

5樓：

是全國少年資訊學奧賽嗎？如果是的話我就多少能幫幫你。

我04年參加過複賽，我那年一般初賽拿到60分左右就能進入複賽，現在應該會更高一些了吧，畢竟搞這個的學校開始多了。

初賽的技巧就是多看看計算機**網路的書，關於基礎知識部分的，c語言或者pascal是必須要過關的，一般完善程式都是寫個分號啊，寫一條簡單語句的。

要保證能過必須要學習演算法，基本的排序，遞迴，巢狀，圖論啥的這個是必須會的。

複賽基本上沒有什麼技巧，複賽比較考驗人，技巧就是多做演算法題，拓展思路，一般複賽第一題和第二題都是比較簡單的，如果實在不會，程式可以寫個「黑盒子」直接將參考例子寫進去，起碼能得個10分。這麼多年了不知道現在的考點和評判標準變了不。

總之多看演算法，多實踐演算法，很有好處。無論是高中時期還是到了大學時期，只要和計算機沾邊，如果要是學過演算法，那就事半功倍了。

6樓：匿名使用者

你是普及組還是提高組呢？我曾參加了三次，初賽大概六十多分就能進複賽。這題要拿多少分看你其他的成績。

選擇題必須做好，而最後的這個我認為大概拿個3/4的分數比較保險，我當初都是基本全對，無壓力進複賽的。如果你對各種演算法很熟悉，那麼這道題就不會很難了。剛開始做的時候掃一遍程式看看它要幹嘛，你自己可以像個大致思路出來，然後跟程式對一下，最後還要注意細節，要仔細，有些地方容易弄錯+1和-1等。

最後還是建立在你的程式設計水平的基礎上，並且如果你平時經常看別人的程式，或者幫助同學改錯誤，那麼這方面的能力就能提高，我在這方面受益不少。

NOIP2019普及組複賽第4題文化之旅

要noip2019普及組複賽試題

2019NOIP複賽怎麼複習,2017NOIP複賽怎麼複習？

解方程組2019x 2019y 4024 2019x 2019y

NOIP2019普及組複賽第4題文化之旅

要noip2019普及組複賽試題

2019NOIP複賽怎麼複習,2017NOIP複賽怎麼複習？

解方程組2019x 2019y 4024 2019x 2019y

相關推薦