sunstrikes / algorithm Goto Github PK

View Code? Open in Web Editor NEW

24.0 24.0 62.0 24.85 MB

ml & dl & kaggle

C++ 0.07% Python 0.18% Makefile 0.01% MATLAB 0.58% Jupyter Notebook 99.18%

deep-learning kaggle machine-learning python tensorflow

algorithm's Introduction

Let's write some code! 🎉🎉🎉

🏗️ Working at @Baidu.Inc
🏡 Living at Beijing
🧐 Try to find it out.

algorithm's People

Contributors

Stargazers

Watchers

Forkers

zhuguangxiang qimo00 skylerwang123 xhufdd fangjyshanghai zoeyqeexo xhqkatrina hanhan1007 jevenzh ajpatrickzhang beichenyibei thematri iefnxtdm andyeexx zaneguqi tianyibing apseele

algorithm's Issues

递归：棋盘分割问题

问题：8*8的棋盘缺个角，问，如何用L型的地板砖铺满。

def cover(board, lab=1, top=0, left=0, side=None):
    if side is None: side = len(board)
    s = side // 2
    offsets = (0,-1), (side-1,0)
    #outer 用来检测哪个角上缺了个
    #inner 用来把棋盘分割为4个子问题
    for dy_outer, dy_inner in offsets:
        for dx_outer, dx_inner in offsets:
            if not board[top+dy_outer][left+dx_outer]:
                board[top+dy_inner+s][left+dx_inner+s] = lab

    lab += 1
    if s > 1:
        for dy in [0,s]:
            for dx in [0,s]:
                lab = cover(board, lab, top+dy, left+dx, s)
    return lab
board = [[0]*8 for i in range(8)]
board[7][7] = -1
cover(board)
for row in board:
    print((" %2i"*8)% tuple(row))

result：

  3  3  4  4  8  8  9  9
  3  2  2  4  8  7  7  9
  5  2  6  6 10 10  7 11
  5  5  6  1  1 10 11 11
 13 13 14  1 18 18 19 19
 13 12 14 14 18 17 17 19
 15 12 12 16 20 17 21 21
 15 15 16 16 20 20 21 -1

1268 九宫 DFS

描述
小Hi最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

pic1.png

有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小Hi准备将一个三阶幻方（不一定是上图中的那个）中的一些数组抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一组解。

而你呢，也被小Hi交付了同样的任务，但是不同的是，你需要写一个程序~

输入
输入仅包含单组测试数据。

每组测试数据为一个3*3的矩阵，其中为0的部分表示被小Hi抹去的部分。

对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。

输出
如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）。

样例输入
0 7 2
0 5 0
0 3 0
样例输出
6 7 2
1 5 9
8 3 4

#include <iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i,s,t) for(int i=int(s); i<int(t); i++)
#define mst(A,k) memset(A,k,sizeof(A))
int a[10];
int vis[10];
int total = 0;
bool judge()
{
        int sum=a[1]+a[2]+a[3];
        for(int i=4;i<=9;i+=3)
                if((a[i]+a[i+1]+a[i+2])!=sum)
                        return false;
        for(int i=1;i<=3;i++)
                if((a[i]+a[i+3]+a[i+6])!=sum)
                return false;
        if((a[1]+a[5]+a[9])!=sum||(a[3]+a[5]+a[7])!=sum)
                return false;
        return true;
}
int res[10];
void dfs(int pos){
    if(pos == 10){
        if(judge()){
            total++;
            if(total==1)
                memcpy(res,a,sizeof(a));
            return;
        }
    }else{
        if(a[pos]) dfs(pos+1);
        else{
            for(int i = 1;i<10;i++){
                if(vis[i]) continue;
                vis[i] = 1;
                a[pos] = i;
                dfs(pos+1);
                a[pos] = 0;
                vis[i] = 0;
            }
        }
    }
}
int main()
{
    memset(vis,0,sizeof(vis));
    for(int i = 1;i<10;i++){
        cin>>a[i];
        if(a[i]) vis[a[i]] = 1;
    }
    dfs(1);

    if(total==1){
        for(int i = 1;i<10;i+=3){
            cout<<res[i]<<" "<<res[i+1]<<" "<<res[i+2]<<endl;
        }
    }else if(total>1)
        cout<<"Too Many"<<endl;
    return 0;
}

网易游戏2016实习生招聘笔试题目--推箱子

题目1 : 推箱子
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
推箱子是一款经典游戏。如图所示，灰色格子代表不能通过区域，蓝色方格是箱子，黑色圆形代表玩家，含有圆点的格子代表目标点。

