2014-04-18

解題區/解題區 - Zerojudge

a962. 新專輯

題目

內容：

給定正整數N，請求出(N除以1的餘數)+(N除以2的餘數)+(N除以3的餘數)+…+(N除以N的餘數)。

輸入說明：

輸入只有一個正整數N，其中1<=N<=1014。

輸出說明：

為了避免要寫大數，你只要輸出這個奇怪的和除以1000000009的餘數就好了。

範例輸入：

範例輸出：

解法

作法：
各種方式要避免 mod 運算。

a962.cpp

/**********************************************************************************/
/*  Problem: a962 "新專輯" from TIOJ 1674                                      */
/*  Language: CPP (1612 Bytes)                                                    */
/*  Result: AC(0.8s, 272KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 20:11:19                                     */
/**********************************************************************************/
#include <stdio.h>
#include <math.h>
#define MOD 1000000009LL
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra;
            lb -= n/m*rb;
        } else {
            ra -= n/m*la;
            rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    if(i)
        return (la%mod+mod)%mod;
    return (ra%mod+mod)%mod;
}
int main() {
    long long inv2 = inv(2, MOD);
    long long n;
    while(scanf("%lld", &n) == 1) {
        long long ret = 0, hret = 0;
        long long half = (long long)sqrt(n)/5;
        long long u = -1, v = 0;
        for(half = 1; u != v; half++, u = v, v = n/half) {
            hret += n%half;
        }
        hret -= n%(half - 1);
        hret %= MOD;
        long long l = half - 1, r, div;
        long long a0, d, tn, buff;
        while(l <= n) {
            div = n / l;
            r = n / div;
            a0 = n % l, d = -div, tn = r - l + 1;
            if(tn >= MOD)   tn %= MOD;
            if(d >= MOD)    d %= MOD;
            if(a0 >= MOD)   a0 %= MOD;
            buff = (a0 * 2 + (tn - 1)*d);
            if(buff < 0 || buff >= MOD) buff %= MOD;
            buff *= tn;
            if(buff < 0 || buff >= MOD) buff %= MOD;
            ret += buff;
            l = r + 1;
        }
        ret %= MOD;
        ret = (ret * inv2)%MOD;
        ret = (ret + hret + MOD)%MOD;
        printf("%lld\n", ret);
    }
    return 0;
}
/*
100000000000000
*/

a981. 求和問題

題目

內容：

給你N個正整數, 試求哪幾個之和剛好為M, 印出所有合條件的解, 如有多組解, 請按由小到大的順序印出(格式可參考樣例輸出)

輸入說明：

n m (1<=n<=30, 1<=m<=100000000) n個正整數, 全部以空格分開

輸出說明：

其和剛好等於m的數, 如果有多組解則按由小到大全部印出, 如果無解則印出 -1

範例輸入：

10 100
10 20 40 30 50 80 60 70 5 15

範例輸出：

5 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60

解法

作法：
分治，將輸入 n 個劃分成兩堆，分別窮舉所有可能，採用合併的方式去運算。

a981.cpp

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main() {
    int n, m;
    int A[35];
    while(scanf("%d %d", &n, &m) == 2) {
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        sort(A, A + n, greater<int>());
        int h1Cnt = n / 2, h2Cnt = n - h1Cnt;
        map<long long, vector<int> > h1, h2;
        for(int i = (1<<h1Cnt)-1; i >= 0; i--) {
            long long sum = 0;
            for(int j = 0; j < h1Cnt; j++) {
                if((i>>j)&1)	sum += A[j];
            }
            h1[sum].push_back(i);
        }
        for(int i = (1<<h2Cnt)-1; i >= 0; i--) {
            long long sum = 0;
            for(int j = 0; j < h2Cnt; j++) {
                if((i>>j)&1)	sum += A[j + h1Cnt];
            }
            h2[sum].push_back(i<<h1Cnt);
        }
        set<int> ret;
        for(map<long long, vector<int> >::iterator it = h1.begin();
            it != h1.end(); it++) {
            long long f = (long long)m - it->first;
            map<long long, vector<int> >::iterator jt = h2.find(f);
            if(jt != h2.end()) {
                for(vector<int>::iterator iv = it->second.begin();
                    iv != it->second.end(); iv++) {
                    for(vector<int>::iterator jv = jt->second.begin();
                        jv != jt->second.end(); jv++) {
                        ret.insert(*iv| *jv);
                    }
                }
            }
        }
        if(ret.size() == 0)
            puts("-1");
        for(set<int>::reverse_iterator it = ret.rbegin();
            it != ret.rend(); it++) {
            for(int i = n-1; i >= 0; i--) {
                if(((*it)>>i)&1) {
                    printf("%d ", A[i]);
                }
            }
            puts("");
        }
    }
    return 0;
}

Scarky 您的博客線上檢測系統

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

文章顯示

theme/layout/_partial/post/article.ejs

<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>