将其抽象成图，建成图的模型 买了一个东西，买其他东西才有优惠 即走到了一个点才能走（走到）下一个点，即图的性质，以此建图 //点和点之间存优惠的价格 建完图后，已有"买了一个东西，买其他东西才有优惠"的性质，所以在选择方法时就不用考虑是否满足这个性质了 买所有东西花的钱最小 即所有边的边权之和最小 即最小生成树 一条边的边权即从某点指向另一点的优惠价格，所有是有向边， 但从i到j和从j到i的边权一样，所以就可以看成无向边 kruskal存的是无向边 最小生成树是n个点n-1条边，即sum是n-1个点权之和，但第一个点也要用钱购买，且是原价 所以 1...

贪心 尽可能让256多 可以合成256的个数z=min(k2,k5,k6); 对于32同理 z=min(k3,k2); #include<bits/stdc++.h> using namespace std; int k2,k3,k5,k6; int main(){ cin >> k2 >> k3 >> k5 >> k6; int z=0; int ans=0; z=min(k2,min(k5,k6)); ans+=z*256; k2-=z;k5-=z; k6-=z; ...

参考博客 #include<bits/stdc++.h> using namespace std; int n,a,d; double z; int main(){ cin >> n >> a >> d; while(n--){ double t0,v; cin >> t0 >> v; double ans=t0; if(v*v/(2*a)>=d){ ans+=sqrt(1.0*2*d/a); ...

#define ll long long ll gcd(ll a,ll b){ //a,b的大小不影响位置，既可以a>b,也可以a<b,也可以a==b return b==0 ? a : gcd(b,a%b); //如果需要高精度，将 %（求模） 变成 -（减号） } //最小公倍数：a*b/gcd(a,b)

{质数*质数 合数={合数*质数 ==> 质数*质数*质数 {合数*合数 ==> 质数*质数*质数*质数 ==> 质数*合数 ==> 合数={质数*质数 {质数*合数 欧拉筛：让每个合数被其最小质因子给筛掉 //由于每个数只被筛一次，时间复杂度为O(n) #include<bits/stdc++.h> using namespace std; int const N=1e3+7; int n,cnt; int v[N]; //v[i]表示(数字)i的最小质因子 int prime[N]; //p...

题目： P3372 【模板】线段树 1 线段树：存线段 除建树外，其余操作的复杂度大部分都为O(lgn) 建一个叶子，首先要访问这个叶子，访问一个叶子的复杂度为O(lgn) 所以建n个叶子的复杂度为O(nlgn) 所以建树的复杂度为O(nlgn) 相对于差分，线段树可以边修改边查询 二叉树的性质可以简单推导，不用记#include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e5+7; int n,m; int a[N]; int lazy[N<<2]; //懒标记 ...

题目：序列为n，将第i个数加或减x，求l到r的和样例： 7 1 4 5 6 3 2 7输出：5 2 #include<bits/stdc++.h> using namespace std; int const N=1e3+7; int n; int a[N]; int tree[N<<2]; //(N<<1)<<1 //N表示叶子节点的个数， //第一次 <<1 表示要给除叶子以外的其他节点开空间；第二次是给最后一层的下一层开空间，用来判断叶子是否是真的叶子（即判断叶子是否有儿子） void bulid(int...

第一题 换零钞 第二题 激光样式 第三题 格雷码 第四题 调手表 第五题 搭积木 第六题 矩阵求和

题目： 搭积木 参考博客 #include<bits/stdc++.h> using namespace std; #define ll long long int const mod=1000000007; int n,m; int h[105]; //每列的高度 char mp[105][105]; int f[105][105][2]; //f[pos][hi][fg][r]表示以pos为起点，r为终点，上一列的高度为hi，上升状态为fg时这个二维区间的方法数。 //因为r可以在使用时更新，所以再优化一维，变成f[pos][hi][fg],具体原因看代码...

kruskal也不怕自环和重边 因其有并查集和排序的操作 排序保证了每次选最优边 并查集保证每次两点不在同一集合，所以保证了无重边和自环此题分析：两点在同一集合表示已联通 #include<bits/stdc++.h> using namespace std; int const M=2e4+7; int const N=1e4+7; struct node{ int a,next,len; friend bool operator<(node a,node b){ return a.len < b.len ; } }e[M]; int f[N]; ...

题目： P3366 【模板】最小生成树 n为点，m为边 prim: O(nlgn) //以边遍历点，因其一边有两个点，所以每个点会有两次判断，所以复杂度为n^2，通过堆优化可以变成 nlgn prim是从一个点散出去找与其相连的未被访问的最小边 所以要用前向星的add kruskal: O(mlgm) //复杂度主要是为边排序 //n小就用prim //m小就用kruskal kruskal是从全局找未被访问的最小边 所以只要边排序就够了，用不到add 前向星：没有add函数的node不是前向星 通过前向星可以访...

1.前向星表示，与i相连点和边。从head[i]开始找，只能找到与i点相连的点和边2.前向星不怕重边

题意：有t组输入，有一个n * m的矩阵，每次只能在n * m的矩阵中取一个a * b大小的矩阵，将其全部减一，问经过若干次后，能否将n * m的矩阵，都变为0，若可以输出"^_^",否则输出"QAQ"分析：把区间减一这个操作翻过来看，就是 地毯 ， 地毯题解（二维前缀和，差分）此题为固定区间修改区间修改————前缀和，差分或线段树或树状数组 #include<bits/stdc++.h> using namespace std; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int const N=...

题意：一张n*m大的地图，每个点都有一个字母，每个字母都有对应的移动规则（W : 向上 ; S : 向下 ;A:向左；D：向右），问地图中有几个点可以移到地图外去 做法：让字母对应相应的方向，因其每个点都有字母，所以每个点都只有一个可搜索的方向 记录状态（记忆化搜索）（类似洛谷的滑雪） #include<bits/stdc++.h> using namespace std; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int const N=1e3+7; int n,m,cnt; st...