I haven't programming for years, so I decided to refresh it today. At least, this is the key point of CS&T, right?
    This problem is quite easy. It is easy to see that 2739 belongs to Number Theory. And key point lies on "consecutive"(If not, it'll be much harder:|). Since it requires that, and we only need to use the primes in [2,10000], it is easy to see that we can solve this in the following steps:
    1.Get all primes in [2,10000];
    2.Reset the counter to 0. Then, start from 2 and calculate the sums, namely, 2, 2+3, 2+3+5, ..., until the sum is great than 10000; for those who are less than that, increase the counter of that sum, correspondingly, 2,5,10,......
    3.For each input between 2 and 10000, output the precalculated sum.
Source code as followed:

Recover My files is a very good software. Easy 2 use and can recover the deleted and unindexed files.

      空域?yàn)V波技術(shù)根據(jù)功能主要分為平滑濾波與銳化濾波，平滑濾波能減弱或消除圖像中的高頻率分量而不影響低頻分量。因?yàn)楦哳l分量對應(yīng)圖像中的區(qū)域邊緣等灰度值 具有較大變化的部分，平滑濾波可將這些分量濾去減少局部灰度起伏，是圖像變得比較平滑。實(shí)際應(yīng)用中，平滑濾波還可用于消除噪聲，或在提取較大目標(biāo)前去除太 小的細(xì)節(jié)或?qū)⒛繕?biāo)的小間斷連接起來。銳化濾波正好相反，實(shí)際應(yīng)用中銳化濾波常用于增強(qiáng)被模糊的細(xì)節(jié)或目標(biāo)的邊緣。

      空域?yàn)V波是在圖像空間通過鄰域操作完成的，實(shí)現(xiàn)的方式基本都是利用模板（窗）進(jìn)行卷積來進(jìn)行，實(shí)現(xiàn)的基本步驟為：

      1、將模板中心與圖中某個(gè)像素位置重合；

      2、將模板的各個(gè)系數(shù)與模板下各對應(yīng)像素的灰度值相乘；

      3、將所有乘積相加，再除以模板的系數(shù)個(gè)數(shù)；

      4、將上述運(yùn)算結(jié)果賦給圖中對應(yīng)模板中心位置的像素。

    

      常見的空域?yàn)V波器：

      1、鄰域平均：將一個(gè)像素鄰域平均值作為濾波結(jié)果，此時(shí)濾波器模板的所有系數(shù)都取為1。

      2、加權(quán)平均：對同一尺寸的模板，可對不同位置的系數(shù)采用不同的數(shù)值。實(shí)際應(yīng)用中，常取模板周邊最小的系數(shù)為1，而取內(nèi)部的系數(shù)成比例增加，中心系數(shù)最 大。

           加權(quán)平均模板示例：

                                                1     2     1

                                                2     4     2

                                                1     2     1

      3、高斯分布：借助楊輝三角對高斯函數(shù)進(jìn)行近似。

           高斯模板系數(shù)：

                                                    1

                                                 1    1

                                              1    2    1    

                                           1    3    3    1

                                        1    4    6    4    1

                                     1    5    10  10    5    1 

      4、中值濾波：中值濾波是一種非線性濾波方式，可用如下步驟完成。

          （1）將模板在圖中漫游，并將模板中心與圖中某個(gè)像素位置重合；

          （2）讀取模板下各對應(yīng)像素的灰度值；

          （3）將這些灰度值從小到大進(jìn)行排序；

          （4）找出中間值并賦給對應(yīng)模板中心位置的像素。

          一般情況下中值濾波的效果要比鄰域平均處理的低通濾波效果好，主要特點(diǎn)是濾波后圖像中的輪廓比較清晰。

      5、最頻值濾波：通過直方圖統(tǒng)計(jì)中心像素點(diǎn)的灰度分布情況，將出現(xiàn)次數(shù)最多的灰度值（即直方圖波峰位置）賦給中心位置的像素。如果直方圖是對稱的且僅有一 個(gè)峰，那么均值、中值和最頻值相同。如果直方圖僅有一個(gè)波峰但不對稱，那么最頻值對應(yīng)波峰，而中值總比均值更接近最頻值。

      6、銳化濾波：圖像銳化一般是通過微分運(yùn)算來實(shí)現(xiàn)的，圖像處理中最常用的微分方法是利用梯度（基于一階微分）。在離散空間，微分用差分實(shí)現(xiàn)，常用的差分模板如下：

                            -1        1                           1   1   1

                            -1        1                          

                            -1        1                          -1  -1 -1

