ZestfulYK的Blog

题目输入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...

二分查找是常见的算法,但是我发现我经常无法区分应当使用哪种变形来计算答案,因此这里做一下讲解. 标准写法123456ll l=___,r=___;while(l<=r){ ll mid=l+(r-l)>>1; if(____) l=mid+1; else r=mid-1;} 判断条件的选择判断条件可以理解为,每次要淘汰哪一部分,并通过l,r指针的移动来确定的 前提条件:假设现在我们有一个升序的数组 比如:我现在要查找第一个大于等于key的值那么我们的条件就应该是每次循环都删去小于key的值,不能删去大于的,因为答案可能在这里面 于是我们的条件就写成:if(a[mid]<key) l=mid+1;为什么是mid+1?因为l表示的是左边界,左边界移动了,就相当于淘汰了左边的小于key的值 同理,我们在写找第一个大于当前值时,只要改成<=即可 那么反过来呢? 没错,把条件和操作全反过来即可.现在我们要找第一个小于等于key的值所以我们每次淘汰的是大于key的值 条件变为:if(a[mid]>key) r=mid-1; 答案的取值弄...

说明这些是我平时攒下来的模板,现在送给大家! 火车头12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <algorithm>#include <bitset>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <map>#include <iostream>#include <queue>#include <set>#include <stack>#include <vector>#include <array>#include <unordered_map>#inclu...

单纯的指针最简单的指针带*的：野指针(确信) 1int *p; //一只快乐的野指针，未初始化的指针，指向随机地址(野指针) 这个表示定义了指针，不过注意，前面的类型是要自己设定的，不能乱写但是提到指针，就不得不提到&(取地址符)了 &的用法：&表示取地址符，比如这样： 12int a=1;cout<<&a<<endl;//输出a的地址 这一句表示输出a变量对应的地址位置，详细见书上的解释，获取地址的开头方便输出 然后指针所能存储的恰好是地址，所以可以这么写：1int *p=&a; 表示p指向a对应的地址 指针的初始化可以把指针设定为NULL，这里表示p不指向任何一个地址要是没有初始化，p可能指向任何一个位置，可能导致代码错误，所以被称作野指针 1234567int *p = NULL; // 未初始化指针（野指针）*p = 10; // 段错误// 解引用前应检查if(p != NULL) { *p = 10;} 指针的多种含义在实际程序中，*p，可能有多种含义： 表示p...

版权说明此文章的所有代码均由qinye_leaf 勤叶大佬收集整理，感谢喵Orz Orz Orz 初始化由于双精度和单精度存在精度问题，所以补能直接判断是否为0或者相等，那么怎么办呢？我们可以取绝对值，然后和一个非常小的数字比较 代码示例：12// 浮点数精度阈值(根据题目要求调整，通常1e-8)const double EPS = 1e-8; 符号函数判断正负号的函数，但是是浮点数数版本的 12345// 符号函数：判断浮点数正负int sgn(double x) {    if (fabs(x) < EPS) return 0;    return x > 0 ? 1 : -1;} 构造函数介绍解释一下构造函数的用法，这里可以直接赋初始值，方便初始化 1234Point(double x_ = 0, double y_ = 0) : x(x_), y(y_) {}//那么我们可以这么来定义一个变量Point p1(2.0,3.0);Point p2; 如果不传参数，那么就是直接得到初始值0,0,要是有值的化就是直接赋值，这样...

循环的遍历 注意一下最内层的循环是什么，他决定了这一步的决策是什么。 例题纸币问题 2 这一题要我们求完全背包的方案数（考虑顺序） 那么内层循环应该放的是面额的遍历，因为最后一步的面额是不一定的。 正确写法✔： 1234for(int i=1;i<=w;i++)   for(int j=1;j<=n;j++)      if(i>=a[j])        dp[i]=(dp[i-a[j]]+dp[i])%mod; 错误写法❌： 123456for(int i=1;i<=n;i++){ ll x; cin>>x; for(int j=x;j<=w;j++){ dp[j]=(dp[j-x]+dp[j])%mod; }} 为什么下面那个是错误的？ 因为把当前面额作为内层循环，相当于固定了最后一步只能是这个面额，没法考虑到顺序问题。这样的话第二次只能在第一次的基础上增加。实际上，第一次的面额也可以在第二次的基础上增加。因此这个做法是不正确的。注意：下面那个方法因为只考...

