Math & DP & Data structure & Graph & Geometry & Game
目錄
- Head
- Math
- 快速冪
- 快速乘
- 除法取整
- 龜速乘
- 數論分塊
- 枚舉子集，超集
- 矩陣乘法
- 線性篩
- 線性篩2
- 埃式篩
- 區間篩
- 質因數分解
- 歐拉函數
- 約數
- 中國剩余定理
- 逆元
- 階 \(a ^ x \equiv 1 (\bmod p)\)
- 原根 \(a ^ x \equiv 1 (\bmod m)\) ，當最小的 \(x\) 是 \(\varphi(m)\) 的時候 \(a\) 是 \(m\) 的原根
- 指數方程1 \(a ^ x \equiv b (\bmod m)\) \(m\) 為質數
- 指數方程2 \(a ^ x \equiv b (\bmod m)\) \(m\) 不為質數
- 排列組合
- 莫比烏斯反演
- 杜教篩
- 大素數判斷 miller_rabin \(O(s \log_2 ^ 3 n)\)， \(n \leq 2 ^ {54}\)
- 勾股數的神奇性質
- DP
- Data structure
- Graph
- 計算幾何
- 大數
- 雜
- 過去犯錯
Head
快讀1
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
快讀2
int rd() {
char act = 0;
int f = 1, x = 0;
while (act = getchar(), act < '0' && act != '-')
;
if (act == '-') f = -1, act = getchar();
x = act - '0';
while (act = getchar(), act >= '0') x = x * 10 + act - '0';
return x * f;
}
快讀3
char nc() {
static char buf[1000000], *p = buf, *q = buf;
return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q)
? EOF
: *p++;
}
int rd() {
int res = 0;
char c = nc();
while (!isdigit(c)) c = nc();
while (isdigit(c)) res = res * 10 + c - '0', c = nc();
return res;
}
模板1
// AC one more times
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
void solve()
{
return;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int TC = 1;
cin >> TC;
for(int tc = 1; tc <= TC; tc++)
{
//cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
模板2
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
return 0;
}
模板3
// AC one more times
////////////////////////////////////////INCLUDE//////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
/////////////////////////////////////////DEFINE//////////////////////////////////////////
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define inf64 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long,long long> pll;
////////////////////////////////////////CONST////////////////////////////////////////////
const int inf = 0x3f3f3f3f;
const int maxn = 2e6 + 6;
///////////////////////////////////////FUNCTION//////////////////////////////////////////
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
inline __int128 read(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}
ll qmi(ll a,ll b,ll p){ ll ans=1%p;while(b){ if(b&1) {ans=ans*a%p;} a=a*a%p,b>>=1; } return ans; }
int dx[]={0, 0, -1, 1};
int dy[]={-1, 1, 0, 0};
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
void solve()
{
return;
}
int main()
{
std::ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int TC = 1;
cin >> TC;
for(int tc = 1; tc <= TC; tc++)
{
//cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Math
快速冪
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
快速乘
//乘法分配率快速乘，時間復雜度O(1)
ll mul(ll a,ll b, ll P){
ll L = a * (b >> 25ll) % P * (1ll << 25) % P;
ll R = a * (b & ((1ll << 25) - 1)) % P;
return (L + R) % P;
}
/*
我們要計算a*b mod p,設b = L+R
那么原式變為a*(L+R)mod p = ((a*L)mod p+(a*R)mod p)mod p
我們定L為b的二進制前x位，R為b的后(64-x)位
這樣得到的代碼(以上代碼x = 25),復雜度近似為O(1).
*/
除法取整
ll floordiv(ll a, ll b)
{
//因為當其是負數時候，c++默認往0取整，所以下取整我們要自己寫
if(a % b == 0) return a / b;
else if(a > 0) return a / b;
else return a / b - 1;
}
ll ceildiv(ll a, ll b)
{
if(a % b == 0) return a / b;
else if(a > 0) return a / b + 1;
else return a / b;
}
龜速乘
ll a,b,p;
ll qmimul(ll a, ll b, ll p)
{
ll ans=0;
a %= p;
for(; b; b >>= 1)
{
if(b & 1)
ans += a, ans %= p;
a += a, a %= p;
}
return ans;
}
void solve()
{
cin>>a>>b>>p; cout<<qmimul(a,b,p)<<endl;
}
數論分塊
void solve()
{
ll n, ans = 0; cin>>n;
for(ll l = 1; l <= n; l++)
{
ll d = n / l, r = n / d;
// ans + ...
l = r;
}
return;
}
枚舉子集，超集
void solve()
{
int n; cin>>n;
// 枚舉子集
for(int i = 1; i < (1 << n); i++)
for(int j = i; j; j = (j - 1) & i)
{
}
// 枚舉超集
for(int i = 0; i < (1 << n); i++)
for(int j = i; ; j = (j + 1) | i)
{
if(j == (1 << n) - 1)
break;
}
}
矩陣乘法
const int mod = 1e9+7;
const int N = 200;
int n, m;
long long a[N + 1][N + 1], f[N + 1];
void aa()
{
long long w[N + 1][N + 1];
memset(w, 0, sizeof w);
for(int i = 1; i <= N; i++)
for(int k = 1; k <= N; k++)
if(a[i][k])
for(int j = 1; j <= N; j++)
if(a[k][j])
w[i][j] += a[i][k] * a[k][j], w[i][j] %= mod;
memcpy(a, w, sizeof a);
}
void fa()
{
long long w[N + 1];
memset(w, 0, sizeof w);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
w[i] += f[j] * a[j][i], w[i] %= mod;
memcpy(f, w, sizeof f);
}
void matrixpow(long long k)
{
for(; k; k /= 2)
{
if(k & 1)
fa();
aa();
}
}
void solve()
{
cin>>n>>m;
ll k; cin>>k;
// construct Martix
matrixpow(k);
cout<<f[ ]<<endl;
return;
}
線性篩
int tot, p[N], pr[N];
void prime(int n)
{
for (int i = 2; i <= n; i++)
{
if (!p[i]) p[i] = i, pr[++tot] = i;
for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
p[pr[j] * i] = pr[j];
if(p[i] == pr[j]) break;
}
}
}
線性篩2
const int N =1000010;
bool is_pri[N];
int pri[N];
int cnt;
void init(int n)
{
memset(is_pri, true, sizeof(is_pri));
is_pri[1] = false;
cnt = 0;
for (int i = 2; i <= n; i++)
{
if (is_pri[i])
pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
{
is_pri[i * pri[j]] = false;
if (i % pri[j] == 0)break;
}
}
}
埃式篩
int tot, p[N], pr[N];
void prime(int n)
{
for(int i = 2; i <= n; i++)
{
if(p[i]) continue;
pr[++tot] = i;
for(int j = i; j <= n / i; j++) p[i * j] = 1;
}
}
區間篩
int tot, p[N], pr[N];
bool vis[N];
void prime(int n)
{
for (int i = 2; i <= n; i++)
{
if (!p[i]) p[i] = i, pr[++tot] = i;
for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
p[pr[j] * i] = pr[j];
if(p[i] == pr[j]) break;
}
}
}
void solve()
{
int l, r; cin>>l>>r;
prime(sqrt((1ll << 31)) + 10);
for(int i = 1; i <= tot; i++)
{
int p = pr[i];
for(int x = r / p * p; x >= l; x -= p)
if(x != p)
vis[x - l] = true;
}
int res = 0;
for(ll x = l; x <= r; x++)
if(!vis[x - l])
res++;
if(l == 1) res--;
cout<<res<<'\n';
return;
}
質因數分解
ll a[N],cnt;
void primer(ll x)
{
for (ll i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
int s = 0;
a[++cnt] = i;
while (x % i == 0)
{
x = x / i;
s++;
}
}
}
if (x > 1) a[++cnt] = x;
}
歐拉函數
ll phi(ll n)
{
ll phin = n;
for(ll i = 2; i <= n / i; i++)
{
if(n % i == 0)
{
phin = phin / i * (i - 1);
while(n % i == 0)
n /= i;
}
}
if(n != 1)
phin = phin / n * (n - 1);
return phin;
}
約數
最大公約數
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
求約數
vector<int> get_yueshu(int x)
{
vector<int> a;
for (int i = 1; i <= x / i; i++)
{
if (x % i == 0)
{
a.push_back(i);
if (i != x / i)
a.push_back(x / i);
}
}
sort(a.begin(), a.end());
return a;
}
擴展歐幾里得1
\(ax - by = \gcd(a, b)\) 的最小非負整數解 \((x,y)\)
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
int _;cin>>_;
while(_--)
{
int a, b, x, y;
cin>>a>>b;
int d = exgcd(a, b, x, y);
y = -y;
while(x < 0 || y < 0) x += b / d, y += a / d;
while(x >= b / d && y >= a / d) x -= b / d, y -= a / d;
cout<<x<<" "<<y<<endl;
}
}
擴展歐幾里得2
\(ax + by = d\) 的 \(x\) 最小的解的非負整數解 \((x,y)\)
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
int _;cin>>_;
while(_--)
{
ll a, b, x, y, m;
scanf("%lld%lld%lld", &a, &b, &m);
ll d = exgcd(a, b, x, y);
if(m % d != 0)
{
puts("-1");
continue;
}
a /= d;
b /= d;
m /= d;
ll xx = (ll) x * (m % b) % b;
if(xx < 0) xx = xx + b;
ll yy = (ll)(m - a * xx) / b;
if(yy < 0)
puts("-1");
else
printf("%lld %lld\n", xx, yy);
}
}
線性同余方程
ll modequ(ll a, ll b, ll m) {
ll x, y;
ll d = exgcd(a, m, x, y);
if (b % d != 0) return -1;
m /= d; a /= d; b /= d;
x = x * b % m;
if (x < 0) x += m;
return x;
}
【模板】二元一次不定方程 (exgcd)
求正整數解個數和 \(xmin,xmax,ymin,ymax\) 的 ，因為要求是正的，注意判等于 \(0\) 的情況
給定不定方程
\[ax+by=c
\]
若該方程無整數解，輸出 \(-1\)。
若該方程有整數解，且有正整數解，則輸出其正整數解的數量，所有正整數解中 \(x\) 的最小值，所有正整數解中 \(y\) 的最小值，所有正整數解中 \(x\) 的最大值，以及所有正整數解中 \(y\) 的最大值。
若方程有整數解，但沒有正整數解，你需要輸出所有整數解中 \(x\) 的最小正整數值， \(y\) 的最小正整數值。
正整數解即為 \(x, y\) 均為正整數的解，\(\boldsymbol{0}\) 不是正整數。
整數解即為 \(x,y\) 均為整數的解。
\(x\) 的最小正整數值即所有 \(x\) 為正整數的整數解中 \(x\) 的最小值，\(y\) 同理。
\(1 \le a, b, c \le {10}^9\)。
sample
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432
4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b==0)
{
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
int main()
{
ll a, b, c, x, y;
cin>>a>>b>>c;
ll d = exgcd(a, b, x, y);
if(c % d)
cout<<-1<<"\n";
else
{
a /= d, b /= d, c /= d;
x *= c,y *= c;//特解
x = (x % b + b) % b;
x = x == 0 ? b : x;
y = (c - a * x) / b;
if(y > 0)
{
ll xmin, xmax, ymin, ymax;
xmin = x,ymax = y;
y %= a;
y = y == 0 ? a : y;
x = (c - b * y) / a;
xmax = x, ymin = y;
ll cnt = (xmax - xmin) / b + 1;//每隔b一個整數解
cout<<cnt<<" "<<xmin<<" "<<ymin<<" "<<xmax<<" "<<ymax<<"\n";
}
else//有整數解，但無正整數解
{
ll xmin, ymin;
xmin = x;
y = y % a + a;
ymin = y;
cout<<xmin<<" "<<ymin<<"\n";
}
}
return 0;
}
中國剩余定理
dls
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
void merge(ll &a, ll &b, ll c, ll d) { // d <= 10^9
// bt=c-a(mod d)
if (a == -1 && b == -1) return;
ll x, y;
ll g = exgcd(b, d, x, y);
//bx=g(mod d)
if ((c - a) % g != 0) {
a = b = -1;
}
d /= g; // d'
ll t0 = ((c - a) / g) % d * x % d;
if (t0 < 0) t0 += d;
// t = t0 (mod d')
a = b * t0 + a;
b = b * d;
}
ex中國剩余定理
typedef long long ll;
const int mod = 19260817;
const int N = 1e8 + 10;
__int128 exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
__int128 xx,yy;
__int128 d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
void merge(__int128 &a, __int128 &b, __int128 c, __int128 d) { // d <= 10^9
// bt=c-a(mod d)
if (a == -1 && b == -1) return;
__int128 x, y;
__int128 g = exgcd(b, d, x, y);
//bx=g(mod d)
if ((c - a) % g != 0) {
a = b = -1;
}
d /= g; // d'
__int128 t0 = ((c - a) / g) % d * x % d;
if (t0 < 0) t0 += d;
// t = t0 (mod d')
a = b * t0 + a;
b = b * d;
}
array<ll, 2> ar[N];
void solve()
{
int n; cin>>n;
for(int i = 1; i <= n; i++)
cin>>ar[i][1]>>ar[i][0];
__int128 a = 0, b = 1;
for(int i = 1; i <= n; i++)
merge(a, b, (__int128)ar[i][0], (__int128)ar[i][1]);
cout<<(ll)a<<'\n';
return;
}
逆元
線性
ll n, p, inv[N];
void solve()
{
cin>>p>>n;
inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = (p - p / i) * inv[p % i] % p;
return;
}
快速冪求逆元
qmi(a, mod - 2, mod)
階 \(a ^ x \equiv 1 (\bmod p)\)
int p, phip;
vector<int> factor;
ll qmi(ll a, ll b, ll p)
{
ll res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
int phi(int p)
{
int res = p;
for(int i = 2; i <= p / i; i++)
if(p % i == 0)
res = res / i * (i - 1);
if(p != 1)
res = res / p * (p - 1);
return res;
}
void solve()
{
int a; cin>>a;
int res = phip;
for(auto &it : factor)
if(qmi(a, res / it, p) == 1)
res /= it;
cout<<res<<'\n';
return;
}
void init()
{
phip = phi(p);
int q = phip;
for(int i = 2; i <= q / i; i++)
if(q % i == 0) while(q % i == 0) factor.push_back(i), q /= i;
if(q != 1) factor.push_back(q);
}
原根 \(a ^ x \equiv 1 (\bmod m)\) ，當最小的 \(x\) 是 \(\varphi(m)\) 的時候 \(a\) 是 \(m\) 的原根
原根個數: 若 \(m\) 有原根， \(m\) 有原根 \(\varphi (\varphi (m))\)個
最小原根的數量級: 若 \(m\) 有原根，最小原根不多于 \(m ^ {0.25}\) 級別
ll qmi(ll a, ll b, ll p)
{
ll res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
int p, phip;
vector<int> factor;
void init()
{
int q = p - 1;
for(int i = 2; i <= q / i; i++)
if(q % i == 0) while(q % i == 0) factor.push_back(i), q /= i;
if(q != 1) factor.push_back(q);
}
void solve()
{
factor.clear();
cin>>p;
phip = p - 1;
init();
for(int i = 1; i < p; i++)
{
bool ok = true;
for(auto &it : factor)
{
if(qmi(i, phip / it, p) == 1)
{
ok = false;
break;
}
}
if(ok)
{
cout<<i<<'\n';
return;
}
}
return;
}
指數方程1 \(a ^ x \equiv b (\bmod m)\) \(m\) 為質數
ll qmi(ll a, ll b, ll p)
{
ll res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
void solve()
{
int a, b, m; cin>>a>>b>>m;
int res = m + 1, T = sqrt(m) + 2;
ll d = 1, v = qmi(a, T, m);
unordered_map<int, int> mp;
for(int q = 1; q <= T; q++)
{
d = v * d % m;
if(mp.count(d)) continue;
mp[d] = q * T;
}
d = b;
for(int r = 1; r <= T; r++)
{
d = a * d % m;
if(mp.count(d))
res = min(res, mp[d] - r);
}
if(res == m + 1)
res = -1;
cout<<res<<'\n';
return;
}
指數方程2 \(a ^ x \equiv b (\bmod m)\) \(m\) 不為質數
ll ksm(ll a, ll b, ll mod)
{
ll ans = 1, base = a;
while(b)
{
if(b & 1) ans = ans * base % mod;
base = base * base % mod;
b >>= 1;
}
return ans;
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
//求a*x = b(mod m)的解
ll modequ(ll a, ll b, ll m)
{
ll x, y;
ll d = exgcd(a, m, x, y);
if(b % d) return -1;
m /= d, a /= d, b /= d;
x = x * b % m;
if(x < 0) x += m;
return x;
}
int MAGIC = 30;
bool ok = false;
/*
21 48 49
0 0 0
*/
void solve()
{
int a, b, m;
cin>>a>>m>>b;
//cout<<a<<" "<<b<<" "<<m<<'\n';
if(a == 0 && b == 0 && m == 0)
{
ok = true;
return;
}
b %= m;
if(b == 1 || m == 1)
{
cout<<0<<'\n';
return;
}
ll v = 1;
for(int i = 0;i < MAGIC; i++)
{
if(v == b)
{
cout<<i<<'\n';
return;
}
v = v * a % m;
}
//v * a^{x-30} = b(mod m);
ll g = __gcd(v, 1ll * m);
if(b % g)
{
cout<<"No Solution"<<'\n';
return;
}
b /= g, m /= g;
a %= m;
//v/g * ? = b/g(mod m)
b = modequ(v / g, b, m);
//BSGS
int T = sqrt(m) + 2;//小心精度誤差，我們+2
v = ksm(a, T, m);
ll d = 1;
unordered_map<int, int>ha;
for(int q = 1; q <= T; q++)
{
d = d * v % m;
//因為我們要求較小的解，如果我們有兩個相同的d，去小的那個
if(!ha.count(d)) ha[d] = q * T;
}
int ans = m + 1;
d = b;
for(int r = 1; r <= T; r++)
{
d = d * a % m;
if(ha.count(d)) ans = min(ans, ha[d] - r);
}
if(ans >= m) cout<<"No Solution"<<'\n';
else cout<<ans + MAGIC<<'\n';
}
排列組合
加法 & 乘法原理
加法原理
完成一個工程可以有\(n\) 類辦法，\(a_i(1\leq i\leq n)\)
代表第 \(i\) 類方法的數目。那么完成這件事共有 \(S = a_1 + a_2 + \dots + a_n\) 種不同的方法。
乘法原理
完成一個工程需要分 \(n\) 個步驟，\(a_i(1 \leq i \leq n)\) 代表第 \(i\) 個步驟的不同方法數目。那么完成這件事共有 \(S = a_1 \times a_2 \times \cdots \times a_n\) 種不同的方法。
組合數
\(O(N^2)\)
int n, c[N][N];
void init()
{
for(int i = 0; i <= 2000; i++)
for(int j = 0; j <= i; j++)
if(j == 0) c[i][j] = 1;
else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
void solve()
{
int a,b; cin>>a>>b;
cout<<c[a][b]<<endl;
}
O(N)
int n;
ll f[N],infact[N];
void init()
{
f[0] = infact[0] = 1;
for(int i = 1; i <= 100000; i++)
{
f[i] = i * f[i - 1] % mod;
infact[i] = infact[i - 1] * 1ll * qmi(i, mod-2, mod) % mod;
}
}
void solve()
{
int a,b; cin>>a>>b;
cout<<(f[a] * infact[b] % mod * infact[a - b] % mod)<<endl;
}
Lucas \(O(\log_pNp\log_p) p 為質數\)
int C(int a, int b, int p)
{
if (b > a) return 0;
int res = 1;
for (int i = 1, j = a; i <= b; i ++, j -- )
{
res = (ll)res * j % p;
res = (ll)res * qmi(i, p - 2, p) % p;
}
return res;
}
int lucas(ll a, ll b, int p)
{
if (a < p && b < p) return C(a, b, p);
return (ll)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
Lucas \(O(\log_qNq\log_q)\)
/*
組合數取模(模數p可以是合數的情況)
p是合數的情況不好處理，
像之前學的CRT，如果p是合數，我們拆成若干素數冪的形式。
比如：
n
m mod q
q = p1^e1*p2^e2...pk^ek
n
m mod pi^ei
再用CRT可以解決
即：我們要解決
n
m mod pi^ei (p^e<=1e6)
CRT
m1,m2...mn
找到xi滿足:xi mod mi = 1
xi mod M/mi = 0;
x ≡ ai(mod mi)
x = Σxi*ai
x就是答案
Q:考慮為什么我們不能用之前的逆元的寫法
A:逆元寫法：
n!/(m!*(n-m)!)
a/b mod p ==> a mod p*(b mod p)^-1
即:
1.n!*(m!)^-1*(n-m)^-1
2.inv[i] = (p-p/i)*inv[p%i]%p
1.因為n可能很大，直接算階乘可能算不出來
2.算逆元的話，分母不一定是可逆的,比如p=2，分母有很多2的因子,所以說它不一定是可逆的
整體思路就是把階乘都用n！= p^an*bn表示出來,其中p不整除bn(把p的因子都提出來,那這個bn相當于是多出來的)
n！= p^an*bn
= p^an*bn/(p^am*bm*p^(an-m)*(bn-m))
= p^(an-am-(an-m))*bn/(bm*(bn-m))
這里b是沒有p的因子,肯定與p的冪次是互質的,那我們可以直接求其逆元
= p^(an-am-(an-m))*bn*(bm*(bn-m))^(-1) (mod p^e)
畫個表...
n！= p^an*bn
預處理：
fac[i]：1~i之間不被p整除%p^e的所有數的乘積
fac[p^e-1]^(n/p^e)*fac[n%p^e]
有(n/p^e)個完整的組，和n%p^e多出來的零頭
遞歸下去就是：p^(n/p)*(n/p)!————>(n/p)!就是子問題
一直遞歸到<p為止
*/
#include<bits/stdc++.h>
//#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
typedef long long ll;
const int N = 101000;
int m, T, M, phipe;
pair<int, int> x[110];
ll pr[110];
ll ans[N], a[N], b[N], fac[1010000];
ll ksm(ll a, ll b, ll m)
{
ll ans = 1, base = a;
while(b > 0)
{
if(b & 1)
{
ans *= base;
ans %= m;
}
base *= base;
base %= m;
b >>= 1;
}
return ans;
}
pair<ll, ll> calc(ll a, int p, int pe)
{
ll cntp = 0, cnts = 0, val = 1;
while(a)
{
cntp += a / p;
cnts += a / pe;
val = val * fac[a % pe] % pe;
//val = val*ksm(fac[pe],a/pe)%pe*fac[a%pe]%pe
a /= p;
}
//val = val*ksm(fac[pe],cnts,pe)%pe;
val = val * ksm(fac[pe - 1], cnts % phipe, pe) % pe;
return {val, cntp};//非素數部分和素數部分
}
ll binom(ll a, ll b, int p, int pe)
{
/*
n！= p^an*bn
= p^an*bn/(p^am*bm*p^(an-m)*(bn-m))
= p^(an-am-(an-m))*bn/(bm*(bn-m))
= p^(an-am-(an-m))*bn*(bm*(bn-m))^(-1) (mod p^e)
*/
auto f1 = calc(a, p, pe);
auto f2 = calc(b, p, pe);
auto f3 = calc(a - b, p, pe);
ll v1 = f1.first * ksm(f2.first * f3.first % pe, phipe - 1, pe) % pe;//與p互質的部分
ll v2 = ksm(p, f1.second - f2.second - f3.second, pe);//與p不互質的部分
return v1 * v2 % pe;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>m>>T;
M = m;
int t = 0;
for(int i = 2; i <= m; i++)
{
if(m % i == 0)//對m進行分解
{
int p = i, pe = 1;
while(m % i == 0) m /= i, pe *= i;
x[t++] = {p, pe};//x記錄分解結果
}
}
/*
CRT
m1,m2...mn
找到xi滿足:xi mod mi = 1
xi mod M/mi = 0;
x ≡ ai(mod mi)
x = Σxi*ai
*/
for(int i = 0; i < t; i++)
{
int pe = x[i].second;
for(int c = 0; c < M; c++)//這里M很小我們可以直接暴力for一遍找xi，就不用寫exgcd了
{
if(c % pe == 1 && c % (M / pe) == 0)
{
pr[i] = c;
break;
}
}
}
for(int i = 0; i < T; i++) cin>>a[i]>>b[i];//先讀進來再每個因子分開處理
for(int i = 0; i < t; i++)
{
int p = x[i].first, pe = x[i].second;
fac[0] = 1;//fac[i]:1~i之間不被p整除%p^e的所有數的乘積
for(int j = 1; j <= pe; j++)
{
if(j % p == 0)
fac[j] = fac[j - 1];
else
fac[j] = fac[j - 1] * j % pe;//注意是%pe不是p
}
//phi(x) = x*∏(i=1~n)(1-1/pi)
//phipe = pe*(1-1/p);
phipe = (pe / p) * (p - 1);
for(int j = 0;j<T;j++)
{
// b
//Ca mod (p^pe)
//cout<<binom(a[j],b[j],p,pe)<<endl;
ans[j] = (ans[j] + binom(a[j], b[j], p, pe) * pr[i]) % M;
}
}
for(int j = 0; j < T; j++)
cout<<ans[j]<<'\n';
return 0;
}
莫比烏斯反演
積性函數
void prime(int n)
{
p[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!p[i]) p[i] = i, pr[++tot] = i, pe[i] = i;
for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
p[pr[j] * i] = pr[j];
if(p[i] == pr[j])
{
pe[i * pr[j]] = pe[i] * pr[j];
break;
}
else
pe[i * pr[j]] = pr[j];
}
}
}
void solve()
{
cin>>n;
prime(n);
f[1] = 1; // !可能要改
for(int i = 2; i <= n; i++)
{
if(i == pe[i]) f[i] = ...
else f[i] = f[pe[i]] * f[i / pe[i]];
}
return;
}
\(\varphi\)
int p[N], pr[N / 5], tot;
ll phi[N], sphi[N];
void prime(int n)
{
phi[1] = 1; p[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!p[i]) p[i] = i, pr[++tot] = i, phi[i] = i - 1;
for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
p[pr[j] * i] = pr[j];
if(p[i] == pr[j])
{
phi[i * pr[j]] = phi[i] * pr[j];
break;
}
else
phi[i * pr[j]] = phi[i] * (pr[j] - 1);
}
}
for(int i = 1; i <= N - 10; i++)
sphi[i] = sphi[i - 1] + phi[i];
}
\(\mu\)
int p[N], pr[N / 5], tot, mu[N];
ll smu[N];
void prime(int n)
{
mu[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!p[i]) p[i] = i, pr[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
p[pr[j] * i] = pr[j];
if(p[i] == pr[j])
{
mu[i * pr[j]] = 0;
break;
}
else
mu[i * pr[j]] = -mu[i];
}
}
for(int i = 1; i <= N - 10; i++)
smu[i] = smu[i - 1] + mu[i];
}
杜教篩
常用于求數論函數前綴和
杜教篩 = 整數分塊+迪利克雷卷積+線性篩
時間復雜度:\(O(n^{\frac{2}{3}})\)
公式：\(g(1)S(n) = \sum_{i = 1}^{n}h(i)-\sum_{i = 2}^{n}g(i)S(\lfloor \dfrac{n}{i}\rfloor)\)
對于函數\(f\) 構造出來\(h,g\)滿足\(f = h*g\)
常見構造：
- \(e = \mu*1\)，即\([n=1]=\sum_{d|n}\mu(d)\)
- \(Id = \varphi*1\)，即\(n = \sum_{d|n}\varphi(d)\)
const int N = 6e6 + 10;
typedef long long ll;
int cnt, pri[N], mu[N], sum1[N], phi[N];
bool vis[N];
ll sum2[N];
map<int, ll> sumphi;
map<int, int> summu;
void init(int n)
{
phi[1] = mu[1] = 1;
vis[0] = vis[1] = 1;
for(int i = 2; i < n; i++)
{
if(!vis[i])
{
pri[++cnt] = i;
mu[i] = -1;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && pri[j] * i <= n; j++)
{
vis[i * pri[j]] = 1;
if(i % pri[j] == 0)
{
mu[i * pri[j]] = 0;
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
else
{
mu[i * pri[j]] = -mu[i];
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
}
for(int i = 1; i < n; i++)
{
sum1[i] = sum1[i - 1] + mu[i];
sum2[i] = sum2[i - 1] + phi[i];
}
}
ll dlsmu(int x)
{
if(x < N) return sum1[x];
if(summu[x]) return summu[x];
int &ans = summu[x];
ans += 1;
for(ll l = 2; l <= x; l++)
{
ll d = x / l;
ll r = x / d;
ans -= (r - l + 1) * dlsmu(d);
l = r;
}
return ans;
}
ll dlsphi(int x)
{
if(x < N) return sum2[x];
if(sumphi[x]) return sumphi[x];
ll &ans = sumphi[x];
ans += (1ll * x + 1) * x / 2;
// x + 1 !!!在模板題中爆int
for(ll l = 2; l <= x; l++)
{
ll d = x / l, r = x / d;
ans -= (r - l + 1) * dlsphi(d);
l = r;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t, n;
cin>>t;
init(N - 10);
while(t--)
{
cin>>n;
cout<<dlsphi(n)<<" "<<dlsmu(n)<<"\n";
}
return 0;
}
大素數判斷 miller_rabin \(O(s \log_2 ^ 3 n)\)， \(n \leq 2 ^ {54}\)
typedef long long ll;
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
bool witness(ll a, ll n)
{
ll u = n - 1;
int t = 0;
//2^t*u
while((u & 1) == 0) u >>= 1, t++;
ll x1, x2;
x1 = qmi(a, u, n); // a ^ u mod n
for(int i = 1; i <= t; i++)
{
x2 = qmi(x1, 2, n);
if(x2 == 1 && x1 != 1 && x1 != n - 1)
return true;
x1 = x2;
}
if(x1 != 1) return true;
return false;
}
int miller_rabin(ll n, ll s)
{
if(n < 2) return 0;
if(n == 2) return 1;
if(n % 2 == 0) return 0;
for(int i = 0; i < s && i < n; i++)
{
ll a = rand() % (n - 1) + 1;
if(witness(a, n)) return 0;
}
return 1;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int m;
while(cin>>m)
{
int cnt = 0;
for(int i = 1; i <= m; i++)
{
ll n; cin>>n;
int s = 50;
cnt += miller_rabin(n, s);
}
cout<<cnt<<"\n";
}
return 0;
}
勾股數的神奇性質
性質1:較大的兩個數之和等于這組數最小值的平方。
勾股數只有兩種：\(奇數^2+偶數^2 = 奇數^2,偶數^2+偶數^2 = 偶數^2\)
性質2：一個正奇數(除了1)與兩個和等于此數的平方的連續正整數的一組勾股數。
比如一正奇數\(n\)，那么以\(n\)為最小值的一組勾股數：\(n,(n^2-1)/2,(n^2+1)/2\)
性質3：一個正偶數(除了0，2，4)，后兩數之和的二倍等于最小數平方。
比如一正偶數\(n\)，那么以\(n\)為最小值的一組勾股數：\(n,(n^2/4)-1,(n^2/4)+1\)
性質4：一組勾股數的倍數還是勾股數。
以上性質用于尋找勾股數，而其逆命題判斷勾股數時可能會有覆蓋不完全現象(如20，21，29)。
DP
01背包
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
完全背包
for(int i = 1; i <= n; i++)
for(int j = v[i]; j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
多重背包
\(O(NMS)\)
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
\(O(NM\log S)\)
for(int i = 1; i <= n; i++){
int v, w, l;
cin >> v >> w >> l;
for(int k = 1; l ; k *= 2){
if(l >= k) l -= k;
else k = l, l = 0;
for(int j = m; j >= v * k; j--)
f[j] = max(f[j], f[j - v * k] + w * k);
}
}
\(O(NM)\) ver 1
int n, m, f[N];
int q[N][3];
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
int v, w, s; cin>>v>>w>>s;
for(int j = 0; j < v; j++)
{
int h = 1, t = 0;
for(int p = j, x = 1; p <= m; p += v, x++)
{
int val = f[p] - x * w, cnt = x + s;
for(; h <= t && q[t][1] <= val; t--);
q[++t][1] = val, q[t][2] = cnt;
f[p] = q[h][1] + x * w;
for(; h <= t && q[h][2] == x; h++);
}
}
}
}
\(O(NM)\) ver 2
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
int v, w, s;
cin>>v>>w>>s;
memcpy(g, dp, sizeof dp);
for(int j = 0; j < v; j++)
{
int hh = 0, tt = -1;
for(int k = j; k <= m; k += v)
{
if(hh <= tt && q[hh] < k - s * v) hh++;
while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
tt--;
q[++tt] = k;
dp[k] = g[q[hh]] + (k - q[hh]) / v * w;
}
}
}
cout<<dp[m]<<endl;
return;
}
分組背包
const int N = 110;
int n, m;
int f[N], w[N][N], v[N][N], s[N];
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>s[i];
for(int j = 0; j < s[i]; j++)
cin>>v[i][j]>>w[i][j];
}
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j--)
for(int k = 0; k < s[i]; k++)
if(v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout<<f[m];
}
最長公共子序列
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(a[i] == b[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
最長上升子序列
\(O(N^2)\)
for(int i = 1; i <= n; i++)
{
f[i] = 1;
for(int j = 1; j < i; j++)
if(a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
}
ans = f[1];
for(int i = 1; i <= n;i++)
ans = max(ans, f[i]);
\(O(N\log N)\)
int len = 0;
for (int i = 0; i < n; i++)
{
int l = 0, r = len;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (a[i] > q[mid]) l=mid;
else r = mid-1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
cout << len << endl;
樹上背包
\(O(N^2)\) 點數和背包大小都為\(N\)
const int N = 2e3 + 10;
const int inf = 1 << 29;
int n, q;
int sz[N], w[N], f[N][N], tmp[N];
vector<int> e[N];
void dfs(int u)
{
sz[u] = 0;
for(auto v : e[u])
{
dfs(v);
for(int i = 0; i <= sz[u] + sz[v]; i++)
tmp[i] = -inf;
for(int i = 0; i <= sz[u]; i++)
for(int j = 0; j <= sz[v]; j++)
tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j]);
sz[u] += sz[v];
for(int i = sz[u]; i >= 0; i--)
f[u][i] = tmp[i];
}
sz[u]++;
for(int i = sz[u]; i >= 1; i--)
f[u][i] = f[u][i - 1] + w[u];
}
\(O(NM^2)\)
const int N = 5e4 + 10;
const int M = 100;
const int inf = 1 << 29;
int n, q;
int sz[N], w[N], f[N][M + 10], tmp[N];
vector<int> e[N];
void dfs(int u)
{
sz[u] = 0;
for(auto v : e[u])
{
dfs(v);
for(int i = 0; i <= sz[u] + sz[v]; i++)
tmp[i] = -inf;
for(int i = 0; i <= sz[u] && i <= M; i++)
for(int j = 0; j <= sz[v] && i + j <= M; j++)
tmp[i + j] = max(tmp[i + j], f[u][i] + f[v][j]);
sz[u] += sz[v];
for(int i = min(M,sz[u]); i >= 0; i--)
f[u][i] = tmp[i];
}
sz[u]++;
for(int i = min(M, sz[u]); i >= 1; i--)
f[u][i] = f[u][i - 1] + w[u];
}
Data structure
單調棧
給定一個長度為 \(N\) 的整數數列，輸出每個數左邊第一個比它小的數，如果不存在則輸出 \(?1\)
。
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> x;
while(tt && a[tt] >= x) tt--; //tt有，棧頂大于待入棧元素
if (tt == 0) cout << "-1 "; //第一個數，棧無
else cout << a[tt] << " "; //輸出所求
a[++tt] = x; //入棧，不符合的話下一次while就清理掉了
}
return 0;
}
單調隊列
滑動窗口
int main()
{
cin >> n>>k;
for(int i = 0; i < n; i++)
cin >> a[i];
int hh = 0, tt = -1;
for(int i = 0; i < n; i++)
{
if(hh <= tt && i - k + 1 > qq[hh]) hh++;//處理框框隊尾,框框滿了處理隊尾
while(hh <= tt && a[qq[tt]] >= a[i]) tt--; //隊首
qq[++tt] = i; //隊列加入新下標
if(i >= k - 1) cout << a[qq[hh]]<<" "; //框框滿了
}
cout << endl;
hh = 0, tt = -1;
for(int i = 0; i < n; i++)
{
if(hh <= tt && i - k + 1 > qq[hh]) hh++;
while(hh <= tt && a[qq[tt]] <= a[i]) tt--;
qq[++tt] = i;
if(i >= k - 1) cout << a[qq[hh]]<<" ";
}
return 0;
}
并查集
普通板子
int find(int x)
{
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
封裝DSU
struct DSU {
std::vector<int> p, siz;
DSU(int n) : p(n + 1), siz(n + 1, 1) { std::iota(p.begin(), p.end(), 0); }
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
siz[x] += siz[y];
p[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
};
帶權并查集
typedef long long ll;
const int N = 201000;
int n, q, fa[N];
ll w[N];
int find(int x)
{
if(x == fa[x]) return x;
int p = fa[x];
find(p);//先把fa[x]做一個路徑壓縮，假設現在的fa[p] = q
/*
w[x] = a[x]-a[p]
fa[p] = q , w[p]:a[p]-a[q]
fa[x] = p , w[x]:a[x]-a[p]
a[x] - a[p] + a[p] - a[q] = a[x]+a[p]
*/
w[x] = w[x] + w[p];
return fa[x] = fa[p];
}
int main()
{
cin>>n>>q;
//w[i] = a[i]-a[fa[i]];
for(int i = 1; i <= n; i++)
fa[i] = i, w[i] = 0;
ll t = 0;
for(int i = 0; i < q; i++)
{
int op, l, r;
cin>>op>>l>>r;
l = (l + t) % n + 1;
r = (r + t) % n + 1;
if(op == 2)
{
if(find(l) != find(r)) continue;
else cout<<w[l] - w[r]<<endl;
t = abs(w[l] - w[r]);
}
else if(op == 1)
{
int x; cin>>x;
if(find(l) == find(r)) continue;
/*
w[fa[l]] = a[fa[l]]-a[fa[r]];
a[l]-a[r] = x;
w[l] = a[l]-a[fa[l]],w[r] = a[r]-a[fa[r]];
a[l] - w[l] = a[fa[l]],a[r]-w[r] = a[fa[r]]
w[fa[l]] = a[l]-w[l]-(a[r]-w[r])
*/
//先改權值再變父親
w[fa[l]] = x - w[l] + w[r];
fa[fa[l]] = fa[r];
}
}
return 0;
}
哈希
單哈希板子
const int p = 9999971, base = 101;
int n , m, c[N + 10], ha[N + 10], hb[N + 10];
char a[N + 10], b[N + 10];
int main()
{
cin>>n>>m;
cin>>a + 1>>b + 1;
c[0] = 1;
for(int i = 1; i <= 200000; i++)
c[i] = (c[i - 1] * base) % p;
for(int i = 1; i <= n; i++)
ha[i] = (ha[i - 1] * base + a[i] - 'a') % p;
for(int i = 1; i <= m; i++)
hb[i] = (hb[i - 1] * base + b[i] - 'a') % p;
int ans = 0;
for(int i = 1; i + m - 1 <= n; i++)
if((ha[i + m - 1] - 1ll * ha[i - 1] * c[m] % p + p) % p == hb[m])
++ans;
cout<<ans<<endl;
return 0;
}
雙哈希封裝
typedef pair<long long, long long> pll;
struct DoubleStringHash
{
vector<long long> h1, h2, w1, w2;
long long base1 = 131, base2 = 13331;
long long p1 = 1e9 + 7, p2 = 1e9 + 9;
void init(string s) {
int len = s.size();
s = " " + s;
h1.resize(len + 1), w1.resize(len + 1);
h2.resize(len + 1), w2.resize(len + 1);
h1[0] = 0, w1[0] = 1;
h2[0] = 0, w2[0] = 1;
for(int i = 1; i <= len; i++) {
h1[i] = (h1[i - 1] * base1 + s[i]) % p1, w1[i] = w1[i - 1] * base1 % p1;
h2[i] = (h2[i - 1] * base2 + s[i]) % p2, w2[i] = w2[i - 1] * base2 % p2;
}
}
pll get(int l, int r) {
return {(h1[r] - h1[l - 1] * w1[r - l + 1] % p1 + p1) % p1, (h2[r] - h2[l - 1] * w2[r - l + 1] % p2 + p2) % p2};
}
};
Trie tree
普通板子
bool isend[N];
int n, m, nxt[N][26], cnt;
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
string s; cin>>s;
int len = s.size(), now = 0;
for(int j = 0; j < len; j++)
{
int x = s[j] - 'a';
if(!nxt[now][x])
nxt[now][x] = ++cnt;
now = nxt[now][x];
}
isend[now] = true;
}
cin>>m;
for(int i = 1; i <= m; i++)
{
string s; cin>>s;
int len = s.size(), now = 0;
bool ok = true;
for(int j = 0; j < len; j++)
{
int x = s[j] - 'a';
if(!nxt[now][x])
{
ok = false;
break;
}
now = nxt[now][x];
}
if(ok)
if(!isend[now])
ok = false;
if(ok)
cout<<1<<endl;
else cout<<0<<endl;
}
return;
}
封裝
struct trie
{
int nxt[500010][26], cnt;
bool isend[500010]; // 該結點結尾的字符串是否存在
void insert(string s) { // 插入字符串
int now = 0;
int l = s.size();
for(int i = 0; i < l; i++)
{
int x = s[i] - 'a';
if(!nxt[now][x]) nxt[now][x] = ++cnt; // 如果沒有，就添加結點
now = nxt[now][x];
}
isend[now] = 1;
}
bool find(string s) { // 查找字符串
int now = 0;
int l = s.size();
for(int i = 0; i < l; i++) {
int x = s[i] - 'a';
if(!nxt[now][x]) return 0;
now = nxt[now][x];
}
return isend[now];
}
}tr;
void solve()
{
int n; cin>>n;
for(int i = 1; i <= n; i++)
{
string s; cin>>s;
tr.insert(s);
}
cin>>n;
for(int i = 1; i <= n; i++)
{
string s; cin>>s;
if(tr.find(s))
cout<<1<<endl;
else cout<<0<<endl;
}
return;
}
01
const int N = 2e5 + 10;
struct
{
int sz, s[2];
}seg[N * 32];
int root, tot = 0, q;
void insert(int x)
{
int p = root;
for(int j = 29; j >= 0; j--)
{
int w = (x >> j) & 1;
seg[p].sz++;
if(seg[p].s[w] == 0) seg[p].s[w] = ++tot;
p = seg[p].s[w];
}
seg[p].sz++;
}
void del(int x)
{
int p = root;
for(int j = 29; j >= 0; j--)
{
int w = (x >> j) & 1;
seg[p].sz--;
// if(seg[p].s[w] == 0) seg[p].s[w] = ++tot;
p = seg[p].s[w];
}
seg[p].sz--;
}
int query(int x, int k) //詢問 S 中有多少個數按位異或上 x 的結果小于 k
{
int p = root;
int ans = 0;
for(int j = 29; j >= 0; j--)
{
int w = (x >> j) & 1;
int t = (k >> j) & 1;
if(w == 0 && t == 0)
{
p = seg[p].s[0];
}
else if(w == 0 && t == 1)
{
ans += seg[seg[p].s[0]].sz;
p = seg[p].s[1];
}
else if(w == 1 && t == 0)
{
// ans += seg[seg[p].s[1]].sz;
p = seg[p].s[1];
}
else if(w == 1 && t == 1)
{
ans += seg[seg[p].s[1]].sz;
p = seg[p].s[0];
}
// 異或第 k 小
// if(seg[seg[p].s[w]].sz >= k)
// p = seg[p].s[w];
// else
// {
// k -= seg[seg[p].s[w]].sz;
// p = seg[p].s[1 ^ w];
// ans = ans ^ (1 << j);
// }
}
return ans;
}
void solve()
{
cin>>q;
root = ++tot;
for(int i = 1; i <= q; i++)
{
int opt; cin>>opt;
if(opt == 1)
{
int x; cin>>x;
insert(x);
}
else if(opt == 2)
{
int x; cin>>x;
del(x);
}
else if(opt == 3)
{
int x, k; cin>>x>>k;
cout<<query(x, k)<<'\n';
}
}
return;
}
KMP
int nxt[N];
void solve()
{
string a, b; cin>>a>>b;
int n = a.size(), m = b.size();
a = "?" + a, b = "?" + b;
vector<int> ans;
for(int i = 2, j = 0; i <= n; i++)
{
while(j && a[i] != a[j + 1]) j = nxt[j];
if(a[i] == a[j + 1]) j++;
nxt[i] = j;
}
for(int i = 1, j = 0; i <= m; i++)
{
while(j == n || (j && b[i] != a[j + 1])) j = nxt[j];
if(b[i] == a[j + 1]) j++;
if(j == n)
ans.pb(i - n + 1);
}
}
DFS序
int l[N], r[N], tot, tid[N];
vector<int> e[N];
template<class T>
struct BIT {
T c[N];
int size;
void resize(int s) { size = s;}
T query(int x) { // 1 ... x
assert(x <= size);
T s = 0;
for (; x; x -= x & (-x)) {
s += c[x];
}
return s;
}
void modify(int x, T s) { // a[x] += s
assert(x != 0);
for (; x <= size; x += x & (-x)) {
c[x] += s;
}
}
};
void dfs(int u,int fa)
{
l[u] = ++tot;
tid[tot] = u;
for(int v : e[u])
{
if(v == fa) continue;
dfs(v, u);
}
r[u] = tot;
}
樹狀數組
普通模板
int n,q;
ll tr[N], a[N];
void modify(int x, ll s)
{
for(; x <= n; x += x & -x)
tr[x] += s;
}
ll query(int x)
{
ll res = 0;
for(; x; x -= x & -x)
res += c[x];
return res;
}
dls封裝
template<class T>
struct BIT {
T c[N];
int size;
void resize(int s) { size = s;}
T query(int x) { // 1 ... x
assert(x <= size);
T s = 0;
for (; x; x -= x & (-x)) {
s += c[x];
}
return s;
}
void modify(int x, T s) { // a[x] += s
assert(x != 0);
for (; x <= size; x += x & (-x)) {
c[x] += s;
}
}
};
BIT<ll> c1, c2;
線段樹
線段樹框架
struct info
{
// ...
};
struct tag
{
// ...
};
info operator + (const info &a, const info &b)
{
info t;
// ...
return t;
}
struct segtree
{
struct info val;
struct tag tag;
int sz; // ...
}seg[N * 4];
void update(int id)
{
// ...
}
void settag(int id, struct tag tag)
{
// ...
// 更新val，tag
}
void pushdown(int id)
{
if(seg[id].tag != null)
{
settag(id * 2, seg[id].tag);
settag(id * 2 + 1, seg[id].tag);
seg[id].tag = null;
}
}
void build(int id, int l, int r)
{
seg[id].sz = r - l + 1;
if(l == r)
{
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
void change(int id, int l, int r, int pos, struct tag tag)
{
if(l == r)
{
settag(id, tag);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(pos <= mid)
change(id * 2, l, mid, pos, tag);
else
change(id * 2 + 1, mid + 1, r, pos ,tag);
update(id);
}
void modify(int id, int l, int r, int ql, int qr, struct tag tag)
{
if(l == ql && r == qr)
{
settag(id, tag);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
modify(id * 2, l, mid, ql, qr, tag);
else if(ql > mid)
modify(id * 2 + 1, mid + 1, r, ql, qr, tag);
else
modify(id * 2, l, mid, ql, mid, tag),
modify(id * 2 + 1, mid +1 , r, mid + 1, qr, tag);
update(id);
}
info query(int id, int l, int r, int ql, int qr)
{
if(ql == l && qr == r)
{
return seg[id].val;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
return query(id * 2, l, mid, ql, qr);
else if(ql > mid)
return query(id * 2 + 1, mid + 1, r, ql, qr);
else
return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);
}
線段樹維護最大字段和
ll a[N];
struct info
{
ll ms,pre,suf,s;
};
info operator + (const info &l, const info &r)
{
info a;
a.s = l.s + r.s;
a.ms = max({l.ms, r.ms, l.suf + r.pre});
a.pre = max(l.pre, l.s + r.pre);
a.suf = max(r.suf, r.s + l.suf);
return a;
}
struct node
{
info val;
} seg[N * 4];;
void update(int id)
{
seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}
void build(int id,int l,int r)
{
if (l == r)
{
seg[id].val = {a[l], a[l], a[l], a[l]};
}
else
{
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
}
void change(int id, int l, int r, int pos, int val)
{
if (l == r)
{
seg[id].val = {a[l], a[l], a[l], a[l]};
}
else
{
int mid = (l + r) >> 1;
if(pos <= mid)
change(id * 2, l, mid, pos, val);
else
change(id * 2 + 1, mid + 1, r, pos, val);
update(id);
}
}
info query(int id, int l, int r, int ql, int qr)
{
if (l == ql && r == qr)
return seg[id].val;
int mid = (l + r) >> 1;
if (qr <= mid)
return query(id * 2, l, mid, ql, qr);
else if (ql > mid)
return query(id * 2 + 1, mid + 1, r, ql, qr);
else
return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid+1, r, mid + 1, qr);
}
int main()
{
std::ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,q; cin>>n>>q;
for(int i = 1; i <= n; i++)
cin>>a[i];
build(1, 1, n);
while(q--)
{
int op,l,r; cin >> op >> l >> r;
if (op == 1)
change(1, 1, n, l, r);
else if (op == 2)
{
auto ans = query(1, 1, n, l, r);
cout<<ans.ms<<endl;
}
}
return 0;
}
動態開點線段樹
struct segtree
{
int l, r;
ll s, tag;
}seg[N * 30];
int n, m, tot = 1;
void update(int &id)
{
seg[id].s = seg[seg[id].l].s + seg[seg[id].r].s;
}
void settag(int id, int sz, ll t)
{
seg[id].s += t * sz;
seg[id].tag += t;
}
void pushdown(int id, int l, int r)
{
if(seg[id].tag == 0) return;
if(seg[id].l == 0) seg[id].l = ++tot;
if(seg[id].r == 0) seg[id].r = ++tot;
int mid = (l + r) >> 1;
if(seg[id].l != 0)
settag(seg[id].l, mid - l + 1, seg[id].tag);
if(seg[id].r != 0)
settag(seg[id].r, r - mid, seg[id].tag);
seg[id].tag = 0;
}
void change(int &id, int l, int r, int pos, int val)
{
if(!id)
id = ++tot;
if(l == r)
{
seg[id].s = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
change(seg[id].l, l, mid, pos, val);
else
change(seg[id].r, mid + 1, r, pos, val);
update(id);
}
void modify(int &id, int l, int r, int ql, int qr, ll t)
{
if(!id)
id = ++tot;
if(l == ql && r == qr)
{
settag(id, r - l + 1, t);
return;
}
pushdown(id, l ,r);
int mid = (l + r) >> 1;
if(qr <= mid)
modify(seg[id].l, l, mid, ql, qr, t);
else if(ql > mid)
modify(seg[id].r, mid + 1, r, ql, qr, t);
else
{
modify(seg[id].l, l, mid, ql, mid, t);
modify(seg[id].r, mid + 1, r, mid + 1, qr, t);
}
update(id);
}
ll query(int id, int l, int r, int ql, int qr)
{
if(!id)
id = ++tot;
if(l == ql && r == qr)
{
return seg[id].s;
}
pushdown(id, l, r);
int mid = (l + r) >> 1;
if(qr <= mid)
return query(seg[id].l, l, mid, ql, qr);
else if(ql > mid)
return query(seg[id].r, mid + 1, r, ql, qr);
else
return query(seg[id].l, l, mid, ql, mid) +
query(seg[id].r , mid + 1, r, mid + 1, qr);
}
可持久化線段樹第\(k\)小數
struct segtree
{
int l, r, s;
}seg[N * 30];
vector<int> vx;
int n, q, a[N], rt[N], tot;
void update(int id)
{
seg[id].s = seg[seg[id].l].s + seg[seg[id].r].s;
}
int build(int l, int r)
{
int id = ++tot;
if(l == r)
return id;
int mid = (l + r) >> 1;
seg[id].l = build(l, mid);
seg[id].r = build(mid + 1, r);
return id;
}
int change(int u, int l, int r, int pos)
{
int id = ++tot;
seg[id] = seg[u];
if(l == r)
{
seg[id].s++;
return id;
}
int mid = (l + r) >> 1;
if(pos <= mid)
seg[id].l = change(seg[u].l, l, mid, pos);
else
seg[id].r = change(seg[u].r, mid + 1, r, pos);
update(id);
return id;
}
int query(int v, int u, int l, int r, int x)
{
if(l == r)
return l;
int cnt = seg[seg[u].l].s - seg[seg[v].l].s;
int mid = (l + r) >> 1;
if(x <= cnt)
return query(seg[v].l, seg[u].l, l, mid, x);
else
return query(seg[v].r, seg[u].r, mid + 1, r, x - cnt);
}
void solve()
{
cin>>n>>q;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
vx.push_back(a[i]);
}
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
rt[0] = build(1, vx.size());
for(int i = 1; i <= n; i++)
rt[i] = change(rt[i - 1], 1, vx.size(), lower_bound(vx.begin(), vx.end(), a[i]) - vx.begin() + 1);
while(q--)
{
int l, r, k; cin>>l>>r>>k;
cout<<vx[query(rt[l - 1], rt[r], 1, vx.size(), k) - 1]<<endl;
}
}
可持久化線段樹前\(k\)大之和
int n, m, q, tot, rt[N], a[N];
ll mi[N];
vector<int> vx;
struct segtree
{
int l, r, cnt;
ll s, val;
}seg[N * 30];
void update(int id)
{
seg[id].s = seg[seg[id].l].s + seg[seg[id].r].s;
seg[id].cnt = seg[seg[id].l].cnt + seg[seg[id].r].cnt;
}
int build(int l, int r)
{
int id = ++tot;
if(l == r)
{
return id;
}
int mid = (l + r) >> 1;
seg[id].l = build(l, mid);
seg[id].r = build(mid + 1, r);
update(id);
return id;
}
int change(int u, int l, int r, int pos)
{
int id = ++tot;
seg[id] = seg[u];
if(l == r)
{
seg[id].s = seg[id].s + vx[pos - 1];
seg[id].cnt = seg[id].cnt + 1;
seg[id].val = vx[l - 1];
return id;
}
int mid = (l + r) >> 1;
if(pos <= mid)
seg[id].l = change(seg[id].l, l, mid, pos);
else
seg[id].r = change(seg[id].r, mid + 1, r, pos);
update(id);
return id;
}
ll query(int v, int u, int l, int r, int k)
{
if(l == r)
{
return seg[u].val * k;
}
int mid = (l + r) >> 1;
int tmp = seg[seg[u].r].cnt - seg[seg[v].r].cnt;
if(tmp >= k)
return query(seg[v].r, seg[u].r, mid + 1, r, k);
else
return seg[seg[u].r].s - seg[seg[v].r].s
+ query(seg[v].l, seg[u].l, l, mid, k - tmp);
}
void solve()
{
tot = 0;
vx.clear();
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
vx.push_back(a[i]);
}
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
int m = vx.size();
rt[0] = build(1, m);
for(int i = 1; i <= n; i++)
{
int pos = lower_bound(vx.begin(), vx.end(), a[i]) - vx.begin() + 1;
rt[i] = change(rt[i - 1], 1, m, pos);
}
cin>>q;
for(int i = 1; i <= q; i++)
{
int l, r, k; cin>>l>>r>>k;
int mm = r - l + 1;
int x = l, y = l + mm - 1;
ll ans = query(rt[x - 1], rt[y], 1, m, k) + mi[mm];
cout<<ans<<'\n';
}
}
樹鏈剖分 點權
// AC one more times
ll mod, w[N];
vector<int> e[N];
int n, root, q;
int tot, l[N], r[N], tid[N], top[N], bs[N], sz[N], f[N], dep[N];
void dfs1(int u, int fa)
{
sz[u] = 1;
dep[u] = dep[fa] + 1;
bs[u] = -1;
f[u] = fa;
for(auto v : e[u])
{
if(v == fa) continue;
dfs1(v, u);
sz[u] +=sz[v];
if(bs[u] == -1 || sz[v] > sz[bs[u]])
bs[u] = v;
}
}
void dfs2(int u,int t)
{
l[u] = ++tot;
tid[tot] = u;
top[u] = t;
if(bs[u] != -1)
dfs2(bs[u], t);
for(auto v : e[u])
{
if(v == bs[u] || v == f[u]) continue;
dfs2(v, v);
}
r[u] = tot;
}
struct segtree
{
ll s, tag, sz;
}seg[N * 4];
void update(int id)
{
seg[id].s = seg[id * 2].s + seg[id * 2 + 1].s;
seg[id].s %= mod;
seg[id].sz = seg[id * 2].sz + seg[id * 2 + 1].sz;
}
void settag(int id, ll tag)
{
seg[id].tag += tag;
seg[id].s += tag * seg[id].sz, seg[id].s %= mod;
}
void pushdown(int id)
{
if(seg[id].tag != 0)
{
settag(id * 2, seg[id].tag);
settag(id * 2 + 1, seg[id].tag);
seg[id].tag = 0;
}
}
void build(int id, int l, int r)
{
seg[id].sz = r - l + 1;
if(l == r)
{
seg[id].s = w[tid[l]];
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
void modify(int id, int l, int r, int ql, int qr, ll tag)
{
if(l > r) return;
if(l == ql && r == qr)
{
settag(id, tag);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
modify(id * 2, l, mid, ql, qr, tag);
else if(ql > mid)
modify(id * 2 + 1, mid + 1, r, ql, qr, tag);
else
{
modify(id * 2, l, mid, ql, mid, tag);
modify(id * 2 + 1, mid + 1, r, mid + 1, qr, tag);
}
update(id);
}
ll query(int id, int l, int r, int ql, int qr)
{
if(l > r) return 0;
if(l == ql && r == qr)
{
return seg[id].s;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
return query(id * 2, l, mid, ql, qr);
else if(ql > mid)
return query(id * 2 + 1, mid + 1, r, ql, qr);
else
{
return (query(id * 2, l, mid, ql, mid) +
query(id * 2 + 1, mid + 1, r, mid + 1, qr)) % mod;
}
update(id);
}
void modify(int u, int v, ll k)
{
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]])
{
modify(1, 1, n, l[top[u]], l[u], k);
u = f[top[u]];
}
else
{
modify(1, 1, n, l[top[v]], l[v], k);
v = f[top[v]];
}
}
if(dep[u] < dep[v]) swap(u, v);
modify(1, 1, n, l[v], l[u], k);
}
ll query(int u, int v)
{
ll ans = 0;
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]])
{
ans += query(1, 1, n, l[top[u]], l[u]);
ans %= mod;
u = f[top[u]];
}
else
{
ans += query(1, 1, n, l[top[v]], l[v]);
ans %= mod;
v = f[top[v]];
}
}
if(dep[u] < dep[v]) swap(u, v);
ans += query(1, 1, n, l[v], l[u]);
ans %= mod;
return ans;
}
void solve()
{
cin>>n>>q>>root>>mod;
for(int i = 1; i <= n; i++)
cin>>w[i];
for(int i = 1; i < n; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(root, 0);
dfs2(root, root);
build(1, 1, n);
while(q--)
{
int op; cin>>op;
if(op == 1)
{
int u, v; cin>>u>>v;
ll k; cin>>k;
modify(u, v, k);
}
else if(op == 2)
{
int u, v; cin>>u>>v;
cout<<query(u, v) % mod<<endl;
}
else if(op == 3)
{
int u; ll k;
cin>>u>>k;
modify(1, 1, n, l[u], r[u], k);
}
else if(op == 4)
{
int u; cin>>u;
cout<<query(1, 1, n, l[u], r[u]) % mod<<endl;
}
}
return;
}
樹鏈剖分 邊權下放
vector<PII> e[N];
int n, q;
int tot, l[N], r[N], tid[N], top[N], bs[N], sz[N], f[N], dep[N];
ll w[N];
pii edge[N];
void dfs1(int u, int fa)
{
sz[u] = 1;
dep[u] = dep[fa] + 1;
bs[u] = -1;
f[u] = fa;
for(auto v : e[u])
{
if(v.fi == fa) continue;
dfs1(v.fi, u);
w[v.fi] = v.se;
sz[u] +=sz[v.fi];
if(bs[u] == -1 || sz[v.fi] > sz[bs[u]])
bs[u] = v.fi;
}
}
void dfs2(int u,int t)
{
l[u] = ++tot;
tid[tot] = u;
top[u] = t;
if(bs[u] != -1)
dfs2(bs[u], t);
for(auto v : e[u])
{
if(v.fi == bs[u] || v.fi == f[u]) continue;
dfs2(v.fi, v.fi);
}
r[u] = tot;
}
struct info
{
ll s, mav, miv;
};
info operator + (const info &a, const info &b)
{
return (info){a.s + b.s, max(a.mav, b.mav), min(a.miv, b.miv)};
}
struct segtree
{
struct info val;
int tag;
}seg[N * 4];
void update(int id)
{
seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}
void settag(int id, int tag)
{
seg[id].tag += tag, seg[id].tag %= 2;
swap(seg[id].val.mav, seg[id].val.miv);
seg[id].val = {-seg[id].val.s, -seg[id].val.mav, -seg[id].val.miv};
}
void pushdown(int id)
{
if(seg[id].tag == 1)
{
settag(id * 2, seg[id].tag);
settag(id * 2 + 1, seg[id].tag);
seg[id].tag = 0;
}
}
void build(int id, int l, int r)
{
seg[id].tag = 0;
if(l == r)
{
seg[id].val = {w[tid[l]], w[tid[l]], w[tid[l]]};
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
void change(int id, int l, int r, int pos, ll ew)
{
if(l == r)
{
seg[id].val = {ew, ew, ew};
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(pos <= mid)
change(id * 2, l, mid, pos, ew);
else if(pos > mid)
change(id * 2 + 1, mid + 1, r, pos, ew);
update(id);
}
void modify(int id, int l, int r, int ql, int qr, ll tag)
{
if(ql > qr || l > r) return;
if(l == ql && r == qr)
{
settag(id, tag);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
modify(id * 2, l, mid, ql, qr, tag);
else if(ql > mid)
modify(id * 2 + 1, mid + 1, r, ql, qr, tag);
else
{
modify(id * 2, l, mid, ql, mid, tag);
modify(id * 2 + 1, mid + 1, r, mid + 1, qr, tag);
}
update(id);
}
info query(int id, int l, int r, int ql, int qr)
{
if((ql > qr || l > r)) return (info){0, -100000000, 100000000};
if(l == ql && r == qr)
{
return seg[id].val;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
return query(id * 2, l, mid, ql, qr);
else if(ql > mid)
return query(id * 2 + 1, mid + 1, r, ql, qr);
else
{
return query(id * 2, l, mid, ql, mid) +
query(id * 2 + 1, mid + 1, r, mid + 1, qr);
}
update(id);
}
void modify(int u, int v, ll k)
{
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]])
{
modify(1, 1, n, l[top[u]], l[u], k);
u = f[top[u]];
}
else
{
modify(1, 1, n, l[top[v]], l[v], k);
v = f[top[v]];
}
}
if(dep[u] < dep[v]) swap(u, v);
modify(1, 1, n, l[v] + 1, l[u], k);
}
info query(int u, int v)
{
info ans = (info){0, -100000000, 100000000};
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]])
{
ans = ans + query(1, 1, n, l[top[u]], l[u]);
u = f[top[u]];
}
else
{
ans = ans + query(1, 1, n, l[top[v]], l[v]);
v = f[top[v]];
}
}
if(dep[u] < dep[v]) swap(u, v);
ans = ans + query(1, 1, n, l[v] + 1, l[u]);
return ans;
}
void solve()
{
cin>>n;
for(int i = 1; i < n; i++)
{
int u, v, w; cin>>u>>v>>w;
u++, v++;
edge[i] = {u, v};
e[u].push_bcak({v, w});
e[v].push_bcak({u, w});
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
cin>>q;
while(q--)
{
string op; cin>>op;
if(op == "C")
{
int i, w; cin>>i>>w;
int u = edge[i].fi, v = edge[i].se;
if(dep[u] < dep[v]) swap(u, v);
change(1, 1, n, l[u], w);
}
else if(op == "N")
{
int u, v;
cin>>u>>v;
u++, v++;
modify(u, v, 1);
}
else if(op == "SUM")
{
int u, v;
cin>>u>>v;
u++, v++;
cout<<query(u, v).s<<endl;
}
else if(op == "MAX")
{
int u, v;
cin>>u>>v;
u++, v++;
cout<<query(u, v).mav<<endl;
}
else if(op == "MIN")
{
int u, v;
cin>>u>>v;
u++, v++;
cout<<query(u, v).miv<<endl;
}
}
}
ST表
const int LOGN = 21;
const int N = 100000;
int f[N + 10][LOGN + 2], LOG[N + 10];
int n, m;
void pre()
{
LOG[1] = 0, LOG[2] = 1;
for(int i = 3; i <= N; i++)
LOG[i] = LOG[i / 2] + 1;
for(int j = 1; j <= LOGN; j++)
{
for(int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>f[i][0];
pre();
for(int i = 1; i <= m; i++)
{
cin>>x>>y;
int s = LOG[y - x + 1];
cout<<max(f[x][s], f[y - (1 << s) + 1][s])<<endl;
}
return;
}
ST 表封裝
const int N = 2e5 + 10;
const int LOGN = 20; // 2 ^ 20 = 1048576
struct S_T {
// op 函數需要支持兩個可以重疊的區間進行合并
// 例如 min、 max、 gcd、 lcm 等
int f[LOGN + 2][N], lg[N];
void build(int n) {
lg[0] = -1;
for(int i = 1; i <= n; ++i) {
f[0][i] = ; // 手動指定原始數組
lg[i] = lg[i / 2] + 1;
}
for(int i = 1; i <= LOGN; ++i)
for(int j = 1; j + (1 << i) - 1 <= n; ++j)
f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r) {
int len = lg[r - l + 1];
return max(f[len][l], f[len][r - (1 << len) + 1]);
}
}ST;
DSU ON TREE
const int N = 1e5 + 10;
int n, k;
vector<int> e[N];
int l[N], r[N], id[N], sz[N], hs[N], tot;
inline void add(int u)
{
}
inline void del(int u)
{
}
inline void query(int k, int u)
{
}
void dfs_init(int u,int f) {
l[u] = ++tot;
id[tot] = u;
sz[u] = 1;
hs[u] = -1;
for (auto v : e[u]) {
if (v == f) continue;
dfs_init(v, u);
sz[u] += sz[v];
if (hs[u] == -1 || sz[v] > sz[hs[u]])
hs[u] = v;
}
r[u] = tot;
}
void dfs_solve(int u, int f, bool keep) {
for (auto v : e[u]) {
if (v != f && v != hs[u]) {
dfs_solve(v, u, false);
}
}
if (hs[u] != -1) {
dfs_solve(hs[u], u, true);
}
for (auto v : e[u]) {
if (v != f && v != hs[u]) {
for (int x = l[v]; x <= r[v]; x++)
query(id[x]);
for (int x = l[v]; x <= r[v]; x++)
add(id[x]);
}
}
//query(u);
add(u);
if (!keep) {
for(int x = l[u]; x <= r[u]; x++)
del(id[x]);
}
}
void solve()
{
cin>>n;
for (int i = 1; i < n; i++) {
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs_init(1, 0);
dfs_solve(1, 0, false);
}
LCA
#include<bits/stdc++.h>
using namespace std;
const int N = 5000010;
const int LOGN = 20;
int n, m, root, dep[N], fa[N][LOGN + 2];
vector<int> e[N];
void dfs(int u, int from)
{
dep[u] += dep[from] + 1;
for(auto v : e[u]) {
if(v == from) continue;
fa[v][0] = u;
dfs(v, u);
}
}
void lca_init()
{
for(int j = 1; j <= LOGN; j++)
for(int i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int j = LOGN; j >= 0; j--)
if(d & (1 << j))
u = fa[u][j];
if(u == v) return u;
for(int j = LOGN; j >= 0; j--)
if(fa[u][j] != fa[v][j])
u = fa[u][j], v = fa[v][j];
return fa[u][0];
}
int main()
{
cin>>n>>m>>root;
for(int i = 2; i <= n; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(root, 0);
lca_init();
while(m--)
{
int u, v; cin>>u>>v;
cout<<lca_query(u, v)<<endl;
}
return 0;
}
笛卡爾樹
int n, a[N], l[N], r[N], ans[N], cnt;
void dfs(int x)
{
ans[x] = ++cnt;
if(l[x]) dfs(l[x]);
if(r[x]) dfs(r[x]);
}
void build()
{
stack<int> st;
int root = 0;
for(int i = 1; i <= n; i++)
{
int last = 0;//在棧里面最后一個被彈出的節點
while(!st.empty() && a[st.top()] > a[i])
{
last = st.top();
st.pop();
}
if(!st.empty()) r[st.top()] = i;//新加入的元素設為棧頂元素的右兒子
else root = i;
l[i] = last;
st.push(i);
}
// for(int i = 1;i<=n;i++)
// cout<<"i = "<<i<<" a[i] = "<<a[i]<<" l[i] = "<<l[i]<<" r[i] = "<<r[i]<<endl;
dfs(root);
}
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
cin>>a[i];
build();
for(int i = 1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<'\n';
}
Graph
樹的重心
int idx, ans = N, n;
vector<int> e[N];
int dfs(int u, int fa)
{
int size = 0, sum = 0;
for(auto v : e[u])
{
if(v == fa) continue;
int s = dfs(v, u);
size = max(size, s);
sum += s;
}
size = max(size, n - sum - 1);
ans = min(ans, size);
return sum + 1;
}
// cout<<ans<<endl;
拓撲排序
int n, m, d[N], l[N], tot;
vector<int> e[N];
void toposort()
{
queue<int> q;
for(int i = 1; i <= n; i++)
if(d[i] == 0)
q.push(i);
while(!q.empty())
{
int u = q.front(); q.pop();
l[++tot] = u;
for(auto v : e[u])
if(--d[v] == 0)
q.push(v);
}
for(int i = 1; i <= n; i++)
if(d[i] > 0)
{
cout<<"Yes"<<endl; // 是否存在toposort
//輸出toposort序列
for(int j = 1; j <= tot; j++)
cout<<l[j]<<" ";
cout<<endl;
return;
}
cout<<"No"<<endl;
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int x , y; cin>>x>>y;
son[x].push_back(y);
d[y]++;
}
toposort();
return;
}
歐拉圖
定義
通過圖中所有邊恰好一次的通路稱為歐拉通路。
通過圖中所有邊恰好一次的回路稱為歐拉回路。
具有歐拉回路的無向圖或有向圖稱為歐拉圖。
具有歐拉通路但不具有歐拉回路的無向圖或有向圖稱為半歐拉圖。
有向圖也可以有類似的定義。
非形式化地講，歐拉圖就是從任意一個點開始都可以一筆畫完整個圖，半歐拉圖必須從某個點開始才能一筆畫完整個圖。
性質
歐拉圖中所有頂點的度數都是偶數。
若 G是歐拉圖，則它為若干個環的并，且每條邊被包含在奇數個環內。
判別法
對于無向圖G ， G是歐拉圖當且僅當 G 是連通的且沒有奇度頂點。
對于無向圖G ， G是半歐拉圖當且僅當 G是連通的且 G 中恰有 0個或 2個奇度頂點。
對于有向圖 G， G是歐拉圖當且僅當 G的所有頂點屬于同一個強連通分量且每個頂點的入度和出度相同。
對于有向圖 G， G是半歐拉圖當且僅當
? 如果將G 中的所有有向邊退化為無向邊時，那么 G的所有頂點屬于同一個連通分量。
? 最多只有一個頂點的出度與入度差為 1。
? 最多只有一個頂點的入度與出度差為 1。
? 所有其他頂點的入度和出度相同。
有向圖
//單詞接龍
#include<bits/stdc++.h>
using namespace std;
std::vector<int> e[27];
int n, m, l, f[27], c[100002], ind[27], outd[27], v[27];
inline void dfs(int x)
{
while(f[x] < v[x]) //當前邊存在
{
int y = e[x][f[x]];
++f[x];
dfs(y);
c[++l] = y;
}
}
inline void Euler()
{
int x = 0, y = 0, z = 0;//x起點，y有多少入度比出度大一，有多少入度不等于出度
for(int i = 1;i <= n; i++)
{
if(outd[i] == ind[i] + 1) y++, x = i;
if(outd[i] != ind[i]) z++;
}
if(!(!z || (y == 1 && z == 2)))
{
cout<<"No\n";
return;
}
if(!x)
for(int i = 1 ; i <= n; i++)
if(ind[i])
x = i;
memset(f, 0, sizeof(f));//表示看到當前的第幾條邊
l = 0;
dfs(x);
c[++l] = x;
if(l == m + 1) cout<<"Yes\n";//注意要判斷連通性,l==m+1,說明經過了m條邊
else cout<<"No\n";
}
int main()
{
n = 26;
cin>>m;
for(int i = 1; i <= m; i++)
{
char str[101];
cin>>str;
int x = str[0]- 'a' + 1, y = str[strlen(str) - 1] - 'a' + 1;
e[x].push_back(y);
++v[x]; //這里的v[x]其實就是outd,記錄每個點連出去多少條邊
++outd[x];
++ind[y];
}
Euler();
return 0;
}
無向圖是否存在歐拉路
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node{
int y, idx;
Node(int _y, int _idx){ y = _y, idx = _idx; };
};
vector<Node> e[N];
int n, m, cnt = 1, l, f[N], c[N], d[N], v[N];
bool b[N * 2];
inline void dfs(int x)
{
while(f[x] < v[x])//當前邊存在
{
int y = e[x][f[x]].y, idx = e[x][f[x]].idx;
if(!b[idx])
{
++f[x];
b[idx] = b[idx ^ 1]=true;
dfs(y);
c[++l] = y;
}
else ++f[x];
}
}
inline void Euler()
{
int x = 0, y = 0;//記錄度數為奇數點的個數
for(int i = 1 ; i <= n; i++)
if(d[i] & 1)
++y, x = i;
if(y && y != 2)
{
cout<<"No\n";
return;
}
if(!x)
for(int i = 1;i <= n; i++)
if(d[i])
x = i;
memset(b, false, sizeof(b));
memset(f, 0, sizeof(f));
l = 0;
dfs(x);
c[++l] = x;
if(l != m + 1)
cout<<"No\n";
else
cout<<"Yes\n";
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v;
cin>>u>>v;
e[u].push_back({v, ++cnt});
e[v].push_back({u, ++cnt});
++d[u];
++d[v];
}
for(int i = 1; i <= n; i++)
v[i] = e[i].size();
Euler();
return 0;
}
分層圖
分層圖
一般模型：
在圖上,有 \(k\) 次機會可以直接通過一條邊,問起點與終點之間的最短路徑.
時間復雜度 \(O(Mk \log (Nk))\)
注意：
1.編號為 \(i\) 的點在第 \(j\) 層的編號是 \(i+j*n\)
2.記得數組開4倍
3.層與層之間單向邊
const int N = 1e5 + 10;
int n, m, k, s, t;
vector<pair<int, int>> e[N * 4];
int dist[N * 4];
bool vis[N * 4];
void dijkstra(int s)
{
priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
q.push({0, s});
while(q.size() >= 1)
{
auto t = q.top(); q.pop();
int u = t.second;
if(vis[u]) continue;
vis[u] = true;
for(auto v : e[u])
{
if(dist[v.first] > dist[u] + v.second)
{
dist[v.first] = dist[u] + v.second;
q.push({dist[v.first], v.first});
}
}
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
cin>>s>>t;
s++, t++;
for(int i = 1; i <= m; i++)
{
int u, v, w; cin>>u>>v>>w;
u++, v++;
e[u].push_back({v, w});
e[v].push_back({u, w});
for(int j = 1;j<=k;j++)
{
//層于層之間對應點連一條權值為0的邊
e[(u + (j - 1) * n)].push_back({v + (j * n), 0});
e[(v + (j - 1) * n)].push_back({u + (j * n), 0});
//每一層對應點的連邊
e[(u + j * n)].push_back({v + j * n, w});
e[(v + j * n)].push_back({u + j * n, w});
}
}
dijkstra(s);
int ans = 1e9;
for(int i = 0; i <= k; i++)
ans = min(ans, dist[t + i * n]);
cout<<ans<<'\n';
return 0;
}
Dijkstra
\(O(N\log M)\)
int n, m, dist[N];
vector<pair<int, int>> e[N];
bool vis[N];
void dijkstra(int start)
{
priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
memset(dist, 0x3f, sizeof dist);
memset(vis, false, sizeof vis);
dist[start] = 0;
q.push({0, start});
while(q.size() >= 1)
{
auto t = q.top(); q.pop();
int u = t.second;
if(vis[u]) continue;
vis[u] = true;
for(auto [v, w] : e[u])
{
if(dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
}
}
\(O(N^2)\)
int n, m, g[N][N], dist[N];
bool st[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n - 1; i++)
{
int t = -1;
for(int j = 1; j <= n; j++)
{
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
for(int j = 1; j <= n; j++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
void solve()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
cout << dijkstra();
return;
}
Bellman-ford \(O(NM)\)
int n, m, k, dist[N], backup[N];
struct EDGES
{
int a, b, w;
}edge[M];
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < k; i++)
{
memcpy(backup, dist, sizeof dist);
for(int j = 0; j < m; j++)
{
auto e = edge[j];
dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
}
}
}
void solve()
{
cin >> n >> m >> k;
for(int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
edge[i] = {u, v, w};
}
bellman_ford();
return;
}
SPFA 判負環
const int N = 4e5 + 10, M = 1e4 + 10;
bool in[N];
int cnt[N],h[N];
inline bool spfa_check_negative_ring(int s, int n)
{
memset(h, 127, sizeof(h));
memset(in, false, sizeof(in));
memset(cnt, 0, sizeof(cnt));
queue<int> q;
h[s] = 0;
in[s] = true;
cnt[s] = 1;
q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
in[u] = false;
for(auto [v, w]: edge[u])
{
if(h[u] + w < h[v])
{
h[v] = h[u] + w;
if(!in[v])
{
q.push(v);
cnt[v]++;
in[v]=true;
if(cnt[v]>=n)
{
return true;
}
}
}
}
}
return false;
}
SPFA 次短路
- 更新了最小距離，要把上次的最小距離先拿給次小距離，因為上次的最小距離就是比當前距離大且最小的距離（即為次短距離）。
- 雖然可能當前路徑無法更新最小距離，但可能更新次小距離，要加判斷
- 從上一個點的次短距離更新這一個點的次短距離
const int N = 10100;
int n, m;
vector<pair<int, int>> edge[N];
int dist[2][N], c[N];
bool in[5001];//是否在隊列里面
int sum;
inline void spfa(int s)
{
memset(dist, 127, sizeof(dist));
memset(in, false, sizeof(in));
queue<int> q;
dist[0][s] = 0;
dist[1][s] = 0;
in[s] = true;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
in[u] = false;
for(auto [v, w] : edge[u])
{
if(dist[0][u] + w < dist[0][v])
{ //更新最短路
dist[1][v] = dist[0][v];
dist[0][v] = dist[0][u] + w;
if(!in[v]){
q.push(v);
in[v] = true;
}
}
if((dist[1][v] > dist[0][u] + w && dist[0][u] + w > dist[0][v]) ||
dist[1][v] == dist[0][v])
{ //當前不能更新最短路，但可以更新次短路
dist[1][v] = dist[0][u] + w;
if(!in[v]){
q.push(v);
in[v] = true;
}
}
if(dist[1][v] > dist[1][u] + w && dist[1][u] + w > dist[0][v])
{ //用次短路更新次短路
dist[1][v] = dist[1][u] + w;
if(!in[v]){
q.push(v);
in[v] = true;
}
}
}
}
return;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin>>u>>v>>w;
edge[u].push_back({v, w});
edge[v].push_back({u, w});
}
spfa(1);
cout<<dist[1][n]<<"\n";
return 0;
}
Floyd \(O(N^3)\)
int d[N][N];
void floyd()
{
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
d[u][v] = min(d[u][v], w);
}
floyd();
return;
}
Johnson 全源最短路 稀疏圖\(O(NM \log M)\) 最慢 \(O((N + M) \times (C + 1))\)，\(C\) 是環數
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int N = 3e3 + 10, M = 1e4 + 10;
// 邊數是 N + M
vector<pair<int, int>>edge[M];
int n, m, k;
int c[N], cnt[N];
ll dist[N], h[N];
bool in[N];
bool vis[N];
void dijkstra(int start)
{
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
memset(vis, false, sizeof vis);
for(int i = 0; i <= n; i++)
dist[i] = INF;
dist[start] = 0;
q.push({0, start});
while(q.size() >= 1)
{
auto t = q.top(); q.pop();
int u = t.second;
if(vis[u]) continue;
vis[u] = true;
for(auto [v, w] : edge[u])
{
if(dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
}
}
inline bool spfa_check_negative_ring(int s, int n)
{
memset(h, 127, sizeof(h));
memset(in, false, sizeof(in));
memset(cnt, 0, sizeof(cnt));
queue<int> q;
h[s] = 0;
in[s] = true;
cnt[s] = 1;
q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
in[u] = false;
for(auto [v, w]: edge[u])
{ //x連出去的邊i
if(h[u] + w < h[v])
{
h[v] = h[u] + w;
if(!in[v])
{
q.push(v);
cnt[v]++;
in[v]=true;
if(cnt[v]>=n)
{
return true;
}
}
}
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin>>u>>v>>w;
edge[u].push_back({v, w});
}
for(int i = 1; i <= n; i++)
edge[0].push_back({i, 0});
if(spfa_check_negative_ring(0, n))
{
cout<<-1<<"\n";
return 0;
}
for(int u = 1; u <= n; u++)
{
for(auto &[v, w] : edge[u])
{
w += h[u] - h[v];
}
}
for(int i = 1; i <= n; i++)
{
dijkstra(i);
ll ans = 0;
for(int j = 1; j <= n; j++)
{
if(dist[j] == INF)
ans += 1ll * j * INF;
else ans += 1ll * j * (dist[j] + h[j] - h[i]);
}
cout<<ans<<"\n";
}
return 0;
}
最小生成樹
Kruskal \(O(M\log M)\)
int n, m, p[N];
struct Edge
{
int u, v;
ll w;
bool operator <(const Edge& W)const
{
return w < W.w;
}
}edge[M];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void kruskal()
{
sort(edge + 1, edge + 1 + m);
ll res = 0;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= m; i++)
{
int u = edge[i].u, v = edge[i].v;
ll w = edge[i].w;
int fu = find(u), fv = find(v);
if (fu != fv)
{
p[fu] = fv;
res += w;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v; ll w; cin >> u >> v >> w;
edge[i] = {u, v, w};
}
kruskal();
}
Kruskal 重構樹
修改點邊數量 點數開兩倍 kruskal_Rebuild_Tree 同樣
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 4e5 + 10, M = 5e5+10;
const int LOGN = 20;
struct Node
{
int u, v, w;
}a[M + 1];
int n, m, q, now, fa[N][LOGN + 2], dep[N];
vector<int> e[N];
int ls[N], rs[N], val[N];
ll sum[N], c[N], dp[N];
//////////////////////////////DSU//////////////////////////////////////
struct Dsu {
int fa[N];
void init(int x) {for(int i = 1; i <= x; i++) fa[i] = i;}
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void merge(int x, int y) {
int u = find(x), v = find(y);
if(u == v) return;
fa[u] = v;
}
}dsu;
/////////////////////////Kruskal////////////////////////////////////
void kruskalRebuildTree()
{
dsu.init(2 * n - 1);
sort(a + 1, a + 1 + m, [](const Node& x, const Node& y) {
//return x.w > y.w; //最大生成樹(最小值最大)
return x.w < y.w; //最小生成樹(最大值最小)
});
now = n;
for(int i = 1; i <= m; i++) {
ll u = dsu.find(a[i].u), v = dsu.find(a[i].v), w = a[i].w;
if(u != v) {
val[++now] = w;
dsu.merge(u, now);
dsu.merge(v, now);
// e[now].push_back(u);
// e[now].push_back(v);
ls[now] = u;
rs[now] = v;
}
}
}
////////////////////////////DP///////////////////////////////////
void dfs(int u)
{
if(!ls[u] || !rs[u])
{
sum[u] = c[u];
dp[u] = INF;
return;
}
dfs(ls[u]), dfs(rs[u]);
sum[u] = sum[ls[u]] + sum[rs[u]];
// 先吃ls[u]
dp[u] = max(min(dp[rs[u]], val[u]) - sum[ls[u]],
min(dp[ls[u]], val[u]) - sum[rs[u]]);
}
////////////////////////////Main///////////////////////////////////
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>c[i];
for(int i = 1; i <= m; i++)
cin>>a[i].u>>a[i].v>>a[i].w;
kruskalRebuildTree();
dfs(now);
return 0;
}
Prim \(O(N^2)\)，稀疏圖可以用堆優化\(O(M\log N)\)，但Kruskal更好
int n, m, g[N][N], dist[N];
bool st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for(int i = 0; i < n; i++)
{
int t = -1;
for (int j = 1; j <= n; j++)
{
if(st[j] == false && (t == -1 || dist[t] > dist[j]))
t = j;
}
if(i && dist[t] == INF) return INF;
if(i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main()
{
memset(g, 0x3f, sizeof g);
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int u, v, c;
cin >> u >> v >> c;
g[u][v] = g[v][u] = min(g[u][v], c);
}
int t = prim();
if(t == INF) cout << "impossible";
else cout << t;
return 0;
}
二分圖
二分圖染色 \(O(N + M)\)
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<int> e[1010];
int n, m, c[1010];
bool dfs(int u)
{
for(auto v : e[u])
{
if(c[v] == 0)
{
c[v] = 3 - c[u];
if(!dfs(v))
return false;
}
else if(c[u] == c[v])
return false;
}
return true;
}
bool check()
{
memset(c, 0 ,sizeof c);
for(int i = 1; i <= n; i++)
{
if(c[i] == 0)
{
c[i] = 1;
if(!dfs(i))
return false;
}
}
return true;
}
int main()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
if(check())
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
二分圖最大匹配 \(O(NM)\)
const int N = 2e6 + 10;
int n, n1, n2, m, v[N];
int b[N];
vector<int> e[N];
int now;
bool find(int x)
{
b[x] = now;
for(auto &y : e[x])
{
if(!v[y] || (b[v[y]] != now && find(v[y])))
{
b[v[y]] = now;
v[y] = x;
return true;
}
}
return false;
}
int match()
{
memset(v, 0, sizeof v);
for(int i = 1; i < 1e6 + 10;i++)
{
// memset(b,0,sizeof(b));
++now;
if(!find(i))
{
return i-1;
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
n1 = n;
// 建圖 染色
cout<<match()<<endl;
return 0;
}
連通性相關
SCC Trajan
vector<int> edge[N];
int n, m;
int dfn[N], low[N], ins[N], idx, bel[N], cnt, sz[N];//sz：每個強連通分量的size
// low記這個子樹里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
stack<int> stk;
void dfs(int u)
{
dfn[u] = low[u] = ++idx;
ins[u] = true;
stk.push(u);//還沒被切掉的點
for(auto v : edge[u])
{
if(!dfn[v]) dfs(v);
if(ins[v]) low[u] = min(low[u], low[v]);
}
if(dfn[u] == low[u]){
++cnt;
while(1)
{
int v = stk.top(); stk.pop();
ins[v] = false;
bel[v] = cnt;
sz[cnt]++;
if(u == v)break;
}
}
}
void tarjan()
{
for(int i = 1; i <= n; i++)
if(!dfn[i]) dfs(i);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v; cin>>u>>v;
edge[u].push_back(v);
}
tarjan();
}
SCC Kosaraju
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 101000;
vector<int> edge[N], erev[N];
vector<int> out;
int n, m;
bool vis[N];
void dfs(int u)
{
vis[u] = true;
for(auto v : edge[u])
{
if(!vis[v]) dfs(v);
}
out.push_back(u);
}
void dfs2(int u)
{
vis[u] = true;
for(auto v : erev[u])
{
if(!vis[v]) dfs2(v);
}
}
void kosaraju()
{
for(int i = 1; i <= n; i++)
{
if(!vis[i]) dfs(i);
}
reverse(out.begin(), out.end());
memset(vis, false, sizeof(vis));
for(auto u : out)
{
if(!vis[u])
{
dfs2(u);
}
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v; cin>>u>>v;
edge[u].push_back(v);
erev[v].push_back(u);
}
kosaraju();
}
縮點
vector<int> edge[N];
int n, m;
int dfn[N], low[N], ins[N], idx, bel[N], cnt, sz[N];//sz：每個強連通分量的size
// low記這個子樹里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
stack<int> stk;
ll ans, dp[N];
int a[N];
void dfs(int u)
{
dfn[u] = low[u] = ++idx;
ins[u] = true;
stk.push(u);//還沒被切掉的點
for(auto v : edge[u])
{
if(!dfn[v]) dfs(v);
if(ins[v]) low[u] = min(low[u], low[v]);
}
if(dfn[u] == low[u]){
++cnt;
dp[cnt] = 0;
ll sval = 0;
while(1)
{
int x = stk.top(); stk.pop();
ins[x] = false;
bel[x] = cnt;
sz[cnt]++;
sval += a[x];
for(auto y : edge[x])
{
if(bel[y] != cnt && bel[y] != 0)
dp[cnt] = max(dp[cnt], dp[bel[y]]);
}
if(u == x)break;
}
dp[cnt] += sval;
ans = max(ans, dp[cnt]);
}
}
void tarjan()
{
for(int i = 1; i <= n; i++)
{
if(!dfn[i]) dfs(i);
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= n; i++)
cin>>a[i];
for(int i = 1; i <= m; i++)
{
int u, v; cin>>u>>v;
edge[u].push_back(v);
}
tarjan();
cout<<ans<<endl;
}
割點（圖不一定聯通）
const int N = 101000;
vector<int> edge[N];
int n, m, idx, sz;
int dfn[N], low[N], cut[N];
// low記這個子樹里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
void dfs(int u, int fa, int root)
{
dfn[u] = low[u] = ++idx;
int ch = 0;//記兒子個數
for(auto v : edge[u])
{
if(!dfn[v]) {
dfs(v, u, root);
ch++;
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) cut[u] = 1;//跳不出去了，說明它是割點
}
else if(v != fa)//返祖邊
{
low[u] = min(low[u], dfn[v]);//?這里就不能亂寫了，要對dfn取min了
}
}
if(u == root && ch <= 1) cut[u] = 0;
sz += cut[u];
}
int main()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v; cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for(int i = 1; i <= n; i++)
if(!dfn[i])
dfs(i, 0, i);
cout<<sz<<"\n";
for(int i = 1; i <= n; i++)
if(cut[i])
cout<<i<<"\n";
}
割邊
const int N = 101000;
vector<pair<int, int>> edge[N];
int n, m, idx;
int dfn[N], low[N];
vector<int>bridge;
void dfs(int u,int id)
{
dfn[u] = low[u] = ++idx;
for(auto [v, id2] : edge[u])
{
if(!dfn[v]){
dfs(v, id2);
low[u] = min(low[u], low[v]);
if(dfn[v] == low[v]) bridge.push_back(id2);
}
else if(id != id2){
//要看它是父親直接下來的邊，還是返祖邊，因為不能把樹邊當成返祖邊去更新low,那么這里只要不是父親就可以了
//?注意：這里要寫它邊的編號不是它父親連下來的邊的編號，而不是說判這個點是不是父親
//因為單純判是不是父親的話，會把重邊判成同一條邊，這樣是錯的。因為重邊是會影響是不是割邊
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v; cin>>u>>v;
edge[u].push_back({v, i});
edge[v].push_back({u, i});
}
dfs(1, -1);
sort(bridge.begin(), bridge.end());
cout<<bridge.size()<<"\n";
for(auto x : bridge)
cout<<x<<" ";
cout<<endl;
}
(e-DCC)Tarjan邊雙縮點
const int N = 101000;
vector<pair<int, int>>edge[N];
int n, m;
int dfn[N], low[N], idx, bel[N], cnt;
stack<int> stk;
vector<int> cc[N];
void dfs(int u, int id)
{
dfn[u] = low[u] = ++idx;
stk.push(u);
for(auto [v, id2] : edge[u])
{
if(!dfn[v]){
dfs(v, id2);
low[u] = min(low[u], low[v]);
}
else if(id != id2){
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]){
++cnt;
while(1)
{
int v = stk.top();
cc[cnt].push_back(v);
bel[v] = cnt;
stk.pop();
if(u == v) break;
}
}
}
int main()
{
cin>>n>>m;
for(int i = 1; i <= m; i++)
{
int u, v; cin>>u>>v;
edge[u].push_back({v, i});
edge[v].push_back({u, i});
}
dfs(1, -1);
int nleaf = 0;
for(int i = 1; i<= cnt; i++)
{
int cnte = 0;
for(auto u : cc[i])
for(auto [v, id] : edge[u])
cnte += (bel[u] != bel[v]);
nleaf += (cnte == 1);//度為1的點是葉子
}
cout<<(nleaf + 1) / 2<<"\n";
}
2 - SAT \(O(\texttt{最短路算法})\)
typedef long long ll;
const int N = 101000;
vector<int> edge[N];
int n, m;
int dfn[N], low[N], ins[N], idx, bel[N], cnt;
stack<int> stk;
void dfs(int u)
{
dfn[u] = low[u] = ++idx;
ins[u] = true;
stk.push(u);
for(auto v : edge[u])
{
if(!dfn[v]) dfs(v);
if(ins[v]) low[u] = min(low[u], low[v]);
}
if(dfn[u] == low[u]){
++cnt;
while(1)
{
int v = stk.top();
ins[v] = false;
bel[v] = cnt;
stk.pop();
if(u == v) break;
}
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t; cin>>t;
while(t--)
{
cin>>n>>m;
//標號0...2n-1 對于滿式mi:2*i,hi:2*i+1
for(int i = 0; i < 2 * n; i++)
dfn[i] = 0, edge[i].clear();
idx = cnt = 0;
for(int i = 1; i <= m; i++)
{
char ty1, ty2;
int u, v;
cin>>ty1>>u>>ty2>>v;
--u, --v;
u = u * 2 + (ty1 == 'h');
v = v * 2 + (ty2 == 'h');
edge[u ^ 1].push_back(v);
edge[v ^ 1].push_back(u);
}
for(int i = 0; i < 2 * n; i++)
{
if(!dfn[i])
dfs(i);
}
bool ok = true;
for(int i = 0; i < n; i++)
{
// bel[2 * i] < bel[2 * i + 1]選 2 * i
if(bel[2 * i]==bel[2 * i + 1])
{
ok = false;
break;
}
}
if(ok)
cout<<"GOOD\n";
else
cout<<"BAD\n";
}
}
計算幾何
模塊1
typedef double db;
const db EPS = 1e-9;
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(db a, db b){ return sign(a-b); }
struct P {
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p) const {
int c = cmp(x, p.x);
if (c) return c == -1;
return cmp(y, p.y) == -1;
}
bool operator==(P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p) { return x * p.x + y * p.y; }
db det(P p) { return x * p.y - y * p.x; }
db distTo(P p) { return (*this-p).abs(); }
db alpha() { return atan2(y, x); }
void read() { cin>>x>>y; }
void write() {cout<<"("<<x<<","<<y<<")"<<endl;}
db abs() { return sqrt(abs2());}
db abs2() { return x * x + y * y; }
P rot90() { return P(-y,x);}
P unit() { return *this/abs(); }
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
P rot(db an){ return {x*cos(an) - y*sin(an),x*sin(an) + y*cos(an)}; }
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
// 直線 p1p2, q1q2 是否恰有一個交點
bool chkLL(P p1, P p2, P q1, P q2) {
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return sign(a1+a2) != 0;
}
// 求直線 p1p2, q1q2 的交點
P isLL(P p1, P p2, P q1, P q2) {
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return (p1 * a2 + p2 * a1) / (a1 + a2);
}
// 判斷區間 [l1, r1], [l2, r2] 是否相交
bool intersect(db l1,db r1,db l2,db r2){
if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2);
return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}
// 線段 p1p2, q1q2 相交
bool isSS(P p1, P p2, P q1, P q2){
return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) &&
crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) <= 0;
}
// 線段 p1p2, q1q2 嚴格相交
bool isSS_strict(P p1, P p2, P q1, P q2){
return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) < 0;
}
// m 在 a 和 b 之間
bool isMiddle(db a, db m, db b) {
/*if (a > b) swap(a, b);
return cmp(a, m) <= 0 && cmp(m, b) <= 0;*/
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
bool isMiddle(P a, P m, P b) {
return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
// 點 p 在線段 p1p2 上
bool onSeg(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
// q1q2 和 p1p2 的交點 在 p1p2 上？
// 點 p 嚴格在 p1p2 上
bool onSeg_strict(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}
// 求 q 到 直線p1p2 的投影（垂足） ?? : p1 != p2
P proj(P p1, P p2, P q) {
P dir = p2 - p1;
return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
// 求 q 以 直線p1p2 為軸的反射
P reflect(P p1, P p2, P q){
return proj(p1,p2,q) * 2 - q;
}
// 求 q 到 線段p1p2 的最小距離
db nearest(P p1, P p2, P q){
if (p1 == p2) return p1.distTo(q);
P h = proj(p1,p2,q);
if(isMiddle(p1,h,p2))
return q.distTo(h);
return min(p1.distTo(q),p2.distTo(q));
}
// 求 線段p1p2 與 線段q1q2 的距離
db disSS(P p1, P p2, P q1, P q2){
if(isSS(p1,p2,q1,q2)) return 0;
return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)), min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
// 極角排序
sort(p, p + n, [&](P a, P b) {
int qa = a.quad(), qb = b.quad();
if (qa != qb) return qa < qb;
else return sign(a.det(b)) > 0;
});
模塊2
db area(vector<P> ps){
db ret = 0; rep(i,0,ps.size()) ret += ps[i].det(ps[(i+1)%ps.size()]);
return ret/2;
}
int contain(vector<P> ps, P p){ //2:inside,1:on_seg,0:outside
int n = ps.size(), ret = 0;
rep(i,0,n){
P u=ps[i],v=ps[(i+1)%n];
if(onSeg(u,v,p)) return 1;
if(cmp(u.y,v.y)<=0) swap(u,v);
if(cmp(p.y,u.y) > 0 || cmp(p.y,v.y) <= 0) continue;
ret ^= crossOp(p,u,v) > 0;
}
return ret*2;
}
vector<P> convexHull(vector<P> ps) {
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
qs.resize(k - 1);
return qs;
}
vector<P> convexHullNonStrict(vector<P> ps) {
//caution: need to unique the Ps first
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
qs.resize(k - 1);
return qs;
}
db convexDiameter(vector<P> ps){
int n = ps.size(); if(n <= 1) return 0;
int is = 0, js = 0; rep(k,1,n) is = ps[k]<ps[is]?k:is, js = ps[js] < ps[k]?k:js;
int i = is, j = js;
db ret = ps[i].distTo(ps[j]);
do{
if((ps[(i+1)%n]-ps[i]).det(ps[(j+1)%n]-ps[j]) >= 0)
(++j)%=n;
else
(++i)%=n;
ret = max(ret,ps[i].distTo(ps[j]));
}while(i!=is || j!=js);
return ret;
}
vector<P> convexCut(const vector<P>&ps, P q1, P q2) {
vector<P> qs;
int n = ps.size();
rep(i,0,n){
P p1 = ps[i], p2 = ps[(i+1)%n];
int d1 = crossOp(q1,q2,p1), d2 = crossOp(q1,q2,p2);
if(d1 >= 0) qs.push_back(p1);
if(d1 * d2 < 0) qs.push_back(isLL(p1,p2,q1,q2));
}
return qs;
}
#include <bits/stdc++.h>
using namespace std;
typedef double db;
#define rep(i, a, n) for (int i = a; i < n; i++)
const db EPS = 1e-9;
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
inline int cmp(db a, db b){ return sign(a-b); }
struct P {
db x, y;
P() {}
P(db _x, db _y) : x(_x), y(_y) {}
P operator+(P p) { return {x + p.x, y + p.y}; }
P operator-(P p) { return {x - p.x, y - p.y}; }
P operator*(db d) { return {x * d, y * d}; }
P operator/(db d) { return {x / d, y / d}; }
bool operator<(P p) const {
int c = cmp(y, p.y);
if (c) return c == -1;
return cmp(x, p.x) == -1;
}
bool operator==(P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p) { return x * p.x + y * p.y; }
db det(P p) { return x * p.y - y * p.x; }
db distTo(P p) { return (*this-p).abs(); }
db alpha() { return atan2(y, x); }
void read() {
int x_, y_;
scanf("%d%d", &x_, &y_);
x = x_, y = y_;
}
void write() {cout<<"("<<x<<","<<y<<")"<<endl;}
db abs() { return sqrt(abs2());}
db abs2() { return x * x + y * y; }
P rot90() { return P(-y,x);}
P unit() { return *this/abs(); }
int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
P rot(db an){ return {x*cos(an) - y*sin(an),x*sin(an) + y*cos(an)}; }
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
// 直線 p1p2, q1q2 是否恰有一個交點
bool chkLL(P p1, P p2, P q1, P q2) {
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return sign(a1+a2) != 0;
}
// 求直線 p1p2, q1q2 的交點
P isLL(P p1, P p2, P q1, P q2) {
db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
return (p1 * a2 + p2 * a1) / (a1 + a2);
}
// 判斷區間 [l1, r1], [l2, r2] 是否相交
bool intersect(db l1,db r1,db l2,db r2){
if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2);
return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}
// 線段 p1p2, q1q2 相交
bool isSS(P p1, P p2, P q1, P q2){
return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) &&
crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) <= 0;
}
// 線段 p1p2, q1q2 嚴格相交
bool isSS_strict(P p1, P p2, P q1, P q2){
return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
* crossOp(q1,q2,p2) < 0;
}
// m 在 a 和 b 之間
bool isMiddle(db a, db m, db b) {
/*if (a > b) swap(a, b);
return cmp(a, m) <= 0 && cmp(m, b) <= 0;*/
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
bool isMiddle(P a, P m, P b) {
return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}
// 點 p 在線段 p1p2 上
bool onSeg(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
// q1q2 和 p1p2 的交點 在 p1p2 上？
// 點 p 嚴格在 p1p2 上
bool onSeg_strict(P p1, P p2, P q){
return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}
// 求 q 到 直線p1p2 的投影（垂足） ?? : p1 != p2
P proj(P p1, P p2, P q) {
P dir = p2 - p1;
return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
// 求 q 以 直線p1p2 為軸的反射
P reflect(P p1, P p2, P q){
return proj(p1,p2,q) * 2 - q;
}
// 求 q 到 線段p1p2 的最小距離
db nearest(P p1, P p2, P q){
if (p1 == p2) return p1.distTo(q);
P h = proj(p1,p2,q);
if(isMiddle(p1,h,p2))
return q.distTo(h);
return min(p1.distTo(q),p2.distTo(q));
}
// 求 線段p1p2 與 線段q1q2 的距離
db disSS(P p1, P p2, P q1, P q2){
if(isSS(p1,p2,q1,q2)) return 0;
return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)), min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
db area(vector<P> ps){
db ret = 0; rep(i,0,ps.size()) ret += ps[i].det(ps[(i+1)%ps.size()]);
return ret/2;
}
int contain(vector<P> ps, P p){ //2:inside,1:on_seg,0:outside
int n = ps.size(), ret = 0;
rep(i,0,n){
P u=ps[i],v=ps[(i+1)%n];
if(onSeg(u,v,p)) return 1;
if(cmp(u.y,v.y)<=0) swap(u,v);
if(cmp(p.y,u.y) > 0 || cmp(p.y,v.y) <= 0) continue;
ret ^= crossOp(p,u,v) > 0;
}
return ret*2;
}
vector<P> convexHull(vector<P> ps) {
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
qs.resize(k - 1);
return qs;
}
vector<P> convexHullNonStrict(vector<P> ps) {
//caution: need to unique the Ps first
int n = ps.size(); if(n <= 1) return ps;
sort(ps.begin(), ps.end());
vector<P> qs(n * 2); int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
qs.resize(k - 1);
return qs;
}
db convexDiameter(vector<P> ps){
int n = ps.size(); if(n <= 1) return 0;
int is = 0, js = 0; rep(k,1,n) is = ps[k]<ps[is]?k:is, js = ps[js] < ps[k]?k:js;
int i = is, j = js;
db ret = ps[i].distTo(ps[j]);
do{
if((ps[(i+1)%n]-ps[i]).det(ps[(j+1)%n]-ps[j]) >= 0)
(++j)%=n;
else
(++i)%=n;
ret = max(ret,ps[i].distTo(ps[j]));
}while(i!=is || j!=js);
return ret;
}
vector<P> convexCut(const vector<P>&ps, P q1, P q2) {
vector<P> qs;
int n = ps.size();
rep(i,0,n){
P p1 = ps[i], p2 = ps[(i+1)%n];
int d1 = crossOp(q1,q2,p1), d2 = crossOp(q1,q2,p2);
if(d1 >= 0) qs.push_back(p1);
if(d1 * d2 < 0) qs.push_back(isLL(p1,p2,q1,q2));
}
return qs;
}
P ld, rd, lu, ru, p[2],q[2];
void solve() {
ld.read();
ru.read();
rd = P(ru.x, ld.y);
lu = P(ld.x, ru.y);
p[0].read(); p[1].read();
q[0].read(); q[1].read();
vector<P> rect{ld, rd, ru, lu};
db ans = 0;
for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++)
if (p[i] == q[j]) {
auto r = convexCut(rect, p[i], p[i] + (p[1 - i] - p[i]).rot90());
r = convexCut(r, q[j], q[j] + (q[1 - j] - q[j]).rot90());
ans += area(r);
}
if (crossOp(p[0], p[1], q[0]) == 0 && crossOp(p[0], p[1], q[1]) == 0) {
auto r = rect;
for (int i = 0; i < 2; i++) {
r = convexCut(r, p[i], p[i] - (p[1 - i] - p[i]).rot90());
r = convexCut(r, q[i], q[i] - (q[1 - i] - q[i]).rot90());
}
ans += area(r);
}
printf("%.10f\n", ans);
}
int main() {
int tc;
for (scanf("%d", &tc); tc; tc--) {
solve();
}
}
模塊3
int type(P o1,db r1,P o2,db r2){
db d = o1.distTo(o2);
if(cmp(d,r1+r2) == 1) return 4;
if(cmp(d,r1+r2) == 0) return 3;
if(cmp(d,abs(r1-r2)) == 1) return 2;
if(cmp(d,abs(r1-r2)) == 0) return 1;
return 0;
}
vector<P> isCL(P o,db r,P p1,P p2){
if (cmp(abs((o-p1).det(p2-p1)/p1.distTo(p2)),r)>0) return {};
db x = (p1-o).dot(p2-p1), y = (p2-p1).abs2(), d = x * x - y * ((p1-o).abs2() - r*r);
d = max(d,(db)0.0); P m = p1 - (p2-p1)*(x/y), dr = (p2-p1)*(sqrt(d)/y);
return {m-dr,m+dr}; //along dir: p1->p2
}
vector<P> isCC(P o1, db r1, P o2, db r2) { //need to check whether two circles are the same
db d = o1.distTo(o2);
if (cmp(d, r1 + r2) == 1) return {};
if (cmp(d,abs(r1-r2))==-1) return {};
d = min(d, r1 + r2);
db y = (r1 * r1 + d * d - r2 * r2) / (2 * d), x = sqrt(r1 * r1 - y * y);
P dr = (o2 - o1).unit();
P q1 = o1 + dr * y, q2 = dr.rot90() * x;
return {q1-q2,q1+q2};//along circle 1
}
// extanCC, intanCC : -r2, tanCP : r2 = 0
vector<pair<P, P>> tanCC(P o1, db r1, P o2, db r2) {
P d = o2 - o1;
db dr = r1 - r2, d2 = d.abs2(), h2 = d2 - dr * dr;
if (sign(d2) == 0|| sign(h2) < 0) return {};
h2 = max((db)0.0, h2);
vector<pair<P, P>> ret;
for (db sign : {-1, 1}) {
P v = (d * dr + d.rot90() * sqrt(h2) * sign) / d2;
ret.push_back({o1 + v * r1, o2 + v * r2});
}
if (sign(h2) == 0) ret.pop_back();
return ret;
}
db rad(P p1,P p2){
return atan2l(p1.det(p2),p1.dot(p2));
}
db areaCT(db r, P p1, P p2){
vector<P> is = isCL(P(0,0),r,p1,p2);
if(is.empty()) return r*r*rad(p1,p2)/2;
bool b1 = cmp(p1.abs2(),r*r) == 1, b2 = cmp(p2.abs2(), r*r) == 1;
if(b1 && b2){
P md=(is[0]+is[1])/2;
if(sign((p1-md).dot(p2-md)) <= 0)
return r*r*(rad(p1,is[0]) + rad(is[1],p2))/2 + is[0].det(is[1])/2;
else return r*r*rad(p1,p2)/2;
}
if(b1) return (r*r*rad(p1,is[0]) + is[0].det(p2))/2;
if(b2) return (p1.det(is[1]) + r*r*rad(is[1],p2))/2;
return p1.det(p2)/2;
}
P inCenter(P A, P B, P C) {
double a = (B - C).abs(), b = (C - A).abs(), c = (A - B).abs();
return (A * a + B * b + C * c) / (a + b + c);
}
P circumCenter(P a, P b, P c) {
P bb = b - a, cc = c - a;
double db = bb.abs2(), dc = cc.abs2(), d = 2 * bb.det(cc);
return a - P(bb.y * dc - cc.y * db, cc.x * db - bb.x * dc) / d;
}
P othroCenter(P a, P b, P c) {
P ba = b - a, ca = c - a, bc = b - c;
double Y = ba.y * ca.y * bc.y,
A = ca.x * ba.y - ba.x * ca.y,
x0 = (Y + ca.x * ba.y * b.x - ba.x * ca.y * c.x) / A,
y0 = -ba.x * (x0 - c.x) / ba.y + ca.y;
return {x0, y0};
}
pair<P,db> min_circle(vector<P> ps){
random_shuffle(ps.begin(), ps.end());
int n = ps.size();
P o = ps[0]; db r = 0;
rep(i,1,n) if(o.distTo(ps[i]) > r + EPS){
o = ps[i], r = 0;
rep(j,0,i) if(o.distTo(ps[j]) > r + EPS){
o = (ps[i] + ps[j]) / 2; r = o.distTo(ps[i]);
rep(k,0,j) if(o.distTo(ps[k]) > r + EPS){
o = circumCenter(ps[i],ps[j],ps[k]);
r = o.distTo(ps[i]);
}
}
}
return {o,r};
}
大數
struct Bigint {
// representations and structures
string a; // to store the digits
int sign; // sign = -1 for negative numbers, sign = 1 otherwise
// constructors
Bigint() {} // default constructor
Bigint( string b ) { (*this) = b; } // constructor for string
// some helpful methods
int size() { // returns number of digits
return a.size();
}
Bigint inverseSign() { // changes the sign
sign *= -1;
return (*this);
}
Bigint normalize( int newSign ) { // removes leading 0, fixes sign
for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- )
a.erase(a.begin() + i);
sign = ( a.size() == 1 && a[0] == '0' ) ? 1 : newSign;
return (*this);
}
// assignment operator
void operator = ( string b ) { // assigns a string to Bigint
a = b[0] == '-' ? b.substr(1) : b;
reverse( a.begin(), a.end() );
this->normalize( b[0] == '-' ? -1 : 1 );
}
// conditional operators
bool operator < ( const Bigint &b ) const { // less than operator
if( sign != b.sign ) return sign < b.sign;
if( a.size() != b.a.size() )
return sign == 1 ? a.size() < b.a.size() : a.size() > b.a.size();
for( int i = a.size() - 1; i >= 0; i-- )
if( a[i] != b.a[i] )
return sign == 1 ? a[i] < b.a[i] : a[i] > b.a[i];
return false;
}
bool operator == ( const Bigint &b ) const { // operator for equality
return a == b.a && sign == b.sign;
}
// mathematical operators
Bigint operator + ( Bigint b ) { // addition operator overloading
if( sign != b.sign ) return (*this) - b.inverseSign();
Bigint c;
for(int i = 0, carry = 0; i<a.size() || i<b.size() || carry; i++ ) {
carry+=(i<a.size() ? a[i]-48 : 0)+(i<b.a.size() ? b.a[i]-48 : 0);
c.a += (carry % 10 + 48);
carry /= 10;
}
return c.normalize(sign);
}
Bigint operator - ( Bigint b ) { // subtraction operator overloading
if( sign != b.sign ) return (*this) + b.inverseSign();
int s = sign; sign = b.sign = 1;
if( (*this) < b ) return ((b - (*this)).inverseSign()).normalize(-s);
Bigint c;
for( int i = 0, borrow = 0; i < a.size(); i++ ) {
borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
borrow = borrow >= 0 ? 0 : 1;
}
return c.normalize(s);
}
Bigint operator * ( Bigint b ) { // multiplication operator overloading
Bigint c("0");
for( int i = 0, k = a[i] - 48; i < a.size(); i++, k = a[i] - 48 ) {
while(k--) c = c + b; // ith digit is k, so, we add k times
b.a.insert(b.a.begin(), '0'); // multiplied by 10
}
return c.normalize(sign * b.sign);
}
Bigint operator / ( Bigint b ) { // division operator overloading
if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
Bigint c("0"), d;
for( int j = 0; j < a.size(); j++ ) d.a += "0";
int dSign = sign * b.sign; b.sign = 1;
for( int i = a.size() - 1; i >= 0; i-- ) {
c.a.insert( c.a.begin(), '0');
c = c + a.substr( i, 1 );
while( !( c < b ) ) c = c - b, d.a[i]++;
}
return d.normalize(dSign);
}
Bigint operator % ( Bigint b ) { // modulo operator overloading
if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
Bigint c("0");
b.sign = 1;
for( int i = a.size() - 1; i >= 0; i-- ) {
c.a.insert( c.a.begin(), '0');
c = c + a.substr( i, 1 );
while( !( c < b ) ) c = c - b;
}
return c.normalize(sign);
}
// output method
void print() {
if( sign == -1 ) putchar('-');
for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
}
};
雜
內建函數
__builtin_ctz( )
返回輸入數二進制表示從最低位開始(右起)的連續的0的個數；如果傳入0則行為未定義。
__builtin_parity( )
返回括號內數的二進制表示形式中1的個數的奇偶性（偶：0，奇：1）。
__builtin_popcount( )
返回括號內數的二進制表示形式中1的個數。
過去犯錯
- 我手比較快，可以拼下手速，如果卡題了，可以拼一下題數，反正實力在那里了，好幾場VP省賽都金銀，不會差的
- 注意細心讀題，不要忽略任何一個條件
- 結果錯了，輸出運算時候的中間值檢驗；
- 代碼在本地編譯錯誤，找不出，一段一段刪除代碼然后編譯看是哪部分有問題（ctrl+z可以返回上一步，要注意你的編譯器有沒有這個功能）
- 代碼過了樣例，交上去錯了，檢查數組有沒有開小，有沒有用long long甚至要高精度計算（注意題目給出的數據范圍），或者是運算的時候超出了int的范圍使得結果不正確等。
- 你在主函數的數組開的太大了，導致你程序無法輸入等問題，開成全局變量就可以解決
- 盡量少用指針，算法競賽的題目不應該出現復雜的指針，隊列，鏈表，樹和圖的存儲可以用數組實現（鏈式前向星）或鄰接矩陣。學習算法競賽中使用的存圖方式
- 你數組開小了，題目的數據范圍是1e5，那你就要開到1e5+10,
- 數組開小，或者開大可能會導致WA,RE,MLE,TLE等，具體問題具體分析
- 代碼盡量不要讓別人幫你看，前期還是提升個人能力為主
- 一些C++20編譯器你RE了，他會爆TLE，坑了我好幾次了，嗚嗚，換C++17,C++11，C++14報錯正常，具體看評測機，再遇到再補充吧
- set判重速度要慢一倍（特定情況下），用了數組才過。Acwing的周賽連通塊
- 異或運算要加括號，運算優先級的問題
- set可以lower_bound
例如int op=*x.lower_bound(x1);
x是set<int>::iterator it; it=se.lower_bound(9);
map<int, string>::iterator p1, p2; p1 = mp.lower_bound(3); /* p1->second == 3 */- 左移運算符
a = 1ll << 60;才是對的 - multiset 刪除
s.erase(s.find(a));
本文來自博客園，作者：magicat，轉載請注明原文鏈接：http://www.rzrgm.cn/magicat/p/17385691.html
浙公網安備 33010602011771號