第一题 给定n个人，每个人有能力值，是一个排列，每次第一个人和第二个人比赛，输的一方会放在最后面，当有一个人连续赢了m场比赛结束，问总共经过几场比赛。 。按题意deque 模拟。 #include<bits/stdc++.h> using namespace std; #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define pr printf #define IN freopen("in.txt","r",stdin); #define OUT freopen(&quot...

面向对象原则 依赖倒置原则（DIP） 高层模块（稳定）不应该依赖于低层模块（变化），二者都应该依赖于抽象（稳定）。 抽象（稳定）不应该依赖于实现细节（变化），实现细节应该依赖于抽象（稳定）。 开发封闭原则（OCP） 对扩展开发，对更改封闭。 类模块应该是可扩展的，但是不可修改。 单一职责原则（SRP） 一个类应该仅有一个引起他改变的原因。 变化的方向隐含着类的责任。 Liskov 替换原则（LSP） 子类必须能够够替换他们的基类（IS-A）。 继承表达类型抽象。 接口隔离原则（ISP） 不应该强迫客户程序依赖于它们不用的方法。 接口应该小而完备。 优先使用对象组合，而不是...

1406. 石子游戏 III 设代表该玩家在区间内的最大值，那么一定是等于减去上一个玩家在区间的最小值上一个玩家可能取了一个，两个或者三个。所以可以有，; class Solution { public: int dp[50005]; string stoneGameIII(vector<int>& a) { int sum=0,n=a.size(); dp[n]=0; for(int i=n-1;i>=0;i--){ sum+=a[i]; int a...

性质 节点是红色或黑色 根节点是黑色 所有叶子都是黑色。（叶子是NUIL节点） 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点） 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点 如果一个节点的一个子节点是黑色，那么这个节点一定有2个节点。 插入情景 删除情景 Code enum Color{red,black}; template<typename T> struct BiTNode{ BiTNode *left; BiTNode *right; BiTNode *parent; C...

AVL树是一种自平衡二叉排序树，它的特点是任何一个节点的左子树高度和右子树的高度差在-1,0,1三者之间。AVL树的任何一个子树都是AVL树。 旋转插入操作： template<typename T> struct BiTNode{ T val; int h; BiTNode *left,*right; BiTNode(){} BiTNode(T val):val(val){ left=NULL;right=NULL; } }; template<typename T,typename node=BiT...

二叉树 template<typename T> struct BiTNode{ BiTNode(){} T val; BiTNode *left,*right; }; using node=BiTNode<int>; void build(node* &root){ int val;cin>>val; if(val==-1){root=NULL;return;} root=new node;root->val=val; build(root->left);build(roo...

二叉堆 template<typename T,size_t _n> struct hep{ int n;T *q; hep(){n=0;q=new int[_n];} ~hep(){delete []q;} void up(int i){ //上浮 for(;i>1;i>>=1) if(q[i]<q[i>>1])swap(q[i],q[i>>1]); } void down(int i){ //下浮 while((i<<1...

栈混洗 有A,B,S，三个栈，初始化一个排列在B中，B中的元素，通过栈S到达栈A中，A中可以得到不同的排列。计数：A中排列的个数记为排列的长度是的时候的个数，若中已经有个元素，则中剩余个元素，这时候的个数是 ,枚举,这就是卡特兰数列， 判断栈A的排列是否能由栈B经过栈S得到模拟栈B，pop()的过程。 bool is(int *A,int *B,int n){ //A 栈底[1,n]栈顶。 //B 栈顶[1...n]栈底 stack<int>S; int t=1; for(int i=1;i<=n;i++){ ...

链表和数组区别 两者的区别： 数组静态分配内存，链表动态分配内存。 数组在内存中是连续的，链表是不连续的。 数组利用下标定位，查找的时间复杂度是O(1)，链表通过遍历定位元素，查找的时间复杂度是O(N)。 数组插入和删除需要移动其他元素，时间复杂度是O(N)，链表的插入或删除不需要移动其他元素，时间复杂度是O(1)。 数组的优点： 随机访问性比较强，可以通过下标进行快速定位。 查找速度快 数组缺点： 插入和删除的效率低，需要移动其他元素。 会造成内存的浪费，因为内存是连续的，所以在申请数组的时候就必须规定七内存的大小，如果不合适，就会造成内存的浪费。 内存空间要求高，创建一个数组，必...

冒泡排序 void maopao(int *a,int n){ if(n==1)return; for(int i=1;i<n;i++)if(a[i]>a[i+1])swap(a[i],a[i+1]); maopao(a,n-1); }复杂度 插入排序 每次将插入到区间里。 void insort(int *a,int n,int d){ for(int i=d+1,j;i<=n;i++){ if(a[i]>=a[i-d])continue; int r=a[i]; for(j=i-d;...

Codeforces Round #629 (Div. 3) A.Divisibility Problem #include<bits/stdc++.h> using namespace std; #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define pr printf #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout)...

牛客小白月赛23 A.膜法记录 二进制枚举行的状态，可以只枚举二进制1个数为a的状态。 #include<bits/stdc++.h> using namespace std; int main(){ int t;cin>>t; while(t--){ int n,m,a,b; scanf("%d%d%d%d",&n,&m,&a,&b); string s[n]; for(int i=0;i<n;i++)cin>>s[i]; ...

Bag of mice A,B两人轮流抽取卡片，有n张中奖的，m张无奖的，A,B抽取完后卡片丢弃，但是B还可以在抽取一张丢弃(即使是中奖的也丢弃)，一方取到中奖游戏结束。 A,B的情况倒推过去就行。 #include<bits/stdc++.h> using namespace std; #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define pr printf #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",...

Educational Codeforces Round 84 A. Sum of Odd Integers for i in range (int(input())): n,k=map(int,input().split()) if k*k<=n and (n-k*k)%2==0: print("YES") else: print("NO")B. Princesses and Princes #include<bits/stdc++.h> using namespace std...