贪心
title: 贪心 categories: ICPC tags: null abbrlink: 34811d5f date: 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()) s=((s<<1)+(s<<3))+c-'0'; return...
Z函数与扩展KMP算法详解 - 以CF126B为例
title: Z函数与扩展KMP算法详解 - 以CF126B为例 categories: 算法 ICPC tags: 字符串 Z函数 KMP abbrlink: dc9ce3fc date: 2024-12-21 00:00:00 mathjax: true Z函数——拓展KMP 算法作用：(考虑1base)求文本串 T 的每一个后缀与模式串 M 的最长公共前缀长度。核心数组z[i]就表示lcp(s[i:end],s[1:n])lcp(s[i:end],s[1:n])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...
Codeforces Round 895 (Div. 3)
title: Codeforces Round 895 (Div. 3) categories: ICPC tags: null abbrlink: 5848dec6 date: 2024-12-16 00:00:00 A题简单的模拟计算，注意上取整的实现。 B题计算每个房间对应的每个最迟时间点，在这些时间点最取最小值，保证能安全通过所有房间。 D题拿到手就可以发现是贪心，但发现两部分会有冲突，也就是重复计算的部分。故提前找到两个数的lcm然后不计算lcm的倍数，为其他参与计算的数安排剩余数种的最大值和最小值，最后需要推导一一下等差数列求和 ...
可持久化字典树（Trie）
title: 可持久化字典树（Trie） categories: ICPC tags: null abbrlink: 493cf1a5 date: 2024-12-16 00:00:00 最大异或和 给定一个非负整数序列 {a}\{a\}{a}，初始长度为 NNN。 有 MMM 个操作，有以下两种操作类型： A x：添加操作，表示在序列末尾添加一个数 xxx，序列的长度 NNN 加 111。 Q l r x：询问操作，你需要找到一个位置 ppp，满足 l≤p≤rl \le p \le rl≤p≤r，使得：a[p]⊕a[p+1]⊕...⊕a[N]⊕xa[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus xa[p]⊕a[p+1]⊕...⊕a[N]⊕x 最大，输出最大值。 对于所有测试点，1≤N,M≤3×1051\le N,M \le 3\times 10 ^ 51≤N,M≤3×105，0≤ai≤1070\leq a_i\leq 10 ^ 70≤ai≤107。 分析：设 Si 表示前缀 i 个异或和，令...
网格图上问题
title: 网格图上问题 categories: ICPC tags: null abbrlink: d8850d48 date: 2024-12-15 00:00:00 2024天梯赛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...
最小费用组最大流——EK算法
title: 最小费用组最大流——EK算法 categories: ICPC tags: null abbrlink: 20afda2b date: 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: ICPC tags: null abbrlink: 15b07eac date: 2024-12-07 00:00:00 给出一组包含 mmm 个不等式，有 nnn 个未知数的形如： {xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym\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} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym 的不等式组，求任意一组满足这个不等式组的解。 输入格式 第一行为两个正整数 n,mn,mn,m，代表未知数的数量和不等式的数量。 接下来 mmm 行，每行包含三个整数 c,c′,yc,c',yc,c′,y，代表一个不等式...
CCF认证202109-4——之状态压缩dp加期望（记忆化搜索
title: CCF认证202109-4——之状态压缩dp加期望（记忆化搜索 categories: ICPC tags: null abbrlink: 2de6437e date: 2024-12-06 00:00:00 https://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: ICPC tags: null abbrlink: dc64ee44 date: 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: ICPC tags: null abbrlink: ‘23933791’ date: 2024-11-28 00:00:00 对于一个字符串 SSS，我们定义 SSS 的分值 f(S)f(S)f(S) 为 SSS 中恰好出现一次的字符个数。 例如 f(“aba”)=1f (“aba”) = 1f(“aba”)=1，f(“abc”)=3f (“abc”) = 3f(“abc”)=3, f(“aaa”)=0f (“aaa”) = 0f(“aaa”)=0。 现在给定一个字符串 S[0…n−1]S[0…n-1]S[0…n−1]（长度为 nnn），请你计算对于所有 SSS 的非空子串 S[i…j](0≤i≤j<n)S[i…j] (0 ≤ i \le j < n)S[i…j](0≤i≤j<n)， f(S[i…j])f (S[i…j])f(S[i…j]) 的和是多少。 ...