以及注意事項
ST Table
C++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
| #include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
const int maxn = 100010;
int stmin[maxn][20],stmax[maxn][20];
int n,a[maxn],ans;
void st()
{
for(int j=1; (1<<j)<=n; j++)
{
for(int i=1; i+(1<<j)-1<=n; i++)
{
stmin[i][j] = min(stmin[i][j-1], stmin[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l, int r)
{
int x = (int)log2(r-l+1);
return min(stmin[l][x], stmin[r-(1<<x)+1][x]);
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++) stmin[i][0] = stmax[i][0] = a[i];
st();
int l,r;
cin >> l >> r;
cout << query(l,r);
return 0;
}
|
Batch Process
也就是對拍。
Batch1
2
3
4
5
6
7
| :loop ::循环
makedata.exe ::生成数据
std.exe ::较优程序
baoli.exe ::暴力程序
fc std.out baoli.out ::比较两个输出文件
if %errorlevel% == 1 pause ::如果不同则暂停
goto loop ::继续循环
|
Linear Prime Sieving
C++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
| #include <stdio.h>
#include <iostream>
using namespace std;
int prime[10000005],len;
int a[10000005];
void Sieve_Primes(int R)
{
a[0] = a[1] = 1;
for(int i=2;i<=R;i++)
{
if(a[i] == 0) prime[++len] = i;
for(int j=1;j<=len && i*prime[j]<=R;j++)
{
a[i*prime[j]] = 1;
if(i%prime[j] == 0) break;
}
}
}
int main()
{
int n,m;
cin >> n >> m;
Sieve_Primes(n);
for(int i=1;i<=m;i++)
{
int num;
cin >> num;
if(a[num] == 1) cout << "No" << endl;
else cout << "Yes" << endl;
}
return 0;
}
|
SA (Simulated Annealing)
Intro
模擬退火1是一種隨機化算法。當一個問題的方案數量極大（甚至是無窮的）而且不是一個單峰函數時，我們常使用模擬退火求解。
Implement
根據爬山算法2的過程，我們發現：對於一個當前最優解附近的非最優解，爬山算法直接捨去了這個解。而很多情況下，我們需要去接受這個非最優解從而跳出這個局部最優解，即為模擬退火算法。
什麼是退火？
退火是一種金屬熱處理工藝，指的是將金屬緩慢加熱到一定溫度，保持足夠時間，然後以適宜速度冷卻。目的是降低硬度，改善切削加工性；消除殘餘應力，穩定尺寸，減少變形與裂紋傾向；細化晶粒，調整組織，消除組織缺陷。準確的說，退火是一種對材料的熱處理工藝，包括金屬材料、非金屬材料。而且新材料的退火目的也與傳統金屬退火存在異同。
由於退火的規律引入了更多隨機因素，那麼我們得到最優解的概率會大大增加。於是我們可以去模擬這個過程，將目標函數作為能量函數。
Description
先用一句話概括：如果新狀態的解更優則修改答案，否則以一定概率接受新狀態。
我們定義當前溫度為T，新狀態與已知狀態（由已知狀態通過隨機的方式得到）之間的能量（值）差為ΔE（E>=0），則發生狀態轉移（修改最優解）的概率為
1
| P(ΔE) = 1 if 新狀態更優 else exp(-(ΔE) / T)
|
- 注意：我們有時為了使得到的解更有質量，會在模擬退火結束後，以當前溫度在得到的解附近多次隨機狀態，嘗試得到更優的解（其過程與模擬退火相似）。
Annealing
如何退火（降溫）？
模擬退火時我們有三個參數：初始溫度T_0，降溫係數d，終止溫度T_k。其中T_0是一個比較大的數，d是一個非常接近1但是小於1的數，T_k是一個接近0的正數。
首先讓溫度T = T_0，然後按照上述步驟進行一次轉移嘗試，再讓T = d·T。當T < T_k時模擬退火過程結束，當前最優解即為最終的最優解。
注意為了使得解更為精確，我們通常不直接取當前解作為答案，而是在退火過程中維護遇到的所有解的最優值。
引用一張 Wiki - Simulated annealing 的圖片（隨著溫度的降低，跳躍越來越不隨機，最優解也越來越穩定）。
Example
C++Luogu P13371
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
| #include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
const int N = 10005;
int n, x[N], y[N], w[N];
double ansx, ansy, dis;
double Rand() { return (double)rand() / RAND_MAX; }
double calc(double xx, double yy) {
double res = 0;
for (int i = 1; i <= n; ++i) {
double dx = x[i] - xx, dy = y[i] - yy;
res += sqrt(dx * dx + dy * dy) * w[i];
}
if (res < dis) dis = res, ansx = xx, ansy = yy;
return res;
}
void simulateAnneal() {
double t = 100000;
double nowx = ansx, nowy = ansy;
while (t > 0.001) {
double nxtx = nowx + t * (Rand() * 2 - 1);
double nxty = nowy + t * (Rand() * 2 - 1);
double delta = calc(nxtx, nxty) - calc(nowx, nowy);
if (exp(-delta / t) > Rand()) nowx = nxtx, nowy = nxty;
t *= 0.97;
}
for (int i = 1; i <= 1000; ++i) {
double nxtx = ansx + t * (Rand() * 2 - 1);
double nxty = ansy + t * (Rand() * 2 - 1);
calc(nxtx, nxty);
}
}
int main() {
srand(time(0));
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &x[i], &y[i], &w[i]);
ansx += x[i], ansy += y[i];
}
ansx /= n, ansy /= n, dis = calc(ansx, ansy);
simulateAnneal();
printf("%.3lf %.3lf\n", ansx, ansy);
return 0;
}
|
Monotonous Queue
參見OI-Wiki相關章節3。
Attentions
以下是注意事項噠！
负数取模 ! ! !
多组数据赋初值
变量名 ! ! !
正难则反 ! ! !
数组越界 ! ! ! !
无向图双倍maxn
要有梦想 ! ! ! ! ! !
NOIP2018.RP++
References
1. OI-Wiki 章節 模擬退火 ↩
2. OI-Wiki 章節 爬山算法 ↩
3. OI-Wiki 章節 單調隊列 ↩