Summary1 常见算法模版

#include stack, unordered_map
stack<char> op; //操作符栈
stack<int> num; //数字栈
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'x', 2}, {'/', 2}}; //定义运算符优先级
void eval() { // 计算函数
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == 'x') x = a * b; // 乘法符号区分'x'和'*'
    else x = a / b;
    num.push(x);
}
int main() {
    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        op = stack<char>();
        num = stack<int>();
        for (int i = 0; i < s.size(); i++) {
            if (isdigit(s[i])) { //是数，压入数字栈
                int j = i, x = 0;
                while (isdigit(s[j]) && j < s.size()) x = x * 10 + s[j++] - '0';
                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() && op.top() != '(' && pr[op.top()] >= pr[s[i]]) eval();
                op.push(s[i]);
            }
        }
        while (op.size()) eval(); // 对最后剩下的内容再进行最后一次运算
        printf("%d\n", num.top()); // 栈顶即为最后的值
    }
    return 0;
}

#include stack, unordered_map
stack<char> op;//存放运算符
stack<double> num;//存放浮点数
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; //定义运算符优先级
void eval() { //运算
    double b = num.top(); num.pop();
    double a = num.top(); num.pop();
    char c = op.top(); op.pop();
    double x;
    if (c == '+') x = a+b;
    else if (c == '-') x = a-b;
    else if (c == '*') x = a * b;
    else x = a/b;
    num.push(x);
}
int main() {
    string s; cin>>s; // (3.34*78-72.3)*54.7-82.4 中间没空格，中间用空格需要特判
    for (int i = 0; i < s.length(); ++i) {
        if (isdigit(s[i])) {
            int j = i, k = 0;double x = 0;
            while (isdigit(s[j]) && j < s.size()) x = x * 10 + s[j++] - '0';
            if (s[j] == '.') {
                j++;
                while (isdigit(s[j]) && j < s.size()) x = x + pow(0.1, ++k) * (s[j++] - '0');
            }
            num.push(x);
            i = j-1;
        } else if (s[i] == '(') {
            op.push(s[i]);
        } else if (s[i] == ')') {
            if (!op.empty() && op.top() != '(') eval();
            op.pop();
        } else {
            if (op.empty()) {
                op.push(s[i]);
            } else if (pr[s[i]] > pr[op.top()]) {
                op.push(s[i]);
            } else if (pr[s[i]] <= pr[op.top()] && op.top() != '(') {
                if (!op.empty() && pr[s[i]] <= pr[op.top()] && op.top() != '(') eval();
                op.push(s[i]);
            } else if (op.top() == '(') {
                op.push(s[i]);
            }
        }
    }
    while (!op.empty()) eval();
    cout << num.top() << endl;
    return 0;
}

int next1[maxn];
char s1[maxn], s2[maxn];

inline void get_next() {//求出next数组 next数组是从 S[0到i-1]前子串 的前缀后缀最大值
    int t1 = 0, t2;
    next1[0] = t2 = -1;
    while (t1 < len2)
        if (t2 == -1 || s2[t1] == s2[t2]) next1[++t1] = ++t2; //类似于KMP的匹配
        else t2 = next1[t2];//失配
}

inline void KMP() { //KMP
    int t1 = 0, t2 = 0;//从0位开始匹配
    while (t1 < len1) { //临界值
        if (t2 == -1 || s1[t1] == s2[t2]) t1++, t2++;//匹配成功，继续
        else t2 = next1[t2]; //失配
        if (t2 == len2) printf("%d\n", t1 - len2 + 1), t2 = next1[t2];//t2==lenn2时，匹配成功；t1-len2+1即为第一个字母的位置
    } //匹配成功后，t2置为next[t2]
}

int main() {
    scanf("%s%s", s1, s2);
    len1 = strlen(s1); len2 = strlen(s2);
    get_next();
    KMP(); // 遍历，得到所有的匹配位点
    for (int i = 1; i <= len2; ++i) printf("%d ", next1[i]);//输出next数组
    return 0;
}

