分类 算法 下的文章

1.在电脑上打开抢购疫苗.exe(可能会被爆病毒)
image.png
2.在微信端打开秒苗小程序
.36b36dab5cc8966e7dcabe42739d24b.png
3.使用Fidder抓取小程序的数据包1e252f0bb7f5f6b4132c9ba06281ead.png

4.
填写cookie和TKaf4d85c48b0f26cea24b21ca35c32d0.png

5.选择接种人2be3b7b4b91a0f81e1601fd9695b458.png
6.刷新疫苗列表ab1848518c0b54f291c58339731f0de.png
7.在秒杀开始前,点击开始,就可以挂着了。

b81629ad470e50946a527272813925a.png
需要注意的是:电脑时间应该和北京时间一致,
登录秒苗小程序的时间应该在秒杀前一小时内,否则COOKIE会失效

一.使用Fiddler等抓包工具抓取约苗小程序请求header

http://www.winwin7.com/soft/13111.html
网站下载Fiddler
抓取 tk ,cookie

use

  • hpv4g.py执行秒杀 -h可选参数

    • 位置参数(固定必传参数)

      • tk 抓包获取的tk数据
      • cookie 抓包获取的cookie数据
    • 可选参数

      • -mw[--max_workers] 最大秒杀线程数(默认使用min(32, cpu_count + 4))
      • -rc[--region_code] 指定区域编码(約苗使用4位行政区域CODE 默认成都:5101)
      • -reload_cache 当前城市所有可秒杀(即5S内可开始秒杀)疫苗一起秒杀。 因此秒杀前会缓存当前城市可秒杀疫苗列表到 cache/vaccines_xxx.json中。真正执行秒杀时从本地获取疫苗列表(减少受Server端降级策略影响)。 -reload_cache参数用于指定本次秒杀需要更新缓存列表(场景:第一天执行秒杀后缓存了数据,第二天再次秒杀时需要重新加载最新疫苗列表一次)
      • -sp[--single_point]只秒杀单个疫苗[即所有线程秒杀同一个疫苗] 默认不开启该参数则所有线程分配秒杀所有可秒杀疫苗
      • -pi[(--proxy_ip)] 开启IP代理池 默认不开启 测试发现使用IP代理池后 对服务端访问频率限制并没有太明显的效果(仍然大量的请求502、操作频繁...), 初步判断服务端是用 【帐号】 维度的限制(有条件可以使用多个微信帐号同时秒杀)
      • --log 日志级别 默认WARNING
  • cache/vaccines.json文件# tkstring cookiestring 为抓包得到的tk cookie scan_vaccine.py tkstring cookiestring
  • 如果是运行 从成都市金牛区妇幼保健院服务号中抢购
    命令:JiuJia jinniu --config=/path/to/your/config.yml
  • 如果是运行 从约苗中抢购
    命令:JiuJia yuemiao --config=/path/to/your/config.yml

  • tkstring cookiestring 为抓包得到的tk

  • cookie scan_vaccine.py tkstring cookiestring
  • 目前只能做到16线程同时抢购
  • 99932751-f9d72100-2d93-11eb-8840-1110e0be3136(1).png

【思考题】

6-1 用插入方法建堆

a) 当输入数组相同时,过程BUILD_MAX_HEAP和BUILD_MAX_HEAP'产生的堆是否总是一样的?是的给出证明;否则给出反例。


n = 9
A = <5 3 17 10 84 19 6 22 9>
BUILD_MAX_HEAP:84 22 19 10 3 17 6 5 9
BUILE_MAX_HEAP':84 22 19 17 10 5 6 3 9
b) 证明:最坏情况下,BUILD_MAX_HEAP'要用⊙(nlgn)时间来建成一个含n个元素的堆。

执行一次MAX_HEAP_INSERT最坏的时间为⊙(logn)。BUILD_MAX_HEAP'中执行了n次,因此复杂度为⊙(nlogn)

template<typename Type>
class CHeap{
private:
    Type *A;
    int heapSize;
    int length;
    inline int left(int x) { return x<<1; }
    inline int right(int x) { return x<<1|1; }
    inline int parent(int x) { return x>>1; }
public:
    CHeap(){}
    CHeap(Type B[],int n) {
        init(B,n);
    }
    void init(Type B[],int n) {
        A = B;
        length = n;
        heapSize = 0;
    }
    void heapSort() {
        buildMaxHeap();
        for (int i=length;i>=2;i--) {
            swap(A[1],A[i]);
            heapSize--;
            maxHeapify(1);
        }
    }
 
