牛寒1补题
以后学习这种解题写法一道简单模拟当时卡了一会儿就是因为“当前双方比分已经使得无论之后的罚球结果如何都不会影响比赛的结果”没有转过来 用了一个变量记轮数其实不用 只需要两个新变量记剩下几个球可以进就可以了
[A模拟点球] [c++]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>using namespace std;void work(){ string s; cin>>s; int a=0,b=0,la=5,lb=5; for(int i=0;i<10;i++){ if(i%2){ lb--; if(s[i]=='1'){ b++; if(b>a+la){ printf("%d\n",i+1); return; & ...
牛寒2补题
第一题和第二题只是数据不同第一题可以通过a+b=n 不枚举第二个区间 直接把b算成n-a就能过第二题只要有枚举那么必超时 所以肯定是推式子可知答案是取[L2,R2] [n-R1,n-L1]的交集求交集有固定写法这个交集就是[max(L2,n-R1),min(R2,n-L1)]当然可能没有交集 所以最后要和0max一下
[a+b=n] [c++]12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;int n,l1,r1,l2,r2,a;int main(){ ios::sync_with_stdio(false); cin.tie(0); int a; cin>>a; while(a--) { int tot=0; cin>>n; cin>>l1>>r1; cin>>l2>>r2; ...
树和图的优先遍历
tips:树是一种特殊的图 是无环连通图
有向图边有方向 如a->b无向图边没有方向 a<->b无向图是特殊的有向图 我们就先理解有向图的储存
1.邻接矩阵 其实就是一个二维数组 g[a][b]就存储a->b 有权重就是权重 没有就是bool值表示有无边 邻接矩阵不能有重边 只能保留一条 这个比较浪费空间
2.邻接表 就是n个节点 每个都开单链表 就跟哈希拉链法一样
[树的存储] [c++]1234567891011121314151617181920#include<bits/stdc++.h>using namespace std;const int N=10010,M=N*2;int h[N],e[N],ne[N]; //h链表头 e节点的值 ne指每个节点的next指针 与之前的单链表一样void add(int a, int b) //添加一条边a->b{ e[idx]=b; //新用到的节点值为b ne[idx]=h[a];//这个节点的next指针指向a所在点的链表原本的头结点 h[a]=idx; / ...
stl 2.0
系统为某一个程序分配空间时,所需时间基本与空间大小无关,与申请次数有关例 vector最开始就分配了32位空间 不够时再申请64的空间 将之前的copy过来实际上是一个倍增的思想
[vector与pair] [c++]123456789101112131415161718192021222324252627282930vector<int> a(10); //定义长度为10的vectorvector<int> b(10,3); //长度为10且初始化为3的vectora.size();//a元素个数 所有容器都有 时间复杂度O(1)a.empty();//返回是否为空a.clear(); //清空 注意队列没有cleara.front();//首位a.back();//末位push_back(); //末尾添加pop_back(); //删掉最后一个数a.erase(a.begin()+2); //删除第3个元素a.insert(a.begin()+i,b); //在第i+1个元素前面插入b;begin() end() //迭代器 前者就是a[0] 后者是最后一 ...
哈希散列表
将-10^9-10^9的数指向0-10^5的数 称为哈希函数一般情况 x mod 10^5但是这个简单方法可能将两个数映射到一个数而冲突
1.拉链法 如果两条链是冲突的 那么在同一位置用一个链将两个数都存下来2.开放寻址法 (感觉这个简单一点)
[拉链法模拟散列表] [c++]12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<bits/stdc++.h>using namespace std;const int N=100003; //模的数是质数且离2的n次方远 冲突概率最小int h[N];//"给拉链开槽"int e[N],ne[N],idx;void insert(int x){ int k= (x%N+N)%N; //c++里负数mod整数是负数 modN再+N再modN就是正的 k就是哈希值 e[idx]=k; //先把新点值赋好 ne[idx]=h[k]; //这一点的next指针 ...
堆
就是stl里的优先队列堆是一棵完全二叉树除了最后一层 上面所有节点都是满的 最后一层是从左到右排列
小根堆 每一个点都小于等于左右子节点的 根节点就是最小值存储根节点是1 x的左儿子是2x 右儿子是2x+1
1.插入一个数 heap[++size]=x; up[size];2.求集合当中最小值 heap[1]; 根节点就是最小的3.删除最小值 heap[1]=heap[size]; size–; down(1); 用尾节点替换最小的堆顶 向下调整4.删除任意一个元素 heap[k]=heap[size]; size–; down(k);up(k) //不知大小关系5.修改任意一个元素 heap[k]=x; down(x);up(x);//同理 不知大小关系直接down了在up
[堆排序] [c++]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748//思路就是将序列建成堆结构 每一次 ...