queue<int>q;
struct Aho_Corasick_Automaton{
    int c[N][26],val[N],fail[N],cnt;
    void ins(char *s){
        int len=strlen(s);int now=0;
        for(int i=0;i<len;i++){
            int v=s[i]-'a';
            if(!c[now][v])c[now][v]=++cnt;
            now=c[now][v];
        }
        val[now]++;
    }
    void build(){
        for(int i=0;i<26;i++)if(c[0][i])fail[c[0][i]]=0,q.push(c[0][i]);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<26;i++)
            if(c[u][i])fail[c[u][i]]=c[fail[u]][i],q.push(c[u][i]);
            else c[u][i]=c[fail[u]][i];
        }
    }
    int query(char *s){
        int len=strlen(s);int now=0,ans=0;
        for(int i=0;i<len;i++){
            now=c[now][s[i]-'a'];
            for(int t=now;t&&~val[t];t=fail[t])ans+=val[t],val[t]=-1;
        }
        return ans;
    }
}AC;
int n;char p[1000005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",p),AC.ins(p);
    AC.build();
    scanf("%s",p);int ans=AC.query(p);
    printf("%d\n",ans);
    return 0;
}

bool check(int tg) {
  if() return true;
  return false;
}
// 整数-初始化二分的左右边界以及中间索引和值 l, r, mid, ans
int l = 0, r = maxx, mid;
while (l<=r) {
  mid = (l+r)>>1;
  int tm = 0;
  if (check(mid)) l = mid+1;
  else r = mid;
}
// 小数-初始化二分的左右边界以及中间索引和值 l, r, mid, ans
double l = 0, r = maxx, mid;
while (r-l>1e-3) { // 最小误差范围边界
  mid = (l+r)/2;
  int tm = 0;
  if (check(mid)) l = mid;
  else r = mid;
}

const int maxn = 1e3 + 9;
const int maxm = 1e5 + 9;
int n, m, fa[maxn], cnt=0, ans=0;
struct node {
    int x, y, c;
    bool operator<(const node nd) const { return c < nd.c; }
} e[maxm];
int findfa(int x) {return fa[x] == x ? x : fa[x] = findfa(fa[x]);} // 判断点属于哪一集合
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].c);
    sort(e, e + m); // 按照边权排序
    for (int i = 1; i <= n; ++i) fa[i] = i; // 初始化并查集fa数组
    for (int i = 0; i < m; ++i) { // 开始遍历所有边（按照边权排序）
        if (findfa(e[i].x) != findfa(e[i].y)) ans+=e[i].c, cnt++, fa[findfa(e[i].x)] = findfa(e[i].y); // 不是同一集合，代表这个边投入使用
        if (cnt == n-1) break; // 总投入使用边数等于节点个数-1.
    }
    printf("%d\n", ans);
    return 0;
}