    void maxHeapify(int i) {
        int l = left(i);
        int r = right(i);
        int largest = i;
        if (l <= heapSize && A[l] > A[largest]) largest = l;
        if (r <= heapSize && A[r] > A[largest]) largest = r;
        if (largest != i) {
            swap(A[i],A[largest]);
            maxHeapify(largest);
        }
    }
    void maxHeapify_NonRecursive(int i) {
        while (true) {
            int l = left(i);
            int r = right(i);
            int largest = i;
            if (l <= heapSize && A[l] > A[largest]) largest = l;
            if (r <= heapSize && A[r] > A[largest]) largest = r;
            if (largest == i) break;
            swap(A[i],A[largest]);
            i = largest;
        }
    }
    void buildMaxHeap() {
        heapSize = length;
        for (int i=length/2;i>=1;i--) {
            maxHeapify(i);
        }
    }
    Type heapMaximum() {
        return A[1];
    }
    Type heapExtractMax() {
        if (heapSize < 1) return 0;
        int max = A[1];
        A[1] = A[heapSize--];
        maxHeapify(1);
        return max;
    }
    void heapIncreaseKey(int i,Type key) {
        if (key < A[i]) return;
        A[i] = key;
        while (i>1 && A[parent(i)] < A[i]) {
            swap(A[i],A[parent(i)]);
            i = parent(i);
        }
    }
    void maxHeapInsert(Type key) {
        heapSize++;
        A[heapSize] = key;
        heapIncreaseKey(heapSize,key);
    }
    void heapDeleteMax(int i) {
        if (i<1||i>heapSize) return;
        A[i] = A[heapSize--];
        maxHeapify(i);
    }
 
    void minHeapify(int i) {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l <= heapSize && A[l] < A[smallest]) smallest = l;
        if (r <= heapSize && A[r] < A[smallest]) smallest = r;
        if (smallest != i) {
            swap(A[i],A[smallest]);
            minHeapify(smallest);
        }
    }
    void minHeapify_NonRecursive(int i) {
        while (true) {
            int l = left(i);
            int r = right(i);
            int smallest = i;
            if (l <= heapSize && A[l] < A[smallest]) smallest = l;
            if (r <= heapSize && A[r] < A[smallest]) smallest = r;
            if (smallest == i) break;
            swap(A[i],A[smallest]);
            i = smallest;
        }
    }
    void buidMinHeap() {
        heapSize = length;
        for (int i=length/2;i>=1;i--) {
            minHeapify(i);
        }
    }
    Type heapMinimum() {
        return A[1];
    }
    Type heapExtractMin() {
        if (heapSize < 1) return 0;
        int min = A[1];
        A[1] = A[heapSize--];
        minHeapify(1);
        return min;
    }
    void heapDecreaseKey(int i,Type key) {
        if (key > A[i]) return;
        A[i] = key;
        while (i>1 && A[parent(i)] > A[i]) {
            swap(A[i],A[parent(i)]);
            i = parent(i);
        }
    }
    void minHeapInsert(Type key) {
        heapSize++;
        A[heapSize] = key;
        heapDecreaseKey(heapSize,key);
    }
    void heapDeleteMin(int i) {
        if (i<1||i>heapSize) return;
        A[i] = A[heapSize--];
        minHeapify(i);
    }
 };




6-2 对d叉堆的分析

a) 如何在一个数组中表示一个d叉堆?

A[(x-1)d+2]、A[(x-1)d+2+1]...A[(x-1)*d+2+k-1] 表示第i个结点的d叉堆第k个子结点。



b) 含n个元素的d叉堆的高度是多少?

c) 给出d叉堆的EXTRACT_MAX的一个有效实现,并用d和n表示出它的运行时间。

Type heapExtractMax() {<br />        if (heapSize < 1) return 0;<br />        int max = A[1];<br />        A[1] = A[heapSize--];<br />        maxHeapify(1);<br />        return max;<br />    }<br />​<br />

d) 给出d叉堆最大堆的INSERT的一个有效实现,并用d和n表示出它的运行时间。

void maxHeapInsert(Type key) {<br />        heapSize++;<br />        A[heapSize] = key;<br />        heapIncreaseKey(heapSize,key);<br />    }

e) 给出INCREASE_KEY(A,i,k)的一个有效实现,该过程首先执行A[i]=max(A[i],k),并相应地更新d叉最大堆的结构。请用d和n表示出它的运行时间。

