Codeforces Round 784 (Div. 4)
title: Codeforces Round 784 (Div. 4)categories: - ICPCtags: - nullabbrlink: 4bd1638edate: 2024-02-25 00:00:00Codeforces 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 st=0; for(int...
点分治
title: 点分治categories: - ICPCtags: - nullabbrlink: 34afe2f1date: 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)
关于char数组的字符串
title: 关于char数组的字符串categories: - ICPCtags: - nullabbrlink: c487264edate: 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: - ICPCtags: - nullabbrlink: e5b5491fdate: 2024-02-10 00:00:00维护集合最值和集合全体加 你有一个可重集合初始有n个数，有4种操作，$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 double #define...
bitset应用
title: bitset应用categories: - ICPCtags: - nullabbrlink: 6dd452c6date: 2024-02-06 00:00:00bitsetbitset前身：普通状态压缩的优化以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++) { for...
概率dp
title: 概率dpcategories: - ICPCtags: - nullabbrlink: 7502a855date: 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: - ICPCtags: - nullabbrlink: fceef695date: 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: - ICPCtags: - nullabbrlink: 4604f3c8date: 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...
trie字典树
title: trie字典树categories: - ICPCtags: - nullabbrlink: a9b036b6date: 2024-01-26 00:00:00维护一个字符串集合，支持两种操作： I x 向集合中插入一个字符串 $x$； Q x 询问一个字符串在集合中出现了多少次。 所有输入的字符串总长度不超过 $10^5$（ 也就是节点数） 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];...
Kummer定理
title: Kummer定理categories: - ICPCtags: - nullabbrlink: 5dcc6de2date: 2024-01-17 00:00:00Kummer定理设 $v_p(n)$表示 n 的质因数分解中质数 p 的幂次，则： $v_p(n!)=\sum\limits_{i=1}^\infty\left[\dfrac{n}{p^i}\right]$ 推论：$\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]...