一道簡單的動態(tài)規(guī)劃，可以先寫出遞歸方程（注意到每一總票值都是由比它小的票值產(chǎn)生的），然后通過其求解。

---

用F[i]表示得到i面值所需要的最少郵票個(gè)數(shù)，Value[j](j=1..Stamps)表示每個(gè)郵票的面值，可得以下轉(zhuǎn)移方程：

F[i]=Min ( F[i-Value[j]] + 1 ) (i-Value[j]>=0 j=1..Stamps)
初始狀態(tài)：F[0]=0;F[i]=INFINITE;

題目中Substitution method的意思是如下：
Substitutes for all letters must be different. For some letters substitute letter may coincide with the original letter.
相當(dāng)于一個(gè)映射，而不能片面的理解成移位的意思。前面就是因?yàn)檫@個(gè)wa的……

注意讀題，不要被水題水了。

while (getline(cin,s)) {
    // TO DO PROGRAM HERE
}

Poj 1597 – Uniform Generator

 

題目的意思就是一個(gè)生成隨機(jī)數(shù)的函數(shù)，

     Seed[x+1] = （ seed[x] + STEP ） % MOD

其中seed就是我們生成出來的隨機(jī)數(shù)，至于seed[0]是哪個(gè)數(shù)并不重要，后面會證明。STEP就是我們每次往前一個(gè)所加的值，再module上MOD得到下一個(gè)隨機(jī)數(shù)。

 

判斷這個(gè)隨機(jī)生成函數(shù)的好壞的依據(jù)是如果能夠產(chǎn)生0~MOD-1內(nèi)的所有數(shù)，就是一個(gè)好的，否則壞。

 

我們知道了同余的特性，便可以假設(shè)在k步之后，生成的seed[k] = seed[0]，所以由此有

        Seed[k] = （ seed[0] + STEP*k ） % MOD

那么，

        STEP * k = MOD

 

而我們?nèi)绻a(chǎn)MOD個(gè)數(shù)，必須使k≥MOD，而且k不可能大于MOD，因?yàn)檫@個(gè)條件下生成的數(shù)又開始重復(fù)，所以k=MOD；在前面的條件下，如果STEP和MOD有大于1的公約數(shù)例如d，那么會有STEP*(k/d) = MOD，這就是一個(gè)循環(huán)了，只會產(chǎn)生k/d<MOD個(gè)隨機(jī)數(shù)。

結(jié)論：iff gcd(STEP, MOD) == 1, good choice.

Poj 3370 Halloween treats

這道題在集訓(xùn)手冊上標(biāo)志是“抽屜原理”，老實(shí)說，在看到這道題的具體解法之前，我還不知道為什么是抽屜原理，這明明是判斷一些數(shù)的同余嘛，后來才發(fā)現(xiàn)鴿籠原理的巧妙之處。

 

4 5

1 2 3 7 5

 

例如對于第一組數(shù)據(jù)，

1 2 3 7 5模上4分別是：

1 2 3 3 1

如果采用同余+dp的方法，難度會相當(dāng)大，規(guī)則比較復(fù)雜；

 

這時(shí)，我們采用一種巧妙地方法，就是用一個(gè)sum[i]數(shù)組來記錄前i個(gè)數(shù)之和%4，例如上例中，我們得到：

