PT07Z

批改 作業 時間。顯然有兩個問題:
– 數據沒有從 IO 讀入讀出。
– 第一個 dfs 求出的不是最遠的端點。

不過我修改了之後目前依然沒有通過 SPOJ 的測試。支持 Javascript 的 OJ 也很少,
Codeforces 上 Javascript 的提交也遠不如其他語言。
如何在 SPOJ 提交 Javascript?這個鏈接 下面附了一個 Life, the Universe, and Everything 的 JS 標程。

let vertexLen = parseInt(readline().trim()); // 頂點數
let vertex = new Map(); // 頂點數據集合 map 可以設置鍵對值 0 1 2 3 4 5 or 1 2 3 4 5 6 or A B C D E F G ... ...

/**
 * 設置頂點
 * @param {String || Number} v 頂點
 */
const setVertex = v => vertex.set(v, []);
/**
 * 設置邊
 * @param {String || Number} v1 點
 * @param {String || Number} v2 點
 */
const setVertexEdge = (v1, v2) => {
  vertex.get(v1).push(v2);
  vertex.get(v2).push(v1);
};

// 設置點
for (let i = 1; i <= vertexLen; i++) setVertex(i);

// 定義邊
let vertexEdge = [[1, 4], [2, 4], [3, 4], [4, 5], [5, 6]];

// 設置邊
// for (let i = 0; i < vertexEdge.length; i++)
//   setVertexEdge(vertexEdge[i][0], vertexEdge[i][1]);
for (let i = 0; i < vertexLen - 1; i++) {
    var edge = readline().trim().split(" ").map(function(x) { return parseInt(x); });
    setVertexEdge(edge[0], edge[1]);
}


/**
 * dfs
 * @param {String || Number} startNode 開始點
 */
const dfs = startNode => {
  let visited = new Map(); // 保持和頂點結構一樣
  let f = startNode;
  let z = 0;
  for (let i = 1; i <= vertexLen; i++) visited.set(i, false); // 設置訪問狀態

  // dfs 方法
  const dfsFunc = (startNode, visited, dep) => {
    if (dep > z) {
        f = startNode;
        z = dep;
    }
    dep += 1;
    visited.set(startNode, true); // 第一個點設置已訪問
    let get_next = vertex.get(startNode); // 獲得頂點的所有臨接點
    for (let i = 0; i < get_next.length; i++) {
      // 循環臨接點
      let get_elem = get_next[i]; // 得到元素
      if (!visited.get(get_elem)) {
        dfsFunc(get_elem, visited, dep);
      }      
    }
    return z;
  };
  dfsFunc(startNode, visited, 0);
  return f;
};

/**
 * dfs
 * @param {String || Number} startNode 開始點
 */
const dfs1 = startNode => {
  // 記錄開始點和父級節點
  const dfsFunc = (startNode, parentNode = -1) => {
    let z = 0; // 記錄長度
    let get_next = vertex.get(startNode); // 得到相鄰節點
    for (let i = 0; i < get_next.length; i++) { // 循環點
      let get_elem = get_next[i]; // 得到點
      if (get_elem === parentNode) continue; // 如果是父節點 跳過
      z = Math.max(z, dfsFunc(get_elem, startNode) + 1); // 遞歸添加長度
    }
    return z;
  };
  return dfsFunc(startNode);
};

let z = dfs(1);

// console.log(z);

let z1 = dfs1(1);
// console.log(z1);

print(z1);

// console.log(vertex);

勿讓權錢交易腐蝕學科競賽的純潔性

子曰:「有教無類」
—— 《論語·衛靈公》

最近幾天 NOIP 停辦的事情牽動著很多 exOIer 們的心,看到好友圈紛紛曬出自己當年的 NOIP 1= 的獎狀,我們現在或活躍在學術一線,或在互聯網公司搬磚,無不是化為一顆社會主義的螺絲釘,為實現四化燃燒著生命在做貢獻。

「最迷人的果然還是中等數學啊」,對我而言,我當然對學科競賽有著特別的感情。對於我這樣的問題學生,按部就班的好好學習文化課似乎無法調動我的興趣,且不說家裡一書櫃的各類學科競賽的題集,小升初、初升高、以及大學也都是一路,最後都是靠著那一點微薄的競賽加分,最後得以逃出生天的。吃水不忘挖井人,而這一切的源頭,就是 NOIP。

這裡說一則佚文,事實上我的那個決定我一生命運的 NOIP 1= 的獎狀,似乎被我撕成了碎片(雖然後來我媽又拿膠水粘起來了)。原因是,那一年高一的暑假,鄭州辦 NOIP 培訓班,我想去參加,但是報名費要 6000 塊,然後我媽就不想讓我去參加(事實上原因應該不僅僅是 6000¥,還有擔心影響我文化課,以及一個人出遠門不放心等。。。),事實上不僅沒有讓我去參加,還在市內帶我去科大找可以輔導我的老師,(當然是不存在啦),總之原本抱著巨大期待的我,感覺被我媽玩弄了幾天,一氣之下,把我貼在牆上的從小學到高中的獎狀全部撕了。

當然後來要感謝網購,感謝噹噹,至少我還可以有辦法自學。。。但是無論如何,學習效率一定是差很多的,主要是中間如果卡住了,沒人指點可能就跳不出來了。

當然我這裡不是要鼓吹教育平權什麼的,我只是認為,NOIP 聯賽作為信息學奧賽里最普及最基礎的部分,不應該被過多的無關因素牽連,她應該是公益的,純粹的,無差別的。

Google Code Jam 2019 World Finals

Google Code Jam 2019 World Finals

今年的 Code Jam 結束了,一不留神 Tourist 又^6 奪冠了。。。
先來看一下 Final 的題目吧。

Board Meeting

Brief Description

交互題。給定一個無限大的棋盤,上面擺放了至多 n 個國王。準備階段,你可以進行詢問至多 r 次,每次詢問一個坐標,系統返回所有國王距離這個坐標的距離和。之後,詢問階段角色互換,系統會向你詢問至多 r 次,每次詢問一個坐標,你需要返回所有國王距離這個坐標的距離和。

(每個國王的坐標絕對值不超過 m,詢問的坐標絕對值不超過 10m)
(n <= 10, m = 1e6,r = 1000)
(小數據中,n = 1)

Idea

先考慮一個點的情況?回憶航海里的三角測量以及 GPS 里的三點定位?
對於大數據,有辦法可以得到每個點的坐標嗎?需要得到每個點坐標嗎?

Sorting Permutation Unit

Brief Description

你需要將 k 段長度為 n 的數組按照非遞減順序排序。排序的方法是使用你自己構造的置換。你可以至多構造 p 組置換,每次排序可以使用這些置換不超過 s 次。

(k <= 30, n <= 50, s = 450)
(Small: p = 20)
(Large: p = 5)

Won’t Sum

Juggle Stuggle Part

Brief Description

平面內給出 n 條線段,稱這組線段是相融的,如果他們兩兩相交。
– Part 1: 給定 2n 個點,構造一組相融的連線方式,數據保證一定有解。
– Part 2: 給定 n 條線段,判斷它們是否相融。

Idea

Go To Considered Helpful

Brief Description

給定一個 r*c 的迷宮,要求構造一個長度最短的帶 Goto 的指令序列,可以從起點走到終點。

(Small: r,c <= 10)
(Large: r,c <= 100)