struct nd {int pos, val;}
priority_queue<nd> pq;
int d[maxpoint], d1, d2; // 用于临时储存两个点到起点的距离，分别是u点到s点的距离以及v点到s点的距离
int vis[maxpoint];
int u, v; // 用于获取边的两个点的坐标，其中u是承接从优先队列中获得的点的位置，v是通过遍历邻接表获得的
void dijkstra(int s, int e) {
  for (int i = 1; i <= n; i++) d[i] = INF;
  dis[s] = 0;
  pq.push({s, dis[s]});
  while (!pq.empty()) {
    u = pq.top().pos, d1 = pq.top().val;pq.pop();
    if (!vis[u]) {
      vis[u] = 1;
      for (auto tm : G[u]) {
        v = tm.first, d2 = tm.second; // 这一块被用来刷新的d必须是从队列中拿的，d数组中的值在这一时刻还是有问题的
        if (d[v] < d1+d2) {
          d[v] = d1+d2;
          if (!vis[v]) pq.push({v, d[v]});
        }
      }
    }
  }
}

  for (int i = 1; i <= n; ++i) {vis[i] = 0;d[i] = INF;}
    d[s] = 0; vis[s] = 1;
    q.push(s); // 首先只需要将起点入队
    while (!q.empty()) {
        u = q.front();q.pop();
        vis[u] = 0;
        for (int j = head[u]; j; j=e[j].nt) {
            int to = e[j].to;
            if (d[to] > d[u]+e[j].c) {
                d[to] = d[u]+e[j].c;
                if (!vis[to]) {
                    q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }

LL n, m, sum1[maxn<<2], sum2[maxn<<2], t, last, tp, ta, tb, tc;
#define lowbit(x) x&(-x)
void add(LL pos, LL k) {
    LL tem = pos*k;
    while (pos <= n) {
        sum1[pos] += k;sum2[pos] += tem;
        pos += lowbit(pos);
    }
}
void interval_add(LL l, LL r, LL k) {add(l, k);add(r+1, -k);}
LL query(LL pos) {
    LL ans = 0,tem = pos;
    while (pos >= 1) {
        ans += ((tem+1)*sum1[pos] - sum2[pos]);
        pos -= lowbit(pos);
    }
    return ans;
}
LL interval_query(LL l, LL r) {return query(r)-query(l-1);}
int main() {
    scanf("%lld%lld", &n, &m);
    for (LL i = 1; i <= n; ++i) {scanf("%lld", &t);add(i, t-last);last = t;}
    while (m--) {
        scanf("%lld", &tp);
        if (tp == 1) {scanf("%lld%lld%lld", &ta, &tb, &tc);interval_add(ta, tb, tc);}
        else {scanf("%lld%lld", &ta, &tb);printf("%lld\n", interval_query(ta, tb));}
    }
    return 0;
}

struct node {
//左端点和右端点//加//乘
  	long long l,r; long long jia; long long ch; long long s;
} t[300100];
long long a[300100]; long long n,m,x,y,k,c,i,j; long long sum,p; //膜数 
void bt(long long l,long long r,long long u) {//建树 
    t[u].l=l;//左端点 
    t[u].r=r;//右端点 
    t[u].jia=0;
    t[u].ch=1;//初始化 
    if (l==r) {//长度为1的区间 
        t[u].s=a[l];
        return;
    }
    bt(l        ,(l+r)/2,u*2);//左子树 
    bt((l+r)/2+1,r      ,u*2+1);//右子树
    t[u].s=(t[u*2].s+t[u*2+1].s)%p;//更新当前结点的值
}
void down(LO x) {
    t[x*2].jia=(t[x*2].jia*t[x].ch+t[x].jia)%p;//加 
    t[x*2+1].jia=(t[x*2+1].jia*t[x].ch+t[x].jia)%p;
    t[x*2].ch=(t[x*2].ch*t[x].ch)%p;//乘 
    t[x*2+1].ch=(t[x*2+1].ch*t[x].ch)%p;
    t[x*2].s=(t[x].jia*(t[x*2].r-t[x*2].l+1)%p+t[x*2].s*t[x].ch%p)%p;//求和 
    t[x*2+1].s=(t[x].jia*(t[x*2+1].r-t[x*2+1].l+1)%p+t[x*2+1].s*t[x].ch%p)%p;//求和 
    t[x].jia=0;t[x].ch=1; 
}
void cheng(LO l,LO r,LO x,LO d) {
    if (l<=t[x].l&&t[x].r<=r)//全部包括 
      t[x].s=t[x].s*d%p;
        t[x].jia=t[x].jia*d%p;
        t[x].ch=t[x].ch*d%p;
    } else {
        down(x);//向下传递值 
        LO mid=(t[x].l+t[x].r)/2;
        if (l<=mid) cheng(l,r,x*2,d);//继续往下搜
        if (r>mid)cheng(l,r,x*2+1,d);
        t[x].s=(t[x*2+1].s+t[x*2].s)%p;//更新sum 
    }
    return;
}
void jf(LO l,LO r,LO x,LO d) {
    if (l<=t[x].l&&t[x].r<=r) { //全部包括 
        t[x].jia=(t[x].jia+d)%p;
        t[x].s=(t[x].s+d*(t[x].r-t[x].l+1))%p;
    } else {
        down(x);//向下传递值 
        LO mid=(t[x].l+t[x].r)/2;
        if (l<=mid) jf(l,r,x*2,d);
        if (r>mid)jf(l,r,x*2+1,d);
        t[x].s=(t[x*2+1].s+t[x*2].s)%p;//更新sum 
    }
    return;
} 
long long qh(LO l,LO r,LO x) {
    if (l<=t[x].l&&t[x].r<=r) //求得区间有这一部分，直接返回
         return t[x].s%p;
    else {
        down(x);//向下传递值 
        LO ans=0;
        LO mid=(t[x].l+t[x].r)/2;
        if (l<=mid) ans=qh(l,r,x*2)%p;
        if (r>mid)ans=ans+qh(l,r,x*2+1);
        return ans%p;
    }
}
int main() {
    scanf("%lld%lld%lld",&n,&m,&p);
    for (i=1;i<=n;i++)
    scanf("%lld",&a[i]);
    bt(1,n,1);//建树 
    for (i=1;i<=m;i++) {
        scanf("%lld",&c);//读入 
        if (c==1) { //乘
            scanf("%lld%lld%lld",&x,&y,&k);
            cheng(x,y,1,k);
        } else if (c==3) { //求和 
            scanf("%lld%lld",&x,&y);
            sum=qh(x,y,1)%p;//求和 
            printf("%lld\n",sum);//结果 
        } else if (c==2) { //加 
            scanf("%lld%lld%lld",&x,&y,&k);
            jf(x,y,1,k);
        }
    }
    return 0;
}