爱飞鱼的blog

贪心 环形均分纸牌问题 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;#define LL long longLL 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())...

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函数的求解： 1234567891011121314151617181920vector<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...

A题简单的模拟计算，注意上取整的实现。 B题计算每个房间对应的每个最迟时间点，在这些时间点最取最小值，保证能安全通过所有房间。 D题拿到手就可以发现是贪心，但发现两部分会有冲突，也就是重复计算的部分。故提前找到两个数的lcm然后不计算lcm的倍数，为其他参与计算的数安排剩余数种的最大值和最小值，最后需要推导一一下等差数列求和 ...

最大异或和 给定一个非负整数序列 {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 个异或和，令 K=x⊕Sn，然后要在 [0,n−1] 中找到一个 p 使得 Sp⊕K...

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

#时间复杂度O（nm^2)，理论上限 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859//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); ...

给出一组包含 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′​​≤y1​xc2​​−xc2′​​≤y2​⋯xcm​​−xcm′​​≤ym​​ 的不等式组，求任意一组满足这个不等式组的解。 输入格式 第一行为两个正整数 n,mn,mn,m，代表未知数的数量和不等式的数量。 接下来 mmm 行，每行包含三个整数 c,c′,yc,c',yc,c′,y，代表一个不等式 xc−xc′≤yx_c-x_{c'}\leq yxc​−xc′​≤y。 数据范围 对于 100%100\%100% 的数据，1≤n,m≤5×1031\leq n,m \leq 5\times...

https://www.acwing.com/problem/content/description/4012/ Acwing long double卡常，注意cin读小数。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#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 ...

输出一个整数，表示a*b mod p的值。 数据范围 1≤a,b,p≤1018 1234567891011ll 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取模溢出相抵消 123456789ll 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;}

对于一个字符串 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]) 的和是多少。 贡献法：考虑当前这个字母可以在多少个子串中贡献，找到左边最近的相同字母，右边最近的相同字母，左右乘法原理计算可贡献子串数 会爆longlong，并且只开ans不够 ##实现：...