push.png

规定以下规则：

1、一局游戏中只会有一个箱子，一个玩家和一个目标点。

2、通过方向键控制玩家移动。

3、图中的灰色格子代表墙壁，玩家与箱子都不能通过。

4、推到墙壁的箱子，就无法再将箱子推离墙壁，因为玩家无法到达箱子靠墙壁的一侧去推箱子。也就是说箱子只能以“被推”的方式被移动，不是以“被拉”的方式被移动。但如果玩家将箱子推至墙壁后，垂直墙壁的两侧没有阻碍物，则玩家可以朝这两个不同的方向推移箱子。如果箱子进入角落，就没有办法再推动这个箱子了。

5、玩家是不能走出场景的。玩家推着箱子到达场景边缘，如果继续点击使玩家和箱子向墙壁前进的方向键，箱子和人都会保持不动。玩家的前进方向上如果有墙壁，也是不能前进的。但是这些点击都视为合理的输入。

6、箱子一旦到达目标点，就不能再移动了。但这时，玩家仍然可以在场景内自由行动。如果继续尝试推箱子，那么玩家将会和箱子一起保持在原地不动。

现在，给出一种方向键的点击方案，请判断，这种方案是否能使箱子最终停在目标点上。为了方便表示，我们以0代表空白格子，以4代表不能通过区域，以1代表玩家，以3代表箱子，以2代表目标点。

输入
第一行数据包含三个整数，N，M，S。其中，N(0 < N <= 100)代表格子的宽度，M(0 < M <= 100)代表格子的高度，S(0 < S <= 200)代表测试点的个数。

接下来的M行，每行都会有N个字符，描述当前的盘面。

接下来的S行，每行都代表一个测试点。每行都以一个整数T(0 < T <= 10000)开头，接下来是一个空格和T个字符。这T个字符仅由d，u，l，r这四个字母组成，分别代表了敲击向下，向上，向左，向右的方向键。

输出
对于每个测试点，输出最后箱子是否在目标点上。如果是，输出YES，如果不是，则输出NO。

样例输入
5 4 3
00000
13000
00200
00000
4 rurd
6 urdldr
6 rrrurd
样例输出
YES
YES
NO

模拟...

#include <iostream>
#include"math.h"
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<numeric>
#include<set>
#include<map>
#include<cstring>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
#define rep(i,s,t) for(int i=int(s); i<int(t); i++)
#define mst(A,k) memset(A,k,sizeof(A))
struct point {
    int x, y;
};

