解題區/出題解題

[ACM 題目] 河道分界

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

sample

Solution

1
Read More +
解題區/出題解題

[ACM 題目] 樹形鎖頭

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
Read More +
解題區/出題解題

Scarky 您的博客線上檢測系統

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

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

matrix67 的說明
Scarky 網址點我

創建題目

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

使用心得

  • 正如上方的題目，編輯頁面要打 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
  • 文章顯示
    theme/layout/_partial/post/article.ejs
    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>
Read More +