ZestfulYK的Blog

ZestfulYK的战绩 比赛难度中等，以基础题为主，拼尽全力战胜少量难题 部分代码F 分析很不错的博弈题目，使我的大脑旋转，最后打表做出来了 题目链接 代码:1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;#define ll long longint main(){ ll n,m; cin>>n>>m; if(n==0&&m==0) cout<<"Bob"<<endl; else if(n==1&m==0) cout<<"Alice"<<endl; else if(n==2&m==0) cout<<"Bob"<<endl; else if(n==3&m==0) cout<<"Bob"...

标题的使用123# 一级标题## 二级标题### 三级标题 字体粗体 斜体 删除线 行内代码 小标题的使用 无序列表项 另一个项目 有序列表 第二项 链接，图片12[链接文字](https://example.com) 引用块12> 这是一个引用块> 可以多行使用 这是一个引用块可以多行使用 表格1234| 姓名 | 年龄 | 城市 ||------|------|------|| 张三 | 25 | 北京 || 李四 | 30 | 上海 | 姓名 年龄 城市 张三 25 北京 李四 30 上海

题目描述给定一个非负整数 $n(0\leq n \leq 10^7)$，求有多少个长为 30 的非负整数序列 a ,满足 $\sum_{i=0}^{29}2^i*a_i=n$由于答案可能很大，请将结果对 998244353 取模后再输出。 解法看到题目，第一反应就是一个完全背包的动态规划题目，所以直接打表解决，不过发现超时了，那么怎么办呢？ 输出前30个数得到如下结果：1231 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36 36 46 46 60 60 74 74 94 94 114 114 140 140 166观察得到，每两个数是一样的，如果去重的话得到： 11 2 4 6 10 14 20 26 36 46 60 每一次的差正好都在前面出现过且这个差的位置刚好是n/2，那么可以得到递推式子：$$\begin{cases}dp[i]=dp[i-1]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{i为奇数}\dp[i]=dp[i-1]+dp[i/2]\ \ \ \ \ \ \text{i为偶...

DSU是并查集的缩写 总共有三种操作 初始化,查找根节点和连接 代码如下: 1234567891011121314struct dsu{//dsu std  vector<ll> fa,sz;  dsu(ll n):fa(n+1),sz(n+1,1){    for(int i=1;i<=n;++i){      fa[i]=i;    }  }  ll find(ll x){return fa[x]==x?x:fa[x]=find(fa[x]);}  void uni(ll x,ll y){    if(sz[x]<sz[y]) swap(x,y);    fa[y]=x;    sz[x]+=sz[y];  }}; 使用方法如下: 123dsu dsu1(n);ll fu=dsu1.find(u),fv=dsu2.find(v);if(fu!=fv) uni(fv,fu); 加了一个sz数组来计算每片区域的大小,这样就能防止图退化成一条链

拓展欧几里得算法用于在计算gcd的同时计算形如 ax+by=gcd(a,b)方程的答案 怎么计算呢? 首先考虑一个类似的方程: bx_2+(a\ mod\ b)y_2=gcd(b,a\ mod\ b)要是能得到这个方程的解,上面那个也行因为 a-\lfloor \frac{a}{b}\rfloor*b=a\ mod\ b所以 bx_2+(a-\lfloor \frac{a}{b}\rfloor*b)y_2=b*(x_2-\lfloor \frac{a}{b}\rfloor y_2)+ay_2因为 gcd(a,b)==gcd(b,a\ mod\ b)两个系数相同的方程有相同的解,那么解对应相等 \begin{cases}x_1=y_2 \\ y_1=x_2-\lfloor \frac{a}{b}\rfloor y_2 \end{cases}接下来只要一直往下递归计算就能得到答案了 边界条件是b=0的时候,在C++内默认gcd(a,0)=a,所以最后一步的方程为 ax+0*y=a因此一般返回值是1,0 最后就能得到一组特解和gcd(a,b)了 代码: 1234567891011121...

用于处理在一个数组的连续区间上进行等差序列的增减 例如:给1-5这个区间增加12345 多次操作后,问数组的最终值 方法就是二阶差分,推导一下就行 1234567 变化值 下标数组 0 1 2 3 4 5 6 7 8 9 10初始 0 0 0 0 0 0 0 0 0 0 0变化 0 1 3 5 7 9 0 0 0 0 0一阶 0 1 2 2 2 2 -9 0 0 0 0二阶 0 1 1 0 0 0 -11 9 0 0 0 所以规律: 12345ll d=(e-s)/(r-l);//s第一个位置的值,e最后一个位置的值,r,l是区间范围b[l]=b[l]+s;b[l+1]=b[l+1]+d-s;b[r+1]=b[r+1]-(d+e);b[r+2]=b[r+2]+e; 然后难一点的话就是阶梯型的修改如123454321这种,然后再不保证l,r一定在范围内,自己推导就行 123456789101112vector<ll> d(n+5,0);for(int i=1;i<...

定义路径的权值为路径上最大的边权,两点的距离定义为所有路径中权值的最小值 给定两张图,判断两张图之间每两个点的距离是否对应相等 思路自环对距离的影响为:增大路径的权值,所以自环没有作用,可以删去图上的环对距离的影响为:因为我们最后总是会选择较短的路,因此所有环上的最大边可以删去重边相当于一种特殊的环,选择最小的那一个留下就行 那么经过处理以后,这个无向图貌似变成了一颗最小生成树? 不用怀疑,这就是最小生成树森林! 那么怎么证明呢? 我发现一个类似的算法:反向删除构建最小生成树构建过程具体如下:按边权从大到小依次删去边,要是不影响连通性则删去,最后得到最小生成树 应用在这一题,我们破环相当于删去了不影响连接性的一条边权较大的边,所以最后得到的就是最小生成树 而我们需要判断距离是否一样,那么只要其最小生成森林一样就行 因为此处已经得出结论,只要算出最小生成树,问题就解决了一半,所以接下来正向考虑每一条边加入图中对距离的影响 在两张图中同时进行最小生成树算法,要是这两条边的边权一样,连起的区块相同,那么所有点在两张图的距离仍对应相等 证明(DeepSeek): 这是因为在按权值从小到...

用途:查询最短路,计算答案值范围较小的dp题目 最短路就不解释了,讲讲第二种是怎么回事 题目:给定两个数组a,b($a_i,b_i<2048$),长度为n$(1<n<2048)$,x初始为0,每次允许操作 \begin{cases} x=max(0,x-a_i)\\ \\ x=x\oplus b[i] \end{cases}求最后x的最大值 因为a对x的影响是减小,b是增大,异或b以后也不会超过2048,也就是最多2048个答案,那么可以用类似广搜的做法来计算每一步能取到的所有答案,这样就不需要dfs了 所以代码: 123456789101112131415161718void solve(){  ll n; cin>>n;  vector<ll> a(n+1),b(n+1);  for(int i=1;i<=n;i++) cin>>a[i];  for(int i=1;i<=n;i++) cin>>b[i];  set<ll> last; last.insert(0);  for...

题目描述:在正常的广搜上加一个条件:每个点有开放时间,在开放之前禁止更新 方法:实际上,当开放后,第一个来更新他的点,是他周围第一个被更新过的点,所以距离直接标为min(dist[nowx][nowy]+1,open[nowx][nowy]+1) 然后加上一个优先队列就行了这里提一下二维的优先队列写法: 1priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<>> q; 这样就不用依赖tuple了

题目输入n,构造长度为$2^n-1$的序列,使得下面在这个式子的值最小 \sum_{i=1}^{2^n-1}a_{i-1} \oplus a_i方法:每组相邻元素最好二进制中只有一位不一样 打表结果: 1234n=1 0 1n=2 0 1 3 2n=3 0 1 3 2 6 7 5 4 1 0 2 3 7 6 4 5 所以暴力或者按结论使用格雷码 12345678910111213#include <iostream>using namespace std;int main() { int n; cin >> n; int m = 1 << n; for (int i = 0; i < m; ++i) { cout << (i ^ (i >> 1)); if (i < m - 1) cout << ' '; } cout << endl; return 0...