point push(char x) {
    point a;
    switch (x) {
    case 'r': {a.x = 0; a.y = 1; break; }
    case 'l': {a.x = 0; a.y = -1; break; }
    case 'u': {a.x = -1; a.y = 0; break; }
    case 'd': {a.x = 1; a.y = 0; break; }
    }
    return a;
}
int n, m, s;
char d[105][105];
char a[105][105];
bool judge(int way, string &s) {
    bool flag = false;
    int x1, y1;
    int x2, y2;
    int x3, y3;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = a[i][j];
            if (d[i][j] == '1') {
                x1 = i; y1 = j;
            }
        }
    }
    for (int i = 0; i < s.size(); i++) {
        point o = push(s[i]);
        x2 = o.x + x1;
        y2 = o.y + y1;
        if (d[x2][y2] == '0') {
            d[x2][y2] = '1';
            d[x1][y1] = '0';
            x1 = x2; y1 = y2;
            continue;
        }
        else if (x2 <= 0 || x2>m || y2 <= 0 || y2>n || d[x2][y2] == '4') {
            continue;
        }
        else if (d[x2][y2] == '3') {
            x3 = x2 + o.x;
            y3 = y2 + o.y;
            if (d[x3][y3] == '0') {
                d[x3][y3] = '3';
                d[x2][y2] = '1';
                d[x1][y1] = '0';
                x1 = x2; y1 = y2;
            }
            else if (d[x3][y3] == '2') {
                flag = true;
                return flag;
            }
            else {
                continue;
            }
        }
    }
    return flag;
}
int main()
{
    //freopen("s.txt", "r", stdin);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char tmpp;
            cin >> tmpp;
            d[i][j] = tmpp;
            a[i][j] = d[i][j];
        }
    }
    for (int i = 0; i < s; i++) {
        int way;
        string strr;
        cin >> way >> strr;
        if (judge(way, strr))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

红黑树复习...写一遍好累..

首先是node:

struct node {
    int value;
    int color;//red 0 , black 1
    node * left;
    node * right;
    node* parent;
    node(int val) {
        value = val;
        left = right = parent = NULL;
    }
};
const int red = 0;
const int black = 1;

类声明:

#include"node.h"
class RBTree {
    /*
    I、红黑树的五个性质：
    1）每个结点要么是红的，要么是黑的。
    2）根结点是黑的。
    3）每个叶结点，即空结点（NIL）是黑的。
    4）如果一个结点是红的，那么它的俩个儿子都是黑的。
    5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
    */
private:
    node * root;
    void rotate_left(node* target);
    void rotate_right(node* target);
    node* successor(node* target);
    void insertAdjust(node* target);
    void removeAdjust(node* target);
public:
    RBTree();
    ~RBTree();
    node* insert(node* parent, int data);
    bool remove(node* parent, int data);
    node* search(node* root, int data);
};

方法实现:
1.左右旋转

void RBTree::rotate_left(node * target)
{
    node* right = target->right;
    node* parent = target->parent;
    if (parent!=NULL)
    {
        right->parent = parent;
        if (parent->right == target)
            parent->right = right;
        else
            parent->left = right;
    }
    node* move = right->left;
    right->parent = target->parent;
    target->parent = right;
    right->left = target;
    if (move!=NULL)
    {
        target->right = move;
        move->parent = target;
    }
    if (target == root)
    {
        root = right;
    }
}

void RBTree::rotate_right(node * target)
{
    node* left = target->left;
    node* parent = target->parent;
    if (parent != NULL) {
        left->parent = parent;//把left挂到parent下
        if (parent->left == target)
            parent->left = left;
        else
            parent->right = left;
    }
    node* move = left->right;
    left->parent = target->parent;//parent is null
    target->parent= left;
    left->right = target;
    if (move != NULL) {
        target->left = move;
        move->parent = target;
    }
    if (target == root)//旋转的是根节点的情况
        root = left;
}

2.查找后继节点:

node * RBTree::successor(node * target)
{
    node* tmp = target;
    if (target->right != NULL) {//case1 当target节点有右孩子时，返回右子树中最小的节点，即7节点
        tmp = target->right;
        while (tmp->left != NULL)
            tmp = tmp->left;
        return tmp;
    }
    while (tmp->parent!=NULL&&tmp==tmp->parent->right)
    {//case 2 当左子树为空时，可以理解为比7节点 小的，但是小节点中最大的节点，这个节点就应该是7节点的             左子树中最大的节点，即6节点。
        tmp = tmp->parent;
    }
    return tmp->parent;
}

3.插入与插入调整


node * RBTree::insert(node * parent, int data)
{
    if (parent->value > data) {
        if (parent->left == NULL) {
            node* res = new node(data);
            res->parent = parent;
            parent->left = res;
            res->color = red;
            insertAdjust(res);
            return res;
        }
        else
            return insert(parent->left, data);
    }
    else {
        if (parent->right == NULL) {
            node* res = new node(data);
            res->parent = parent;
            parent->right = res;
            res->color = red;
            insertAdjust(res);
            return res;
        }
        else {
            return insert(parent->right, data);
        }
    }
}

void RBTree::insertAdjust(node * target)
{
    node* tmp = target;
    while (tmp != NULL&&tmp != root&&tmp->parent->color == red) {
        //父节点为红
        node* parent = tmp->parent;
        node* grand = parent->parent;
        if (parent == grand->left) //case1
        {
            node* uncle = grand->left;
            if (uncle&&uncle->color == red) {
                grand->color = red;
                parent->color = black;
                uncle->color = black;
                tmp = grand;//观察爷节点
            }
            else {
                if (tmp == parent->right) {//case2
                    tmp = tmp->parent;
                    rotate_left(tmp);
                }
                tmp->parent->color = black;//case3
                tmp->parent->parent->color = red;
                rotate_right(tmp->parent->parent);
            }
        }
        else//反方向
        {
            node* uncle = grand->left;
            if (uncle&&uncle->color == red) {
                grand->color = red;
                parent->color = black;
                uncle->color = black;
                tmp = grand;
            }
            else {
                if (tmp == parent->left) {
                    tmp = tmp->parent;
                    rotate_right(tmp);
                }
                tmp->parent->color = black;
                tmp->parent->parent->color = red;
                rotate_left(tmp->parent->parent);
            }
        }
        root->color = black;
    }
}

4.删除与删除调整

void RBTree::removeAdjust(node * tar)
{
    node* other;//w
    node* parent = tar->parent;
    while ((!tar || tar->color == black) && tar != root)
    {
        if (parent->left == tar) {
            other = parent->right;
            if (other->color == red) {
                //case1 : x的兄弟w是红的
                other->color = black;
                parent->color = red;
                rotate_left(parent);
                other = parent->right;
            }
            if ((!other->left || other->left->color == black) &&
                (!other->right || other->right->color == black))
            { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 
                other->color = red;
                tar = parent;
                parent = tar->parent;
            }
            else {
                if (!other->right || other->right->color == black) {
                    // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。  
                    other->left->color = black;
                    other->color = red;
                    rotate_right(other);
                    other = parent->right;
                }
                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                other->color = parent->color;
                parent->color = black;
                other->right->color = black;
                rotate_left(parent);
                tar = root;
                break;
            }
        }
        else {
            other = parent->left;
            if (other->color == red) {
                //case1 : x的兄弟w是红的
                other->color = black;
                parent->color = red;
                rotate_right(parent);
                other = parent->left;
            }
            if ((!other->left || other->left->color == black) &&
                (!other->right || other->right->color == black))
            { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 
                other->color = red;
                tar = parent;
                parent = tar->parent;
            }
            else {
                if (!other->left || other->left->color == black) {
                    // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。  
                    other->right->color = black;
                    other->color = red;
                    rotate_left(other);
                    other = parent->left;
                }
                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                other->color = parent->color;
                parent->color = black;
                other->left->color = black;
                rotate_right(parent);
                tar = root;
                break;
            }
        }
    }
    if (tar)
        tar->color = black;
}

bool RBTree::remove(node * root, int data)
{
    node* del = search(root,data);
    node* child;
    node* parent;
    if (!del) {//找不到的情况
        return false;
    }
    if (del->left != NULL && del->right != NULL) {
        node* replace = del;//用来代替被删节点,即后继节点
        replace = replace->right;
        while (replace->left != NULL) {
            replace = replace->left;
        }
        if (del->parent) {
            //不是根节点
            if (del->parent->left == del)
                del->parent->left = replace;
            else
                del->parent->right = replace;
        }
        else
            root = replace;

        //child 是 取代节点右孩子
        child = replace->right;
        parent = replace->parent;
        int color = replace->color;
        if (parent == del)
            parent = replace;//是后继节点的父节点
        else {
            if (child)//删掉后继节点的处理
                child->parent = parent;
            parent->left = child;

            replace->right = del->right;//设好del的右子树
            del->right->parent = replace;
        }

        replace->parent = del->parent;
        replace->color = del->color;
        replace->left = del->left;
        del->left->parent = replace;

        if (color == black)
            removeAdjust(child);
        delete del;
    }

    //只有一个子树的情况
    if (del->left != NULL)
        child = del->left;
    else
        child = del->right;

    parent = del->parent;
    int color = del->color;
    if (child)
        child->parent = parent;
    if (parent) {
        if (parent->left == del)
            parent->left = child;
        else
            parent->right = child;
    }
    else
        root = child;
    //如果y不是黑色，是红色的，则当y被删除时，红黑性质仍然得以保持。不做操作，返回。

    //因为：1.树种各结点的黑高度都没有变化。2.不存在俩个相邻的红色结点。

    //3.因为入宫y是红色的，就不可能是根。所以，根仍然是黑色的。
    if (color == black)
        removeAdjust(child);
    delete del;
    return true;
}

5.查找:

node * RBTree::search(node * root, int data)
{
    node* tmp = root;
    while (tmp != NULL) {
        if (data < tmp->value) {
            tmp = tmp->left;
        }
        else if (data > tmp->value)
        {
            tmp = tmp->right;
        }
        else
            break;
    }
    return tmp;
}

Best Compression Algorithms 模拟..栈

小Y是一名负责处理文字信息的易信工程师，每天他都要和字符串打交道。为了提高存储和传输效率，小Y在课余时间经常会去研究字符串的存储方法。通过内部使用的一种统一的加密算法，所有的文字信息首先都会被转化成只包含大写字母['A'...'Z']的字符串。为了压缩这个加密后的字符串，小Y最近想出了两个存储的规则：

(1)如果字符串中有连续相同的大写字母，它们可以选择用"字符+出现次数"的方式替代。如字符串'AABCCCCDD'，可以用'A2BC4D2'表示，也可以用'A2BC2C2DD'表示。

(2)如果字符串中有连续出现的模式串(模式串长度大于1)，它们可以选择用"(模式)+出现次数"的方式替代。如字符串'FABCABCABCE'，可以用'F(ABC)3E'表示，也可以用'F(ABC)2ABCE'表示。

上述规则中的"连续"均指出现次数大于1，规则(2)中的括号后一定是一个大于1的数值，代表出现次数。

综合上述两个规则，字符串'AABAABFAABAABFG'可以用'((A2B)2F)2G'表示。小Y保证输出的压缩串符合上述的两个规则，以下类型的非法字符串不会出现：

'(A)5': 括号冗余

'A1A4': 数字1冗余

'A((AA))2': 括号冗余

(ABC)1: 括号和数字1冗余

对于给定的一个用上述规则压缩后的字符串，对应的原串是唯一的。小Y想知道这个字符串原来的长度是多少，以此计算压缩倍率。你能帮助他吗？

输入
第一行是整数T(T <= 100)，表示下面有T组数据。之后T行，每行为一组数据，每组数据为一个字符串。

每个字符串只会包含26个大写字母['A'...'Z']，数字['0'...'9']和左右括号['(', ')']。

保证输入数据一定合法，括号内的模式串长度一定大于1，表示出现次数的数字一定大于1，且字符串长度L <= 100。

输出
输出T行，每行对应一个数据的输出结果，表示字符串的实际长度。

保证每个字符串展开后的长度不超过109。

样例输入
4
(AA)2A
((A2B)2)2G
WANGYI
A2BC4D2
样例输出
5
13
6
9

遇到左括号把当前k入栈
遇到右括号先算括号里的,再把出栈的加上
遇到字母,下一位是数字的话直接加..

#include <iostream>
#include"math.h"
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iterator>
#include<sstream>
#include<numeric>
#include<set>
#include<map>
#include<cstring>
#include<stack>
using namespace std;
typedef long long ll;
#define rep(i,s,t) for(int i=int(s); i<int(t); i++)
#define mst(A,k) memset(A,k,sizeof(A))
inline bool isdigit(char c) {
    return  c >= '0' && c <= '9';
}
inline bool isalpha(char c) {
    return (c >= 'A'&&c <= 'Z') || (c >= 'a'&&c <= 'z');
}
int main()
{
    freopen("s.txt","r",stdin);
    int n;
    cin >> n;
    string s;
    while (n--) {
        cin >> s;
        stack<ll> st;
        ll k = 0;
        int i = 0;
        while(i<s.size()){
            if (isalpha(s[i])) {
                if (i < s.size() - 1 && isdigit(s[i + 1])) {//处理单个的
                    i++;
                    ll  count = 0;
                    while (i < s.size()&&isdigit(s[i])) {
                        count += count * 10 + s[i] - '0';
                        i++;
                    }
                    k += count;
                }
                else {
                    k++;
                    i++;
                }
            }
            else if (s[i] == '(') {
                st.push(k);
                k = 0;
                i++;
            }
            else if(s[i] ==')' ){
                ll count = 0;
                i++;
                while (i < s.size() && isdigit(s[i])) {
                    count = count * 10 + s[i] - '0';
                    i++;
                }
                ll tmp = st.top();
                st.pop();
                k = k * count + tmp;
            }

        }
        cout << k << endl;
    }
    return 0;
}

Battle to the West (乱斗西游) is a MOBA(multiplayer online battle arena) mobile game developed by Netease Games. It has grown fast in popularity since the release at Oct 2014. And for its high quality and popularity, it was named “AppStore Best of 2014” by Apple.

ldxy-s1.jpgldxy-s2.jpgldxy-s3.jpgldxy-s4.jpg

The 3v3 mode is a new PvP mode in Battle to the West. In this mode, a player needs to choose a hero to play first. And then all online players are randomly grouped in sixes. Each group has exactly 6 players and corresponds to a new game. In the new game, the 6 players are further randomly divided into 2 opposing teams, each of which has 3 players.

To make the gameplay fair and fun, no two players choosing the same hero should appear in a single team. As a developer of this game, you may design the way of grouping all online players, and the way of dividing players into teams. Then a problem arises. What is the maximum number of games (or groups) that could possibly be generated from online players satisfying all above constraints?

To make the problem clear, we assume that there are H distinct heroes, named from hero1 to heroH. A player must choose exactly one from the H heroes. The number of players choosing heroi is ai. Given H and ai, you need to write a program to find the maximum number of games that could be grouped by these players.

输入
The input contains several test cases.

The first line contains T(T ≤ 100), the number of the test cases.

The following T lines each start with an integer H(1 ≤ H ≤ 1000), which is the number of possible choices for hero. Then H integers (a1 … aH) follow, where ai (ai > 0) is the number of players who choose the i-th hero. It is guaranteed that the sum of ai will no more than 200000.

输出
For each test case, please output the maximum number of games that could be grouped by the players.

提示
For the 1st test case, there are 6 online players choosing 6 different heroes. So 1 game can be formed.

For the 2nd test case, we can divide the 6 heroes into 2 teams: (1, 2, 3) and (1, 2, 3). So no 2 heroes appear in a single team, and 1 game can be formed.

There are 7 players in the 3rd test case, but a game has exactly 6 players. The extra player is in no team.

For the 4th test case, there are 3 players choosing the hero3. So no game could be formed.

样例输入
4
6 1 1 1 1 1 1
3 2 2 2
3 2 2 3
3 1 2 3
样例输出
1
1
1
0


struct classcomp {
    bool operator() (const int& lhs, const int& rhs) const
    {
        return lhs>rhs;
    }
};
int hero[1006];
int a[3];
int main()
{
    freopen("s.txt","r",stdin);
    int n;
    cin >> n;
    int h;
    while (n--) {
        cin >> h;
        for (int i = 0; i < h; i++) {
            cin >> hero[i];
        }
        multiset<int, classcomp> s(hero,hero+h);
        int sum = 0;
        int tmp = 0;
        bool flag ;
        while (!s.empty()) {
            tmp++;
            flag = true;
            for(int i = 0;i<3;i++){
                if(!s.empty()){
                    a[i] = *s.begin();
                    s.erase(s.begin());
                }else{
                    flag = false;
                    break;
                }
            }
            if(flag){
                for(int i =0 ;i<3;i++){
                    if(a[i]-1>0){
                        s.insert(a[i]-1);
                    }
                }
                sum++;
            }
        }
        cout << sum/2 << endl;
    }
    return 0;
}

1269 优化延迟优先队列+二分

#1269 : 优化延迟

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho编写了一个处理数据包的程序。程序的输入是一个包含N个数据包的序列。每个数据包根据其重要程度不同，具有不同的"延迟惩罚值"。序列中的第i个数据包的"延迟惩罚值"是Pi。如果N个数据包按照<Pi1, Pi2, ... PiN>的顺序被处理，那么总延迟惩罚

SP=1_Pi1+2_Pi2+3_Pi3+...+N_PiN（其中i1, i2, ... iN是1, 2, 3, ... N的一个排列)。

