1、基础算法
快速排序
void qs(int q[], int l ,int r) // qs(a, 0, n - 1);
{
if(l>=r) return;
int i = l-1 , j = r+1, x = q[l+r>>1];
while(i<j)
{
do i++; while(a[i]<x);
do j--; while(a[j]>x);
if(i<j) swap(a[i],a[j]);
}
qs(q,l,j);
qs(q,j+1,r);
//若是判断第k小的数
//if(k<=j+1) qs(q,l,j);
//else qs(q,j+1,r);
}
归并排序
void ms(int q[],int l ,int r) // ms(a, 0, n - 1); int tmp[N];
{
if(l>=r) return;
int mid = l+r>>1;
ms(q,l,mid), ms(q,mid+1,r);
int i = l, j = mid+1, k = 0;
while(i<=mid && j<=r)
{
if(q[i]<=q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++]; // 求逆序对:res += mid + 1 - i; res (ll) 类型
}
while(i<=mid) tmp[k++] = q[i++];
while(j<=r) tmp[k++] = q[j++];
for(int i = l ,j = 0;i<=r;i++,j++) q[i] = tmp[j];
}
整数二分
while(l<r) // 找到第一个大于等于x的位置
{
int mid = l+r>>1;
if(x <= a[mid]) r = mid;
else l = mid+1;
}
return l;
while(l<r) // 找到最后一个小于等于x的位置
{
int mid = l+r+1>>1;
if(x >= a[mid]) l = mid;
else r = mid - 1;
}
return l;
// *lower_bound(stk.begin(),stk.end(),a[i]) = a[i]; 找到第一个大于等于a[i]的数并替换成a[i];
// 浮点数二分
while(l<r) // 注意eps
{
double mid = (l+r)/2;
if(fabs(mid * mid * mid - n ) < eps)
{
printf("%.6lf",mid);
return 0;
}
else if(mid * mid * mid > n ) r = mid;
else l = mid;
}
高精乘
void mul(vector<int> & a, int b)
{
vector<int> c;
int t = 0;
for(int i = a.size() -1; i>=0;i--)
{
t += a[i] * b;
c.push_back(t%10);
t/=10;
}
while(t)
{
c.push_back(t%10);
t/=10;
}
while(c.back()==0 && c.size()>1) c.pop_back();
for(int i = c.size()-1;i>=0;i--) printf("%d",c[i]);
}
for(int i = 0;i<a.size();i++) c.push_back(a[i] - '0');
mul(c,b);
高精除
void div(vector<int> &a, int b)
{
vector<int> c;
int t = 0;
for(int i = 0;i<a.size();i++)
{
t = t * 10 + a[i];
if(t>=b)
{
c.push_back(t/b);
t %= b;
}
else c.push_back(0);
}
res = t;
reverse(c.begin(),c.end());
while(c.size()>1 && c.back()==0) c.pop_back();
for(int i = c.size()-1 ;i>=0;i--) printf("%d",c[i]);
puts("");
printf("%d",res);
}
for(int i = 0 ;i<a.size();i++) c.push_back(a[i] - '0');
div(c,b);
二维前缀和
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
scanf("%d",&s[i][j]);
s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
}
}
while(q--) // 询问
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]);
}
一维差分
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i] = a[i] - a[i-1];
}
while(q--) // 区间加减
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
b[l] += c;
b[r+1] -=c;
}
for(int i = 1;i<=n;i++)
{
b[i] += b[i-1];
printf("%d ",b[i]);
}
二维差分
for(int i =1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
scanf("%d",&a[i][j]);
b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
}
}
while(q--) // 矩阵内元素加减操作
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
b[x1][y1] += c;
b[x1][y2+1] -= c;
b[x2+1][y1] -= c;
b[x2+1][y2+1] += c;
}
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
b[i][j] = b[i][j] - b[i-1][j-1] + b[i-1][j] + b[i][j-1];
printf("%d ",b[i][j]);
}
puts("");
}
双指针
int j = 0;
for(int i = 0 ;i<n;i++) // 找出最长的不包含重复的数的连续区间,输出它的长度
{
book[a[i]] ++;
while(j<i && book[a[i]] > 1) book[a[j++]] --;
res = max(res, i - j + 1);
}
printf("%d",res);
int j = m - 1; // 求出满足 A[i]+B[j]= x 的数对 (i,j) A、B 均为升序
for(int i = 0;i<n;i++)
{
while(a[i] + b[j] >x && j>0) j--;
if(a[i]+b[j]==x)
{
printf("%d %d",i,j);
return 0;
}
}
int j = 0; // 判断a序列是否是b序列的子序列
for(int i = 0;i<n;i++)
{
while(a[i]!=b[j] && j<m) j++;
if(a[i]==b[j])
{
cnt++;
j++;
}
}
if(cnt==n) printf("Yes");
else printf("No");
lowBit
位运算
求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n
int lowbit(int x) // 找二进制中1的个数
{
return x&-x; //找二进制情况下,数字中,最后1个1以及后面的所有位
}
int res=0;
while(x)
{
x-=lowbit(x); //每次减去lowbit找到的数
res++; //找到一个,记上一个,直到为0
}
printf("%d ",res);
离散化 // 询问所求的区间内数字和
vector<int> add;
vector<pii> alls,query;
int a[N],s[N];
int n,m;
int find(int x)
{
int l = 0, r = add.size()-1;
while(l<r)
{
int mid = l+r>>1;
if(x<=add[mid]) r = mid;
else l = mid + 1;
}
return l + 1;
}
int main()
{
cin>>n>>m;
for(int i = 0 ;i<n;i++)
{
int x,c;
scanf("%d%d",&x,&c);
alls.push_back({x,c});
add.push_back(x);
}
for(int i = 0 ;i<m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
add.push_back(l);
add.push_back(r);
query.push_back({l,r});
}
sort(add.begin(),add.end());
add.erase(unique(add.begin(),add.end()),add.end()); //去重
for(int i = 0;i<alls.size();i++)
{
int x = find(alls[i].first);
a[x] += alls[i].second;
}
for(int i = 1;i<=add.size();i++) s[i] = s[i-1] + a[i];
for(int i = 0;i<query.size();i++)
{
int l = find(query[i].first);
int r = find(query[i].second);
printf("%d\n",s[r] - s[l-1]);
}
区间合并 // 求合并后有几个区间
for(int i = 0;i<n;i++)
{
scanf("%d%d",&l,&r);
query.push_back({l,r});
}
sort(query.begin(),query.end());
int end = query[0].second;
int res = 1;
for(int i = 1;i<query.size();i++)
{
if(query[i].first>end)
{
res ++;
end = query[i].second;
}
else
{
end = max(end,query[i].second);
}
}
printf("%d",res);
图论
// BFS求最短路
void bfs()
{
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
memset(d,-1,sizeof d);
d[1][1] = 0;
int head = 0, tail = 0;
q[0] = {1,1};
while(head <= tail)
{
auto t = q[head++];
int x = t.first, y = t.second;
for(int i = 0;i<4;i++)
{
int a = x + dx[i], b = y + dy[i];
if(a >= 1 && a <= n && y >= 1 && y <= m && g[a][b] == '0' && d[a][b] == -1)
{
d[a][b] = d[x][y] + 1;
if(a == n && b ==m)
{
printf("%d",d[a][b]);
return;
}
q[++tail] = {a,b};
}
}
}
}
int bfs(string start) // 八数码
{
unordered_map<string,int> d;
queue<string> q;
q.push(start);
d[start] = 0;
int dx[4] = {-1,0,1,0},dy[4] = {0,-1,0,1};
string end = "12345678x";
while(q.size())
{
auto t = q.front();
q.pop();
int distance = d[t];
if(t == end) return distance;
int k = t.find('x');
int x = k/3 , y = k%3;
for(int i = 0 ;i<4;i++)
{
int a = x + dx[i], b = y + dy[i];
if(a>=0 && a<3 && b >=0 && b<3)
{
swap(t[a * 3 + b],t[k]);
if(!d.count(t))
{
q.push(t);
d[t] = distance + 1;
}
swap(t[a * 3 + b], t[k]);
}
}
}
return -1;
}
树的重心 //重心:如果将这个点删除后,剩余各个连通块中点数的最大值最小
int dfs(int u) // dfs(1);
{
st[u] = true;
int sum = 1, res = 0;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(st[j]) continue;
int s = dfs(j);
res = max(res,s);
sum += s;
}
res = max(res, n - sum);
ans = min(ans, res);
return sum;
}
cout << ans << endl;
int bfs() // 求图中点的层次
{
memset(d,-1,sizeof d);
q[0] = 1;
int hh = 0 , tt = 0;
d[1] = 0;
while(hh<=tt)
{
int t = q[hh++];
for(int i = h[t] ; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
q[++tt] = j;
d[j] = d[t] + 1;
}
}
}
return d[n];
}
拓扑排序
bool topsort()
{
int num = 0;
for(int i = 1;i<=n;i++)
{
if(d[i] == 0)
{
q.push(i);
v.push_back(i);
num++;
}
}
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j]--;
if(d[j] == 0)
{
q.push(j);
v.push_back(j);
num++;
}
}
}
if(num == n) return true;
return false;
}
add(a,b), d[b]++;
if(topsort())
{
for(int i = 0;i<v.size();i++) printf("%d ",v[i]);
}
else puts("-1");
// 朴素版dijkstra O(n^2 + m) n 为点数, m 为边数
int dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
for(int i = 0;i<n;i++)
{
int t = -1;
for(int j = 1;j<=n;j++)
{
if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
}
st[t] = true;
for(int j = 1;j<=n;j++) dist[j] = min(dist[j],dist[t] + g[t][j]);
}
if(dist[n] == 0x3f3f3f3f ) return -1;
return dist[n];
}
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
g[a][b] = min(g[a][b],w);
}
int t = dijkstra();
// dijkstra 堆优化 邻接表
int dijkstra() // memset(dist,0x3f,sizeof dist);
{
priority_queue<pii,vector<pii>,greater<pii>> heap;
dist[1] = 0;
heap.push({0,1});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int distance = t.first, ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver];i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
//bellman-ford 图中可以有负权回路,以及边权为负的边
struct edg
{
int a,b,w;
}edge[M];
// 判断从1 - n 最多不经过k条边的最短路
int bf() // 时间复杂度 O(nm)O(nm), nn 表示点数,mm 表示边数
{
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++)
{
int a = edge[j].a, b = edge[j].b, w = edge[j].w;
dist[b] = min(dist[b],backup[a] + w);
}
}
if(dist[n]>0x3f3f3f3f/2) return -1;
return dist[n];
}
// spfa 求最短路(有负环)
int spfa() //有add函数
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
st[1] = true;
queue<int> q;
q.push(1);
while(q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i !=-1; i = ne[i]) // memset(h,-1,sizeof h);
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
if(dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
bool spfa() // spfa判断负环
{
queue<int> q;
for(int i = 1;i<=n;i++)
{
st[i] = true;
q.push(i);
}
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; i!= -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
// floyd O(n ^ 3) n 表示点数
for(int i = 1;i<=n;i++) // 初始化 读入: g[a][b] = min(g[a][b],w);
{
for(int j = 1;j<=n;j++)
{
if(i == j) g[i][j] = 0;
else g[i][j] = 0x3f3f3f3f;
}
}
void floyd() // g[j][k] 表示从j到k的最短距离
{
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
for(int k = 1;k<=n;k++)
{
g[j][k] = min(g[j][k],g[j][i] + g[i][k]);
}
}
}
}
// 最后判断能否到达 : if(g[a][b] > 0x3f3f3f3f / 2 ) printf("impossible\n");
// Prim 求最小生成树 // 时间复杂度是 O(n^2 + m ), n 表示点数,m 表示边数
int prim() // w[a][b] = w[b][a] = min(w[a][b],c);
{
memset(dist,0x3f,sizeof dist);
for(int i = 0 ;i<n;i++)
{
int t = -1;
for(int j = 1;j<=n;j++)
{
if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
}
if(i && dist[t] > INF / 2 ) return INF; // 不连通就不存在最小生成树
if(i) res += dist[t];
for(int j = 1;j<=n;j++) dist[j] = min(dist[j], w[t][j]); // 更新点到集合的距离
st[t] = true;
}
return res;
}
// Kruskal 求最小生成树 // 时间复杂度是 O(mlogm), n 表示点数,m 表示边数
struct edge // 存储边
{
int a,b,w;
bool operator<(const edge & W) const
{
return w < W.w;
}
}edges[N];
cin>>n>>m;
for(int i = 1;i<=n;i++) p[i] = i;
for(int i = 0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edges[i] = {a,b,w};
}
sort(edges,edges + m);
for(int i = 0;i<m;i++)
{
int a = edges[i].a ,b = edges[i].b , w = edges[i].w;
a = find(a), b = find(b); // 并查集需要写find函数
if(a != b)
{
p[a] = b;
res += w;
cnt++;
}
}
if(cnt < n - 1) printf("impossible");
else printf("%d",res);
//染色法判别二分图
时间复杂度是 O(n + m), n 表示点数,m 表示边数
bool flag = true;
for(int i = 1;i<=n;i++) //add(a,b), add(b,a) 邻接表存图
{
if(!color[i])
{
if(!dfs(i,1))
{
flag = false;
break;
}
}
}
bool dfs(int u, int c)
{
color[u] = c;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!color[j])
{
if(!dfs(j,3 - c)) return false;
}
else if(color[j] == c) return false;
}
return true;
}
for(int i = 1;i<=n1;i++) // 初始化 res = 0; 依次枚举第一个集合中的每个点能否匹配第二个集合中的点
{
memset(st,false,sizeof st);
if(find(i)) res++;
}
bool find(int x) add(a,b);单向连接
{
for(int i =h[x] ; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
if(!match[j] || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
最短路计数
void bfs() // 从顶点 1 开始,到其他每个点的最短路有几条
{
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
q.push(1);
cnt[1] = 1;
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
q.push(j);
}
else if(dist[j] == dist[t] + 1) cnt[j] = (cnt[j] + cnt[t]) % mod;
}
}
}
给定一棵 N 个节点的树,要求增加若干条边,把这棵树扩充为完全图,并满足图的唯一最小生成树仍然是这棵树。
求增加的边的权值总和最小是多少。
for(int i = 1;i<=n;i++) p[i] = i, sizes[i] = 1;
for(int i = 0;i< n - 1;i ++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
e[i] = {a,b,w};
}
sort(e, e + n - 1);
int res = 0;
for(int i = 0;i<n - 1;i++)
{
int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
if(a != b)
{
res += (sizes[a] * sizes[b] - 1) * (w + 1);
sizes[b] += sizes[a];
p[a] = b;
}
}
cout << res << endl;
严格次小生成树
struct Edge // int dist1[N][N],dist2[N][N];
{
int a,b,w;
bool f;
bool operator <(const Edge &t) const
{
return w < t.w;
}
}edge[M];
void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[])
{
d1[u] = maxd1, d2[u] = maxd2;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
int td1 = maxd1, td2 = maxd2;
if(w[i] > td1) td2 = td1, td1 = w[i];
else if(w[i] < td1 && w[i] > td2) td2 = w[i];
dfs(j,u,td1,td2,d1,d2);
}
}
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i = 1;i<=n;i++) p[i] = i;
for(int i = 0; i < m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edge[i] = {a,b,w};
}
sort(edge,edge + m);
ll sum = 0;
for(int i = 0;i<m;i++)
{
int a = edge[i].a, b = edge[i].b , w = edge[i].w;
int pa = find(a), pb = find(b);
if(pa != pb)
{
p[pa] = pb;
sum += w;
add(a,b,w), add(b,a,w);
}
}
for(int i = 1;i<=n;i++) dfs(i,-1,-1e9,-1e9,dist1[i],dist2[i]);
ll res = 1e18;
for(int i = 0;i<m;i++)
{
if(!edge[i].f)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
ll t = 0;
if(w > dist1[a][b]) t = sum + w - dist1[a][b];
else if(w > dist2[a][b]) t = sum + w - dist2[a][b];
res = min(res,t);
}
}
cout << res << endl;
动态规划
// 01背包
for(int i = 0 ;i<n;i++)
{
int v,w;
scanf("%d%d",&v,&w);
for(int j = m;j>=v;j--) f[j] = max(f[j],f[j - v] + w);
}
// 完全背包
for(int i = 0;i<n;i++)
{
int v,w;
scanf("%d%d",&v,&w);
for(int j = v;j<=m;j++) f[j] = max(f[j],f[j - v] + w); // 完全背包体积从小到大枚举
}
//多重背包问题 暴力写法
for(int i = 1;i<=n;i++) // 物品数量从1开始枚举
{
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 - v[i] * k] + w[i] * k);
}
}
}
// 多重背包 二进制优化
for(int i = 1;i<=n;i++)
{
int a,b,s;
scanf("%d%d%d",&a,&b,&s);
int k = 1;
while(k <= s)
{
cnt++;
v[cnt] = k * a;
w[cnt] = k * b;
s -= k;
k *= 2;
}
if(s)
{
cnt++;
v[cnt] = s * a;
w[cnt] = s * b;
}
}
n = cnt;
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++)
{
f[i] = 1;
for(int j = 1;j<i;j++)
{
if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1);
}
}
int ans = 0;
for(int i = 1;i<=n;i++) ans = max(ans, f[i]);
// 最长上升子序列 二分(贪心)优化
for(int i = 1;i<=n;i++)
{
if(!v.size() || a[i] > v.back()) v.push_back(a[i]);
else *lower_bound(v.begin(),v.end(),a[i]) = a[i];
}
cout << v.size() << endl;
传纸条 // 两次(1,1) 到(n,m) 不经过重复的点的最大值
for(int k = 2;k<=n + m;k++)
{
for(int i1 = 1;i1 <= n;i1++)
{
for(int i2 = 1;i2 <=n;i2++)
{
int j1 = k - i1, j2 = k - i2;
if(j1 < 1 || j1 > m || j2 < 1 || j2 > m) continue;
int t = w[i1][j1];
if(i1 != i2) t += w[i2][j2];
f[k][i1][i2] = max(f[k - 1][i1 - 1][i2], f[k - 1][i1][i2 - 1]);
f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1]);
f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2]);
f[k][i1][i2] += t;
}
}
}
cout << f[n + m][n][n] << endl;
// 求用几个非上升序列能将全部序列表示出来
for(int i = 1;i<=n;i++)
{
f[i] = 1;
for(int j = 1; j < i ;j++)
{
if(h[i] <= h[j]) f[i] = max(f[i], f[j] + 1);
}
}
int res = 0;
for(int i = 1;i<=n;i++) res = max(res,f[i]);
int cnt = 0;
for(int i = 1;i<=n;i++)
{
int k = 0;
while(k < cnt && g[k] < h[i]) k++;
g[k] = h[i];
if(k >= cnt) cnt++;
}
cout << res << endl;
cout << cnt << endl;
// 求用几个单调上升或者单调下降的序列能将全部序列表示出来
void dfs(int u ,int su, int du)
{
if(su + du >= ans) return;
if(u > n)
{
ans = min(ans,su + du);
return;
}
int k = 0;
while(k < su && up[k] >= h[u]) k++;
int t = up[k];
up[k] = h[u];
if(k < su) dfs(u + 1,su,du);
else dfs(u + 1,su + 1,du);
up[k] = t;
k = 0;
while(k < du && down[k] <= h[u]) k++;
t = down[k];
down[k] = h[u];
if(k < du) dfs(u + 1,su,du);
else dfs(u + 1,su,du + 1);
down[k] = t;
}
for(int i = 1;i<=n;i++) scanf("%d",&h[i]);
ans = n;
dfs(1,0,0);
cout << ans << endl;
// 最长上升公共子序列
for(int i = 1;i<=n;i++)
{
int maxv = 1;
for(int j = 1;j<=n;j++)
{
f[i][j] = f[i - 1][j];
if(a[i] == b[j]) f[i][j] = max(f[i][j],maxv);
if(a[i] > b[j]) maxv = max(maxv,f[i][j] + 1);
}
}
int ans = 0;
for(int i = 1;i<=n;i++) ans = max(ans,f[n][i]);
// 求v不超过m - 1时获取到的最大价值,并求此时剩余的体积
for(int i = 0;i < k ;i++)
{
int c,r;
scanf("%d%d",&c,&r);
for(int j = n;j >= c; j--)
{
for(int v = m - 1; v >= r; v--)
{
f[j][v] = max(f[j][v], f[j - c][v - r] + 1);
}
}
}
cout << f[n][m - 1] << " ";
int v = m - 1;
while( v > 0 && f[n][v-1] == f[n][m-1]) v--;
cout<< m - v <<endl;
// 求n个整数中选若干个组成m的方案
f[0] = 1;
for(int i = 0;i<n;i++)
{
for(int j = m; j >= a[i]; j--) f[j] += f[j - a[i]];
}
// 求用原来的n个数能表示出来的所有数 等价于新的m个数能表示出来的所有的数
cin>>n;
for(int i = 0;i < n; i++) scanf("%d",&a[i]);
sort(a, a + n);
int m = a[n - 1];
memset(f,0,sizeof f);
f[0] = 1;
int res = 0;
for(int i = 0 ;i < n;i++)
{
if(!f[a[i]]) res++;
for(int j = a[i]; j <= m;j ++) f[j] += f[j - a[i]];
}
cout << res << endl;
// 分组背包
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。
for(int i = 1;i<=n;i++)
{
scanf("%d",&s[i]);
for(int k = 1;k<=s[i];k++) scanf("%d%d",&v[i][k],&w[i][k]);
}
for(int i = 1;i<=n;i++)
{
for(int j = m;j>=0;j--)
{
for(int k = 1;k<=s[i];k++)
{
if(v[i][k] > j) continue;
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
cout << f[m] << endl;
// 混合背包
if(!s) // 能用无限次
{
for(int j = v; j <= m;j++) f[j] = max(f[j], f[j - v] + w);
}
else
{
if(s == -1) s = 1; // 能用一次
for(int k = 1; k <= s;k *= 2) // 能用s次
{
for(int j = m; j >= v * k; j--) f[j] = max(f[j], f[j - v * k] + w * k);
s -= k;
}
if(s)
{
for(int j = m;j >= v * s; j--) f[j] = max(f[j], f[j - v * s] + w * s);
}
}
//二维费用的背包问题
for(int i = 0;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
for(int j = v;j >= a;j--)
{
for(int k = m;k >= b;k--) f[j][k] = max(f[j][k], f[j - a][k - b] + c);
}
}
// 二维费用的背包问题求最小值
memset(f,0x3f,sizeof f);
f[0][0] = 0;
for(int i = 0;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
for(int j = v1;j >= 0; j--)
{
for(int k = v2; k >= 0; k--)
{
f[j][k] = min(f[j][k], f[max(0, j - a)][max(0, k - b)] + c);
}
}
}
cout << f[v1][v2] << endl;
分公司数N,设备台数M;
N*M的矩阵,矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。
第一行输出最大盈利值;
接下N行,每行有2个数,即分公司编号和该分公司获得设备台数。// 输出方案
cin>>n>>m;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++) scanf("%d",&w[i][j]);
for(int i = 1;i<=n;i++)
{
for(int j = 0;j<=m;j++)
{
f[i][j] = f[i - 1][j];
for(int k = 0;k<=j;k++)
{
f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
}
}
}
cout << f[n][m] << endl;
int j = m;
for(int i = n;i >= 1;i--)
{
for(int k = 0;k<=j;k++)
{
if(f[i][j] == f[i - 1][j - k] + w[i][k])
{
ways[i] = k;
j -= k;
break;
}
}
}
for(int i = 1;i<=n;i++) cout<< i<< " " << ways[i] <<endl;
// 有依赖的背包问题
void dfs(int u) // 选子节点之前必须选其父子点
{
for(int i = h[u]; i != -1; i = ne[i])
{
int son = e[i];
dfs(son);
for(int j = m - v[u];j >= 0;j--)
{
for(int k = 0;k <= j; k++)
{
f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
}
}
}
for(int i = m; i>= v[u];i--) f[u][i] = f[u][i - v[u]] + w[u];
for(int i = 0;i< v[u];i ++) f[u][i] = 0;
}
main:
int root = 0;
for(int i = 1;i<=n;i++)
{
int p;
scanf("%d%d%d",&v[i],&w[i],&p);
if(p == -1) root = i;
else add(p,i);
}
dfs(root);
cout << f[root][m] <<endl;
// 背包问题求方案数
memset(f, -0x3f, sizeof f);
f[0] = 0;
g[0] = 1;
for(int i = 0; i < n;i++)
{
int v,w;
scanf("%d%d",&v,&w);
for(int j = m;j >= v;j--)
{
int cnt = 0;
int maxv = max(f[j], f[j - v] + w);
if(f[j] == maxv) cnt += g[j];
if(f[j - v] + w == maxv) cnt += g[j - v];
f[j] = maxv;
g[j] = cnt % mod;
}
}
int res = 0;
int t = 0;
for(int i = 1;i<=m;i++) t = max(t,f[i]);
for(int i = 0; i <= m;i++) if(f[i] == t) res = (res + g[i]) % mod;
cout << res << endl;
// 背包问题求具体方案
for(int i = n; i >= 1; i--)
{
for(int j = 0 ; j <= m ;j++)
{
f[i][j] = f[i + 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
}
int j = m;
for(int i = 1;i<=n;i++)
{
if(f[i][j] == f[i + 1][j - v[i]] + w[i] && j >= v[i])
{
printf("%d ",i);
j -= v[i];
}
}
状态机
memset(f,0,sizeof f); // 不经过相邻的两个地方 获得的最大值
for(int i = 1;i<=n;i++)
{
f[i][0] = max(f[i - 1][1], f[i - 1][0]);
f[i][1] = f[i - 1][0] + a[i];
}
cout << max(f[n][0], f[n][1]) << endl;
// 最多不超过m次交易的股票买卖
memset(f,-0x3f,sizeof f);
for(int i = 0;i<=n;i++) f[i][0][0] = 0;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - a[i]);
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + a[i]);
}
}
int res = 0;
for(int i = 0;i <= m ;i++) res = max(res,f[n][i][0]);
//卖出股票后,第二天不能买入股票 (即冷冻期为 1 天)
f[0][0] = f[0][1] = -1e9;
f[0][2] = 0;
for(int i = 1;i<=n;i++)
{
f[i][0] = f[i - 1][1] + a[i];
f[i][1] = max(f[i - 1][1], f[i - 1][2] - a[i]);
f[i][2] = max(f[i - 1][2], f[i - 1][0]);
}
int res = 0;
for(int i = 1;i<=n;i++) res = max(res, f[i][0]), res = max(res,f[i][2]);
cout << res << endl;
区间DP
石子排成一排 合并相邻的两个石子
for(int i = 1;i<=n;i++) scanf("%d",&s[i]), s[i] += s[i - 1];
for(int len = 2; len <= n; len++)
{
for(int i = 1; i + len - 1 <= n; i++)
{
int l = i, r = i + len - 1;
f[l][r] = 1e8;
for(int k = l; k < r; k++)
{
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}
}
}
cout << f[1][n] << endl;
// 环形石子合并
for(int i = 1;i<=n;i++) scanf("%d",&w[i]), w[i + n] = w[i];
for(int i = 1;i<=n * 2;i++) s[i] = s[i - 1] + w[i];
memset(f,-0x3f,sizeof f);
memset(g,0x3f,sizeof g);
for(int i = 1;i<= 2 * n;i++) f[i][i] = 0, g[i][i] = 0;
for(int len = 2; len<= n; len++)
{
for(int l = 1;l + len <= 2 * n;l++)
{
int r = l + len - 1;
for(int k = l; k < r;k++)
{
f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = min(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}
// 能量项链 聚合两个项链释放的能量为 m × r × n
for(int i = 1;i<=n;i++) scanf("%d",&a[i]), a[i + n] = a[i];
for(int len = 3;len <= n + 1;len++)
{
for(int l = 1; l + len - 1 <= 2 * n; l++)
{
int r = l + len - 1;
for(int k = l + 1; k < r; k++) f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
}
}
int res = 0;
for(int i = 1;i<=n;i++) res = max(res,f[i][i + n]);
计数类DP
现在给定一个正整数 n,请你求出 n 共有多少种不同的划分方法。例如5 = 1 + 2 + 2
f[0] = 1;
for(int i = 1;i<=n;i++)
{
for(int j = i ;j <= n; j++) f[j] = (f[j] + f[j - i]) % mod;
}
状压DP
蒙德里安的梦想 先放横着的
for(int i = 0 ;i < 1 << n; i++)
{
int cnt = 0;
bool f = true;
for(int j = 0; j < n ;j++)
{
if(i >> j & 1)
{
if(cnt & 1)
{
f = false;
break;
}
cnt = 0;
}
else cnt++;
}
if(cnt & 1) f = false;
st[i] = f;
}
for(int i = 0 ;i < 1 << n ;i++)
{
state[i].clear();
for(int j = 0; j < 1 << n; j++)
{
if((i & j) == 0 && st[i | j]) state[i].push_back(j);
}
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 1;i<=m;i++)
{
for(int j = 0 ; j < 1 << n ;j++)
{
for(int k = 0; k < state[j].size();k++) f[i][j] += f[i - 1][state[j][k]];
}
}
cout << f[m][0] << endl;
最短哈密顿路径
求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
memset(f, 0x3f,sizeof f);
f[1][0] = 0;
for(int i = 0;i< 1 << n ;i++)
{
for(int j = 0; j < n;j++)
{
if(i >> j & 1)
{
for(int k = 0;k<n;k++)
if(i - (1 << j) >> k & 1) f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[j][k]);
}
}
}
cout << f[(1 << n) - 1][n - 1] << endl;
// n × n 的棋盘上放 k 个国王,国王可攻击相邻的 8 个格子,求使它们无法互相攻击的方案总数
bool check(int x)
{
for(int i = 0 ;i<n;i++)
{
if((x>>i&1) && (x>>i+1 &1)) return false;
}
return true;
}
int count(int x)
{
int res = 0;
for(int i = 0 ;i<n;i++) res += x>>i &1;
return res;
}
int main()
{
cin>>n>>m;
for(int i = 0 ; i<1<<n ;i++)
{
if(check(i))
{
state.push_back(i);
cnt[i] = count(i);
}
}
for(int i = 0 ; i<state.size();i++)
{
for(int j = 0 ;j<state.size();j++)
{
int a = state[i], b = state[j];
if((a&b)==0 && check(a|b))
{
head[i].push_back(j);
}
}
}
f[0][0][0] = 1;
for(int i = 1;i<=n+1;i++)
{
for(int j = 0 ;j<=m;j++)
{
for(int a = 0;a<state.size();a++)
{
for(int b: head[a])
{
int c = cnt[state[a]];
if(j>=c) f[i][j][a] += f[i-1][j-c][b];
}
}
}
}
cout<<f[n+1][m][0]<<endl;
// M × N 个小方格组成,现在他要在土地里种植玉米。一些土地无法种玉米,
而且,相邻的土地不能同时种植玉米,也就是说种植玉米的所有方格之间都不会有公共边缘。求方案数
vector<int> state;
vector<int> head[M];
bool check(int x)
{
for(int i = 0 ; i<m;i++)
{
if((x >> i &1) && (x >> i+1 &1)) return false;
}
return true;
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
for(int j = 0;j<m;j++)
{
int t;
cin>>t;
g[i] += !t <<j;
}
}
for(int i = 0;i<1<<m;i++)
{
if(check(i))
{
state.push_back(i);
}
}
for(int i = 0 ;i<state.size();i++)
{
for(int j = 0;j<state.size();j++)
{
int a = state[i], b = state[j];
if((a&b)==0) head[i].push_back(j);
}
}
f[0][0] = 1;
for(int i = 1;i<=n+1;i++)
{
for(int j = 0;j<state.size();j++)
{
for(int k : head[j])
{
if(g[i] & state[j]) continue;
f[i][j] = (f[i-1][k] + f[i][j])%mod;
}
}
}
cout<<f[n+1][0]<<endl;
return 0;
}
数位DP
// 求 a 和 b 之间的所有数字中 0∼9 的出现次数
int base[10];
int f[10][10];
int g[10][10];
void init()
{
base[0] = 1;
for(int i = 1 ; i <= 9 ; i++) base[i] = base[i-1]*10;
//从00……0 - 99……9 的各位数字有多少个,其中i为数字个数(包含前导零)
for(int i = 0 ; i <= 9 ; i++) f[1][i] = 1;
for(int i = 2 ; i <= 9 ; i++)
for(int j = 0 ; j <= 9 ; j++)
f[i][j] = f[i-1][j]*10 + base[i-1];
//从1 - 99……9 的各位数字有多少个,其中i为数字个数(不包含前导零)
for(int i = 1 ; i <= 9 ; i++) g[1][i] = 1;//循环从1开始
for(int i = 2 ; i <= 9 ; i++) {
g[i][0] = g[i-1][0] + f[i-1][0]*9;
for(int j = 1 ; j <= 9 ; j++)
g[i][j] = g[i-1][j] + f[i-1][j]*9 + base[i-1];
}
}
vector<int> dp(int n)
{
vector<int> ans(10,0); //记录答案
if(n<=0) return ans; //边界条件
vector<int> nums;
while(n) nums.push_back(n%10), n/=10;
vector<int> last(10,0); //记录前缀中各个数字个数
//统计1 - 99……9(n-1个9)里面各个数字有多少个
for(int i = 0 ; i <= 9 ; i++) ans[i] = g[nums.size()-1][i];
//统计大于10……0(n-1个0) 的树里各个数字有多少个
for(int i = nums.size()-1 ; i >=0 ; i--) {
//循环变量i可以表示剩下的数字有多少个
int x = nums[i];
for(int j = i==nums.size()-1 ; j < x ; j++) { //第一次循环不能有0
//前缀部分
for(int k = 0 ; k <= 9 ; k++)
ans[k] += last[k] * base[i];
//当前位置部分
ans[j] += base[i];
//后缀部分
for(int k = 0 ; k <= 9 ; k++)
ans[k] += f[i][k];
}
//更新前缀计数器
last[x] ++;
//统计叶子节点(这个数本身)
if(!i) for(int k = 0 ; k <= 9 ; k++) ans[k] += last[k];
}
return ans;
}
vector<int> ask(int a, int b)
{
auto x = dp(b);
auto y = dp(a-1);
vector<int> ans;
for(int i = 0 ; i <= 9 ; i++) ans.push_back(x[i]-y[i]);
return ans;
}
void print(vector<int> ans)
{
for(auto x:ans) printf("%d ",x);
puts("");
}
int main()
{
init();
int a,b;
while(cin >> a >> b, a||b) {
if(a>b) swap(a,b);
auto t = ask(a,b);
print(t);
}
return 0;
}
//求给定区间 [X,Y] 中满足下列条件的整数个数:这个数恰好等于 K 个互不相等的 B 的整数次幂之和。
例如
17=2^4+2^0
18=2^4+2^1
20=2^4+2^2
int f[N][N];
int a,b,K,B;
void init()
{
for(int i = 0;i<N;i++)
{
for(int j = 0;j<=i;j++)
{
if(!j) f[i][j] = 1;
else f[i][j] = f[i-1][j] + f[i-1][j-1];
}
}
}
int dp(int n)
{
if(!n) return 0;
vector<int> num;
int last = 0, res = 0;
while(n)
{
num.push_back(n % B);
n /= B;
}
for(int i = num.size() - 1;i>=0;i--)
{
int x = num[i];
if(x)
{
res += f[i][K - last];
if(x>1)
{
if(K - last - 1 >= 0) res += f[i][K - last - 1];
break;
}
else
{
last++;
if(last - K > 0) break;
}
}
if(!i && K == last) res++;
}
return res;
}
int main()
{
init();
cin>>a>>b>>K>>B;
printf("%d",dp(b) - dp(a-1));
return 0;
}
// 指定一个整数闭区间 [a,b],问这个区间内有多少个不降数 如123、 446
const int N = 15;
int f[N][N];
void init()
{
for(int i = 0;i<=9;i++) f[1][i] = 1;
for(int i = 2;i<N;i++)
{
for(int j = 0;j<=9;j++)
{
for(int k = j;k<=9;k++) f[i][j] += f[i-1][k];
}
}
}
int dp(int n)
{
if(!n) return 1;
vector<int> num;
while(n)
{
num.push_back(n%10);
n /= 10;
}
int last = 0, res = 0;
for(int i = num.size() - 1; i>=0 ;i--)
{
int x = num[i];
for(int j = last;j<x;j++) res += f[i+1][j];
if(last>x) break;
last = x;
if(!i) res++;
}
return res;
}
int main()
{
init();
while(cin>>a>>b)
{
printf("%d\n",dp(b) - dp(a-1));
}
return 0;
}
Windy 数:不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。
求在 A 和 B 之间,包括 A 和 B,总共有多少个 Windy 数?
const int N = 15;
int f[N][N];
void init()
{
for(int i = 0;i<=9;i++) f[1][i] = 1;
for(int i = 2;i<N;i++)
{
for(int j = 0 ;j<=9;j++)
{
for(int k = 0;k<=9;k++) if(abs(j - k) >= 2) f[i][j] += f[i-1][k];
}
}
}
int dp(int n)
{
if(!n) return 0;
int res = 0;
vector<int> num;
while(n)
{
num.push_back(n%10);
n /= 10;
}
int last = -2;
for(int i = num.size() - 1;i>=0;i--)
{
int x = num[i];
for(int j = (i == num.size() - 1);j < x ;j++) if(abs( j - last ) >= 2) res += f[i+1][j];
if(abs(last - x) < 2) break;
last = x;
if(!i) res++;
}
for(int i = 1;i<num.size();i++)
{
for(int j = 1;j<=9;j++) res += f[i][j];
}
return res;
}
int main()
{
init();
int l,r;
cin>>l>>r;
cout<< dp(r) - dp(l - 1) <<endl;
return 0;
}
树形DP
// 没有上司的舞会
void dfs(int u)
{
f[u][1] = w[u];
for(int i = h[u] ; i != -1 ; i = ne[i])
{
int j = e[i];
dfs(j);
f[u][0] += max(f[j][0], f[j][1]);
f[u][1] += f[j][0];
}
}
int main()
{
cin>>n;
memset(h, -1 , sizeof h);
for(int i = 1;i<=n;i++) scanf("%d",&w[i]);
for(int i = 0; i < n - 1; i ++)
{
int a,b;
scanf("%d%d",&a,&b);
st[a] = true;
add(b,a);
}
int root = 1;
while(st[root]) root++;
dfs(root);
cout << max(f[root][1], f[root][0]) << endl;
// 树的最长路径
int dfs(int u, int f)
{
int d1 = 0, d2 = 0;
int dist = 0;
for(int i = h[u]; i != - 1; i = ne[i])
{
int j = e[i];
if(j == f) continue;
int d = dfs(j, u) + w[i];
if(d >= d1)
{
d2 = d1, d1 = d;
}
else if(d > d2)
{
d2 = d;
}
dist = max(d,dist);
}
res = max(res,d1 + d2);
return dist;
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i = 0;i < n - 1; i ++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
dfs(1, - 1);
cout << res << endl;
return 0;
}
// 树的中心 、 该点离树中其他结点最远距离最近
int w[M],e[M],h[N],ne[M],p1[M],p2[M];
int n,idx;
int d1[M],d2[M],up[M];
int dfs_d(int u, int father)
{
d1[u] = d2[u] = -INF;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j==father) continue;
int d = dfs_d(j,u) + w[i];
if(d>=d1[u])
{
d2[u] = d1[u], d1[u] =d;
p2[u] = p1[u], p1[u] = j;
}
else if(d>=d2[u])
{
d2[u] = d;
p2[u] = j;
}
}
if(d1[u]==-INF) d1[u] = d2[u] = 0;
return d1[u];
}
void dfs_u(int u, int father)
{
for(int i = h[u];i != -1; i = ne[i])
{
int j = e[i];
if(j==father) continue;
if(p1[u]==j) up[j] = max(up[u],d2[u]) + w[i];
else up[j] = max(up[u],d1[u]) + w[i];
dfs_u(j,u);
}
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for(int i = 0 ;i<n-1;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c), add(b,a,c);
}
dfs_d(1,-1);
dfs_u(1,-1);
int res = INF;
for(int i = 1;i<=n;i++) res = min(res,max(d1[i],up[i]));
printf("%d",res);
return 0;
}
记忆化搜索
//滑雪
int dp(int x, int y)
{
if(f[x][y] != -1) return f[x][y];
f[x][y] = 1;
int dx[4] = {-1,0,1,0}, dy[4] = {0,-1,0,1};
for(int i = 0;i<4;i++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 1 || a > n || b < 1 || b > m) continue;
if(h[a][b] >= h[x][y]) continue;
f[x][y] = max(f[x][y], dp(a,b) + 1);
}
return f[x][y];
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++) scanf("%d",&h[i][j]);
int res = 0;
memset(f, -1, sizeof f);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++) res = max(res, dp(i,j));
cout << res << endl;
return 0;
}
数据结构
表达式求值 如(2+2)*(1+1) = 8
stack<int> num;
stack<char> op;
unordered_map<char,int> h{ {'+',1},{'-',1},{'*',2},{'/',2} };
void eval()
{
int a = num.top();
num.pop();
int b = num.top();
num.pop();
char p = op.top();
op.pop();
int r = 0;
if(p == '+') r = a + b;
if(p == '-') r = b - a;
if(p == '*') r = a * b;
if(p == '/') r = b / a;
num.push(r);
}
int main()
{
string s;
cin>>s;
for(int i = 0 ;i<s.size();i++)
{
if(isdigit(s[i]))
{
int x = 0, j = i;
while(isdigit(s[j]))
{
x = x * 10 + s[j] - '0';
j++;
}
num.push(x);
i = j - 1;
}
else if(s[i]=='(') op.push(s[i]);
else if(s[i]==')')
{
while(op.top() != '(') eval();
op.pop();
}
else
{
while(op.size() && h[op.top()] >= h[s[i]]) eval();
op.push(s[i]);
}
}
while(op.size()) eval();
printf("%d",num.top());
return 0;
}
// 单调栈 给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。
int a[N], q[N];
int n;
int tail = -1;
int main()
{
cin>>n;
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
q[++tail] = a[1];
printf("-1 ");
for(int i = 2;i<=n;i++)
{
if(q[tail] >= a[i])
{
while(q[tail] >= a[i] && tail >=0) tail--;
if(tail == -1) printf("-1 ");
else printf("%d ",q[tail]);
q[++tail] = a[i];
}
else
{
printf("%d ",q[tail]);
q[++tail] = a[i];
}
}
return 0;
}
// 滑动窗口 n 和 k,分别代表数组长度和滑动窗口的长度
输出,从左至右,每个位置滑动窗口中的最小值和最大值
int a[N],q[N],h[N];
int n,k;
int head , tail = -1;
int main()
{
cin>>n>>k;
for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
for(int i = 1;i<=n;i++)
{
while(tail >= head && a[i] < q[tail]) tail --;
q[++tail] = a[i];
h[tail] = i;
while(h[tail] - h[head] >=k && head <= tail) head ++;
if(i>=k) printf("%d ",q[head]);
}
puts("");
head = 0, tail = -1;
for(int i = 1;i<=n;i++)
{
while(tail >= head && a[i] > q[tail]) tail --;
q[++tail] = a[i];
h[tail] = i;
while(h[tail] - h[head] >=k && head <= tail) head ++;
if(i>=k) printf("%d ",q[head]);
}
return 0;
}
// KMP
char p[N], q[M];
int ne[N];
int n,m;
int main()
{
cin>> n >> p + 1 >> m >> q + 1;
for(int i = 2, j = 0 ; i <= n ; i ++) // 求next数组
{
while(p[i] != p[j + 1] && j) j = ne[j];
if(p[i] == p[j + 1]) j++;
ne[i] = j;
}
for(int i = 1, j = 0 ; i <= m ;i ++) // 匹配过程
{
while(q[i] != p[j + 1] && j) j = ne[j];
if(q[i] == p[j + 1]) j++;
if(j == n)
{
printf("%d ",i - j);
j = ne[j];
}
}
return 0;
}
Trie树
int son[26][N], cnt[N];
int n,m,idx;
void insert(string s) // 插入一个字符串
{
int p = 0;
for(int i = 0;i<s.size();i++)
{
int u = s[i] - 'a';
if(!son[u][p]) son[u][p] = ++idx;
p = son[u][p];
}
cnt[p]++;
}
int query(string s) // 查询一个字符串出现的次数
{
int p = 0;
for(int i = 0 ;i<s.size();i++)
{
int u = s[i] - 'a';
if(!son[u][p]) return 0;
p = son[u][p];
}
return cnt[p];
}
int main()
{
cin>>n;
string s,s1;
while(n--)
{
cin>>s>>s1;
if(s=="I") insert(s1);
else printf("%d\n",query(s1));
}
return 0;
}
//Trie树求N个整数中选出两个进行 xor(异或)运算,得到的结果最大是多少
const int N = 100010, M = 31 * N;
int son[M][2];
int a[N];
int n,idx;
int res;
void insert(int x)
{
int p = 0;
for(int i = 30;i>=0;i--)
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}
int query(int x)
{
int cnt = 0;
int p = 0;
for(int i = 30;i>=0;i--)
{
int u = x >> i & 1;
if(son[p][!u])
{
cnt += 1 << i;
p = son[p][!u];
}
else p = son[p][u];
}
return cnt;
}
int main()
{
cin>>n;
for(int i = 0 ;i<n;i++)
{
scanf("%d",&a[i]);
insert(a[i]);
}
for(int i = 0;i<n;i++)
{
res = max(res,query(a[i]));
}
printf("%d",res);
return 0;
}
并查集
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() // 求连通块中点的数量
{
cin>>n>>m;
for(int i = 1;i<=n;i++)
{
p[i] = i;
cnt[i] = 1;
}
while(m--)
{
string s;
cin>>s;
if(s == "C")
{
int a,b;
scanf("%d%d",&a,&b);
if(find(a) != find(b))
{
cnt[find(b)] += cnt[find(a)];
p[find(a)] = find(b);
}
}
else if(s == "Q1")
{
int a,b;
scanf("%d%d",&a,&b);
if(find(a) == find(b)) printf("Yes\n");
else printf("No\n");
}
else
{
int x;
scanf("%d",&x);
printf("%d\n",cnt[find(x)]);
}
}
return 0;
}
// 食物链
int find(int x) // 维护到祖宗节点距离的并查集
{
if(x != p[x])
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++) p[i] = i;
while(m--)
{
int k,a,b;
scanf("%d%d%d",&k,&a,&b);
if(a > n || b > n)
{
res++;
continue;
}
int x = find(a), y = find(b);
if(k == 1)
{
if(x == y && (d[a] - d[b]) % 3) res ++;
else if(x != y)
{
p[x] = y;
d[x] = d[b] - d[a];
}
}
else
{
if(x == y && (d[a] - d[b] - 1) % 3) res++;
else if(x != y) // d[x] + d[a] - 1 = d[b];
{
p[x] = y;
d[x] = d[b] - d[a] + 1;
}
}
}
printf("%d",res);
return 0;
}
// 字符串哈希
const int N = 100010, p = 131;
typedef unsigned long long ULL;
int h[N],b[N];
int n,m;
char s[N];
ULL query(int l , int r) // 取模的数用2^64,这样直接用unsigned long long存,溢出的结果就是取模的结果
{
return h[r] - h[l-1] * b[r - l + 1];
}
int main()
{
cin>> n >> m >> s + 1;
b[0] = 1;
for(int i = 1;i<=n;i++)
{
b[i] = b[i-1] * p;
h[i] = h[i-1] * p + s[i];
}
while(m--)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(query(l1,r1) == query(l2,r2)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
数学
// 试除法判断素数
bool is_prime(ll x)
{
if(x<2) return false;
for(int i = 2;i<=x/i;i++)
{
if(x%i==0) return false;
}
return true;
}
// 试除法分解约数
for(int i = 2;i<=x/i;i++)
{
int sum = 0;
if(x%i==0)
{
while(x%i==0)
{
x /= i;
sum++;
}
printf("%d %d\n",i,sum);
}
}
if(x>1) printf("%d 1\n",x);
puts("");
// 线性筛法求素数
for(int i = 2;i<=n;i++)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0; primes[j] <= n / i ;j++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
// 试除法求所有约数
void get_ys(int x)
{
vector<int> s;
for(int i = 1;i<=x/i;i++)
{
if(x%i==0)
{
s.push_back(i);
if(x/i != i) s.push_back(x/i);
}
}
sort(s.begin(),s.end());
for(int i = 0 ; i<s.size();i++) printf("%d ",s[i]);
puts("");
}
//求约数个数,约数之和
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数: (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和: (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
// 求最大公约数 gcd
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
// 欧拉函数
1∼N 中与 N 互质的数的个数被称为欧拉函数,记为 ϕ(N)。
若在算数基本定理中,N = p1^a1 * p2^a2 * p3^a3 …… * pm^am
ϕ(N) = N * (p1-1)/p1 * (p2-1)/p2 * (p3-1)/p3 …… * (pm-1)/pm
// 筛法求欧拉函数 // 求1-n中每个数的欧拉函数之和
ll prim(int n)
{
phi[1] = 1;
int cnt = 0;
for(int i = 2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++] = i;
phi[i] = i - 1;
}
for(int j = 0; primes[j] <= n / i; j++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0)
{
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * phi[primes[j]];
}
}
ll res = 1;
for(int i = 2;i<=n;i++) res += phi[i];
return res;
}
// 快速幂 注意mod1 = 0;
int qmi(int a, int k , int p) //求 a ^ k % p
ll res = 1;
while(k)
{
if(k&1) res = (ll) res * a % p;
k >>= 1;
a = (ll) a * a % p;
}
return res;
}
// 快速幂求逆元 一个数除b模m的结果等于这个数乘他的逆元模m
if(b % k ==0) printf("impossible\n"); //b存在乘法逆元的充要条件是b与模数m互质
else printf("%d\n",qmi(b,k-2,k));
//费马小定理
如果整数p是一个质数,且a不是p的倍数,则 a ^ (p-1) 模 p = 1;
// 扩展欧几里得算法
// 求x, y,使得ax + by = gcd(a, b)
void exgcd(int a, int b , int &x, int &y)
{
if(!b) x = 1, y = 0; // 需要返回最大公约数时需要加上 return a;
else
{
exgcd(b,a%b,x,y);
int t = x;
x = y;
y = t - a/b * y; // 如果需要返回最大公约数则 将exgcd换成int d = exgcd(b,a%b,x,y), 最后return d;
}
}
// 中国剩余定理
给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn,求一个最小的非负整数 x,满足 ∀i∈[1,n],x≡mi(mod ai)。
LL exgcd(LL a, LL b, LL& x, LL& y)
{
if(!b)
{
y = 0;
x = 1;
return a;
}
int d = exgcd(b,a%b,y,x);
y = y - a/b * x;
return d;
}
int main()
{
int n;
cin>>n;
bool has_answer = true;
LL a1, m1;
cin>>a1>>m1;
for(int i = 0; i<n-1; i++)
{
LL a2,m2,k1,k2;
cin>>a2>>m2;
LL d = exgcd(a1,a2,k1,k2);
if((m2-m1)%d)
{
has_answer = false;
break;
}
k1 = k1 *(m2-m1) / d;
LL t = a2/d;
k1 = (k1%t+t)%t;
m1 = a1 * k1 + m1;
a1 = abs(a1/d*a2);
}
if(has_answer) cout<<(m1%a1+a1)%a1<<endl;
else puts("-1");
return 0;
}
// 递推法求组合数
void init()
{
for(int i = 0;i<N;i++)
{
for(int j = 0;j<=i;j++)
{
if(!j) c[i][j] = 1;
else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}
}
}
// 通过预处理逆元的方式求组合数
fact[0] = infact[0] = 1; // 两个数组均是long long型的
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
printf("%lld\n",fact[a] * infact[b] % mod * infact[a-b] % mod);
// 用Lucas定理求组合数
int C(int a, int b, int p) // 通过定理求组合数C(a, b)
{
if (a < b) return 0;
LL x = 1, y = 1; // x是分子,y是分母
for (int i = a, j = 1; j <= b; i --, j ++ )
{
x = (LL)x * i % p;
y = (LL) y * j % p;
}
return x * (LL)qmi(y, p - 2, p) % p;
}
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;
}
// 卡特兰数
给定n个0和n个1,它们按照某种顺序排成长度为2n的序列,满足任意前缀中0的个数都不少于1的个数的序列的数量为:
Cat(n) = C(2n, n) / (n + 1)
// Nim游戏
定理: NIM博弈先手必胜,当且仅当 A1 ^ A2 ^ … ^ An != 0
// 容斥原理
请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。
int p[N];
int main()
{
int n,m,res=0;
cin>>n>>m;
for(int i = 0 ; i<m ; i++) cin>>p[i];
for(int i = 1; i < 1<<m ; i++)
{
int t = 1, cnt = 0;
for(int j = 0; j<m ;j++)
{
if(i>>j&1)
{
cnt++;
if((LL) t * p[j] >n)
{
t = -1;
break;
}
t *= p[j];
}
}
if(t!=-1)
{
if(cnt%2) res += n/t;
else res -= n/t;
}
}
cout<<res<<endl;
return 0;
}
贪心
// 区间选点
给定 N 个闭区间 [ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
struct edg
{
int l,r;
bool operator <(const edg & W) const
{
return r < W.r;
}
}edge[N];
int main()
{
cin>>n;
for(int i = 0 ;i < n ; i++)
{
int l,r;
scanf("%d%d",&l,&r);
edge[i] = {l,r};
}
sort(edge,edge + n);
int res = 1;
int end = edge[0].r;
for(int i = 0 ;i<n;i++)
{
int l = edge[i].l;
if(l > end)
{
res ++;
end = edge[i].r;
}
}
cout << res << endl;
return 0;
}
// 区间分组
给定 N 个闭区间 [ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。
struct edg
{
int l, r;
bool operator<(const edg & W) const
{
return l < W.l;
}
}edge[N];
int main()
{
cin>>n;
for(int i = 0 ;i<n;i++)
{
int l ,r;
scanf("%d%d",&l,&r);
edge[i] = {l,r};
}
sort(edge, edge + n);
priority_queue<int,vector<int>,greater<int> > heap;
for(int i = 0 ;i< n; i++)
{
int l = edge[i].l, r = edge[i].r;
if(heap.empty() || l <= heap.top()) heap.push(r);
else
{
heap.pop();
heap.push(r);
}
}
cout << heap.size()<< endl;
return 0;
}
// 区间覆盖
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出 −1。
int l,r;
int main()
{
cin>>l>>r>>n;
vector<pii> query;
for(int i = 0 ;i<n;i++)
{
int x1,x2;
scanf("%d%d",&x1,&x2);
query.push_back({x1,x2});
}
sort(query.begin(),query.end());
int res = 1;
int end = - 2e9;
if(query[0].first > l)
{
printf("-1");
return 0;
}
for(int i = 0 ;i<n;i++)
{
int x1 = query[i].first, x2 = query[i].second;
if(x1 < l)
{
end = max(end,x2);
}
else
{
if(x1 > end)
{
printf("-1");
return 0;
}
else
{
int j = i;
int cnt = -2e9;
while(query[j].first <= end)
{
cnt = max(cnt,query[j].second);
j++;
}
j--;
i = j ;
if(end != cnt)
{
res ++;
end = cnt;
}
if(end >= r) break;
}
}
}
if(end < r) res = -1;
cout << res <<endl;
}
// 小根堆 大根堆则是less
priority_queue<int, vector<int>, greater<int> > heap;
priority_queue<pii, vector<pii>, greater<pii> > heap; // pair
# 感谢大佬科普!
Orz