爱飞鱼的blog

title: Codeforces Round 784 (Div. 4) categories: ICPC tags: null abbrlink: 4bd1638e date: 2024-02-25 00:00:00 Codeforces Round 784 (Div. 4) 感觉是所有cf里简单的一场了 D:题意：给一排白砖染色，每次可以选择两个相邻的数染成红蓝或蓝红，可以覆盖。多次询问，每次给出一个终态（红蓝白），问这个状态有没有可能作为终态？ Solution：快速猜猜题.首先发现white直接将状态分割成若干段，也就是染色操作显然不能跨过W，所以考虑单独考察某一段，发现无论怎么操作只要出现两种颜色怎么样都能成功，所以对每个段维护颜色种类数，每段的种类数都为2才合法。 void solve(){ cin>>n; string str;cin>>str;str=" "+str; bool flag=true; set<char>s; bool end=0; bool...

title: 点分治 categories: ICPC tags: null abbrlink: 34afe2f1 date: 2024-02-22 00:00:00 点分治 P6326 Shopping - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 树形依赖背包的两种做法 - shzr - 博客园 (cnblogs.com) 算法｜点分治算法小结（实用入门篇） - 知乎 (zhihu.com) 点分治 - RainPPR’s Blog 【学习笔记】树论—点分树（动态点分治） - 辰星凌 - 博客园 (cnblogs.com) 算法学习笔记(73): 点分治 - 知乎 (zhihu.com) 【算法学习】点分治 - 粉兔 - 博客园 (cnblogs.com)

title: 关于char数组的字符串 categories: ICPC tags: null abbrlink: c487264e date: 2024-02-21 00:00:00 在 C/C++ 中，‘\0’ 和 0 是等价的。它们都表示数值零。 ‘\0’ 是一个字符常量，表示 ASCII 值为零的空字符（null character）。在字符串中，‘\0’ 用作字符串的结束标志。 而 0 是整数常量，表示数值零。在 C/C++ 中，字符类型可以看作是整数类型的一种特殊形式，因此 ‘\0’ 可以被视为整数常量 0。 下面展示一个字符数组遍历的例子 void insert(char *s){ int p=0; for(int i=0; s[i]; i ++){ int j=s[i]-'a';//字母映射 if(!ch[p][j])ch[p][j]=++idx; p=ch[p][j]; } cnt[p]++;//插入次数 }

title: 维护集合最值和集合全体加 categories: ICPC tags: null abbrlink: e5b5491f date: 2024-02-10 00:00:00 维护集合最值和集合全体加 你有一个可重集合初始有n个数，有4种操作，5e5次操作5e5次操作5e5次操作 向集合中加入一个数 删除集合中一个数 集合中所有数加x 查询集合最大值 进一步考虑另一个可以使用这个模型的问题。一个vector，动态在尾部增加数，删除数，边操作边求后缀和最小值 #include <bits/stdc++.h> #ifdef LOCAL #include "debug.h" #else #define deb(...) #endif using namespace std; #define ll long long // #define int long long #define ull unsigned long long #define pii pair<int, int> #define db...

title: bitset应用 categories: ICPC tags: null abbrlink: 6dd452c6 date: 2024-02-06 00:00:00 bitset bitset前身：普通状态压缩的优化 以cf937G为例,对于邻接矩阵的由二维压缩到一维 #include <bits/stdc++.h> using i64 = long long; void solve() { int n; std::cin >> n; std::vector<std::string> g(n), w(n); for (int i = 0; i < n; i++) { std::cin >> g[i] >> w[i]; } std::vector<int> e(n); for (int i = 0; i < n; i++) { ...

title: 概率dp categories: ICPC tags: null abbrlink: 7502a855 date: 2024-02-04 00:00:00 概率dp 首先是正着递推的计算概率的dp问题 https://ac.nowcoder.com/acm/contest/28263/A 纯数学题 对随机的数字大小分类讨论，计算概率的时候利用高中几何概型的线性规划手法进行计算。 double g=0.5; void solve(){ double k,x;cin>>k>>x; double ans=0; if(k==x)ans=g; else if(k>=2*x)ans=0; else if(k<x){ ans=g*(x*x-k*k); ans/=x*x; ans+=g; } else...

title: 倍增思想专题 categories: ICPC tags: null abbrlink: fceef695 date: 2024-02-03 00:00:00 倍增大专题【每日一题】倍增专题11月26-12月3日题目_牛客网 (nowcoder.com) [AHOI2008] 紧急集合 / 聚会 - 洛谷 题意：给定一棵树，多次查询费马点（bushi 费马点的含义是：到三个点的距离之和最小 Solution:考虑画图发现树上三点两两求lca，必然至少两个相同，然后我们只需要让费马点为另一个点就可以了，因为这一段路程只需要一个点走就最好了。 //考虑到让一个点走多的路程，两点走短路程 //首先对多种情况画图，可以知道树上三点两两求lca，必然至少两个相同 vector<int> e[N]; int fa[N],son[N],dep[N],siz[N]; int top[N]; void dfs1(int u,int f){ //搞fa,dep,son fa[u]=f;siz[u]=1;dep[u]=dep[f]+1; ...

title: 每天干了啥？ categories: ICPC tags: null abbrlink: 4604f3c8 date: 2024-01-27 00:00:00 每天干了啥？ 10.14上周一晚上内耗 ，，还在高斯消元呃呃 10.15上周二早上来实验室被因子square被gauss卡死，写了行列式生成树板子（非质数取模） 10.16周三下午集美大学校赛，晚上22南京 10.17周四上午o(1)k级祖先，下午长链剖分树形dp，晚上写作业 10.18开了离线并查集，周五下午来了以后写abc睡着了，状态不好。回去睡觉，十点多才来了以后 周六起来以后，写虚数板子，调试虚树。晚上打了有cf 周日呃呃，vp香港，补了f题。吃饭睡觉，来了以后写膝盖。回去写了计算机网络 10.21开了个新坑slope...

title: trie字典树 categories: ICPC tags: null abbrlink: a9b036b6 date: 2024-01-26 00:00:00 维护一个字符串集合，支持两种操作： I x 向集合中插入一个字符串 xxx； Q x 询问一个字符串在集合中出现了多少次。 所有输入的字符串总长度不超过 10510^5105（ 也就是节点数） const int N=100010; int n; char s[N]; int ch[N][26],cnt[N],idx; void insert(char *s){ int p=0; for(int i=0; s[i]; i ++){ int j=s[i]-'a';//字母映射 if(!ch[p][j])ch[p][j]=++idx; p=ch[p][j]; } cnt[p]++;//插入次数 } int query(char *s){ int p=0; for(int i=0; s[i];...

title: Kummer定理 categories: ICPC tags: null abbrlink: 5dcc6de2 date: 2024-01-17 00:00:00 Kummer定理 设 vp(n)v_p(n)vp​(n)表示 n 的质因数分解中质数 p 的幂次，则： vp(n!)=∑i=1∞[npi]v_p(n!)=\sum\limits_{i=1}^\infty\left[\dfrac{n}{p^i}\right]vp​(n!)=i=1∑∞​[pin​] 推论：$\begin{aligned} v_p(\text{C}_{n+m}^m)&=v_p((n+m)!)-v_p(m!)-v_p(n!) \\ &=\sum\limits_{i=1}^\infty\left[\dfrac{n+m}{p^i}\right]-\sum\limits_{i=1}^\infty\left[\dfrac{m}{p^i}\right]-\sum\limits_{i=1}^\infty\left[\dfrac{n}{p^i}\right]...