小Ho的程序会依次处理每一个数据包，这时N个数据包的总延迟惩罚值SP为

1_P1+2_P2+3_P3+...+i_Pi+...+N*PN。

小Hi希望可以降低总延迟惩罚值。他的做法是在小Ho的程序中增加一个大小为K的缓冲区。N个数据包在被处理前会依次进入缓冲区。当缓冲区满的时候会将当前缓冲区内"延迟惩罚值"最大的数据包移出缓冲区并进行处理。直到没有新的数据包进入缓冲区时，缓冲区内剩余的数据包会按照"延迟惩罚值"从大到小的顺序被依次移出并进行处理。

例如，当数据包的"延迟惩罚值"依次是<5, 3, 1, 2, 4>，缓冲区大小K=2时，数据包被处理的顺序是：<5, 3, 2, 4, 1>。这时SP=1_5+2_3+3_2+4_4+5*1=38。

现在给定输入的数据包序列，以及一个总延迟惩罚阈值Q。小Hi想知道如果要SP<=Q，缓冲区的大小最小是多少？

输入
Line 1: N Q

Line 2: P1 P2 ... PN

对于50%的数据： 1 <= N <= 1000

对于100%的数据： 1 <= N <= 100000, 0 <= Pi <= 1000, 1 <= Q <= 1013

