Description

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』

Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
5
1 1
5 2
3 0
0 4
4 8

Sample Output

1
2
3
4
5

1
3
1
4
12

More

名為 “學姊”。

Solution

1

Description

Background

正陷入暗戀的蘿莉控，對象正是那小海女 “能年犬”，為了與其相遇，做了一個情報偵測器，但總不能刻意繞道去相遇，這顯然會相當接近跟蹤狂。根據情報網顯示，地圖將會長得跟樹狀圖一樣，接著會有一連串的消息顯示小海女疑似出現的地方，同時也會被驗證是假消息。

蘿莉控只想知道如果從 x 點回到家的路上，有沒有機會遇到小海女。如果事先知道將會在哪個場所相遇，就能事先準備。接下來就請你協助他了！

Problem

給定一棵樹，樹根編號 0，每個點一開始的權重為 0，操作有以下兩種。

操作 M x : 將節點 x 的權重從 0->1 或者 1->0。
操作 S x : 輸出從 x 到 root 路徑上，第一個權重為 1 的節點編號。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
10
M 1
S 8
S 4
M 0
M 7
M 9
S 5
M 3
M 8
S 5
31
0 1
0 2
0 3
1 4
1 5
2 6 
2 7
3 8
4 9
4 10
4 11
6 12
6 13
12 14
12 15
13 16
13 17
14 18
14 19
14 20
17 21
17 22
20 23
21 24
21 25
22 26
22 27
23 28
24 29
24 30
10
M 6
S 29
S 9
M 0
S 9
S 6
S 2
M 6
S 29
S 6

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12

1
-1
1
3
6
-1
0
6
0
0
0

Solution

1

Problem

某 M 現在正在平面座標上的原點 (0, 0)，現在四周被擺放了很多很多鏡子，某 M 可以藉由鏡子與他的人格小夥伴對話，請問那些鏡子可以見到小夥伴。

鏡子可以當作一個線段，之間不會交任何一點，只要能見到該鏡子中一小段區域就算可見到。

備註：不考慮反射看到。

Input

輸入有多組測資。

每組測資第一行將會有一個整數 n (n < 32767)，表示總共有多少個鏡子。
接著會有 n 行，每一行上會有 4 個整數 sx, sy, ex, ey，表示鏡子所在的線段。

(-32767 < sx, sy, ex, ey < 32767)

Output

對於每組測資輸出一行，每一行將會有 n 個整數 (0/1)，分別表示輸入中第 i 個鏡子是否可見到。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1
5 -5 5 5
4
4 2 5 -2
2 4 6 1
5 5 8 1
3 -4 7 -1
7
-1 2 3 1
2 4 5 -1
-3 -1 1 -2
-1 -4 3 -2
-2 -4 1 -5
-4 1 -1 4
-3 4 -4 3
1
1 1 2 2
2
-1 3 -2 -2
-2 -1 -3 -1

Sample Output

1
2
3
4
5

1
1 1 0 1
1 1 1 1 0 1 0
0
1 0

More

Solution

1

Problem

M 國開始藉由河道進行分裂，M 國土只會介於 y = 0 和 y = 1 之間，在 x 軸兩側無限延伸，保證河道彼此不會相交任何一點。

操作 A u v : 增加河道 (u, 1) 到 (v, 0)，該河道編號為當前操作 A 的數量。

操作 Q x y : 詢問位置 (x, y) 在哪兩個河道之間。

Input

第一行將會有一個整數 N (N < 100, 000)，表示接下來會有幾筆操作。

操作 A u v : u, v [-50000, 50000] 之間的實數。

操作 Q x y : x 屬於 [-50000, 50000], y 屬於 [0, 1]。

Output

對於每個詢問，輸出在哪兩個河道之間，邊界為 [S, M]，如果恰好在河道上輸出 [?, ?]，詳細請參考範例輸出。

Sample Input

1
2
3
4
5
6
7
8
9

8
A 0 0
Q -1 0
Q 1 0
Q 0 0
A 1 2
Q 1 0.5
Q 3 0.5
Q 1.5 0.5

Sample Output

1
2
3
4
5
6

[S, 1]
[1, M]
[?, ?]
[1, 2]
[2, M]
[?, ?]

More

Solution

1

Problem

Background

正值大四的 Morris，面臨無法畢業的窘境，每天不是玩 PoE 遊戲就是在解題目，為了逃避現實解題目也越來越多，但對於未來目標仍然沒有任何進展，一個人在房間裡孤拎拎地打著 PoE，萬萬沒想到遊戲帳號被盜取，「密碼鎖什麼的果然太天真的，ACM 鎖才是未來的目標」打密碼登入有什麼了不起的，寫程式 AC 登入才有意思。

Problem