不知道vector的size是size_t类型 因为是size_t所以直接加减会出错，比如减成负数的时候。 内层循环变量写错 这个会导致外层循环少了几次 sort里面的数据范围没开正确 例如要对n * m的数据排序，却只写了n 不看清读入顺序 看清读入的是有序的还是乱序的，不要被样例蒙蔽了双眼 位运算不写ll 区分以下代码的区别: 12(1<<i) //得到int(1ll<<i) //得到ll 特判不提前return 特判不提前return的话会导致产生多个输出 答案有取余输出不额外取余 输入万一本身就比mod大,自然是要取余的 提交时忘记去掉测试语句 没招了,这是真防不胜防

定义 构造一些操作，使得数据满足操作要求，通常还会有次数限制 方法此类题目现在遇到过三种做法： 一种是直接操作，不关心部分值，直接对全局操作，使得再让全局满足要求的同时，使得部分也满足要求 另一种是进行操作，最后只改变一个量，每次用多步做一步（和魔方有点像？） 例题1.B. Siga ta Kymata 题目描述：给你一个排列 $^{\text{∗}}$ 。从 $1$ 到 $n$ 的每个整数的排列 $p$ 。您还拥有一个大小为 $n$ 的二进制 $^{\text{†}}$ 字符串 $s$ ，其中 $s_i = \mathtt{0}$ 代表所有 $1 \le i \le n$ 。您最多可以执行以下操作 $5$ 次：选择任意两个整数 $l$ 和 $r$ ，使得 $1 \le l \le r \le n$ .然后，对于每一个 $i$ 使得 $l< i< q$ 和 $\min(p_l, p_r) < p_i < \max(p_l, p_r)$ 同时成立，你将把 $s_i$设为 $\mathtt{1}$ 。您还会得到一个大小为 $n$ 的二进制字符串 $x$...

递归函数的定义注意一下在命名函时，可以不写参数的名称，比如：1void fun(int,int) 结构体排序12345678910111213void mySwap(Data *p1,Data *p2){//交换函数    Data t=*p1;    *p1=*p2;    *p2=t;}for(int i=0;i<n-1;i++){    for(int j=0;j<n-i-1;j++){       if(a[j].num>a[j+1].num ||        (a[j].num==a[j+1].num && a[j].value>a[j+1].value)){           mySwap(&a[j],&a[j+1]);        }    }} 传入时注意，要加上&，传入地址，使得函数可以交换地址。 数组的定义 使用new和delete一起运算。 基本方法1234// 创建一维动态数组数据类型* 指针名 = n...

第一类有理积分主要方法 放入分子 放入分子的部分 放入分母 放入分母的部分 特殊构造|—商的导数求积分部分|—两个函数相乘求导$e^x$|—三角函数构造$\tan x$ 最后复习一下一些特殊的积分公式放入分子 这一中方法比较基础。 如果是放入分子的，那么必然是如下形式的\int \frac{f'(x)}{f(x)}\,dx 这样就能得到\int \frac{df(x)}{f(x)} 所以先看一下分母求导的结果有没有可能等于分子，如果是，那么就可以用这种方法 例题\int \frac{\sin x+\cos x}{\sqrt[3]{\sin x-\cos x}}\,dx放入分子的部分 这个通常出现在三角函数中，因为这样可以把所有三角函数化程同名。 然后放入时注意一下和分子的形式要对上。例题\int \frac{\sin x\cos x^3}{1+\cos x^2}\,dx 这题直接放入$\sin x$还不行，因为要注意一下分母的形式。所以注意到可以凑出$\sin 2x$，这样放入时形式就一样了 放入分母 放入分母的实际上是这种形式$\int f’(x)f(x)\,dx$ 然后被...