输出
输出最小的正整数K值能满足SP<=Q。如果没有符合条件的K，输出-1。

样例输入
5 38
5 3 1 2 4
样例输出
2

没想到二分法...遇到这种题先暴力啊..一直想没作用的!

#include <iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<queue>
#define rep(i,s,t) for(int i=int(s); i<int(t); i++)
#define mst(A,k) memset(A,k,sizeof(A))
using namespace std;
typedef long long ll;
priority_queue<int> pq;
int a[100005];

    int n,p;
    ll q;
ll sum(int depth){
    ll res = 0;        int len =1;
    for(int i = 0;i<n;i++){
        if(i<depth){
            pq.push(a[i]);
        }else{
            int tmp = pq.top();
            pq.pop();
            res+=tmp*len;
            len++;
            pq.push(a[i]);
        }
    }
    while(pq.size()){
            int tmp = pq.top();
            pq.pop();
            res+=tmp*len;
            len++;
    }
    return res;
}
int main()
{
    memset(a,0,sizeof(a));
    cin>>n>>q;
    for(int i = 0;i<n;i++){
        cin>>a[i];
    }
    ll res = 999999999;
    ll left = 1;
    ll right = n;
    ll mid;
    while(left<=right){
        mid = (left+right+1)/2;
        ll ddd = sum(mid);
        //cout<<mid<<" "<<ddd<<endl;
        if(ddd<=q){
            res = min(mid,res);
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    if(sum(res)<=q)
        cout<<res<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

1270 : 建造基地完全背包

#1270 : 建造基地

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在遥远的未来，小Hi成为了地球联邦外空间联合开发工作组的一员，前往一颗新发现的星球开发当地的重金属资源。

为了能够在当地生存下来，小Hi首先要建立一个基地。建立基地的材料可以直接使用当地的石材和富裕的重金属资源。基地建设分为N级，每一级都需要达成K的建设值后才能够完成建设，当前级别的建设值溢出后不会影响到下一级的建设。

小Hi可以产出的重金属资源按照精炼程度分为M级，根据开采的数量和精炼的工艺，可以将获取精炼程度为第i级的重金属资源的成本量化为Ai。

在建设第1级基地时，一块精炼度为i的重金属可以提供Bi的建设值，此后基地的级别每提高一级，建设值将除以T并下取整(整除)。

现给定N、M、K、T、A[]和B[]，小Hi需要你帮助他计算他完成基地建设的最小成本。

输入
输入包含多组测试数据。

输入的第一行为一个整数Q，表示测试数据的组数。

每组测试数据的第一行为4个整数N、M、K和T，意义如前文所述。

接下来的一行为M个整数，分别表示A1~AM。

接下来的一行为M个整数，分别表示B1~BM。

对于100%的数据，满足1<=N<=10，1<=M<=100，1<=K,T<=104

对于100%的数据，满足Ai和Bi均为32位整型范围内的正整数

对于100%的数据，满足1<=Q<=10

输出
对于每组测试数据，如果小Hi最终能够完成基地建设，则输出小Hi完成基地建设所需要的最小成本，否则输出“No Answer”。

样例输入
2
2 2 2 2
1 3
1 2
2 2 2 2
1 2
1 1
样例输出
8
No Answer

妈个鸡..卡在dp取的范围上...无语了

#include <iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<queue>
#define rep(i,s,t) for(int i=int(s); i<int(t); i++)
#define mst(A,k) memset(A,k,sizeof(A))
using namespace std;
typedef long long ll;
int const INF = (1 << 30);
int n,m,k,t;
struct food{
    int a,b;
}f[105];

ll dp[10005];//1.dp 范围问题 
int main()
{
    //freopen("s.txt","r",stdin);
    int q;
    cin>>q;
    ll sum = 0;
    while(q--){
        scanf("%d %d %d %d", &n, &m, &k, &t);
        for(int i = 0;i<m;i++){
            scanf("%d", &f[i].a);
        }
        for(int i = 0;i<m;i++){
            scanf("%d", &f[i].b);
        }
         bool flag=true;
         sum = 0;
        for(int i = 1;i<=n;i++){//每一层
            for(int j = 0;j<=10005;j++){
                dp[j] = INF;
            }
            dp[0] = 0;
            ll cur = INF;
            flag = true;
            for(int j =0;j<m;j++){
                for(int l= 0;l<=k;l++){
                    if(f[j].b+l>k)
                        cur = min(cur,dp[l]+f[j].a);
                    else
                        dp[f[j].b+l] = min(dp[f[j].b+l],dp[l]+f[j].a);
                }
            }

            cur = min(cur,dp[k]);//不一定正好在dp[k]处取得最小值,一定注意
            if(cur==INF){
                flag = false;
                printf("No Answer\n");
                break;
            }
            sum+=cur;
            for(int j =0;j<m;j++){
                f[j].b/=t;
            }
        }
        if(flag)
            printf("%lld\n", sum);
    }
    return 0;
}

DFS+状态压缩

时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi实验室所在的建筑一楼有一个用于贴海报的黑板，不停的有新的海报往上贴，也会安排人员不断的对海报进行清理，而最近，轮到了小Hi去对海报进行清理。

黑板是一块W*H大小的区域，如果以左下角为直角坐标系的话，在上次清理后第i张贴上去的海报可以视作左下角为(X1i, Y1i)，右上角为(X2i, Y2i)的一个矩形。

撕去一张海报会导致所有覆盖在其上的海报都被同时撕掉（这样被称为连带，这个过程是具有传递性的，即如果A覆盖B，B覆盖C，那么撕掉C会导致A和B均被撕掉），但是一张海报想要被手动撕掉的话需要至少存在一个角没有被其他海报覆盖（海报A被海报B覆盖当且仅当他们存在面积大于0的交集并且A在B之前贴出，海报A的一个角被海报B覆盖当且仅当这个顶点处于海报B的内部）。

于是现在问题来了，为了节约时间，小Hi决定一次性撕掉尽可能多的海报，那么他应该选择哪张海报呢？在效果相同的情况下，小Hi倾向于选择更早贴出的海报。

输入
每个输入文件仅包含单组测试数据。

每组测试数据的第一行为三个正整数W，H和N，分别表示黑板的宽、高以及目前张贴出的海报数量。

接下来的N行，每行为四个正整数X1i、Y1i、X2i和Y2i，描述第i张贴出的海报。

对于20%的数据，满足1<=N<=5，1<=W,H<=10

对于100%的数据，满足1<=N<=1000，0<=X1i, X2i <= W, 0<=Y1i, Y2i<=H, 1<=W,H<=108

输出
对于每组测试数据，输出两个正整数Ans和K，表示小Hi一次最多能撕掉多少张海报，和他选择的海报是第几张贴出的。

样例输入
6 7 4
0 0 4 4
1 0 3 4
1 4 4 6
0 0 3 5
样例输出
3 1

这题都做不出来..感觉雪崩啊...

#include <iostream>
#include<cmath>
#include<cstdio>
#include<cstring>

#define rep(i,s,t) for(int i=int(s); i<int(t); i++)
#define mst(A,k) memset(A,k,sizeof(A))
#include<vector>
/*
DFS+状态压缩
*/
using namespace std;
typedef long long ll;
vector<int> st[1010];
struct Rect{
    int x1,y1,x2,y2;
    void init(int a,int b,int c,int d){
        x1 = a;
        y1 = b;
        x2 = c;
        y2 = d;
    }
}r[1010];
bool over(Rect a,Rect b){//是否两个矩形有交集
    int min_x,max_x,min_y,max_y;
    min_x = max(a.x1,b.x1);
    min_y = max(a.y1,b.y1);
    max_x = min(a.x2,b.x2);
    max_y = min(a.y2,b.y2);
    return min_x<max_x && min_y<max_y;
}
int state(int x,int y, Rect a){//检查点是不是在矩形内
    return (x>a.x1 && x<a.x2 && y>a.y1 && y<a.y2);
}
int can[1010];
int vis[1010];
int total;
void dfs(int x){
    vis[x] = 1;
    total++;
    for(int i = 0; i<st[x].size();i++){
        if(vis[st[x][i]] == 0)
            dfs(st[x][i]);
    }
}
int main()
{
    int w,h,n;
    while(cin>>w>>h>>n)
    {
        memset(can,0,sizeof(can));
        int x1,y1,x2,y2;
        for(int i = 0;i<n;i++){
            cin>>x1>>y1>>x2>>y2;
            r[i].init(x1,y1,x2,y2);
        }

        for(int i = 0 ;i<n;i++){
            for(int j = i+1;j<n;j++){
                if(state(r[i].x1,r[i].y1,r[j])) can[i]|=1;
                if(state(r[i].x1,r[i].y2,r[j])) can[i]|=2;
                if(state(r[i].x2,r[i].y1,r[j])) can[i]|=4;
                if(state(r[i].x2,r[i].y2,r[j])) can[i]|=8;
                if(over(r[i],r[j]))
                    st[i].push_back(j);
            }
        }
        int k = 0,ans = 0;
       for(int i = 0 ;i<n;i++){
           if(can[i]!=15){
               memset(vis,0,sizeof(vis));
               total = 0;
               dfs(i);
               if(total>ans){
                   ans = total;
                   k = i+1;
               }
           }
       }
       cout<<ans<<" "<<k<<endl;
    }
    return 0;
}

算法时间评估

算法评估：使用timeit模块评估，profiler找出瓶颈
timeit例：

import timeit
timeit.timeit("x = sum(range(10)")

profiler:

import cProfile
cProfile.run('main()')

用matplotlib库绘制结果