高斯消元
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int n;
double a[23][23], b[23], c[23][23], temp;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n + 1; i++)
for(int j = 1; j <= n; j++)
scanf("%lf", &a[i][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
c[i][j] = 2 * (a[i][j] - a[i + 1][j]);
b[i] += a[i][j] * a[i][j] - a[i + 1][j] * a[i + 1][j];
}
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j++)
{
if(fabs(c[j][i]) > 1e-8)
{
for(int k = 1; k <= n; k++)
swap(c[i][k], c[j][k]);
swap(b[i], b[j]);
}
}
for(int j = 1; j <= n; j++)
{
if(i == j) continue;
temp = c[j][i] / c[i][i];
for(int k = i; k <= n; k++)
c[j][k] -= c[i][k] * temp;
b[j] -= b[i] * temp;
}
}
for(int i = 1; i <= n; i++)
printf("%0.3lf ", b[i] / c[i][i]);
return 0;
} 并查集
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, dad[10007];
int find(int x)
{
if(dad[x] != x) return dad[x] = find(dad[x]);
return x;
}
void uni(int x, int y)
{
int r1 = find(x);
int r2 = find(y);
if(r1 != r2)
dad[r1] = r2;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
dad[i] = i;
for(int i = 1; i <= m; i++)
{
int x, y, op;
scanf("%d%d%d", &op, &x, &y);
if(op == 1)
uni(x, y);
else if(op == 2)
{
int r1 = find(x);
int r2 = find(y);
if(r1 != r2)
printf("N\n");
else printf("Y\n");
}
}
return 0;
} 离散化
sort(hash + 1, hash + 1 + n);
int siz =unique(hash + 1, hash + 1 + n) - hash - 1;线段树
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef int int_;
#define int long long
using namespace std;
int tree[800007], lazy[800007];
int n, m;
void pushup(int o)
{
tree[o] = tree[o << 1] + tree[o << 1 | 1];
}
void pushdown(int o, int l, int r)
{
if(!lazy[o]) return ;
int mid = (l + r) >> 1;
tree[o << 1] += lazy[o] * (mid - l + 1);
tree[o << 1 | 1] += lazy[o] * (r - mid);
lazy[o << 1] += lazy[o];
lazy[o << 1 | 1] += lazy[o];
lazy[o] = 0;
}
void build(int o, int l, int r)
{
if(l == r)
{
int x;
scanf("%lld", &x);
tree[o] = x;
return ;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid);
build(o << 1 | 1, mid + 1, r);
pushup(o);
}
void update(int o, int l, int r, int ql, int qr, int k)
{
if(ql <= l && qr >= r)
{
tree[o] += k * (r - l + 1);
lazy[o] += k;
return ;
}
pushdown(o, l, r);
int mid = (l + r) >> 1;
if(ql <= mid) update(o << 1, l, mid, ql, qr, k);
if(qr > mid) update(o << 1 | 1, mid + 1, r, ql, qr, k);
pushup(o);
}
int query(int o, int l, int r, int ql, int qr)
{
if(ql <= l && qr >= r) return tree[o];
pushdown(o, l, r);
int mid = (l + r) >> 1, ret = 0;
if(ql <= mid) ret += query(o << 1, l, mid, ql, qr);
if(qr > mid) ret += query(o << 1 | 1, mid + 1, r, ql, qr);
return ret;
}
int_ main() {
int x, y, op, k;
scanf("%lld%lld", &n, &m);
build(1, 1, n);
for(int i = 1; i <= m; i++)
{
scanf("%lld", &op);
if(op == 1)
{
scanf("%lld%lld%lld", &x, &y, &k);
update(1, 1, n, x, y, k);
}
else
{
scanf("%lld%lld", &x, &y);
printf("%lld\n", query(1, 1, n, x, y));
}
}
return 0;
}主席树
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int a[200007], hash[200007], T[200007], L[200007 << 5], R[200007 << 5], sum[200007 << 5];
int n, m, ncnt;
int build(int l, int r)
{
int num = ++ncnt;
if(l != r)
{
int mid = (l + r) >> 1;
L[num] = build(l, mid);
R[num] = build(mid + 1, r);
}
return num;
}
int update(int o, int l, int r, int x)
{
int num = ++ncnt;
L[num] = L[o], R[num] = R[o], sum[num] = sum[o] + 1;
if(l != r)
{
int mid = (l + r) >> 1;
if(x <= mid) L[num] = update(L[o], l, mid, x);
else R[num] = update(R[o], mid + 1, r, x);
}
return num;
}
int query(int u, int v, int l, int r, int k)
{
if(l == r) return hash[l];
int num = sum[L[v]] - sum[L[u]];
int mid = (l + r) >> 1;
if(num >= k) return query(L[u], L[v], l, mid, k);
else return query(R[u], R[v], mid + 1, r, k - num);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
hash[i] = a[i];
}
sort(hash + 1, hash + 1 + n);
int siz =unique(hash + 1, hash + 1 + n) - hash - 1;
T[0] = build(1, siz);
for(int i = 1; i <= n; i++)
{
int x = lower_bound(hash + 1, hash + 1 + siz, a[i]) - hash;
T[i] = update(T[i - 1], 1, siz, x);
}
int l, r, k;
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", query(T[l - 1], T[r], 1, siz, k));
}
return 0;
} LCA
//倍增
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 600010
using namespace std;
int cnt, n, m, deep[maxn], dp[maxn][21], head[maxn];
struct node{
int v, next;
}e[maxn << 1];
void add(int u, int v)
{
e[++cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
void dfs(int x, int fa)
{
deep[x] = deep[fa] + 1;
dp[x][0] = fa;
for(int i = head[x]; i; i = e[i].next)
{
int v = e[i].v;
if(v != fa)
dfs(v, x);
}
}
void init()
{
for(int j = 1; (1 << j) <= n; j++)
{
for(int i = 1; i <= n; i++)
if(deep[i] >= (1 << j))
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
int lca(int x, int y)
{
if(deep[x] < deep[y]) swap(x, y);
int d = deep[x] - deep[y];
for(int j = 20; j >= 0; j--) if(d & (1 << j)) x = dp[x][j];
if(x == y)
return x;
for(int i = 20; i >= 0; i--)
{
if(dp[x][i] != dp[y][i])
{
x = dp[x][i];
y = dp[y][i];
}
}
return dp[x][0];
}
int main() {
int rt, x, y;
scanf("%d%d%d", &n, &m, &rt);
for(int i = 1; i < n; i++)
{
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(rt, 0);
init();
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &x, &y);
printf("%d\n", lca(x, y));
}
return 0;
}tarjan
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
int n, m, flag;
struct node {
int v, next;
}e[50009];
int head[50009], cnt;
void add(int u, int v)
{
e[++cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int vis[10009], tot, ctot, now, num[10009], ran[10009];\
int dfn[10009], low[10009];
stack<int> s;
void tarjan(int x)
{
vis[x] = 1;
s.push(x);
dfn[x] = low[x] = ++tot;
for(int i = head[x]; i; i = e[i].next) {
int v = e[i].v;
if(!dfn[v]) {
tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(vis[v]) {
low[x] = min(low[x], dfn[v]);
}
}
if(dfn[x] == low[x]) {
ctot++;
now = -1;
while(now != x) {
now = s.top();
s.pop();
vis[now] = 0;
ran[now] = ctot;
num[ctot]++;
}
}
}
int cd[10009];
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
for(int i = 1; i <= n; i++) {
if(!dfn[i]) tarjan(i);
}
for(int i = 1; i <= n; i++) {
for(int j = head[i]; j; j = e[j].next) {
int v = e[j].v;
if(ran[i] != ran[v]) {
cd[ran[i]] += 1;
}
}
}
for(int i = 1; i <= ctot; i++) {
if(!cd[i]) {
if(flag) {
printf("0");
return 0;
}
flag = i;
}
}
printf("%d", num[flag]);
return 0;
} 2 缩点【模板】缩点
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#define maxn 100010
using namespace std;
int n, m, u, v, head[maxn], HEAD[maxn], dfn[maxn], low[maxn], vis[maxn], cnt;
int now, tot, jh[maxn], VAL[maxn], val[maxn], rd[maxn], dp[maxn], ans;
stack<int> s;
queue<int> q;
struct node{
int v, next;
}e[100010], E[100010];
void add(int u, int v)
{
e[++cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
void ADD(int u, int v)
{
E[++cnt].v = v;
E[cnt].next = HEAD[u];
HEAD[u] = cnt;
}
void tarjan(int x)
{
dfn[x] = low[x] = ++cnt;
s.push(x);
vis[x] = 1;
for(int i = head[x]; i; i = e[i].next)
{
int v = e[i].v;
if(!dfn[v])
{
tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(vis[v])
low[x] = min(low[x], dfn[v]);
}
if(dfn[x] == low[x])
{
now = -1;
tot++;
while(now != x)
{
now = s.top();
s.pop();
jh[now] = tot;
VAL[tot] += val[now];
vis[now] = 0;
}
}
}
void rebuild()
{
for(int x = 1; x <= n; x++)
{
for(int i = head[x]; i; i = e[i].next)
{
int v = e[i].v;
if(jh[x] != jh[v])
{
ADD(jh[x], jh[v]);
rd[jh[v]]++;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &val[i]);
for(int i = 1; i <= m; i++)
{
scanf("%d%d", &u, &v);
add(u, v);
}
cnt = 0;
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i);
cnt = 0;
rebuild();
for(int i = 1; i <= tot; i++)
{
if(!rd[i])
{
q.push(i);
dp[i] = VAL[i];
}
}
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = HEAD[x]; i; i = E[i].next)
{
int v = E[i].v;
dp[v] = max(dp[v], dp[x] + VAL[v]);
rd[v]--;
if(!rd[v]) q.push(v);
}
}
for(int i = 1; i <= tot; i++) ans = max(ans, dp[i]);
printf("%d", ans);
return 0;
}3割点【模板】割点（割顶）
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, cnt, rt, vis[20050], dfn[20050], low[20050], head[20050], son, ans[20050], tot;
struct node{
int v, next;
}e[200050];
void add(int u, int v)
{
e[++cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
void tarjan(int x, int f)
{
low[x] = dfn[x] = ++cnt;
for(int i = head[x]; i; i = e[i].next)
{
int v = e[i].v;
if(!dfn[v])
{
tarjan(v, x);
low[x] = min(low[x], low[v]);
if(low[v] >= dfn[x])
{
if(x == rt) son++;
else if(!ans[x])
{
ans[x] = 1;
tot++;
}
}
}
else if(v != f) low[x] = min(low[x], dfn[v]);
}
}
int main() {
int u, v;
scanf("%d%d", &n, &m);
while(m--)
{
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
cnt = 0;
for(int i = 1; i <= n; i++)
{
if(!dfn[i]) tarjan(rt = i, 0);
if(son >= 2)
{
ans[rt] = 1;
tot++;
}
son = 0;
}
printf("%d\n", tot);
for(int i = 1; i <= n; i++)
if(ans[i])
printf("%d ", i);
return 0;
} 最短路
dijkstra【模板】单源最短路径（标准版）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 2147483647
#define maxn 1000010
using namespace std;
int n, m, s, dis[maxn], vis[maxn];
int u, v, val, head[maxn], cnt;
priority_queue<pair<int, int> > q;
struct node{
int v, val, next;
}e[maxn << 1];
void add(int u, int v, int val)
{
e[++cnt].v = v;
e[cnt].val = val;
e[cnt].next = head[u];
head[u] = cnt;
}
void dijkstra()
{
for(int i = 1; i <= n; i++) dis[i] = INF;
dis[s] = 0;
q.push(make_pair(0, s));
while(!q.empty())
{
int x = q.top().second;
q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; i; i = e[i].next)
{
int v = e[i].v, val = e[i].val;
if(!vis[v] && dis[v] > dis[x] + val)
{
dis[v] = dis[x] + val;
q.push(make_pair(-dis[v], v));
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &val);
add(u, v, val);
}
dijkstra();
for(int i = 1; i <= n; i++)
printf("%d ", dis[i]);
return 0;
}SPFA【模板】单源最短路径（弱化版）
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define INF 2147483647
using namespace std;
int n, s, m, cnt, head[10007], dis[10007], vis[10007];
struct node{
int v, next, val;
}edge[500007];
void add(int u, int v, int val)
{
edge[++cnt].v = v;
edge[cnt].val = val;
edge[cnt].next = head[u];
head[u] = cnt;
}
void spfa()
{
queue<int> q;
for(int i = 1; i <= n; i++) dis[i] = INF;
dis[s] = 0;
q.push(s);
while(!q.empty())
{
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = edge[i].next)
{
int v = edge[i].v, val = edge[i].val;
if(dis[v] > dis[x] + val)
{
dis[v] = dis[x] + val;
if(!vis[v])
{
vis[v] = 1;
q.push(v);
}
}
}
}
}
int main() {
int u, v, val;
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &val);
add(u, v, val);
}
spfa();
for(int i = 1; i <= n; i++)
printf("%d ", dis[i]);
return 0;
} Floyd P1119 灾后重建
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[205][205], n, m, k, q, mp[205];
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
dp[i][j] = 1e9 + 7;
dp[i][i] = 0;
}
for(int i = 0; i < n; i++) scanf("%d", &mp[i]);
for(int i = 1; i <= m; i++)
{
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
dp[u][v] = dp[v][u] = min(dp[u][v], val);
}
scanf("%d", &q);
for(int wt = 1; wt <= q; wt++)
{
int qa, qb, qt;
scanf("%d%d%d", &qa, &qb, &qt);
while(mp[k] <= qt && k < n)
{
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
k += 1;
}
if(dp[qa][qb] >= 1e9 + 7 || mp[qa] > qt || mp[qb] > qt)
printf("-1\n");
else printf("%d\n", dp[qa][qb]);
}
}差分约束系统
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
const int INF = 1e9 + 7;
using namespace std;
int n, m;
int cnt1, cnt2, cnt;
int head1[2009], head2[2009], head[2009];
struct node {
int u, v, next, val;
}e1[2009], e2[2009], e[2009];
void add1(int u, int v) {
e1[++cnt1].v = v;
e1[cnt1].u = u;
e1[cnt1].next = head1[u];
head1[u] = cnt1;
}
void add2(int u, int v) {
e2[++cnt2].v = v;
e2[cnt2].next = head2[u];
head2[u] = cnt2;
}
void add(int u, int v, int val) {
e[++cnt].v = v;
e[cnt].u = u;
e[cnt].val = val;
e[cnt].next = head[u];
head[u] = cnt;
}
int vis1[1009], vis2[1009];
void dfs1(int x) {
vis1[x] = 1;
for(int i = head1[x]; i; i = e1[i].next) {
int v = e1[i].v;
if(vis1[v]) continue;
vis1[v] = 1;
dfs1(v);
}
return ;
}
void dfs2(int x)
{
vis2[x] = 1;
for(int i = head2[x]; i; i = e2[i].next) {
int v = e2[i].v;
if(vis2[v]) continue;
vis2[v] = 1;
dfs2(v);
}
return ;
}
int dis[1009], vis[1009], scnt[1009];
int spfa(int x) {
queue<int> q;
for(int i = 1; i <= n; i++) dis[i] = INF;
q.push(x);
vis[x] = 1;
dis[x] = 0;
scnt[x] = 1;
while(!q.empty()) {
x = q.front();
q.pop();
vis[x] = 0;
for(int i = head[x]; i; i = e[i].next) {
int v = e[i].v, val = e[i].val;
if(dis[v] > dis[x] + val) {
dis[v] = dis[x] + val;
scnt[v]++;
if(scnt[v] > n) {
return -1;
}
if(!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return 0;
}
int jud[1009];
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add1(u, v), add2(v, u);
}
dfs1(1);
dfs2(n);
for(int i = 1; i <= n; i++) {
if(vis1[i] && vis2[i]) {
jud[i] = 1;
add(0, i, 0);
}
}
if(!jud[n]) {
printf("-1");
return 0;
}
for(int i = 1; i <= m; i++) {
int u = e1[i].u, v = e1[i].v;
if(!(jud[u] && jud[v])) continue;
add(u, v, 9);
add(v, u, -1);
}
if(spfa(1) == -1) {
printf("-1");
return 0;
}
printf("%d %d\n", n, m);
for(int i = 1; i <= m; i++) {
int u = e1[i].u, v = e1[i].v;
printf("%d %d ", u, v);
if(!(jud[u] && jud[v])) printf("1\n");
else printf("%d\n", dis[v] - dis[u]);
}
return 0;
}
最小生成树
最小生成树P1195 口袋的天空
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node{
int a,b,c;
}l[100005];
int dad[1006];
int cmp(const node s1,const node s2)
{
return s1.c < s2.c;
}
int find(int x)
{
if(dad[x] != x) return dad[x] = find(dad[x]);
return x;
}
int main() {
int n,m,ans = 0,k = 0,r;
scanf("%d%d%d",&n,&m,&r);
for(int i = 1; i <= n; i++) dad[i] = i;
for(int i = 1; i <= m; i++)
scanf("%d%d%d",&l[i].a,&l[i].b,&l[i].c);
sort(l + 1,l + 1 + m, cmp);
for(int i = 1; i <= m; i++)
{
int r1 = find(l[i].a);
int r2 = find(l[i].b);
if(r1 != r2)
{
dad[r2] = r1;
k++;
ans += l[i].c;
}
if(k == n-r)
{
printf("%d",ans);
return 0;
}
}
printf("No Answer");
return 0;
}HASH
#include <cstdio>
#include <cstring>
#include <algorithm>
unsigned long long s[10010];
char a[10010];
unsigned long long hashh(char x[])
{
int len = strlen(x);
unsigned long long temp = 0;
for(int i = 0; i < len; i++)
{
temp = (temp * 13331 + (unsigned long long)x[i]);
}
return temp;
}
int main() {
int n,ans = 1;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%s",a);
s[i] = hashh(a);
}
std::sort(s + 1,s + n + 1);
for(int i = 2; i <= n; i++)
if(s[i] != s[i - 1]) ans++;
printf("%d\n",ans);
return 0;
}