一張無向圖，給 N 個點、N - 1 條邊，任兩點之間只會有一條路徑。

操作 (u, v, k)：將 u, v 之間經過的節點權重加上 k。

請問經過 M 次操作後，每個節點的權重值為何？

Input

輸入有多組測資。

每一組測資第一行 會有兩個正整數 N, M (0 < N, M < 32767)，接下來會有 N - 1 行，每行上會有兩個整數 u, v (0 <= u, v < N) 表示 u 和 v 之間有一條邊。接著會有 M 行操作 (u, v, k) (0 < k < 32767)。

Output

每組測資輸出一行，分別將節點權重輸出。

Sample Input

1
2
3
4
5
6
7
8
9
10
11

7 4
0 1
0 2
1 3
1 4
2 5
2 6
2 3 1
3 4 2
0 5 4
6 6 8

Sample Output

1

5 3 5 3 2 4 8

Solution

1

Scarky 提供線上出程式題目的平台

出了一道好题目却不知道该怎样投递到各大OJ上？现在不用担心这个问题了，因为你可以直接把自己的Blog变成一个OJ。Scarky是一个建立在SPOJ系统上的OJ平台。所不同的是，任何人无需注册便可以编写自己的题目并发在自己的网站上与网友分享，并且网友们提交答案时也不需要进行注册。这个网站的功能还在不断扩充中，但目前就Programming Challenge模块看来，这个网站已经很强大了。以后我有了好题目就用这种方式和大家分享了，这里先试用一下，题目来源好像是某次USACO月赛。

matrix67 的說明
Scarky 網址點我

創建題目

• 點進網站，點選創建自己的題目，您將會看到下圖的訊息，記得要求它寄封題目鏈結到你的信箱。這些題目內容稍後還能修改。
  
• 在信封中，將會收到編輯頁面鏈結。
  
• 回到編輯頁面，將可以把輸入輸出測資放上去，最後按儲存訊息即可。
  基本上這裡都採用嚴格比對，也就是多空白多換行字符都是不行的。
  
• 編輯者還能看到目前的統計資料。為什麼身為管理者看不到別人上傳的代碼，這不科學。
  
• 放上博客有三種方式。
  

使用心得

• 正如上方的題目，編輯頁面要打 HTML，這點不科學也不方便。
• 頁面顯示上就是固定，大小無法更動。
• 題目生存期限有多久？曾經放著一年前的題目還在。
• HTML 打好放上去，編輯時從曾經打過的 <br/> 會消失。
• 最後附上簡單的測試。

    <strong>題目描述</strong><br/><br/>
        <p>
            請將 NFA 轉換成 DFA，不用進行最佳化。
        </p><br/>
    <strong>輸入描述</strong><br/><br/>
        <p>
            輸入只會有一筆 NFA 描述，輸入以 EOF(end-of-file) 為結尾。
            <br/><br/>
            略 ...
        </p><br/>
    <strong>輸出格式</strong><br/><br/>
        <p>
        輸出對於每一組 DFA，格式如下。<br/>
        輸出第一行為字母集 CDFA (按照字典順序輸出)。<br/>
        <br/>
        略 ...
        </p><br/>
    <strong>Example Input :</strong><br/>
        <pre>
        (l,a,b,2)
        (2,0)(3,0)(0,0)
        (0,0)(4,5)(0,0)
        (0,0)(0,0)(4,0)
        (0,0)(5,0)(5,0)
        (*,*)(*,*)(*,*)
        略 ...
        </pre>
    <strong>Example Output:</strong><br/>
        <pre>
        (a,b)
        (1,2)(*3,4,5)(0)
        (*3,4,5)(*5)(*4,5)
        (*5)(0)(0)
        (*4,5)(*5)(*5)
        略 ...
        </pre>
  

Hexo

• 文章格式

    title: Scarky 您的博客線上檢測系統
    date: 2014-04-17 19:35:27
    tags: [Scarky, ACM, Judge]
    categories: 出題解題
    scarky: PNFCQOY5
  

• 文章顯示

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

  <div id="main" class="<%= item.layout %>" itemscope itemprop="blogPost"> <article itemprop="articleBody"> <%- partial('header') %> <div class="article-content"> <%- partial('gallery') %> <% if( table&&(item.toc !== false) && theme.toc.article){ %> <div id="toc" class="toc-article"> <strong class="toc-title"><%= __('contents') %></strong> <%- toc(item.content) %> </div> <% } %> <% if(item.scarky) { %> <!-- scarky widget http://scarky.com/ --> <script type="text/javascript" src="http://scarky.com/widget/get/<%= item.scarky %>/"></script> <!-- end scarky widget --> <% } %> <%- item.content %> </div> <%- partial('footer') %> </article> <%- partial('pagination') %> <%- partial('comment') %> </div>