void heapIncreaseKey(int i,Type key) {<br />        if (key > A[i]) A[i] = key;<br />        while (i>1 && A[parent(i)] < A[i]) {<br />            swap(A[i],A[parent(i)]);<br />            i = parent(i);<br />        }<br />    }<br />​<br />

d叉堆:

template <typename Type>
class CDHeap{
same:
private:
    Type *A;
    int d;
    int heapSize;
    int length;
    inline int son(int x,int k) { return (x-1)*d+2+k; }
    inline int parent(int x) { return (x-2)/d+1; }
public:
    CDHeap(){}
    CDHeap(Type B[],int n,int dd) {
        init(B,n,dd);
    }
    void init(Type B[],int n,int dd) {
        A = B;
        length = n;
        d = dd;
        heapSize = 0;
    }
    void maxHeapify(int x) {
        int largest = x;
        for (int i=0;i<d;i++) {
            int k = son(x,i);
            if (k <= heapSize && A[k] > A[largest]) largest = k;
        }
        if (largest != x) {
            swap(A[x],A[largest]);
            maxHeapify(largest);
        }
    }
    void buildMaxHeap() {
        heapSize = length;
        for (int i=length/d;i>=1;i--) {
            maxHeapify(i);
        }
    }
    Type heapMaximum() {
        return A[1];
    }
    Type heapExtractMax() {
        if (heapSize < 1) return 0;
        int max = A[1];
        A[1] = A[heapSize--];
        maxHeapify(1);
        return max;
    }
    void heapIncreaseKey(int i,Type key) {
        if (key > A[i]) A[i] = key;
        while (i>1 && A[parent(i)] < A[i]) {
            swap(A[i],A[parent(i)]);
            i = parent(i);
        }
    }
    void maxHeapInsert(Type key) {
        heapSize++;
        A[heapSize] = key;
        heapIncreaseKey(heapSize,key);
    }
    void heapSort() {
        buildMaxHeap();
        for (int i=length;i>=2;i--) {
            swap(A[1],A[i]);
            heapSize--;
            maxHeapify(1);
        }
    }
};

6-3 Young氏矩阵

a) 画一个包含元素{9,16,3,2,4,8,5,14,12}的4X4Young氏矩阵。

b) 讨论一个mXn的Young氏矩阵,如果Y[1,1]=OO,则Y为空;如果Y[m,n]<OO,则Y是满的(包含mXn个元素)。

1、当Y[1,1]=OO时,由Young氏矩阵的性质可知,A[1,1]右侧的元素 >= OO,下侧的元素 >= OO,因此A[1,1]的右侧和下侧均为OO。

对Y[1,2...n]做同样的分析,可知矩阵中所有元素均为OO,表示矩阵中不存在元素。

2、当Y[m,n]<OO时,由Young氏矩阵的性质可知,A[m,n]左侧和上侧元素 <= Am < OO。

对Y[m,1...n-1]做同样的分析,可知矩阵中所有元素均小于OO,矩阵中不存在空位置,所以矩阵是满的。

c) 给出一个在非空mXn的Young氏矩阵上实现EXTRACT_MIN的算法,使其运行时间为O(m+n)。

将存在于(1,1)中的最小元素取出。用OO代替,将OO与右边或下边更小的元素进行交换,直至到达正确的位置。

由于元素只能向右或向下移动,F(i,j) = F(i-1,j) or F(i,j-1)。
令p = n+m,,因此F(p) = F(p-1) + O(1),运行时间为O(m+n)。

    void extractYoungs(int x,int y) {
        int sx = x;
        int sy = y;
        if (x < n && matrix[x+1][y] < matrix[sx][sy]) {
            sx = x + 1;
            sy = y;
        }
        if (y < m && matrix[x][y+1] < matrix[sx][sy]) {
            sx = x;
            sy = y + 1;
        }
        if (sx != x || sy != y) {
            swap(matrix[x][y],matrix[sx][sy]);
            extractYoungs(sx,sy);
        }
    }
    int extractMin() {
        int ret = matrix[1][1];
        matrix[1][1] = INF;
        extractYoungs(1,1);
        return ret;
    }


d) 说明如何在O(m+n)的时间内,将一个新元素插入到一个未满的 mXn Young氏矩阵中。

将元素替换掉矩阵中最大的元素An,循环将其与左侧或上侧更大的元素交换,维护矩阵性质。

