淺淺記錄一下自己在算法競(jìng)賽中的注意事項(xiàng)。
數(shù)據(jù)類(lèi)
注意看數(shù)大小，數(shù)學(xué)庫(kù)中的函數(shù)盡量加上 * 1.0，轉(zhuǎn)成double，防止整型溢出。，int型相乘如果可能溢出，乘 * 1LL。
數(shù)據(jù)范圍大于1e6，注意用快讀。
浮點(diǎn)數(shù)輸入輸出：
少用float
scanf("%lf", &d);
printf("%.f",d)
取模，注意取成負(fù)數(shù)的情況。
全int,但是數(shù)據(jù)太大，全轉(zhuǎn)long long。
#include <iostream>
using namespace std;
#define int lnog long
signed main() // 注意 int -> signed
{
}
行末無(wú)空格
cout<<data<<" \n"[i == n];
數(shù)據(jù)存儲(chǔ)盡量不要自定義struct或者class，善于使用pair，array等，防止需要重載什么的，導(dǎo)致代碼層面的錯(cuò)誤。
多組注意清空。
樹(shù)結(jié)構(gòu)注意單邊和雙邊。
STL
STL 常用算法_golitter.的博客-CSDN博客
熟悉stl的數(shù)據(jù)結(jié)構(gòu)，string, map, set,queue, stack, priority_queue, vector,array等。
熟悉stl的算法函數(shù)
lower_bound()
upper_bound()
find()
count()
substr()
*max_element()
sort()
unique()
在c++11中，max和min函數(shù)可以多個(gè)值。
max({v1,v2,v3,v4})
優(yōu)先隊(duì)列的重載
// 用priority_queue 自定義堆 http://www.cbww.cn/news/37826.shtml
// 要重載 < 操作符 ，注意兩個(gè)const才可以通過(guò)編譯
// 方法一 重載運(yùn)算符<
struct adt { // 小頂堆
int a;
bool operator<(const adt& rhs) const { // 優(yōu)先隊(duì)列的><與sort的><相反. ** 沒(méi)有const會(huì)報(bào)錯(cuò)
return a > rhs.a; // 這里 從大到小進(jìn)行排序，隊(duì)列從最右邊開(kāi)始，所以是小頂堆
}
};
// 方法二 使用lambda表達(dá)式
void test_priority_queue() {
auto cmp = [](int pre, int suf) { return pre > suf; }; // 小頂堆
priority_queue<int,vector<int>, decltype(cmp)> pq(cmp); // decltype 類(lèi)型說(shuō)明符
// 實(shí)現(xiàn)自定義PII堆結(jié)構(gòu)
auto pii_cmp = [](PII pre, PII suf) {return pre.vf < suf.vf; };
priority_queue<PII, vector<PII>, decltype(pii_cmp)> heap(pii_cmp);
}
<bitset> * 是由int型拼接的， e.g. 1000位bitset 操作時(shí)間復(fù)雜度 O( 1000 / (大于等于 32))
熟悉運(yùn)用pair<int,int>，vector
vector重新賦值
vector<int> ve;
ve.assign(N,3)
雜
整數(shù)取整，可以用(LL)(ceil(a / b))，也可以用a / b + (a % b == 0 ? 0 : 1)。也可以用(a + b - 1) / b（感覺(jué)這個(gè)更簡(jiǎn)便一些。
lambda表達(dá)式的使用：
- 自定義排序
sort(all(ve), [](int pre, int suf) {
return pre > suf; // 從大到小
});
// 等價(jià)于
sort(all(ve), greater<int>());
- 寫(xiě)函數(shù)
auto lam = [&](int a) -> int {
if(a > 0) return 1;
else if(a == 0) return 0;
else return -1;
}
注意lambde遞歸用法，c++11可以用
functional<void(int)> dfs = (int u) {};
c++14可以用
auto dfs = [&](auto &&dfs, int u) -> void {};
創(chuàng)建數(shù)組，個(gè)人常用vector
vector<vector<int>> f(n, vector<int> (n, 1));
算法代碼實(shí)現(xiàn)
個(gè)人算法模板整理：2022/Algorithm__Template at main · golitter/2022 (github.com)
不定項(xiàng)輸入
// 需要包含 <sstream>
stringstream put_str;
string str;
getline(cin, str);
put_str<<str;
int cnt = 0,p;
while(put_str>>p) cnt++;
二分答案
- 最大值最小
int l, r;
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
- 最小值最大
int l, r;
while(l < r) {
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
去重離散化
vector<int> a,id,last;
id = a;
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end()); // 去重
for(int i = 0; i < n; ++i) {
last[i] = lower_bound(id.begin(), id.end(), a[i]) - id.begin();
}
建圖
- 鏈?zhǔn)角跋蛐?/li>
// 鏈?zhǔn)角跋蛐?/span>
int h[N]; // 鏈表頭，初始為-1 memset(h, -1, sizeof(h));
int e[N]; // 鏈表內(nèi)容
int ne[N]; // 鏈表中指向下一個(gè)元素的指針
int w[N]; // 鏈表內(nèi)容的權(quán)重
bool vis[N];
int idx; //
// <u , -- c -- , v> ( u --- w --> v
void add(int u, int v, int c) {
e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx++;
}
- vector<pair<int,int>> 或者 vector<array<int,2>>
vector<vector<int>> g(n + 1); // 無(wú)權(quán)重w
vector<vector<pair<int,int>>> g(n + 1); // 有權(quán)重
時(shí)間復(fù)雜度
1e8大概1秒。
注意調(diào)和級(jí)數(shù)等反直覺(jué)時(shí)間復(fù)雜度。
注意根據(jù)給的數(shù)據(jù)范圍和特殊性猜解法。
刷題策略
30分鐘沒(méi)有思路就可以看題解了，不能沒(méi)有思路就看題解。
刷題 + 寫(xiě)題解 提高較快，便于復(fù)習(xí)（雖然不復(fù)習(xí)
每次模擬賽要有總結(jié)和反饋。
平時(shí)要注意找到自己模擬賽時(shí)的不好的狀態(tài)和好的狀態(tài)，進(jìn)行加強(qiáng)或減少。比如，我就是做題，想出來(lái)一點(diǎn)就去敲代碼，之后再想剩下的算法。其實(shí)這是很不對(duì)的，算法競(jìng)賽主要考察的算法而不是什么代碼，目前也在一直減少這個(gè)狀況發(fā)生。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-704442.html
就算自己AC了題，也不要忘了去看看大佬們的代碼，可能他們更加簡(jiǎn)潔，可以學(xué)學(xué)不同的思路等。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-704442.html
到了這里，關(guān)于算法競(jìng)賽個(gè)人注意事項(xiàng)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
