爱飞鱼的blog

title: 矩阵快速幂categories: - ICPCtags: - nullabbrlink: 7f45ba65date: 2024-05-16 00:00:00debug:重载乘号的时候要把两个传进来的矩阵用起来// 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...

title: DFS ordercategories: - ICPCtags: - nullabbrlink: ac1f1f56date: 2024-05-02 00:00:00DFS 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: - ICPCtags: - nullabbrlink: 7463b265date: 2024-04-16 00:00:00const 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: - ICPCtags: - nullabbrlink: b5073eccdate: 2024-04-12 00:00:00最长上升子序列我们讨论的是严格单调递增的LIS，然后考虑基本状态$dp[i]$表示以i结尾的LIS长度。状态转移是$dp_i=\max\limits_{j<i, a_j<a_i} dp_j+1$ 朴素$O(n^2)$ 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++) { dp[i] = 1; for (int j = 1; j <= i - 1; j++) { ...

title: log_trickcategories: - ICPCtags: - nullabbrlink: f88e4243date: 2024-04-05 00:00:00一类子区间gcd，按位与，按位或的问题有 $T$ 组询问，每次给出 $n$ 个数 $a_i$。[P7009 CERC2013] Magical GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)你需要找到这个数组的一个子序列（要求编号连续），使得该序列中所有数的最大公约数和序列长度的乘积最大，并输出这个最大值。Sol:重要性质如果右端点不同，那么gcd意义下本质不同的左端点只有log个https://www.luogu.com.cn/problem/P5502include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e5+10; #define LL long...

title: 最短路计数categories: - ICPCtags: - nullabbrlink: fa5b931edate: 2024-03-30 00:00:00P1144 最短路计数题意：求出起点到各个点的最短路条数。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: - ICPCtags: - nullabbrlink: bd001d9edate: 2024-03-29 00:00:00https://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: - ICPCtags: - nullabbrlink: d2ddb657date: 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: - ICPCtags: - nullabbrlink: ea3c3b0adate: 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: - ICPCtags: - nullabbrlink: 98ff3a70date: 2024-03-19 00:00:00比赛环境配置及机器测试$coderunner$配置：注意打开: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// 启用性能分析 ...