void insertYoungs(int x,int y) {
        int lx = x;
        int ly = y;
        if (x > 1 && matrix[x-1][y] > matrix[lx][ly] ) {
            lx = x - 1;
            ly = y;
        }
        if (y > 1 && matrix[x][y-1] > matrix[lx][ly]) {
            lx = x;
            ly = y - 1;
        }
        if (lx != x || ly != y) {
            swap(matrix[x][y],matrix[lx][ly]);
            insertYoungs(lx,ly);
        }
    }
    void insert(int x) {
        if (matrix[n][m]!=INF) return;
        matrix[n][m]=x;
        insertYoungs(n,m);
    }
<br />

e)在不用其他排序算法帮助的情况下,说明利用 nXn Young氏矩阵对n^2个数排序的运行时间为O(n^3)。

将n^2个数插入矩阵:O(n+n)*O(n^2) = O(n^3)

取出矩阵中的最小元素n^2次:O(n+n)*O(n^2) = O(n^3)

因此排序运行时间为 O(2*n^3) = O(n^3)



f) 给出一个运行时间为O(m+n)的算法,来决定一个给定的数是否存在于一个给定的 mXn Young氏矩阵内。


  pair<int,int> find(int c) {
        int x = 1,y = m;
        while (x <= n && y >= 1) {
            if (matrix[x][y] == c) return make_pair(x,y);
            if (matrix[x][y] < c) x++;
            if (matrix[x][y] > c) y--;
        }
        return make_pair(0,0);
    }




Young氏矩阵完整代码:


const int MAXN = 100;
const int INF = 0x3f3f3f3f;
class CYoungs{
private:
    int n,m;
    int matrix[MAXN][MAXN];
    void extractYoungs(int x,int y) {
        int sx = x;
        int sy = y;
        if (x < n && matrix[x+1][y] < matrix[sx][sy]) {
            sx = x + 1;
            sy = y;
        }
        if (y < m && matrix[x][y+1] < matrix[sx][sy]) {
            sx = x;
            sy = y + 1;
        }
        if (sx != x || sy != y) {
            swap(matrix[x][y],matrix[sx][sy]);
            extractYoungs(sx,sy);
        }
    }
    void insertYoungs(int x,int y) {
        int lx = x;
        int ly = y;
        if (x > 1 && matrix[x-1][y] > matrix[lx][ly] ) {
            lx = x - 1;
            ly = y;
        }
        if (y > 1 && matrix[x][y-1] > matrix[lx][ly]) {
            lx = x;
            ly = y - 1;
        }
        if (lx != x || ly != y) {
            swap(matrix[x][y],matrix[lx][ly]);
            insertYoungs(lx,ly);
        }
    }
public:
    CYoungs() {}
    void init(int a,int b) {
        n = a;
        m = b;
        memset(matrix,INF,sizeof matrix);
    }
    int extractMin() {
        int ret = matrix[1][1];
        matrix[1][1] = INF;
        extractYoungs(1,1);
        return ret;
    }
    void insert(int x) {
        if (matrix[n][m]!=INF) return;
        matrix[n][m]=x;
        insertYoungs(n,m);
    }
    pair<int,int> find(int c) {
        int x = 1,y = m;
        while (x <= n && y >= 1) {
            if (matrix[x][y] == c) return make_pair(x,y);
            if (matrix[x][y] < c) x++;
            if (matrix[x][y] > c) y--;
        }
        return make_pair(0,0);
    }
    void showMatrix() {
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                cout<<matrix[i][j]<<" ";
            }
            cout<<endl;
        }
    }
};



6.1 堆

最大堆:A[PARENT(i)]>=A[i]
最小堆:A[PARENT(i)]<=A[i]


6.2 维护堆的性质

void HeapAdjust(int H[],int s, int length)  
{  
    int tmp  = H[s];  
    int child = 2*s+1; //左孩子结点的位置。(i+1)为当前调整结点的右孩子结点的位置
    while (child < length) {  
        if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
            ++child ;  
        }  
        if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
            H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点  
            s = child;       // 重新设置s ,即待调整的下一个结点的位置  
            child = 2*s+1;  
        }  else {            // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出  
             break;  
        }  
        H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上
}  


6.3 建堆

void BuildingHeap(int H[], int length)  
{   
    //最后一个有孩子的节点的位置 i = (length -1) / 2  
    for (int i = (length -1) / 2 ; i >= 0; --i)  
        HeapAdjust(H,i,length);  
} 


6.4 堆排序

