爱飞鱼的blog

title: 贪心categories: - ICPCtags: - nullabbrlink: 34811d5fdate: 2024-12-22 00:00:00贪心环形均分纸牌问题 #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; #define LL long long LL read(){ LL s=0,ne=1; char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1; for(;c>='0'&&c<='9';c=getchar())...

title: Z_exkmpcategories: - ICPCtags: - nullabbrlink: dc9ce3fcdate: 2024-12-21 00:00:00Z函数——拓展KMP算法作用：(考虑1base)求文本串 T 的每一个后缀与模式串 M 的最长公共前缀长度。核心数组z[i]就表示$lcp(s[i:end],s[1:n])$ 模板： 1.传的是0base串，函数内部会处理。 2.其次一般来说前面是模式串，间隔一个$分隔符后是文本串。这样就是可以知道文本串中出现了多少次模式串。 z函数的求解： vector<int> exkmp(string s){ int len=s.size(); s=" "+s; vector<int>z(len+1); z[1]=0; int l=1,r=0; for(int i=2;i<=len;i++){ if(i>r)z[i]=0; else {//利用之前的信息 int...

title: Codeforces Round 895 (Div. 3)categories: - ICPCtags: - nullabbrlink: 5848dec6date: 2024-12-16...

title: 可持久化字典树（Trie）categories: - ICPCtags: - nullabbrlink: 493cf1a5date: 2024-12-16 00:00:00最大异或和给定一个非负整数序列 ${a}$，初始长度为 $N$。 有 $M$ 个操作，有以下两种操作类型： A x：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $N$ 加 $1$。 Q l r x：询问操作，你需要找到一个位置 $p$，满足 $l \le p \le r$，使得：$a[p] \oplus a[p+1] \oplus … \oplus a[N] \oplus x$ 最大，输出最大值。 对于所有测试点，$1\le N,M \le 3\times 10 ^ 5$，$0\leq a_i\leq 10 ^ 7$。 分析：设 Si​ 表示前缀 i 个异或和，令 K=x⊕Sn，然后要在 [0,n−1] 中找到一个 p 使得 Sp⊕K 最大。// 递归版 const int N=600010, len=23; int n, m, s[N]; int...

title: 网格图上问题categories: - ICPCtags: - nullabbrlink: d8850d48date: 2024-12-15 00:00:002024天梯赛L3-1https://pintia.cn/problem-sets/994805046380707840/exam/problems/1781658570803388428?type=7&page=1 题意：网格图上有障碍物，空地，给定若干起点，和一个终点，求唯一的最短路。也就是存在大于等于两个起点到终点距离相同的时候，这些起点无法贡献答案。Solution：考虑直接从终点开始bfs，得到所有答案，最后统计起点即可更新答案。实现细节：首先这个题目给的坐标是和以往反过来的，需要我们仔细读题和看样例。其次我们在统计答案的时候，直接维护值域的哈希表，不应该维护pair坐标的哈希表，不然肯定不会出现重复。int n, m; int a[N][N]; map<pii,int>mp; int dx[5]={1,0,0,-1}; int...

title: 最小费用组最大流——EK算法categories: - ICPCtags: - nullabbrlink: 20afda2bdate: 2024-12-13 00:00:00#时间复杂度O（nm^2)，理论上限 //n,m,s,t，分别代表该网络的点数n，网络的边数m，源点编号s，汇点编号t。 const int N=5010,M=100010,INF=1e8; int n,m,S,T; struct edge{int v,c,w,ne;}e[M]; int h[N],idx=1;//从2,3开始配对 int d[N],mf[N],pre[N],vis[N]; int flow,cost; void add(int a,int b,int c,int d){ e[++idx]={b,c,d,h[a]}; h[a]=idx; } bool spfa(){ memset(d,0x3f,sizeof d); memset(mf,0,sizeof mf); ...

title: 【模板】差分约束categories: - ICPCtags: - nullabbrlink: 15b07eacdate: 2024-12-07 00:00:00给出一组包含 $m$ 个不等式，有 $n$ 个未知数的形如：$$ \begin{cases} x_{c_1}-x_{c’1}\leq y_1 \x{c_2}-x_{c’2} \leq y_2 \ \cdots\ x{c_m} - x_{c’_m}\leq y_m\end{cases}$$ 的不等式组，求任意一组满足这个不等式组的解。 输入格式第一行为两个正整数 $n,m$，代表未知数的数量和不等式的数量。 接下来 $m$ 行，每行包含三个整数 $c,c’,y$，代表一个不等式 $x_c-x_{c’}\leq y$。 数据范围 对于 $100%$ 的数据，$1\leq n,m \leq 5\times 10^3$，$-10^4\leq y\leq 10^4$，$1\leq c,c’\leq n$，$c \neq c’$。 #define MAXN 5005 #define MAXM...

title: CCF认证202109-4——之状态压缩dp加期望（记忆化搜索categories: - ICPCtags: - nullabbrlink: 2de6437edate: 2024-12-06 00:00:00https://www.acwing.com/problem/content/description/4012/Acwing long double卡常，注意cin读小数。 #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 double long double #define baoliu(x, y) cout << fixed << setprecision(y) << x #define endl ...

title: 快速乘categories: - ICPCtags: - nullabbrlink: dc64ee44date: 2024-12-03 00:00:00输出一个整数，表示a*b mod p的值。 数据范围1≤a,b,p≤1018 ll qadd(ll a, ll b, ll p) { ll res = 0; while (b) { if (b & 1) res = (res + a) % p; a = (a + a) % p; b >>= 1; } return res; } 利用longlong取模溢出相抵消 ll mul(ll x,ll y,ll m){ x%=m;y%=m; ll d=((long double )x*y/m); d=x*y-d*m; if(d>=m)d-=m; if(d<0)d+=m; return d; }

title: 贡献法解决子串问题categories: - ICPCtags: - nullabbrlink: ‘23933791’date: 2024-11-28 00:00:00对于一个字符串 $S$，我们定义 $S$ 的分值 $f(S)$ 为 $S$ 中恰好出现一次的字符个数。 例如 $f (“aba”) = 1$，$f (“abc”) = 3$, $f (“aaa”) = 0$。 现在给定一个字符串 $S[0…n-1]$（长度为 $n$），请你计算对于所有 $S$ 的非空子串 $S[i…j] (0 ≤ i \le j < n)$， $f (S[i…j])$ 的和是多少。 贡献法：考虑当前这个字母可以在多少个子串中贡献，找到左边最近的相同字母，右边最近的相同字母，左右乘法原理计算可贡献子串数 会爆longlong，并且只开ans不够 ##实现： 用哈希表正序逆序扫一遍，注意对于左右边界的处理时假设0和n+1存在相同字母 // Problem: 子串分值 // Contest: AcWing // URL:...