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:
#include <cmath>
using namespace std;
const int MAXN = 10000;
bool f[MAXN+10];
int np;
int p[MAXN+10];
int sum[MAXN+10];
void findPrime() {
memset(f, 1, sizeof(f));
f[0] = 0; f[1] = 0;//doesn't matter anyway
int tmp = abs(sqrt(MAXN*1.0));
for (int i = 2; i <= tmp; i++) {
if (f[i]) {
for (int j = i+i; j <= MAXN; j+=i)
f[j] = 0; //false
}
}
int ctr = 0;
for (int i = 2; i <= MAXN; i++)
if (f[i]) {
p[ctr++] = i;
}
np = ctr;
}
void geneSum() {
memset(sum, 0, sizeof(sum));
for (int i = 0; i < np; i++) {
int tsum = 0;
for (int j = i; j < np; j++) {
tsum += p[j];
if (tsum > MAXN) break;
sum[tsum]++;
}
}
}
void initi() {
findPrime();
geneSum();
}
int main() {
initi();
int n;
while (1) {
scanf("%d", &n);
if (n == 0) break;
printf("%d\n", sum[n]);
}
return 0;
}
空域?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
用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;
相當(dāng)于一個(gè)映射，而不能片面的理解成移位的意思。前面就是因?yàn)檫@個(gè)wa的……
注意讀題，不要被水題水了。
}
Poj 1597 – Uniform Generator
題目的意思就是一個(gè)生成隨機(jī)數(shù)的函數(shù)，
Seed[x+1] = （ seed[x] + STEP ） % MOD
其中seed就是我們生成出來的隨機(jī)數(shù)，至于seed[0]是哪個(gè)數(shù)并不重要，后面會(huì)證明。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，那么會(huì)有STEP*(k/d) = MOD，這就是一個(gè)循環(huán)了，只會(huì)產(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的方法，難度會(huì)相當(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é)題還是要自己想才好（本例中（后略）是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. 在代碼中間加了一些注釋，希望會(huì)有一些幫助。
2 #include <queue>
3 #include <algorithm>
4 using namespace std;
5
6 int M, N;
7 int a[30010], u[30010];
8
9 int main() {
10 #ifdef _DEBUG
11 freopen("in.txt", "r", stdin);
12 freopen("out.txt", "w", stdout);
13 #endif
14 int i, j, value;
15 while (scanf("%d %d", &M, &N) != EOF) {
16 // 左邊大根堆，右邊小根堆
17 // 這樣，當(dāng)我們把它們看作一體時(shí)，可以保證它的有序性
18 priority_queue< int, vector<int>, less<int> > hmax;
19 priority_queue< int, vector<int>, greater<int> > hmin;
20
21 for (i = 0; i < M; i++)
22 scanf("%d", &a[i]);
23
24 u[0] = 0;
25 for (i = 1; i <= N; i++)
26 scanf("%d", &u[i]);
27
28 for (i = 1; i <= N; i++) {
29
30 // inserting a+ 0 to 1, 1 to 2, 2 to 6, 6 to 6 according to i
31 for (j = u[i-1]; j < u[i]; j++) {
32 hmax.push(a[j]);
33 /* we want to get the i-th smallest number, so when
34 * we reach i(in the big-root heap), the excessive(for
35 * ive(for now) must be in the small-root heap so that
36 * we could sort it and might use it later
37 */
38 if (hmax.size() > i-1) {
39 value = hmax.top();
40 hmax.pop();
41 hmin.push(value);
42 }
43 }
44 // after the loop, the answer is the root of the small-r heap
45 value = hmin.top();
46 hmin.pop();
47 hmax.push(value);
48 printf("%d\n", hmax.top());
49 }
50 }
51 }
52
那么
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í)會(huì)有誤差，還不清楚為什么？（準(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;
}