void HeapSort(int H[], int length)  
{  
    //初始堆  
    BuildingHeap(H, length);  
    //从最后一个元素开始对序列进行调整  
    for (int i = length - 1; i > 0; --i)  
    {  
        //交换堆顶元素H[0]和堆中最后一个元素  
        int temp = H[i]; H[i] = H[0]; H[0] = temp;  
        //每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整  
        HeapAdjust(H, 0, i);
     }  
} 

6.5 优先队列

HeapExtractMax:去掉并返回S中的具有最大键字的元素
int HeapExtractMax(int H[], int length)  
{
    if (length < 1)
        return -1;
    int max = H[0];
    H[0] = H[length-1]
    HeapAdjust(H, 0, length - 1)
    return max;
}

HeapIncreaseKey:将元素x的关键字值增加到key
void HeapIncreaseKey(int H[], int length, int i, int key)  
{
    if (key < H{i])
        return;
    H[i] = key
    while (i > 0 && H[(i-1)/2] < H[i]){
        H[i] = H[(i-1)/2];
        H[(i-1)/2] = key;
        i = (i-1)/2;
    }
}

MaxHeapInsert:将新元素x插入到集合S中
int[] MaxHeapInsert(int H[], int length, int key){
    int newH[] = new int[length + 1];
    for (int i  = 0; i <= length; i++)
        newH[i] = H[i];
    newH[length] = -1;
    length++;
    HeapIncreaseKey(H, length, length - 1, key);
}

贪 心

简单贪心

贪心法是求解一类最优化问题的方法,它总是考虑在当前状态下局部最优(或较优)的策略,来使全局的结果达到最优(或较优)。显然,如果采取较优而非最优的策略(最优策略可能不存在或是不易想到),得到的全局结果也无法是最优的。而要获得最优结果,则要求中间的每步策略都是最优的,因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法,即假设策略不能导致最优解,然后通过一系列系列推导来得到矛盾,以此证明策略是最优的,最后用数学归纳法保证全局最优。不过对平常使用来说,也许没有时间或不太容易对想到的策略进行严谨的证明(贪心的证明往往比贪心本身更难),因此一般来说, 如果在想到某个似乎可行的策略,并且自己无法举出反例,那么就勇敢地实现它。
PAT1024B

#include<iostream>
#include<algorithm>
using namespace std;
struct mooncake{
    double store;
    double sell;
    double price;
}cake[1010];
bool cmp(mooncake a,mooncake b){
    return a.price>b.price;
} 
int main(){
    int n;
    double D;
    scanf("%d%lf",&n,&D);
    for(int i=0;i<n;i++){
        scanf("%lf",&cake[i].store);
    }
    for(int i=0;i<n;i++){
        scanf("%lf",&cake[i].sell);
        cake[i].price=cake[i].sell/cake[i].store;
    }
    sort(cake,cake+n,cmp);
    double ans=0;
    for(int i=0;i<n;i++){
        if(cake[i].store<=D){
            D-=cake[i].store;
            ans+=cake[i].sell;
        }else{
            ans+=cake[i].price*D;
            break;
        }
    }
    printf("%.2f\n",ans);
    return 0;
}

区间贪心
区间不相交问题:给出N个开区间(x,y),从中选择尽可能多的开区间,使得这些开区间两两没有交集。
如果开区间i1被开区间i2包含,那么显然选择i1是最好的选择。所以总是选择左端最大的区间。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=110;
struct Inteval{
    int x,y;
}I[maxn];
bool cmp(Inteval a,Inteval b){
    if(a.x!=b.x) return a.x>b.x;
    else return a.y<b.y;
}
int main(){
    int n;
    while(scanf("%d",&n),n!=0){
        for(int i=0;i<n;i++){
            scanf("%d%d",&I[i].x,&I[i].y);
        }
        sort(I,I+n,cmp);
        int ans=1,lastX=I[0].x;
        for(int i=1;i<n;i++){
            if(I[i].y<=lastX){
                lastX=I[i].x;
                ans++; 
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

区间选点问题:给出N个闭区间[x,y],求最少需要确定多少个点,才能使没个闭区间中都至少存在一个点。例如对闭区间[1,4]、[2,6]、[5,7]来说,需要两个点才能保证每个闭区间都至少存在一个点。事实上,这个问题和区间不相交问题策略是一样的。

贪心是用来解决一类最优化问题,并希望由局部最优策略来推得全局最优结果的算法思想。贪心算法适用的问题一定满足最优子结构性质,即一个问题的最优解可以由它的子问题的最优解有效地构造出来。