矩阵快速幂
title: 矩阵快速幂 categories: ICPC tags: null abbrlink: 7f45ba65 date: 2024-05-16 00:00:00 debug:重载乘号的时候要把两个传进来的矩阵用起来 // Problem: P3390 【模板】矩阵快速幂 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3390 // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define ll long long # define int long long #define ull unsigned long long #define pii pair<int,int> #define baoliu(x, y) cout...
DFS order
title: DFS order categories: ICPC tags: null abbrlink: ac1f1f56 date: 2024-05-02 00:00:00 DFS order [P9872 EC Final 2021] DFS Order - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) [P9669 ICPC2022 Jinan R] DFS Order 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) [P9669 ICPC2022 Jinan R] DFS Order 2 题解 - 洛谷专栏 (luogu.com.cn) DFS Order 3 - Problem - QOJ.ac DFS Order 4 - Problem - QOJ.ac DFS Order 5 - Problem - QOJ.ac
线段树模板区间加（含懒标记）
title: 线段树模板区间加（含懒标记） categories: ICPC tags: null abbrlink: 7463b265 date: 2024-04-16 00:00:00 const int N = 1e5 + 10; int n, m; int a[N]; struct Tree{ int l,r; ll sum,add; }tr[4*N]; void build(int u,int l,int r){ // l=tr[u].l;r=tr[u].r; //注释掉的部分是典型的错误，对于build过程中我们是初始化编号对应区间节点，上面赋值逻辑反了 tr[u]={l,r}; if(l==r)tr[u].sum=a[l]; else{ int...
最长上升子序列
title: 最长上升子序列 categories: ICPC tags: null abbrlink: b5073ecc date: 2024-04-12 00:00:00 最长上升子序列 我们讨论的是严格单调递增的LIS，然后考虑基本状态dp[i]dp[i]dp[i]表示以i结尾的LIS长度。状态转移是dpi=maxj<i,aj<aidpj+1dp_i=\max\limits_{j<i, a_j<a_i} dp_j+1dpi=j<i,aj<aimaxdpj+1 朴素O(n2)O(n^2)O(n2) void solve() { int n; cin >> n; vector<int> dp(n + 1); vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++)...
log_trick
title: log_trick categories: ICPC tags: null abbrlink: f88e4243 date: 2024-04-05 00:00:00 一类子区间gcd，按位与，按位或的问题 有 TTT 组询问，每次给出 nnn 个数 aia_iai。[P7009 CERC2013] Magical GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 你需要找到这个数组的一个子序列（要求编号连续），使得该序列中所有数的最大公约数和序列长度的乘积最大，并输出这个最大值。 Sol:重要性质如果右端点不同，那么gcd意义下本质不同的左端点只有log个https://www.luogu.com.cn/problem/P5502 include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e5+10; #define LL...
最短路计数
title: 最短路计数 categories: ICPC tags: null abbrlink: fa5b931e date: 2024-03-30 00:00:00 P1144 最短路计数 题意：求出起点到各个点的最短路条数。 Solution：在堆优化dij的过程中维护每个点的最短路条数数组，如果严格小于就赋值，如果等于就累加 struct edge{int v,w;}; vector<edge>e[N]; void add(int u,int v,int w){ e[u].push_back({v,w}); } void solve(){ cin>>n>>m; for(int i=1;i<=m;i++){ int...
二叉树已经知道先序中序推后序
title: 二叉树已经知道先序中序推后序 categories: ICPC tags: null abbrlink: bd001d9e date: 2024-03-29 00:00:00 https://www.acwing.com/problem/content/3601/ 不断找新的先序的根节点，根据位置切割中序，根据中序左右子树大小反切割先序，找到左子树对应的先序中序，然后递归处理 #include<stdio.h> #include<vector> #include<map> #include<algorithm> #include <algorithm> #include <iostream> #include<string> using namespace std; #define ll long long //# define int long long #define ull unsigned long long #define pii...
比赛注意事项——喵亦或鱼
title: 比赛注意事项——喵亦或鱼 categories: ICPC tags: null abbrlink: d2ddb657 date: 2024-03-29 00:00:00 比赛注意事项——喵亦或鱼 1.先看多测关没关，需不需要开 2.本地不开无限栈 3.检查同步流开没开，endl替换!!! 4.MLE显示RE->检查define int long long是不是导致消耗过多空间 5.输入有没有全部读完，检查是不是存在提前return的情况。 6.Clarification出现就要报，已经过的确认不是重测 7.当发现题目不会做但是过了一片时应冲一发暴力或guess 8.每道题需至少有两个人确认题意，上机之前做法需得到队友确认 10细节、公式等在上机前应在草稿纸上准备好，防止上机后越写越乱 11.对于舍入输出，若 abs 不超过 eps，需要强行设置为0 来防止 −0.0000 的出现。 12.将待写的题按所需时间放入小根堆中，每次选堆顶的题目写
无容量限制的出栈序列验证——模拟
title: 无容量限制的出栈序列验证——模拟 categories: ICPC tags: null abbrlink: ea3c3b0a date: 2024-03-20 00:00:00 #include<iostream> #include<stack> using namespace std; //stack<int>q;//栈q int n,m,t; const int N=1100; int a[N],sum=1;//入栈队列a，待检验队列b，计数器sum int main() { cin>>m>>n>>t; for(int i=1;i<=n;i++) cin>>a[i]; while(t--){ stack<int>q;//栈q int b[N];sum=1; bool hve=false; for(int i=1;i<=n;i++) cin>>b[i];//平平无奇的输入...
比赛环境配置及测试
title: 比赛环境配置及测试 categories: ICPC tags: null abbrlink: 98ff3a70 date: 2024-03-19 00:00:00 比赛环境配置及机器测试 coderunnercoderunnercoderunner配置：注意打开:Run In Terminal设置，不然无法手动输入 "cpp": "cd $dir && g++ $fileName -Wall -Wextra -fsanitize=undefined -DLOCAL -D_GLIBCXX_DEBUG -std=c++17 -g -O2 -o $fileNameWithoutExt && $dir/$fileNameWithoutExt" 编译命令可加参数： -fdiagnostics-color=always //启用彩色诊断信息 -pg// 启用性能分析 ...