算法设计与分析期末上机板子——课内题目题意与题解分析+课外知识点总结！
课内
//解决爆栈，手动加栈，必须放在头文件之前
#pragma comment(linker,"/STACK:1024000000,1024000000")
//万能头文件，部分比赛中可能不让用
#include <bits/stdc++.h> //C++
//STL专用，使用了哪种数据结构，就要用到哪种头文件
#include <map> //C++
#include <vector> //C++
#include <set> //C++
#include <stack>//c++
#include <deque>//双端队列
//C++必备头文件，cin、cout及其相关函数在这里
#include <isotream> //C++
//strlen()、strcat()等字符串操作函数在这里
#include <cstring> //C++
#include <string.h> //C语言
//min()、max()等在这里
#include <cstdlib> //C++
#include <stdlib.h> //C语言
//scanf()、printf()以及和它们长得像的函数在这里
#include <cstdio> //C++
#include <stdio.h> //C语言
//sort()在这里
#include <algorithm>> //C++
//log()、sin()、pow()等数学运算的函数在这里
#include <cmath>> //C++
#include <math.h> //C语言
//文件模板
#include<bits/stdc++.h>
inline int getint(){//快读
int x = 0, f = 1;char ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch -'0';ch = getchar();}
return x * f;
}
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--) solve();
return 0;
}
堆实现C语言
题意：第一行一个正整数 n（1 \le n \le 10^5），表示操作的数量。接下来 n 行，每行为一个操作，数据保证后两种操作时堆非空。格式如下：
- 1 x：向堆中插入元素 xx（1 \le x \le 10^91 \le x \le 10^9）。
- 2：删除堆顶元素。
- 3：查询堆顶元素。
输出
对于每次查询堆顶元素时，输出一行一个正整数，表示此时堆顶元素的值。 在所有操作结束后，将堆中的元素从大到小依次输出到一行中。
#define maxn 1000005
#define inf 0x3f3f3f3f
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int n, sz, a[maxn];
void swap(int *a, int *b) {
int t = *a;
*a = *b, *b = t;
}
void maxHeapify(int x) {
int l = ls(x), r = rs(x), larg;
if (l <= sz && a[l] > a[x]) larg = l;
else larg = x;
if (r <= sz && a[r] > a[larg]) larg = r;
if (larg != x) swap(&a[x], &a[larg]), maxHeapify(larg);
}
void increaseKey(int i, int key) {
a[i] = key;
while (i > 1 && a[i / 2] < a[i]) {
swap(&a[i / 2], &a[i]);
i = i / 2;
}
}
void insert(int x) {
sz += 1;
a[sz] = -inf;
increaseKey(sz, x);
}
int top() {
return a[1];
}
void pop() {
if (sz < 1) exit(1);
a[1] = a[sz];
sz -= 1;
maxHeapify(1);
}
int main() {
scanf("%d", &n);
int i;
for (i = 1; i <= n; i++) {
int op, x;
scanf("%d", &op);
if (op == 1) {
scanf("%d", &x);
insert(x);
}
if (op == 2) pop();
if (op == 3) printf("%d\n", top());
}
while (sz) {
printf("%d ", top()), pop();
}
}
矩阵连乘
题意：每组数据 第一行-方阵阶数n 接下来n行，表示整数方阵A。输出 A n A^n An
#define maxn 205
typedef long long ll;
const int p = 1e9 + 7;
int n;
ll k;
struct Martix {
ll a[maxn][maxn];
};
inline Martix multiply(Martix x, Martix y) {
Martix z;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
z.a[i][j] = 0;
for (int k = 1; k <= n; k++) {
z.a[i][j] += x.a[i][k] * y.a[k][j];
z.a[i][j] %= p;
}
}
}
return z;
}
inline Martix fpow(Martix x, ll k) {
Martix y;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) y.a[i][j] = 1;
else y.a[i][j] = 0;
}
}
while (k) {
if (k & 1) y = multiply(y, x);
x = multiply(x, x);
k >>= 1;
}
return y;
}
void solve{
scanf("%d%", &n);
k = n;
Martix x;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%lld", &x.a[i][j]);
x = fpow(x, k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%lld ", x.a[i][j]);
}
printf("\n");
}
}
E1D连分数计算
题意：
可用一组序列 表示，我们记其第 n n n 项表示为
p n q n = a 0 + 1 a 1 + 1 a 2 + 1 a 3 + 1 ? + 1 a n \frac{p_n}{q_n} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\ddots + \frac{1}{a_n}}}}} qn?pn??=a0?+a1?+a2?+a3?+?+an?1?1?1?1?1?
现给出 a 0 , a 1 , ? ? , a n a_0, a_1, \cdots, a_n a0?,a1?,?,an?，求出其表示的分数 p n q n \frac{p_n}{q_n} qn?pn?? 在模 998244353 998244353 998244353 意义下的值。即输出 r n = p n ? q n ? 1 ? m o d ? 998244353 r_n = p_n \cdot q_n^{-1} \bmod 998244353 rn?=pn??qn?1?mod998244353，其中 q n ? 1 满足 q n ? q n ? 1 ≡ 1 ( m o d 998244353 ) q_n^{-1} 满足q_n \cdot q_n^{-1} \equiv 1 \pmod{998244353} qn?1?满足qn??qn?1?≡1(mod998244353)。测试数据保证 q n q_n qn? 的逆元 q n ? 1 q_n^{-1} qn?1? 存在
const int mod = 998244353;
long long fp(long long a, long long x) {
long long ret = 1;
while (x) {
if (x & 1) { ret *= a; ret %= mod; }
a *= a; a %= mod;
x >>= 1;
}
return ret;
}
void solve(){
int n;
cin >> n;
vector<long long> a(n + 1);
vector<long long> p(n + 1), q(n + 1);
for (int i = 0; i <= n; i++)
cin >> a[i];
p[0] = a[0];
q[0] = 1;
p[1] = (a[0] * a[1] + 1) % mod;
q[1] = a[1];
for (int i = 2; i <= n; i++) {
p[i] = (a[i] * p[i - 1] + p[i - 2]) % mod;
q[i] = (a[i] * q[i - 1] + q[i - 2]) % mod;
}
cout << p[n] * fp(q[n], mod - 2) % mod << '\n';
}
C3A-钢管切割：动态规划
题意：第一行一个正整数 n n n（ 1 ≤ n ≤ 1 0 4 1 \le n \le 10^4 1≤n≤104），表示钢管的总长度。第二行 n n n 个正整数 p 1 , p 2 , … , p n p_1,p_2,\ldots,p_n p1?,p2?,…,pn?（ 1 ≤ p i ≤ 1 0 7 1 \le p_i \le 10^7 1≤pi?≤107），表示长度 i i i钢管的价格。
输出：第一行一个正整数，表示最大总销售价格。第二行一个正整数 k k k，表示钢管被分割成 k k k 段。第三行 k k k 个正整数 a 1 , … , a k a_1, \dots, a_k a1?,…,ak?，表示钢管的分割方式，需保证 ∑ a i = n \sum a_i = n ∑ai?=n
#include<bits/stdc++.h>
#define maxn 200005
typedef long long ll;
using namespace std;
ll read(){
ll x = 0, f = 1;char ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
int n, p[maxn];
ll f[maxn];
vector<int> ans;
void solve(){
n = read();
for(int i = 1; i <= n; i++) p[i] = read();
for(int i = 1; i <= n; i++){
for(int j = 0; j < i; j++){
f[i] = max(f[i], f[j] + p[i - j]);
}
}
printf("%lld\n", f[n]);
int now = n;
while(now){
for(int i = 1; i <= now; i++){
if(f[now] == f[now - i] + p[i]){
ans.push_back(i);
now -= i;
break;
}
}
}
printf("%d\n", ans.size());
for(int i = 0; i < ans.size(); i++) printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
}
C3C-流水线调度：动态规划
题意：
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int M = 1e5 + 5;
int p[3][M], t[3][3];
long long dp[3][M];
void solve() {
int m;
cin >> m;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < m; j++) {
cin >> p[i][j];
}
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> t[i][j];
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < 3; i++) {
dp[i][j] = inf;
for (int k = 0; k < 3; k++) {
dp[i][j] = min(
dp[i][j],
(j - 1 >= 0 ? dp[k][j - 1] + t[k][i] : 0LL) + p[i][j]
);
}
}
}
long long ans = inf;
for (int i = 0; i < 3; i++) {
ans = min(ans, dp[i][m - 1]);
}
cout << ans << '\n';
}
C3E-矩阵连乘效率：区间动态规划
题意：第一行一个整数 n n n（ 2 ≤ n ≤ 300 2 \le n \le 300 2≤n≤300） ，表示矩阵的个数。第二行 n + 1 n+1 n+1 个正整数 a 1 , a 2 , … , a n + 1 a_1,a_2,\ldots,a_{n+1} a1?,a2?,…,an+1?（ 1 ≤ a i ≤ 1 0 3 1 \le a_i \le 10^3 1≤ai?≤103），表示矩阵 A i A_i Ai? 的行数和列数为 a i a_i ai? 和 a i + 1 a_{i+1} ai+1?。
输出：一行一个浮点数，表示运算次数最多是最少的多少倍，结果保留4位小数。
#include<bits/stdc++.h>
#define maxn 305
typedef long long ll;
using namespace std;
ll read(){
ll x = 0, f = 1;char ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
int n, a[maxn];
ll f[maxn][maxn];
void solve(){
n = read();
memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n + 1; i++) a[i] = read(), f[i][i] = 0;
for(int len = 2; len <= n; len++){
for(int l = 1; l + len - 1 <= n; l++){
int r = l + len - 1;
for(int k = l; k < r; k++){
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + 1ll * a[l] * a[k + 1] * a[r + 1]);
}
}
}
ll mx = f[1][n];
memset(f, 0, sizeof(f));
for(int len = 2; len <= n; len++){
for(int l = 1; l + len - 1 <= 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] + 1ll * a[l] * a[k + 1] * a[r + 1]);
}
}
}
printf("%.4f\n", 1.0 * f[1][n] / mx);
}
C3F-导弹轰炸（小偷问题）：动态规划
题意：每组测试数据包含两行。第一行包含一个正整数 n ( 2 ≤ n ≤ 1 0 5 ) n(2 \le n \le 10^5) n(2≤n≤105)。第二行包含 n n n 个正整数 w 1 , w 2 , … , w n ( 1 ≤ w i ≤ 1 0 5 ) w_1, w_2, \dots, w_n (1 \le w_i \le 10^5) w1?,w2?,…,wn?(1≤wi?≤105)，表示每个前哨站的重要程度。数据保证 ∑ n ≤ 4 ? 1 0 5 \sum n \le 4 \cdot10^5 ∑n≤4?105 。不能轰炸连续两个前哨战。
输出：对于每组测试数据，输出一行一个整数，表示在导弹互不干扰的情况下，能够轰炸的前哨站的重要程度之和的最大值。
#define maxn 200005
typedef long long ll;
const double eps = 1e-9;
const int mod = 998244353;
ll read(){
ll x = 0, f = 1;char ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
return x * f;
}
int n;
ll w[maxn], f[maxn][2];
void solve(){
n = read();
for(int i = 1; i <= n; i++) w[i] = read(), f[i][0] = f[i][1] = 0;
for(int i = 1; i <= n; i++){
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = w[i] + (i == 1 ? 0 : max(f[i - 2][0], f[i - 2][1]));
}
printf("%lld\n", max(f[n][0], f[n][1]));
}
C4F-最长公共子串/子序列长度：动规|||考虑加一个输出字符串
每组数据：输入两个字符串，输出一行两个整数，表示最长公共子串/最长公共子序列长度
const int N = 2005;
int n1, n2;
char s1[N], s2[N];
int f[N][N], g[N][N];
int maxf, maxg;
void solve() {
scanf("%s", s1 + 1);
scanf("%s", s2 + 1);
n1 = strlen(s1 + 1);
n2 = strlen(s2 + 1);
maxf = maxg = 0;
for (int i = 1; i <= n1; i++)
for (int j = 1; j <= n2; j++) {
f[i][j] = s1[i] == s2[j] ? f[i - 1][j - 1] + 1 : 0;
g[i][j] = max({g[i - 1][j - 1] + (s1[i] == s2[j]), g[i - 1][j], g[i][j - 1]});
maxf = max(maxf, f[i][j]);
maxg = max(maxg, g[i][j]);
}
printf("%d %d\n", maxf, maxg);
}
E3B-锯钢条:优先队列贪心
输入：第一行一个整数n,表示需要钢条数量，第二行n个整数，表示每个钢条的长度。
把钢条切成两段的代价为总长度的二倍，一次只能切一刀。输出最小代价。
typedef long long ll;
int n;
priority_queue<ll, vector<ll>, greater<> > q;//小根堆，默认大
int main(){
scanf("%d", &n);
for(int i = 1;i <= n;i++){
int x;
scanf("%d", &x);
q.push(x);
}
ll ans = 0;
for(int i = 1;i < n;i++){
ll x = q.top();q.pop();
x += q.top();q.pop();
ans += x * 2;
q.push(x);
}
printf("%lld", ans);
E3F-身高变化:动态规划
每组数据：输入：第一行n,m,k表示有n个事件，k次跳过机会，h表示初始身高。第二行n个整数，表示n个事件。若事件为正，身高增加；若事件为负，若身高+事件>0,那么可以越过，否则身高减半（向下取整），也可以使用一次跳过。当身高变为0,则失败
输出：若可以走完全程，输出最大值，否则输出"-1"
void solve(){
int n, k, h;
cin >> n >> k >> h;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<long long> f(k + 1, h), g(k + 1);
long long s = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= 0) {
s += a[i];
continue;
}
for (int j = 0; j <= k; j++)
if (f[j] > 0) f[j] += s;
s = 0;
for (int j = 0; j <= k; j++)
g[j] = max(f[j] > -a[i] ? f[j] : f[j] / 2,j + 1 <= k ? f[j + 1] : 0);
swap(f, g);
}
long long ans = *max_element(f.begin(), f.end());
if (ans <= 0) cout << -1 << '\n';
else cout << ans + s << '\n';
}
图论
C4E-无向图源点到所有点最短距离：Dijkstra模板！
求出无向图中一个源点到其余点的最短距离，并判断这个最短距离是否可接受。
第一行四个正整数n,m,s,t表示点/边/源点/限制
接下来m行，每行x,y,t表示x和y之间有边，代价为t
输出：第一行k表示有k个点不超过限制，接下来k行，每行x,t表示超过限制的节点以及代价。若无法到达该点，代价为-1.
typedef long long ll;
const ll inf=2e18;
class Dijkstra{
public :
int n;
vector<vector<pair<int,ll>>>g;
vector<ll>distance;
Dijkstra(int _n):n(_n){
g.resize(n+1);
distance.resize(n+1,inf);
}
void add(int u,int v,ll w){
g[u].emplace_back(v,w);
}
void solve(int s){//源点s
vector<bool> vis(n);
priority_queue<pair<ll,int>>q;//默认大根堆
distance[s]=0;
q.push({0,s});
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;
vis[u]=true;
for(auto p:g[u]){//u的所有出边
int v=p.first;
ll w=p.second;
if(distance[v]>distance[u]+w){//可以更新距离
distance[v]=distance[u]+w;
q.push({-distance[v],v});//压入负距离，小根堆
}
}
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m,s,cnt=0;ll t;
vector<int>ans;
cin>>n>>m>>s>>t;
Dijkstra d(n);
for(int i=1;i<=m;i++){
int u,v;ll w;
cin>>u>>v>>w;
d.add(u,v,w);
d.add(v,u,w);
}
d.solve(s);
for(int i=1;i<=n;i++)
if(d.distance[i]>t)
cnt++,ans.push_back(i);
cout<<cnt<<endl;
for(auto i:ans) cout<<i<<" "<<(d.distance[i]==inf?-1:d.distance[i])<<"\n";
}
C4G-1到其他的最短距离+负环：Bellman_Ford模板
每组数据：输入：第一行n,m接下来m行，每行三个整数u,v,w，表示u->v权值为w
输出：若存在负环输出“boo how”否则输出1点到每个点(1-n)的最短距离
#define MAXN 2003
#define MAXM 6003
#define MAX 1000000000
int n, m;
struct edge {
int from, to, val;
} e[MAXM * 2];
int dis[MAXN];
bool Bellman_Ford(int s) {
fill(dis, dis + n + 1, 2 * MAX);
dis[s] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dis[e[j].to] = min(dis[e[j].to], dis[e[j].from] + e[j].val);
for (int i = 1; i <= m; i++)
if (dis[e[i].to] > dis[e[i].from] + e[i].val)
return true;
return false;
}
void solve(){
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> e[i].from >> e[i].to >> e[i].val;
bool res = Bellman_Ford(1);
if (res) cout << "boo how\n";
else
for (int i = 1; i <= n; i++)
cout << (dis[i] >= MAX ? MAX : dis[i]) << " \n"[i == n];
}
C4I-有向图最长路径:动规
无权有向图最长路径
每组数据：输入：第一行n,m表示点/边，接下来m行，每行两个整数u,v表示u->v边，输出：有向图最长路径长度
const int maxn=2000009;
int n,m,ans=0,cnt=0;
int in[maxn],f[maxn],head[maxn];//in:依赖几个，f:完成此步的时间，head:
struct node{
int nex;
int to;
}e[maxn];
void add(int u,int v){
cnt++;
e[cnt].nex=head[u];
e[cnt].to=v;
head[u]=cnt;
in[v]++;
}
void solve(){
ans=0;
cin>>n>>m;
for(int i=0;i<=n;i++)
in[i]=0,head[i]=0,f[i]=1;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
add(u,v);
}
queue<int>q;
for(int i=1;i<=n;i++) if(!in[i]) q.push(i);//可以进行的
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nex){
int v=e[i].to;
f[v]=max(f[v],f[u]+1);
if(--in[v]==0) q.push(v);//依赖的全完成了
}
}
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
cout<<ans<<endl;
}
C4J-通过所有边的简单路径:欧拉路径模板
每组数据：输入：第一行n,m表示点/边个数，接下来m行，每行两个整数，表示u->v的边。
输出：若不存在欧拉路径，输出"mission impossible",否则输出字典序最小的欧拉路径。
题解：欧拉路径充要条件：
- 图是连通图（弱联通）
- 无向图：奇点为0或2，一个为起点，一个为终点
- 有向图：可以存在2个点，入度不等于出度，其中一个入度比出度大1（起点），另一个出度比入度大一（终点）。或者不存在这样的点。
const int N = 2.5e4 + 5;
const int E = 5e4 + 5;
int n, m;
int h[N], to[E], nx[E], et;
int indeg[N], outdeg[N];
int u[E], v[E], p[E];
int q[E], cnt;
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[u];
h[u] = et;
indeg[v]++;
outdeg[u]++;
}
bool cmp(int a, int b) {
return v[a] > v[b];
}
void dfs(int u) {
for (int i = h[u]; i; i = h[u]) {
h[u] = nx[i];
dfs(to[i]);
}
q[++cnt] = u;
}
void solve() {
scanf("%d%d", &n, &m);
et = 0;
for (int i = 1; i <= n; i++)
h[i] = indeg[i] = outdeg[i] = 0;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u[i], &v[i]);
p[i] = i;
}
sort(p + 1, p + m + 1, cmp);
for (int i = 1; i <= m; i++)
ae(u[p[i]], v[p[i]]);
int s = 1, i0 = 0, o0 = 0;
while (s < n && outdeg[s] == 0)
s++;
for (int i = 1; i <= n; i++) {
if (indeg[i] == outdeg[i])
continue;
if (indeg[i] < outdeg[i]) {
i0 += outdeg[i] - indeg[i];
s = i;
}
if (indeg[i] > outdeg[i])
o0 += indeg[i] - outdeg[i];
}
if (i0 > 1 || o0 > 1) {
printf("mission impossible\n");
return;
}
cnt = 0;
dfs(s);//拓扑，弱连通
if (cnt != m + 1) {//不是联通图
printf("mission impossible\n");
return;
}
for (int i = cnt; i; i--)
printf("%d%c", q[i], " \n"[i == 1]);
}
E3H-:fenwick树状数组模板
我们称一个二维点集 S S S 是优雅的，当且仅当对任意的点 ( x 1 , y 1 ) , ( x 2 , y 2 ) ∈ S (x_1, y_1), (x_2, y_2) \in S (x1?,y1?),(x2?,y2?)∈S，都有 ( min ? ( x 1 , x 2 ) , min ? ( y 1 , y 2 ) ) ∈ S (\min(x_1, x_2), \min(y_1, y_2)) \in S (min(x1?,x2?),min(y1?,y2?))∈S。
现在给出一个二维点集 S S S，请你向其中加入最少的点，使其变为优雅的点集 S ’ S’ S’，求出 S ’ S’ S’中点的个数。
每组数据：输入：第一行n表示n个点，接下来n行，每行两个点，表示点坐标。
输出： S ′ S' S′中点的个数
class fenwick {
public:
int n;
vector<int> a;
fenwick(int _n) : n(_n) { a.resize(n); }
void modify(int x, int val) {
while (x < n) {
a[x] += val;
x |= (x + 1);
}
}
int get(int x) {
int ret = 0;
while (x >= 0) {
ret += a[x];
x = (x & (x + 1)) - 1;
}
return ret;
}
};
void solve() {
set<pair<int, int>> st;
int n;
cin >> n;
vector<int> x(n), y(n), sy(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
st.insert({x[i], y[i]});
sy[i] = y[i];
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int u, int v) {
return (x[u] > x[v]) || (x[u] == x[v] && y[u] < y[v]);
});
sort(sy.begin(), sy.end());
map<int, int> sp;
int id = 0;
for (int i = 0; i < n; i++) {
if (sp.find(sy[i]) == sp.end()) {
sp[sy[i]] = id++;
}
}
fenwick tr = fenwick(n);
vector<bool> vis(n);
long long ans = 0;
for (int i = 0; i < n; i++) {
int a = sp[y[p[i]]];
if (!vis[a]) {
tr.modify(a, 1);
vis[a] = true;
}
if (i == n - 1 || x[p[i]] > x[p[i + 1]])
ans += tr.get(a);
}
cout << ans << '\n';
}
C5A-有向图任意两点最短路径:Floyd模板
输入：第一行两个整数n,m表示点/边，接下来m行，每行三个整数u,v,w表示u->v权值为w的有向边。接下来一个整数q，表示询问q次，接下来q行，每行两个整数u,v，询问u->v最短距离
输出：每次询问，到达自身为0，无法到达为-1，输出最短距离
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
class Floyd {
public:
int n;
vector<vector<long long>> g;
Floyd(int _n) : n(_n) {
g.resize(n);
for (int i = 0; i < n; i++) g[i].resize(n, inf);
for (int i = 0; i < n; i++) g[i][i] = 0;
}
void add(int u, int v, long long w) { g[u][v] = min(g[u][v], w); }
void solve() {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
};
int main() {
ios::sync_with_stdio(false);cin.tie(0);
int n, m, u, v, w,q;
cin >> n >> m;
Floyd f = Floyd(n);
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
u--, v--;
f.add(u, v, w);
}
f.solve();
cin >> q;
while (q--) {
cin >> u >> v;
u--, v--;
long long ans = f.g[u][v];
if (ans == inf) ans = -1;
cout << ans << '\n';
}
return 0;
}
E4A-字典序最大Topo：Topo模板
输入：第一行n,m表示n点m边的有向无环图，接下来m行，每行两个整数u,v表示存在u->v的有向边
输出：字典序最大的拓扑排序
int in[200009] ;
vector<int>dag[200009];
priority_queue<int>q;//默认大根堆
//priority_queue<int,vector<int>,greater<>>q;//小根堆实现
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
in[v]++; dag[u].push_back(v);
}
for(int i=1;i<=n;i++)
if (in[i] == 0)
q.push(i);
while(!q.empty()){
int now=q.top();q.pop();
cout<<now<<" ";
for(int v : dag[now]){
in[v]--;
if(in[v]==0) q.push(v);
}
}
}
E4B-最小生成树:Krusal模板
每组数据：输入：第一行n,m表示n点m边的无向图，接下来m行，每行三个整数u,v,w，表示u和v之间边权为w
class dsu {//并查集
public:
int n; vector<int> p;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
//查找
inline int find(int x)
{ return (x == p[x] ? x : (p[x] = find(p[x]))); }
//把x合并到y
inline bool unite(int x, int y) {
x = find(x),y = find(y);
if (x != y) { p[x] = y; return true; }
return false; }
};
void solve(){
int n, m; cin >> n >> m;
vector<array<int, 3>> e(m);
for (int i = 0; i < m; i++) {//读边
int u, v, w; cin >> u >> v >> w;
u--,v--; e[i] = {u, v, w}; }
vector<int> p(m);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int u, int v) {return e[u][2] < e[v][2];});
dsu d = dsu(n);
long long ans = 0;
for (int i : p) {
int u = e[i][0], v = e[i][1];
if (d.unite(u, v))
ans += e[i][2];
}
cout << ans << '\n';
}
E4C-:Dinic最大流模板
给定 n n n个点 m m m条边的有向图，每条边有最大容量，求从点 s s s 到点 t t t 的最大流。（可以存在重边和自环）
每组数据：输入：第一行四个整数n,m,s,t表示n点m边，源点s,汇点t;接下来m行，每行三个数u,v,w表示u->v存在有向边，权值w
输出：最大流
const int N = 105;
const int E = 1e4 + 5;
const long long oo = 1e18;
int n, m, s, t;
int h[N], nx[E], to[E], et;
long long ans,cap[E];
int d[N], q[N], ql, qr;
void add(int u, int v, long long w) {
et++;
to[et] = v;
cap[et] = w;
nx[et] = h[u];
h[u] = et;
}
bool bfs(int s, int t) {
for (int i = 1; i <= n; i++) d[i] = n + 1;
d[s] = 1; q[1] = s; ql = qr = 1;
while (ql <= qr) {
for (int i = h[q[ql]]; i; i = nx[i])
if (cap[i] && d[to[i]] == n + 1) {
d[to[i]] = d[q[ql]] + 1;
q[++qr] = to[i];
}
ql++;
}
return d[t] <= n;
}
long long dfs(int u, int t, long long c) {
if (!c) return 0;
if (u == t) return c;
long long r = 0;
for (int i = h[u]; i; i = nx[i])
if (d[to[i]] == d[u] + 1) {
long long v = dfs(to[i], t, min(c - r, cap[i]));
if (v) {
r += v;
cap[i] -= v;
cap[i ^ 1] += v;
if (r == c) return r;
}
}
if (r == 0) d[u] = n + 1;
return r;
}
void solve() {
et = 1,ans = 0; cin>>n>>m>>s>>t;
for (int i = 1; i <= n; i++) h[i] = 0;
for (int i = 1; i <= m; i++) {
int u, v;long long w; cin>>u>>v>>w;
add(u, v, w),add(v, u, 0);
}
while (bfs(s, t)) ans += dfs(s, t, oo);
cout<<ans<<'\n';
}
E4E-约会大作战：二分图匈牙利最大匹配
输入：第一行n,表示n对男女生，下面四行，每行n个数，第一行是男生魅力，第二行是男生要求对方最低值，第三行是女生魅力，第四行是女生要求对方魅力最低值
输出：最多能匹配几队
const int N = 500;
int n,a[N], p[N], b[N], q[N],girl[N];
bool mat[N][N],vis[N];
bool find(int x) {
for (int i = 1; i <= n; i++)
if (mat[x][i] && !vis[i]) {
vis[i] = true;
if (!girl[i] || find(girl[i])) {
girl[i] = x;
return true;
}
}
return false;
}
void solve(){
cin>>n;
for (int i = 1; i <= n; i++) cin>>a[i];
for (int i = 1; i <= n; i++) cin>>p[i];
for (int i = 1; i <= n; i++) cin>>b[i];
for (int i = 1; i <= n; i++) cin>>q[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (b[j] >= p[i] && a[i] >= q[j])
mat[i][j] = true;
int ans = 0;
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
if (find(i))
ans++;
}
printf("%d", ans);
}
E4G-不超过k条边的最短路径：BF
给定带权无向图，处理q次询问，每次询问从s到t不超过t条边的最短路长度（没有重边和自环）
输入：第一行n,m,q,表示n点，m边，q次询问，接下来m行，每行三个整数u,v,w表示u和v之间有无向边，权值w。接下来q行，每行三个整数s,t,k
输出：若不存在，输出-1，否则输出不超过k条边最短路长度
const int N = 105;
const long long oo = 1e18;
int n, m, q;
long long f[N][N][N];
int main() {
scanf("%d%d%d", &n, &m, &q);
for (int i = 0; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
f[i][j][k] = oo;
for (int x = 0; x <= n; x++)
for (int i = 1; i <= n; i++)
f[x][i][i] = 0;
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
f[1][u][v] = min(f[1][u][v], 1ll * w);
f[1][v][u] = min(f[1][v][u], 1ll * w);
}
for (int t = 1; t < n; t++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
f[t + 1][i][j] = f[t][i][j];
for (int k = 1; k <= n; k++)
f[t + 1][i][j] = min(f[t + 1][i][j], f[t][i][k] + f[1][k][j]);
}
while (q--) {
int s, t, k;
scanf("%d%d%d", &s, &t, &k);
k = min(k, n);
long long ans = f[k][s][t];
if (ans == oo)
ans = -1;
printf("%lld\n", ans);
}
return 0;
}
E4J-不经过某点最短路径:
输入：有向无环带权图第一行n,m,q表示n点，m边，q次询问，接下来m行，每行三个整数u,v,w表示u->v有向边权值为w。接下来q行，每行三个整数u,v,s，表示从u到v不经过s
输出：若能到达，输出最短路径；若不能到达输出0
const int N = 305;
const int C = 45005;
int n, m, t;
int d[N][N];
int vf[N][C], vg[N][C];
int *f[N][N], *g[N][N];
int deg[N], p[N], pre[N];
int q[N], ql, qr;
int a, b, w,u, v, s, last;
int main() {
scanf("%d%d%d", &n, &m, &t);
for (int i = 1; i <= n; i++) pre[i] = n - i;
for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];
for (int i = 0; i <= n + 1; i++)
for (int j = 1; j <= n; j++)
f[i][j] = &vf[i][pre[j - 1]] - j;
for (int i = 0; i <= n + 1; i++)
for (int j = 1; j <= n; j++)
g[i][j] = &vg[i][pre[j - 1]] - j;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &a, &b, &s);
if (d[a][b] == 0 || s < d[a][b])
d[a][b] = s;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[i][j])
deg[j]++;
ql = 1; qr = 0;
for (int i = 1; i <= n; i++)
if (!deg[i])
q[++qr] = i;
while (ql <= qr) {
int cur = q[ql];
p[cur] = ql;
for (int i = 1; i <= n; i++)
if (d[cur][i]) {
deg[i]--;
if (!deg[i])
q[++qr] = i;
}
ql++;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[q[i]][q[j]]) {
f[0][i][j] = d[q[i]][q[j]];
g[n + 1][i][j] = d[q[i]][q[j]];
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
f[k][i][j] = f[k - 1][i][j];
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (i < k && k < j)
if (f[k][i][k] && f[k][k][j])
if (f[k][i][j] == 0 ||
f[k][i][k] + f[k][k][j] < f[k][i][j])
f[k][i][j] = f[k][i][k] + f[k][k][j];
}
for (int k = n; k; k--) {
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
g[k][i][j] = g[k + 1][i][j];
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (i < k && k < j)
if (g[k][i][k] && g[k][k][j])
if (g[k][i][j] == 0 ||
g[k][i][k] + g[k][k][j] < g[k][i][j])
g[k][i][j] = g[k][i][k] + g[k][k][j];
}
while (t--) {
scanf("%d%d%d", &u, &v, &s);
if (p[u] >= p[v] || u == s || v == s) {
last = 0;
printf("%d\n", last);
continue;
}
last = d[u][v];
for (int i = 1; i <= n; i++)
if (p[u] < i && i < p[v] && q[i] != s)
if (f[p[s] - 1][p[u]][i] && g[p[s] + 1][i][p[v]])
if (last == 0 || f[p[s] - 1][p[u]][i] + g[p[s] + 1][i][p[v]] < last)
last = f[p[s] - 1][p[u]][i] + g[p[s] + 1][i][p[v]];
printf("%d\n", last);
}
return 0;
}
E5D-二分图最大权完美匹配:KM算法
二维平面上两组点，要求必须两两配对，求最小曼哈顿距离和
typedef long long ll;
const ll Maxn = 505;
const ll inf = 1e18;
ll n, m, Map[Maxn][Maxn], matched[Maxn];
ll slack[Maxn], pre[Maxn], ex[Maxn], ey[Maxn];//ex,ey顶标
bool visx[Maxn], visy[Maxn];
void match(ll u) {
ll x, y = 0, yy = 0, delta;
memset(pre, 0, sizeof(pre));
for (ll i = 1; i <= n; i++)slack[i] = inf;
matched[y] = u;
while (true) {
x = matched[y];
delta = inf;
visy[y] = true;
for (ll i = 1; i <= n; i++) {
if (visy[i])continue;
if (slack[i] > ex[x] + ey[i] - Map[x][i]) {
slack[i] = ex[x] + ey[i] - Map[x][i];
pre[i] = y;
}
if (slack[i] < delta) {
delta = slack[i];
yy = i;
}
}
for (ll i = 0; i <= n; i++) {
if (visy[i])ex[matched[i]] -= delta, ey[i] += delta;
else slack[i] -= delta;
}
y = yy;
if (matched[y] == -1)break;
}
while (y) {
matched[y] = matched[pre[y]];
y = pre[y];
}
}
ll KM() {
memset(matched, -1, sizeof(matched));
memset(ex, 0, sizeof(ex));
memset(ey, 0, sizeof(ey));
for (ll i = 1; i <= n; i++) {
memset(visy, 0, sizeof(visy));
match(i);
}
ll res = 0;
for (ll i = 1; i <= n; i++)
if (matched[i] != -1)res += Map[matched[i]][i];
return res;
}
struct node {
long long x, y;
} n1[250], n2[250];
long long mhd(node a, node b) {
return abs(a.x - b.x) + abs(a.y - b.y);
}
void solve(){
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
Map[i][j] = -inf;
for (int i = 1; i <= n; i++)
cin >> n1[i].x >> n1[i].y;
for (int i = 1; i <= n; i++)
cin >> n2[i].x >> n2[i].y;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
Map[i][j] = -mhd(n1[i], n2[j]);
printf("%lld\n", -KM());
}
计算几何
C5E/F-凸包面积&旋转卡壳:凸包模板
每组数据：输入：第一行n，表示n个点，接下来n行，每行两个正整数，表示一个点坐标。
输出：凸包面积 | | 最远两点距离平方
#include <bits/stdc++.h>
using namespace std;
/* template begin */
struct Vec {
long long x, y;
Vec() {}
Vec(long long x, long long y) {this->x = x;this->y = y;}
long long len2() const { return x * x + y * y; }
void read() { scanf("%lld%lld", &x, &y); }
void print() { printf("%lld %lld\n", x, y); }
};
typedef Vec Point;
//运算并返回一个点
Vec operator+(const Vec &a, const Vec &b) { return Vec(a.x + b.x, a.y + b.y); }
Vec operator-(const Vec &a, const Vec &b) { return Vec(a.x - b.x, a.y - b.y); }
Vec operator*(long long a, const Vec &b) { return Vec(a * b.x, a * b.y); }
// cross product叉积
long long operator*(const Vec &a, const Vec &b) { return a.x * b.y - b.x * a.y; }
// inner product点积
long long operator^(const Vec &a, const Vec &b) { return a.x * b.x + a.y * b.y; }
typedef vector<Point> Polygon;
typedef Polygon Points;
//a在b逆时针（左返回true
bool onleft(const Vec &a, const Vec &b) { return a * b < 0; }
//a在b顺时针（右返回true
bool onright(const Vec &a, const Vec &b) { return a * b > 0; }
//传入未排序点，返回凸包
Polygon convex(Points p) {
int sz = p.size(),n=0;
sort(p.begin(), p.end(), [&](const Point &a, const Point &b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });
Polygon c(p.size() + 1);
for (int i = 0; i < sz; i++) {
while (n > 1 && !onleft(p[i] - c[n - 2], c[n - 1] - c[n - 2])) n--;
c[n++] = p[i];
}
int t = n;
for (int i = sz - 1; i >= 0; i--) {
while (n > t && !onleft(p[i] - c[n - 2], c[n - 1] - c[n - 2])) n--;
c[n++] = p[i];
}
c.resize(--n);
return c;
}
//传入凸包集合，返回凸包面积
long long areadb(Polygon &p) {
long long r = 0;
int n = p.size();
for (int i = 0; i < n; i++)
r += (p[i] - p[0]) * (p[(i + 1) % n] - p[i]);
return r;
}
//旋转卡壳-凸包最大距离的平方
long long diameter2(Polygon &p) {
long long r = 0;
int n = p.size(), a = 0;
for (int i = 0; i < n; i++) {
Vec e = p[(i + 1) % n] - p[i];
while (onleft(p[(a + 1) % n] - p[a % n], e) || a == i) {
r = max({r, (p[i] - p[a]).len2(), (p[(i + 1) % n] - p[a]).len2()});
a = (a + 1) % n;
}
r = max({r, (p[i] - p[a]).len2(), (p[(i + 1) % n] - p[a]).len2()});
}
return r;
}
/* template end */
int n;
Points p;
void solve() {
scanf("%d", &n);
p.resize(n);
for (int i = 0; i < n; i++)
p[i].read();
p = convex(p);
long long r = diameter2(p);
// printf("%lld.%lld\n", r / 2, (r & 1) * 5);
printf("%lld\n",r);
}
C5G-最小曼哈顿距离：线段树模板
每组数据：输入：第一行n，表示n个点，接下来n行，每行x,y表示点坐标。
输出:定义曼哈顿距离： d ( P , Q ) = ∣ x P ? x Q ∣ + ∣ y P ? y Q ∣ d(P, Q)=|x_P - x_Q| + |y_P - y_Q| d(P,Q)=∣xP??xQ?∣+∣yP??yQ?∣。求全局最小曼哈顿距离。
#define LL long long
const LL inf = 1e18;
const int N = 4e5 + 5;
vector<LL> seg1(N), tag1(N);
vector<LL> seg2(N), tag2(N);
void pushdown(int l, int r, int id, vector<LL> &seg,vector<LL> &tag) {
if (l != r && tag[id]) {
tag[2 * id] = max(tag[2 * id], tag[id]);
tag[2 * id + 1] = max(tag[2 * id + 1], tag[id]);
seg[2 * id] = max(seg[2 * id], tag[id]);
seg[2 * id + 1] = max(seg[2 * id + 1], tag[id]);
tag[id] = -inf;
}
}
void modify(int ll, int rr, int l, int r, int id, LL val,vector<LL> &seg, vector<LL> &tag) {
if (ll <= l && r <= rr) {
tag[id] = max(tag[id], val);
seg[id] = max(tag[id], val);
return;
}
int m = l + (r - l) / 2;
pushdown(l, r, id, seg, tag);
if (ll <= m) modify(ll, rr, l, m, 2 * id, val, seg, tag);
if (m < rr) modify(ll, rr, m + 1, r, 2 * id + 1, val, seg, tag);
seg[id] = max(seg[2 * id], seg[2 * id + 1]);
}
LL get(int ll, int rr, int l, int r, int id, vector<LL> &seg,vector<LL> &tag) {
if (ll <= l && r <= rr) return seg[id];
int m = l + (r - l) / 2;
LL ret = -inf;
pushdown(l, r, id, seg, tag);
if (ll <= m) ret = max(ret, get(ll, rr, l, m, 2 * id, seg, tag));
if (m < rr) ret = max(ret, get(ll, rr, m + 1, r, 2 * id + 1, seg, tag));
return ret;
}
void solve(){
int n; cin >> n;
for (int i = 0; i <= 4 * n + 1; i++) {
seg1[i] = tag1[i] = -inf;
seg2[i] = tag2[i] = -inf;
}
vector<pair<int, int>> p(n);
vector<int> py(n);
for (int i = 0; i < n; i++) {
cin >> p[i].first >> p[i].second;
py[i] = p[i].second;
}
sort(py.begin(), py.end());
map<int, int> id;
for (int i = 0; i < n; i++)
id[py[i]] = i + 1;
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int u, int v) {
return p[u] < p[v];
});
LL ans = inf;
for (int i : order) {
LL x = p[i].first, y = p[i].second;
int od = id[y];
LL d = get(1, od, 1, n, 1, seg1, tag1);
ans = min(ans, x + y - d);
d = od + 1 <= n ? get(od + 1, n, 1, n, 1, seg2, tag2) : -inf;
ans = min(ans, x - y - d);
modify(od, od, 1, n, 1, x + y, seg1, tag1);
modify(od, od, 1, n, 1, x - y, seg2, tag2);
}
cout << ans << '\n';
}
FFT
C6B-高精度乘法:FFT模板
每组数据：输入两个十进制非负整数 a , b a, b a,b（ 0 ≤ a , b < 1 0 1 0 5 0\leq a, b< 10^{10^5} 0≤a,b<10105）
输出：乘积
using ld = double;
const int N = (1 << 18) + 5;
const ld pi = acosl(-1.0);
struct Complex
{
ld r, i;
Complex() { r = 0; i = 0; }
Complex(ld re, ld im) { r = re; i = im; }
ld len2() const { return r * r + i * i; }
Complex bar() const { return Complex(r, -i); }
};
Complex operator + (const Complex &x, const Complex &y) { return Complex(x.r + y.r, x.i + y.i); }
Complex operator - (const Complex &x, const Complex &y) { return Complex(x.r - y.r, x.i - y.i); }
Complex operator * (ld x, const Complex &y) { return Complex(x * y.r, x * y.i); }
Complex operator * (const Complex &x, ld y) { return Complex(x.r * y, x.i * y); }
Complex operator * (const Complex &x, const Complex &y) { return Complex(x.r * y.r - x.i * y.i, x.r * y.i + x.i * y.r); }
Complex operator / (const Complex &x, ld y) { return Complex(x.r / y, x.i / y); }
Complex operator / (const Complex &x, const Complex &y) { return x * y.bar() / y.len2(); }
char s[N], t[N];
int lens, lent,len;
Complex a[N], b[N];
Complex v[N];
int rev[N],ans[N];
void fft(Complex c[], int inv = 0) {
for (int i = 0; i < len; i++) v[rev[i]] = c[i];
for (int i = 2; i <= len; i <<= 1){
Complex wn(cosl(2 * pi / i), sinl(2 * pi / i));
for (int j = 0; j < len; j += i) {
Complex w(1, 0);
for (int k = 0; k < (i >> 1); k++) {
Complex x = v[j + k], y = v[j + k + (i >> 1)] * w;
v[j + k] = x + y;
v[j + k + (i >> 1)] = x -y;
w = w * wn;
}
}
}
if (inv){
for (int i = 0; i < len; i++) v[i] = v[i] / len;
for (int i = 1, j = len - 1; i < j; i++, j--) swap(v[i], v[j]);
}
for (int i = 0; i < len; i++) c[i] = v[i];
}
void solve() {
scanf("%s", s); scanf("%s", t);
lens = strlen(s); lent = strlen(t);
len = 1;
while (len <= lens + lent) len <<= 1;
for (int i = 0; i < len; i++) {
a[i] = b[i] = Complex(0, 0);
ans[i] = 0;
}
for (int i = 0; i < lens; i++) a[i] = Complex(s[lens - 1 - i] - '0', 0);
for (int i = 0; i < lent; i++) b[i] = Complex(t[lent - 1 - i] - '0', 0);
for (int i = 0; i < len; i++) {
rev[i] = 0;
for (int j = 1, t = i; j < len; j <<= 1, t >>= 1)
rev[i] <<= 1, rev[i] += t & 1;
}//在此之前都是必写
fft(a); fft(b);
for (int i = 0; i < len; i++) b[i] = a[i] * b[i];
fft(b, 1);
for (int i = 0; i < len; i++) {
ans[i] += round(b[i].r);
ans[i + 1] += ans[i] / 10;
ans[i] %= 10;
}
while (len > 1 && ans[len - 1] == 0) len--;
for (int i = len - 1; i >= 0; i--) printf("%d", ans[i]);
printf("\n");
}
字符串匹配
C6A-字符串匹配:kmp模板//也可以直接用find或strstr
每组数据：输入：两行两个字符串s,t,在s里匹配t,若一个位置被匹配了，那么该部分不能再次被匹配（两个匹配不能有交叉）
输出：一行若干整数，表示子串起始位置
const int N = 2e6;
char s[N], t[N];
int nxt[N];
bool kmp(int n, char *a, int m, char *b) {
bool flag = true;int i, j，ans=0;
// n=strlen(a);m=strlen(b);
for (nxt[0] = j = -1, i = 1; i < n; nxt[i++] = j) {//求nxt数组
while (~j && a[j + 1] != a[i]) j = nxt[j];
if (a[j + 1] == a[i]) j++;
}
for (j = -1, i = 0; i < m; i++) {//匹配
while (~j && a[j + 1] != b[i]) j = nxt[j];
if (a[j + 1] == b[i]) j++;
if (j == n - 1) printf("%d ", i - n + 2), j = -1, flag = false;
//if (j == n - 1) ans=i-n+1, j = nxt[j];匹配第一个
}
return flag;
//return ans;
}
void solve() {
scanf("%s", s); scanf("%s", t);
int len1 = strlen(t), len2 = strlen(s);
if (kmp(len1, t, len2, s)) cout << "-1";
cout << endl;
}
C6E-前缀等于后缀的长度：Next数组
给定字符串 s s s，请你求出对于 i = 1 , 2 , … , ∣ s ∣ i=1,2,\ldots,|s| i=1,2,…,∣s∣而言，长度为 i i i 的前缀和长度为 i i i 后缀是否相同。
每组数据：输入：一行一个字符串
输出：从小打到大所有的 i i i
char s[1000010];
int next[1000010], ans[1000010];
void getNext(char *target) {
int i = 0, j = -1; next[0] = -1;
while (target[i] != '\0')
if (j == -1 || target[i] == target[j]) next[++i] = ++j;
else j = next[j];
}
void solve(){
scanf("%s", s);
getNext(s);
int n = 1; ans[0] = strlen(s);
for (int i = strlen(s); next[i] > 0; i = next[i])
ans[n++] = next[i];
for (int i = n - 1; i >= 0; i--) printf("%d ", ans[i]);
printf("\n");
}
int main() {
int t; scanf("%d", &t);
while (t--) solve();
return 0;
}
C6D-最长回文子串:中心扩散定理
每组数据：输入：一个字符串
输出：最长回文子串
char ch[110005],pat[220005];
int pos,r[220005],ans,n;
void solve(){
int i, j, u, v;
scanf("%s", ch + 1);
n = strlen(ch + 1);
pat[0] = '@';
ans = 0;
for (int i = 0; i <= 2 * n + 2; i++) r[i] = 0;
for (i = 1; i <= n; i++) pat[2 * i - 1] = ch[i], pat[2 * i] = '@';
pos = 0, r[0] = 0;
for (i = 1; i <= 2 * n; i++) {
if (i <= pos + r[pos]) r[i] = min(pos + r[pos] - i, r[pos * 2 - i]);
while (i > r[i] && pat[i + r[i] + 1] == pat[i - r[i] - 1]) r[i]++;
if (i + r[i] > pos + r[pos]) pos = i;
ans = max(ans, r[i]);
}
printf("%d\n", ans);
}
C6G-:字符串哈希表
给定一个只包含小写字母的字符串 s s s， 请你判断该字符串的两个子串是否相等。
定义长度为 的字符串 s s s的子串 s u b [ i , j ] sub[i,j] sub[i,j] 为：
s u b [ i , j ] = { s i s i + 1 ? s j i ≤ j s i s i + 1 ? s n s 1 ? s j i > j sub[i,j] = \begin{cases} s_{i}s_{i+1} \cdots s_{j} &i \le j \\ s_{i} s_{i+1} \cdots s_{n} s_{1} \cdots s_{j} & i > j \end{cases} sub[i,j]={si?si+1??sj?si?si+1??sn?s1??sj??i≤ji>j?
具体来说，对于字符串 s s s，给出两个子串 s u b [ a , b ] sub[a,b] sub[a,b] 和 s u b [ x , y ] sub[x,y] sub[x,y]，请你判断两个子串是否相等
输入：第一行一个字符串，第二行一个数字Q，表示Q组查询，接下来Q行，每行四个数字a,b,x,y(保证两子串长度相等)
输出：Q行，若匹配"owo",不匹配"qeq"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
struct Hash {//多项式哈希表
//BASE:基数；P:大质数，取模确保不溢出；val:存放每个字符哈希值；pw:存储多项式系数
long long BASE, P, val[MAXN], pw[MAXN];
void init(int base, int p, string s) {
BASE=base,P = p; int n = s.size();
val[0] = s[0]; pw[0] = 1;
for (int i = 1; i < n; i ++)
val[i] = ((long long)val[i - 1] * base + s[i]) % p;
for (int i = 1; i <= n; i ++) pw[i] = (long long)pw[i - 1] * base % p;
}
long long query(int l, int r) {//输出指定子串哈希值
if (l) return (val[r] + P - (long long)val[l - 1] * pw[r - l + 1] % P) % P;
return val[r];
}
};
Hash hs; string s;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> s; int len = s.size();
s = s + s;
hs.init(233, 1000000007, s);
int Q; cin >> Q;
while(Q--) {
int a, b, x, y;
cin >> a >> b >> x >> y;
if(b < a) b += len;
if(y < x) y += len;
if(hs.query(a - 1, b - 1) == hs.query(x - 1, y - 1))
cout << "owo\n";
else cout << "qwq\n";
}
return 0;
}
课外
快读
#define ll long long
inline ll read() {
ll s = 0, w = 1;
char c = getchar();
while (c < '0' || c > '9') {if (c == '-') w = -1; c = getchar();}
while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
return s * w;
}
树状数组
// 此处为查询区间和的树状数组。
int bit[500010];
void add(int k, int x) {
while (k <= n) {
bit[k] += x;
k += lowbit(k);
}
}
int ask(int k) {
int res = 0;
while (k) {
res += bit[k];
k -= lowbit(k);
}
return res;
}
线段树
// 此处为区间修改区间查询区间和的线段树。
struct SegmentTree {
ll sum[N << 2], lazy[N << 2];
int l[N << 2], r[N << 2];
void update(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void pushdown(int rt) {
if (!lazy[rt]) return ;
sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt], lazy[rt << 1] += lazy[rt];
sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
update(rt);
}
void build(int rt, int L, int R) {
l[rt] = L, r[rt] = R;
if (L == R) {
sum[rt] = a[L];
return ;
}
int mid = L + R >> 1;
build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R);
update(rt);
}
void change(int rt, int L, int R, int x) {
if (L <= l[rt] && r[rt] <= R) {
sum[rt] += (r[rt] - l[rt] + 1) * x;
lazy[rt] += x;
return ;
}
pushdown(rt);
if (L <= r[rt << 1]) change(rt << 1, L, R, x);
if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x);
update(rt);
}
ll query(int rt, int L, int R) {
if (L <= l[rt] && r[rt] <= R) return sum[rt];
pushdown(rt);
ll res = 0;
if (L <= r[rt << 1]) res += query(rt << 1, L, R);
if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R);
return res;
}
} tree;
并查集
struct Disjoint_Set {
int p[N], size[N];
void build() {
for (int i = 1; i <= n; i++) p[i] = i, size[i] = 1;
}
int root(int x) {
if (p[x] != x) return p[x] = root(p[x]);
return x;
}
void merge(int x, int y) {
x = root(x), y = root(y);
if (size[x] > size[y]) swap(x, y);
p[x] = y;
size[y] += size[x];
}
bool check(int x, int y) {
x = root(x), y = root(y);
return x == y;
}
} a;
堆优化Dijkstra
void dij(int s) {
priority_queue <pii, vector<pii>, greater<pii> > q;
memset(dis, 0x7f7f7f7f, sizeof(dis));
q.push({0, s});
dis[s] = 0;
while (!q.empty()) {
pii u = q.top(); q.pop();
int pos = u.second;
if (vis[pos]) continue;
vis[pos] = 1;
for (int j = last[pos]; j; j = e[j].next) {
int v = e[j].to;
if (vis[v]) continue;
if (dis[pos] + e[j].w < dis[v]) dis[v] = dis[pos] + e[j].w, q.push({dis[v], v});
}
}
}
乘法逆元
fac[0] = fac[1] = 1;
for (int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
快速幂
ll qpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
矩阵快速幂
struct Martix {
int n, m;
ll a[N][N];
void clear() {memset(a, 0, sizeof(a));}
void init() {clear(); for (int i = 1; i <= n; i++) a[i][i] = 1;}
Martix operator *(const Martix b) const {
Martix res; res.clear(); res.n = n, res.m = b.m;
for (int i = 1; i <= res.n; i++)
for (int j = 1; j <= res.m; j++)
for (int k = 1; k <= m; k++)
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
return res;
}
Martix operator ^(ll x) const {
Martix res, a = *this; res.n = res.m = n, res.init();
while (x) {
if (x & 1) res = res * a;
a = a * a;
x >>= 1;
}
return res;
}
} a;
欧拉素数筛
int prime[6000010], cnt;
bool isprime[N + 10];
void prim() {
isprime[0] = isprime[1] = 1;
for (int i = 2; i <= n; i++) {
if (!isprime[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
isprime[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
KMP
// s 和 t 为需要匹配的两个 char 类型数组。
// border[i] 表示 t 长度为 i 的前缀最长的 border 长度。
ls = strlen(s + 1), lt = strlen(t + 1);
int j = 0;
for (int i = 2; i <= lt; i++) {
while (j >= 1 && t[j + 1] != t[i]) j = border[j];
if (t[j + 1] == t[i]) j++;
border[i] = j;
}
int sx = 1, tx = 0;
while (sx <= ls) {
while (tx >= 1 && s[sx] != t[tx + 1]) tx = border[tx];
if (t[tx + 1] == s[sx]) tx++;
if (tx == lt) printf("%d\n", sx - lt + 1);
sx++;
}
最长上升子序列
int lengthOfLIS(vector<int>& nums) {
int n = (int)nums.size();
if (n == 0) {
return 0;
}
vector<int> dp(n, 0);
for (int i = 0; i < n; ++i) {
dp[i] = 1;
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
最大连续子序列和
#include <stdio.h>
int main() {
int N, n, s, ans, m = 0;
scanf("%d%d", &N, &n); //读取数组长度和序列中的第一个数
ans = s = n; //把ans初始化为序列中的的第一个数
for (int i = 1; i < N; i++) {
if (s < m) m = s;
scanf("%d", &n);s += n;
if (s - m > ans) ans = s - m;
}
printf("%d\n", ans);
return 0;
}
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！