I	0(該列隱含)	1	2	3	4	5
Sweet[i]	0	1	2	3	7	5
Sum[i]	0	1	3	2	1	2

 

由此，我們在碰到1.sum[i] == 0 或者2.sum[i]的值已經(jīng)在前面出現(xiàn)過的情況時(shí)，就可以知道有解，并且解是從上一個(gè)出現(xiàn)該sum[i]數(shù)值的后一個(gè)位置開始→現(xiàn)在sum[i]的位置，這個(gè)貌似可以解出可能的解；但由于加和的順序隨機(jī)，所以還不清楚是否可以在該case有解的情況下一定能夠解出解。這時(shí)候，我們就要用到鴿籠原理了。

 

運(yùn)用《離散數(shù)學(xué)與組合數(shù)學(xué)》書中的方法，我們可以把sum[1~n=nneighbor](或0~n)看做n+1只鴿子（注意上面的隱含0列），飛入c=nchild個(gè)鴿籠中，再注意到題目中有這樣的數(shù)據(jù)范圍：

The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000) （這是本題能用鴿籠原理的最重要的前提）

由此我們可以知道一定有兩只鴿子是飛入同一個(gè)籠子當(dāng)中的，所以加法的順序就自然不用考慮了；而且由這個(gè)我們也可以知道，此題一定不存在無解的情況。

代碼就不貼了，數(shù)學(xué)題還是要自己想才好

 

讀題讀得有點(diǎn)累，不過最后還是看懂了。意思就是給定一組數(shù)據(jù)按順序插入，每次在u個(gè)元素的時(shí)候

（本例中（后略）是1，2，6，6），
找到第i小的數(shù)，i= 1，2，3，4...，correspondly，相對應(yīng)的。

開始用線性表做，TLE了，沒注意到查詢是線性的……
后來看了參考了別人的solutions，發(fā)現(xiàn)了stl中的一個(gè)好東東，priority_queue

priority_queue的功能和用法可以看下 C++ STL

至于解題報(bào)告嘛，由于我也是參考別人寫的代碼，所以就不東施效顰了，貼一下：
http://www.stubc.com/thread-3511-1-2.html(這篇分析選用哪個(gè)數(shù)據(jù)結(jié)構(gòu)思路比較好)
http://hi.baidu.com/leisimeng/blog/item/2a307e6110f394d78db10d02.html

P.S. 在代碼中間加了一些注釋，希望會有一些幫助。

設(shè)2^n為x, 設(shè)x為10^y次方級的數(shù)（用科學(xué)計(jì)數(shù)法表示的后綴），要求的首位為f

那么
             lg(x/10^y) = lg(f)         lg是底為10的對數(shù)
上式可以變?yōu)?nbsp; lg(x) - y = lg(f)
       ==>  n*lg(2) - y = lg(f)

現(xiàn)在，只用求y即可，
其實(shí)， (int) y = lg(x) = lg(2^n) = n*lg(2),
看起來不是跟上一個(gè)相等嗎？但是注意y展開后是100000...的形式，所以我們在求出了它的對數(shù)之后，只取它的整數(shù)部分即可，即y是int型，所以……后面的不用推了，把f外面的對數(shù)符號拿過去就是了。

最后得到：
            f = 10^(n*lg(2)- (int)(n*lg(2)))

同樣的，如果要求3、4、5...的n次方，只需要把2改為它們即可


P.S. 不過此算法在算2的3次方時(shí)會有誤差，還不清楚為什么？（準(zhǔn)確地說，在冪n小的時(shí)候都有誤差）想請教一下各位大牛，謝謝啦~

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int n;
    while (scanf("%d", &n) && n!=-1) {
        int y = (int) (n * log10(2.0));
        double t = n * log10(2.0);
        int ans = (int) (pow(10.0, t-(double)y) + 1e-8);
        //n == 2 答案有誤差，在加上1e-8后，誤差消除
        printf("%d\n", ans);
    }
    return 0;
}