POJ模拟题

选题来源：http://pythontip.sinaapp.com/acm/problemCategory

POJ1006

题目链接：http://poj.org/problem?id=1006

写循环就好，我每次加最大的天数，然后判断即可。

//#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
using namespace std;

int sd[3], d;

int day;

int days[3]={23, 28, 33};

int ans;

bool getdata()
{
    for(int i=0;i!=3;i++)
    {
        scanf("%d", &sd[i]);
    }
    scanf("%d", &d);
    return sd[0]!=-1;
}

bool judge()
{
    bool flag=1;
    if(day<=d)
    {
        flag=0;
    }
    else
    {
        for(int i=0;i!=3;i++)
        {
            if(day%days[i]!=sd[i])
            {
                flag=0;
                break;
            }
        }
    }
    return flag;
}

void calc()
{
    for(int i=0;i!=3;i++)
    {
        sd[i]%=days[i];
    }
    day = sd[2];
    while(!judge())
    {
        day+=days[2];
    }
}

int main()
{
    freopen("in.txt", "r", stdin);

    int cnt=0;
    while(getdata())
    {
        cnt++;
        calc();
        printf("Case %d: the next triple peak occurs in %d days.\n", cnt, day-d);
    }
    return 0;
}

POJ1008

题目链接：http://poj.org/problem?id=1008

emmm，一个365天制的，转成绝对天数，然后再换成260天制的就好。

注意月份，天数这40个英文单词，我是漏了一个一直wrong answer。。。

//#include<bits/stdc++.h>
#include<string.h>
#include<iostream>
#include<stdio.h>
using namespace std;

int n;

int day;

char month[10];

int year;

int absolute_day;

int month_number;

char Haab[20][10]=
{
    "pop", "no", "zip", "zotz", "tzec", "xul", "yoxkin", "mol",
    "chen", "yax", "zac", "ceh", "mac", "kankin", "muan", "pax", "koyab", "cumhu", "uayet"
};

char Tzolkin[20][10]=
{
"imix", "ik", "akbal", "kan", "chicchan",
"cimi","manik", "lamat", "muluk", "ok",
"chuen", "eb", "ben", "ix", "mem",
"cib", "caban", "eznab", "canac", "ahau"
};

void month2number()
{
    for(int i=0;i!=20;i++)
    {
        if(strcmp(month, Haab[i])==0)
        {
            month_number=i+1;
            break;
        }
    }
}
class Tzolkin_Day
{
    public:
        int day;
        int strday_number;
        int year;
        Tzolkin_Day(int absolute_day)
        {
            year=absolute_day/260;
            int t = absolute_day%260;
            day = t%13+1;
            strday_number = t%20;
        }   
};

int main()
{
    freopen("in.txt", "r", stdin);

    scanf("%d", &n);
    printf("%d\n", n);
    for(int i=0;i!=n;i++)
    {
        scanf("%d. %s %d", &day, month, &year);
        absolute_day=year*365;
        month2number();
        absolute_day+=(month_number-1)*20;
        absolute_day+=day;
        Tzolkin_Day td(absolute_day);
        printf("%d %s %d\n", td.day, Tzolkin[td.strday_number], td.year);
    }
    return 0;
}

POJ1013

题目链接：http://poj.org/problem?id=1013

基本思路是枚举每一枚硬币是假币，或轻或重，直到枚举到一次满足三个等式的时候就是答案了。

注意天平两边的硬币数量不固定，但是相等。

//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>

using namespace std;

int n;

const int buff_size = 12;

char a[3][buff_size], b[3][buff_size], c[3][buff_size];

int check(char k)
{
    int sum_a=0, sum_b=0;
    bool flag = true;
    for(int weight = -1;weight<=1;weight+=2)
    {
        flag = true;
        for(int i=0;i!=3;i++)
        {
            sum_a = 0;
            sum_b = 0;
            for(int j=0;j!=strlen(a[i]);j++)
            {
                sum_a+=(a[i][j]==k)*weight;
                sum_b+=(b[i][j]==k)*weight;
            }
            if(sum_a==sum_b)
            {
                if(strcmp(c[i], "even")!=0)
                {
                    flag = false;
                    break;
                }
            }
            if(sum_a>sum_b)
            {
                if(strcmp(c[i], "up")!=0)
                {
                    flag = false;
                    break;
                }
            }
            if(sum_a<sum_b)
            {
                if(strcmp(c[i], "down")!=0)
                {
                    flag = false;
                    break;
                }
            }
        }
        if(flag)
            return weight==-1? 0 : 1;
    }
    return -1;
}

int main()
{
//    freopen("/home/amzing/in.txt", "r", stdin);
    scanf("%d", &n);
    char *lhs[2] = {"light", "heavy"};
    for(int i=0;i!=n;i++)
    {
        memset(a, 0 ,sizeof(a));
        memset(b, 0 ,sizeof(b));
        memset(c, 0 ,sizeof(c));
        for(int j=0;j!=3;j++)
        {
            scanf("%s %s %s", a[j], b[j], c[j]);
        }
        for(char k='A';k<='L';k++)
        {
            int ret = check(k);
            if(ret!=-1)
            {
                printf("%c is the counterfeit coin and it is %s.\n", k, lhs[ret]);
                break;
            }
        }
    }

    return 0;
}

POJ1016

题目链接：http://poj.org/problem?id=1016

判断一个数的统计数是不是这个数，或者迭代了几次后进入循环了。最多循环15次即可。

无脑模拟即可

//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>

using namespace std;

const int buff_size = 100;

char buff[buff_size];

vector<string> vs;

string calc(string s)
{
    int cnt[10];
    memset(cnt, 0 ,sizeof(cnt));
    for(int i=0;i!=s.size();i++)
    {
        cnt[s[i]-'0']++;
    }
    string ans="";
    for(int i=0;i!=10;i++)
    {
        if(cnt[i])
        {
            char buffer[4];
            memset(buffer, 0, sizeof(buffer));
            sprintf(buffer,"%d",cnt[i]);
            ans+=buffer;
            memset(buffer, 0, sizeof(buffer));
            sprintf(buffer,"%d",i);
            ans+=buffer;
        }
    }
    return ans;
}

int vs_find(string &s)
{
    int ans=-1;
    for(int i=0;i!=vs.size();i++)
    {
        if(vs[i]==s)
        {
            ans = i;
            break;
        }
    }
    return ans;
}

void process()
{
    string origin_s = buff;
    const int max_try = 15;
    vs.clear();
    vs.push_back(origin_s);
    string t=origin_s;
    bool flag = false;
    for(int i=0;i!=max_try;i++)
    {
        t = calc(t);
        int _find = vs_find(t);
        if(_find>=0)
        {
            flag = true;
            if(vs.size()==1)
                printf("%s is self-inventorying\n", buff);
            else
                if(_find==vs.size()-1)
                    printf("%s is self-inventorying after %d steps\n", buff, vs.size()-1);
                else
                    printf("%s enters an inventory loop of length %d\n", buff, vs.size()-_find);
            break;
        }
        vs.push_back(t);
    }
    if(!flag)
        printf("%s can not be classified after 15 iterations\n", buff);
}

int main()
{
//    freopen("/home/amzing/in.txt", "r", stdin);
    scanf("%s", buff);
    while(strcmp(buff, "-1")!=0)
    {
        process();
        memset(buff, 0, sizeof(buff));
        scanf("%s", buff);
    }

    return 0;
}

POJ1017

题目链接：http://poj.org/problem?id=1017

哎，我也没啥好方法，手动模拟好6中情况的处理。

#include <string.h>
#include <stdio.h>
#include <string>

int a[7];

int calc()
{
    int ans=0;
    int left=0;
    ans+=a[6];
    while(a[5])
    {
        ans++;
        a[5]--;
        left = 11;
        while(a[1]&&left>=1)
        {
            a[1]--;
            left-=1;
        }
    }
    while(a[4])
    {
        ans++;
        a[4]--;
        left = 20;
        while(a[2]&&left>=4)
        {
            left-=4;
            a[2]--;
        }
        while(a[1]&&left>=1)
        {
            left-=1;
            a[1]--;
        }
    }
    while(a[3])
    {
        ans++;
        a[3]--;
        left=27;
        int max3 = 3;
        int max2 = 5;
        while(a[3]&&max3>0&&left>=9)
        {
            a[3]--;
            max3--;
            max2-=2;
            left-=9;
        }
        while(a[2]&&max2>0&&left>=4)
        {
            a[2]--;
            max2--;
            left-=4;
        }
        while(a[1]&&left>=1)
        {
            a[1]--;
            left--;
        }
    }
    while(a[2])
    {
        ans++;
        left = 36;
        while(a[2]&&left>=4)
        {
            a[2]--;
            left-=4;
        }
        while(a[1]&&left>=1)
        {
            a[1]--;
            left-=1;
        }
    }
    while(a[1])
    {
        ans++;
        left = 36;
        while(a[1]&&left>=1)
        {
            a[1]--;
            left-=1;
        }
    }
    return ans;
}

int main()
{
//    freopen("D:\\c++\\dev\\in.txt", "r", stdin);
    while(~scanf("%d %d %d %d %d %d", &a[1], &a[2], &a[3], &a[4], &a[5], &a[6]))
    {
        int ans=calc();
        if(ans)
            printf("%d\n", ans);
        else
            break;
    }
    return 0;
}

POJ1169

题目链接：http://poj.org/problem?id=1169

题目给了6种情况，但是实际上算的时候第4种和第5种是一样的。

你把第5种中中间的那个矩形放到最左边就可以发现和第4种是一模一样的了。

为什么可以放到最左边呢？

因为你算第4种的时候思路是：整体宽度是最左边的矩形的宽度加上中间两个矩形的最大宽度加上最右边矩形的宽度，整体高度是比较最左边矩形的高度，中间矩形高度之和，最右边矩形高度三者谁最高。

算第5种的思路也是这样。所以两者在算的时候没有区别。

下面简述一下这5种不同的计算方法（将题目中的第4种和第5种合并）

第一种：

整体宽度是：四个矩形的宽度之和

整体高度是：四个矩形最高的那个

第二种：

先选一个矩形放在下面

整体宽度是：取 上面三个矩形宽度之和 和 下面矩形的宽度 中大的那个。

整体高度是，上面三个矩形最高的 加 下面矩形的高度

第三种：

先选一个放在最右边

再选一个放在左下方

整体宽度是：左边的宽度加右边的宽度，类似与第二种的算法

整体高度是：左边高度和右边高度中大的那个

第四种：

先选一个矩形放在最左边

再选一个矩形放在最右边

整体宽度是：三部分之和

整体高度是：三部分较高的

第五种：

我们设定4个矩形的序号是1，2，3， 4

按照如下顺序摆放：

可以发现要想摆成这样要满足三个条件：

条件一：下面两个矩形的宽度之和大于上面两个矩形的宽度之和，即2，3的宽度之和大于1，4的宽度之和

条件二：保证1不会因为2过低，顶到3里面去

条件三：保证4不会因为3过低，顶到2里面去

然后写遍历即可

整体宽度是：2，3宽度之和

整体高度是：1，2高度之和 和 3，4 高度之和 中大的那个

#include <string.h>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class A
{
friend bool operator < (const A &a,const A &b);
friend bool operator == (const A &a,const A &b);
public:
    int min_l, max_l;
    A(int min_l, int max_l)
    {
        this->min_l = min_l;
        this->max_l = max_l;
    }
};

bool operator < (const A &a, const A &b)
{
    if(a.min_l<b.min_l)return true;
    return false;
}

bool operator == (const A &a, const A &b)
{
    if(a.min_l==b.min_l&&a.max_l==b.max_l)return true;
    return false;
}

int r[4][2];

const int inf = ~(1<<31);

int min_area = inf;

vector<A> ans;

int getbit(int number, int bit)
{
    return (number>>bit)&(1);
}

void shape1()
{
    //枚举4个矩形不同的长宽防止方式，可知最终结果与4个矩形的左右排放顺序无关，所以就默认的即可
    //2**4 = 16
    int sum_w, max_h, area;
    int min_l, max_l;
    //第i种方案
    for(int i=0;i!=16;i++)
    {
        sum_w = 0;
        max_h = 0;
        //第j个矩形
        for(int j=0;j!=4;j++)
        {
            //获取这个方法种第j个矩形是先w后h，还是先h后w
            int t = getbit(i, j);
            int w = r[j][t];
            int h = r[j][1-t];
            sum_w+=w;
            max_h = max(max_h, h);
        }
        area = sum_w*max_h;
        min_l = min(sum_w, max_h);
        max_l = max(sum_w, max_h);
        if(area<min_area)
        {
            min_area = area;
            ans.clear();
            ans.push_back(A(min_l, max_l));
        }
        else if(area==min_area)
        {
            ans.push_back(A(min_l, max_l));
        }
    }
}

void shape2()
{
    int down_w, down_h, up_w, up_h, area, area_w, area_h;
    int min_l, max_l;
    //这个需要枚举4个矩形种谁在下面
    for(int down_rectangle=0;down_rectangle!=4;down_rectangle++)
    {
        //内部还是枚举16种方案
        //第i种方案
        for(int i=0;i!=16;i++)
        {
            down_w = 0;
            down_h = 0;
            up_w = 0;
            up_h = 0;
            //第j个矩形
            for(int j=0;j!=4;j++)
            {
                //获取这个方法种第j个矩形是先w后h，还是先h后w
                int t = getbit(i, j);
                int w = r[j][t];
                int h = r[j][1-t];
                if(j==down_rectangle)
                {
                    down_w=w;
                    down_h=h;
                }
                else
                {
                    up_w+=w;
                    up_h=max(up_h, h);
                }
            }
            area_w = max(down_w, up_w);
            area_h = down_h+up_h;
            area = area_w*area_h;
            min_l = min(area_w, area_h);
            max_l = max(area_w, area_h);
            if(area<min_area)
            {
                min_area = area;
                ans.clear();
                ans.push_back(A(min_l, max_l));
            }
            else if(area==min_area)
            {
                ans.push_back(A(min_l, max_l));
            }
        }
    }
}

void shape3()
{
    int area, area_w, area_h, right_w, right_h, left_w, left_h, left_down_w, left_down_h, left_up_w, left_up_h;
    int min_l, max_l;
    //先选出谁在右边
    for(int right_rectangle=0;right_rectangle!=4;right_rectangle++)
    {
        //再选出谁在下面
        for(int left_down_rectangle=0;left_down_rectangle!=4;left_down_rectangle++)
        {
            if(left_down_rectangle==right_rectangle)continue;
            //内部还是枚举16种方案
            //第i种方案
            for(int i=0;i!=16;i++)
            {
                left_up_w = 0;
                left_up_h = 0;
                //第j个矩形
                for(int j=0;j!=4;j++)
                {
                    //获取这个方法种第j个矩形是先w后h，还是先h后w
                    int t = getbit(i, j);
                    int w = r[j][t];
                    int h = r[j][1-t];
                    if(j==right_rectangle)
                    {
                        right_w = w;
                        right_h = h;
                    }
                    else if(j==left_down_rectangle)
                    {
                        left_down_w = w;
                        left_down_h = h;
                    }
                    else
                    {
                        left_up_w+=w;
                        left_up_h=max(left_up_h, h);
                    }
                }
                area_w = max(left_up_w, left_down_w)+right_w;
                area_h = max(left_up_h+left_down_h, right_h);
                area = area_w*area_h;
                min_l = min(area_w, area_h);
                max_l = max(area_w, area_h);
                if(area<min_area)
                {
                    min_area = area;
                    ans.clear();
                    ans.push_back(A(min_l, max_l));
                }
                else if(area==min_area)
                {
                    ans.push_back(A(min_l, max_l));
                }
            }
        }
    }
}

void shape4()
{
    int area, area_w, area_h, left_w, left_h, mid_w, mid_h, right_w, right_h;
    int min_l, max_l;
    //选出左边的矩形
    for(int left_rectangle=0;left_rectangle!=4;left_rectangle++)
    {
        //选出右边的矩形
        for(int right_rectangle=0;right_rectangle!=4;right_rectangle++)
        {
            if(left_rectangle==right_rectangle)continue;
            //内部还是枚举16种方案
            //第i种方案
            for(int i=0;i!=16;i++)
            {
                mid_w = 0;
                mid_h = 0;
                //第j个矩形
                for(int j=0;j!=4;j++)
                {
                    //获取这个方法种第j个矩形是先w后h，还是先h后w
                    int t = getbit(i, j);
                    int w = r[j][t];
                    int h = r[j][1-t];
                    if(j==left_rectangle)
                    {
                        left_w=w;
                        left_h=h;
                    }
                    else if(j==right_rectangle)
                    {
                        right_w = w;
                        right_h = h;
                    }
                    else
                    {
                        mid_w = max(mid_w, w);
                        mid_h += h;
                    }
                }
                area_w = left_w+mid_w+right_w;
                area_h = max(max(left_h, mid_h), right_h);
                area = area_w*area_h;
                min_l = min(area_w, area_h);
                max_l = max(area_w, area_h);
                if(area<min_area)
                {
                    min_area = area;
                    ans.clear();
                    ans.push_back(A(min_l, max_l));
                }
                else if(area==min_area)
                {
                    ans.push_back(A(min_l, max_l));
                }
            }
        }
    }
}

void shape5()
{
    int area, area_w, area_h;
    int first_w, first_h, second_w, second_h, third_w, third_h, forth_w, forth_h;
    int min_l, max_l;
    int f[4];
    for(int first=0;first!=4;first++)
    {
        for(int second=0;second!=4;second++)
        {
            for(int third=0;third!=4;third++)
            {
                for(int forth=0;forth!=4;forth++)
                {
                    int flag=true;
                    memset(f, 0, sizeof(f));
                    f[first]=1;
                    f[second]=1;
                    f[third]=1;
                    f[forth]=1;
                    for(int ff=0;ff!=4;ff++)
                    {
                        if(!f[ff])
                        {
                            flag = false;break;
                        }
                    }
                    if(!flag)continue;
                    //内部还是枚举16种方案
                    //第i种方案
                    for(int i=0;i!=16;i++)
                    {
                        int t;
                        t = getbit(i, first);
                        first_w = r[first][t];
                        first_h = r[first][1-t];
                        t = getbit(i, second);
                        second_w = r[second][t];
                        second_h = r[second][1-t];
                        t = getbit(i, third);
                        third_w = r[third][t];
                        third_h = r[third][1-t];
                        t = getbit(i, forth);
                        forth_w = r[forth][t];
                        forth_h = r[forth][1-t];
                        //1 4
                        //2 3
                        //保证下面两个矩形比较宽
                        if(first_w+forth_w>second_w+third_w)continue;
                        //保证4不会因为3过低，顶到2里面去
                        if(forth_w>third_w&&third_h<second_h)continue;
                        //保证1不会因为2过低，顶到3里面去
                        if(first_w>second_w&&second_h<third_h)continue;

                        area_w = second_w+third_w;
                        area_h = max(first_h+second_h, third_h+forth_h);
                        area = area_w*area_h;
                        min_l = min(area_w, area_h);
                        max_l = max(area_w, area_h);
                        if(area<min_area)
                        {
                            min_area = area;
                            ans.clear();
                            ans.push_back(A(min_l, max_l));
                        }
                        else if(area==min_area)
                        {
                            ans.push_back(A(min_l, max_l));
                        }
                    }
                }
            }
        }
    }
}

void calc()
{
    shape1();
    shape2();
    shape3();
    shape4();
    shape5();
}

int main()
{
    freopen("D:\\c++\\dev\\in.txt", "r", stdin);
    for(int i=0;i!=4;i++)
    {
        scanf("%d %d", &r[i][0], &r[i][1]);
    }

    calc();

    printf("%d\n", min_area);

    sort(ans.begin(), ans.end());

    for(int i=0;i<ans.size();i++)
    {
        if(i==0||(i>0&&ans[i-1]<ans[i]))
            printf("%d %d\n", ans[i].min_l, ans[i].max_l);
    }

    return 0;
}

POJ1298

题目链接：http://poj.org/problem?id=1298

#include <string.h>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string input="";

char c;

int main()
{
    freopen("D:\\c++\\dev\\in.txt", "r", stdin);
    getline(cin, input);
    while(input!="ENDOFINPUT")
    {
        if(input!="START"&&input!="END")
        {
            for(int i=0;i!=input.size();i++)
            {
                if(input[i]>='A'&&input[i]<='Z')
                {
                    c = input[i]-5;
                    if(c<'A')c+=26;
                    printf("%c", c);
                }
                else printf("%c", input[i]);
            }
            printf("\n");
        }
        getline(cin, input);
    }
    return 0;
}

POJ1326

题目链接：http://poj.org/problem?id=1326

#include <string.h>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

char city[30];
int miles;
char c;

int ans;

int main()
{
    freopen("D:\\c++\\dev\\in.txt", "r", stdin);
    memset(city, 0, sizeof(city));
    scanf("%s", city);
    while(strcmp(city, "#")!=0)
    {
        ans=0;
        while(strcmp(city, "0")!=0)
        {
            memset(city, 0, sizeof(city));
            scanf("%s %d %c", city, &miles, &c);
            if(c=='F')
                ans+=(miles+miles);
            else if(c=='B')
                ans+=(miles+int(0.5*miles+0.5));
            else
                ans+=(miles>=500? miles: 500);
            memset(city, 0, sizeof(city));
            scanf("%s", city);
        }
        printf("%d\n", ans);
        memset(city, 0, sizeof(city));
        scanf("%s", city);
    }
    return 0;
}

POJ1350

题目链接：http://poj.org/problem?id=1350

#include <string.h>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

char s[5];

int a[4];

char c;

bool flag;

int big, small, result;

int getsmall()
{
    int ans=0;
    int cnt=0;
    int t_result = result;
    for(int i=0;i!=4;i++)
    {
        if(t_result>0)cnt++;
        a[i]=t_result%10;
        t_result/=10;
    }
    sort(a, a+cnt);
    for(int i=0;i!=cnt;i++)
    {
        ans*=10;
        ans+=a[i];
    }
    return ans;
}

int getbig()
{
    int ans=0;
    int cnt=0;
    int t_result = result;
    for(int i=0;i!=4;i++)
    {
        if(t_result>0)cnt++;
        a[i]=t_result%10;
        t_result/=10;
    }
    sort(a, a+cnt);
    for(int i=cnt-1;i>=0;i--)
    {
        ans*=10;
        ans+=a[i];
    }
    return ans;
}

void init_result()
{
    result = 0;
    for(int i=0;i!=4;i++)
    {
        result*=10;
        result+=s[i]-'0';
    }
}

int main()
{
    freopen("D:\\c++\\dev\\in.txt", "r", stdin);
    scanf("%s", s);
    while(strcmp(s, "-1")!=0)
    {
        flag = true;
        if(strlen(s)!=4)
            flag = false;
        if(flag)
        {
            c = s[0];
            bool different = false;
            for(int i=0;i!=4;i++)
            {
                if(s[i]<'0'||s[i]>'9')
                {
                    flag = false;
                    break;
                }
                if(c!=s[i])different = true;
            }
            if(!different)flag = false;
        }

        if(flag)
        {
            printf("N=%s:\n", s);
            init_result();
            int cnt=0;
            while(result!=0&&result!=6174)
            {
                cnt++;
                big = getbig();
                small = getsmall();
                result = big-small;
                printf("%d-%d=%d\n", big, small, result);
            }
            printf("Ok!! %d times\n", cnt);
        }
        else
        {
            printf("N=%s:\nNo!!\n", s);
        }
        scanf("%s", s);
    }
    return 0;
}

POJ1363

题目链接：http://poj.org/problem?id=1363

题目的意思是他的输入一直都是1-N，让你看能不能按照他的那个给出的顺序输出。

5是说5个数1-5 然后对于5这个长度不断输入5个数，你去判断，如果遇到某一行是0，那么5这个长度的输入结束，你输出一个回车 最后如何碰到某个输入长度是0，那么就结束

//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>

using namespace std;

const int maxn=1001;

int n;

int a[maxn];
int s[maxn];

int stack_len=0;
int p_a=0;

bool check()
{
    stack_len = 0;
    p_a = 0;
    for(int i=1;i<=n;i++)
    {
        //判断进
        if(a[p_a]==i)p_a++;
        else
            s[stack_len++]=i;
        //判断是否可以清空栈
        while(stack_len&&s[stack_len-1]==a[p_a])
        {
            p_a++;
            stack_len--;
        }
    }
    return stack_len==0;
}

int main()
{
    freopen("/home/amzing/in.txt", "r", stdin);
    scanf("%d", &n);
    while(n)
    {
        for(int i=0;i!=n;i++)
        {
            scanf("%d", &a[i]);
            if(!a[i])break;
        }

        if(a[0])
        {
            if(check())
                printf("Yes\n");
            else
                printf("No\n");
        }
        else
        {
            printf("\n");
            scanf("%d", &n);
        }
    }

    return 0;
}

POJ1676

题目链接：http://poj.org/problem?id=1676

哎，本来以为是个简单题，没想到坑还不少。

所有数字都要猜测，两个时间差15分钟的情况有下面三种：

第一：小时相同，分钟差15分钟

第二：第一个小时大，第二个小时小，二者时间相差15分钟

第三：第一个时间指的是前一天的时间，第二是今天的时间，二者差15分钟，例如：00：14-23：59

//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>

using namespace std;

bool digits[10][7]={
        1,0,1,1,1,1,1,
        0,0,0,0,1,0,1,
        1,1,1,0,1,1,0,
        1,1,1,0,1,0,1,
        0,1,0,1,1,0,1,
        1,1,1,1,0,0,1,
        1,1,1,1,0,1,1,
        1,0,0,0,1,0,1,
        1,1,1,1,1,1,1,
        1,1,1,1,1,0,1,
};

class D
{
public:
    bool a[7];
    vector<int> guess();
    void print();

    D();
    D(char *s);
};

D::D()
{
    memset(a, 0, sizeof(a));
}

D::D(char *s)
{
    memset(a, 0, sizeof(a));
    if(s[1]=='_')a[0]=1;
    if(s[3]=='|')a[3]=1;
    if(s[4]=='_')a[1]=1;
    if(s[5]=='|')a[4]=1;
    if(s[6]=='|')a[5]=1;
    if(s[7]=='_')a[2]=1;
    if(s[8]=='|')a[6]=1;
}

vector<int> D::guess()
{
    vector<int> ans;
    bool flag = true;
    for(int i=0;i!=10;i++)
    {
        flag = true;
        for(int j=0;j!=7;j++)
        {
            if(a[j]&&!digits[i][j])
            {
                flag = false;
                break;
            }
        }
        if(flag)ans.push_back(i);
    }
    return ans;
}

void D::print()
{
    if(a[0])printf(" _ ");
    else printf("   ");
    printf("\n");

    if(a[3])printf("|");
    else printf(" ");

    if(a[1])printf("_");
    else printf(" ");

    if(a[4])printf("|");
    else printf(" ");

    printf("\n");

    if(a[5])printf("|");
    else printf(" ");

    if(a[2])printf("_");
    else printf(" ");

    if(a[6])printf("|");
    else printf(" ");

    printf("\n");
}

void show_d()
{
    for(int i=0;i!=10;i++)
    {
        D d;
        for(int j=0;j!=7;j++)
        {
            d.a[j]=digits[i][j];
        }
        d.print();
    }
}

int n;

D d[8];

vector<int> d_guess[8];
vector<int> d_ok[8];

int d_int[8];

void input_one_case()
{
    char s[8][9];
    memset(s, 0 ,sizeof(s));
    for(int line=0;line!=3;line++)
    {
        int start_no = 3*line;
        for(int i=0;i!=8;i++)
        {
            for(int j=0;j!=3;j++)
            {
                s[i][start_no+j]=getchar();
//                printf("%c", s[i][start_no+j]);
            }
            if(i==3)getchar();
        }
//        printf("\n");
        getchar();
    }
    for(int i=0;i!=8;i++)
    {
        d[i] = D(s[i]);
//        d[i].print();
//        printf("****************\n");
    }
}

void dfs(int d_no)
{
    for(int i=0;i!=d_guess[d_no].size();i++)
    {
        d_int[d_no]=d_guess[d_no][i];
        if(d_no==7)
        {
            int h, m, late_h, late_m;
            h = d_int[0]*10+d_int[1];
            m = d_int[2]*10+d_int[3];
            late_h = d_int[4]*10+d_int[5];
            late_m = d_int[6]*10+d_int[7];

            if(h<=23&&late_h<=23&&m<=59&&late_m<=59&&((h*60+m-15==late_h*60+late_m)||(h*60+m+24*60-15==late_h*60+late_m)))
                for(int j=0;j!=8;j++)d_ok[j].push_back(d_int[j]);
        }
        else dfs(d_no+1);
    }
}

int main()
{
    freopen("/home/amzing/in.txt", "r", stdin);
    scanf("%d", &n);
    getchar();
    for(int i=0;i!=n;i++)
    {
        input_one_case();

        for(int j=0;j!=8;j++)
        {
            d_guess[j] = d[j].guess();
            d_ok[j].clear();
        }

        dfs(0);

//        for(int j=0;j!=d_ok[0].size();j++)
//        {
//            for(int k=0;k!=8;k++)
//                printf("%d", d_ok[k][j]);
//            printf("\n");
//        }

        if(d_ok[0].size()==1)printf("%d%d%d%d\n", d_ok[0][0], d_ok[1][0], d_ok[2][0], d_ok[3][0]);
        else printf("Not Sure\n");
    }
    return 0;
}

POJ1786

题目链接：http://poj.org/problem?id=1786

这个题虽说是个简单模拟题，但是写的代码却一直超时，网上的代码也一直超时，我也不太会改了，就先放这里一份参考代码吧

//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

char c;

char s[104];

char suit_list[] = "CDSH";
char rank_list[] = "23456789TJQKA";

int card_suit_char2int_map[91];
int card_rank_char2int_map[91];
//char card_suit_int2char_map[91];
//char card_rank_int2char_map[91];

class Card
{
    friend bool operator < (const Card &a, const Card &b);
public:
    char c_suit, c_rank;
    int suit, rank;

    Card();
    Card(char suit, char rank);
};

bool operator < (const Card &a, const Card &b)
{
    if(a.suit!=b.suit)return a.suit<b.suit;
    if(a.rank!=b.rank)return a.rank<b.rank;
    return false;
}

Card::Card() {}

Card::Card(char suit, char rank)
{
    this->c_suit = suit;
    this->c_rank = rank;
    this->suit = card_suit_char2int_map[suit];
    this->rank = card_rank_char2int_map[rank];
}

priority_queue<Card> cards_queue[4];

Card cards[4][13];

void init_card_map()
{
    for(int i=0;i!=4;i++)
    {
        card_suit_char2int_map[suit_list[i]]=i;
//        card_suit_int2char_map[suit_list[i]]=suit_list[i];
    }

    for(int i=0;i!=13;i++)
    {
        card_rank_char2int_map[rank_list[i]]=i;
//        card_rank_int2char_map[rank_list[i]]=rank_list[i];
    }
}

char order[]="SWNE";
char player[4][15] = {"South player:", "West player:", "North player:", "East player:"};

int main()
{
    freopen("/home/amzing/in.txt", "r", stdin);
    init_card_map();
    while((c=getchar())!='#')
    {
        scanf("%s", s);
        scanf("%s", s+52);
        getchar();

        int cnt=0;
        for(int i=0;i<4;i++)
        {
            cnt++;
            if(c==order[i])break;
        }
        cnt%=4;

        for(int i=0;i!=4;i++)
            while(!cards_queue[i].empty())cards_queue[i].pop();

        int t = 0;
        for(int i=0;i!=13;i++)
        {
            for(int j=0;j!=4;j++)
            {
                cards_queue[cnt].push(Card(s[t], s[t+1]));
                t+=2;
                cnt++;
                cnt%=4;
            }
        }

        cnt = 2;
        for(int i=0;i!=4;i++)
        {
            for(int j=12;j>=0;j--)
            {
                cards[i][j] = cards_queue[i].top();
                cards_queue[i].pop();
            }
            printf("%s\n", player[i]);
            printf("+---+---+---+---+---+---+---+---+---+---+---+---+---+\n");
            printf("|");
            for(int j=0;j!=13;j++)
                printf("%c %c|", cards[i][j].c_rank, cards[i][j].c_rank);
            printf("\n|");
            for(int j=0;j!=13;j++)
                printf(" %c |", cards[i][j].c_suit);
            printf("\n|");
            for(int j=0;j!=13;j++)
                printf("%c %c|", cards[i][j].c_rank, cards[i][j].c_rank);
            printf("\n+---+---+---+---+---+---+---+---+---+---+---+---+---+\n");
            cnt++;
            cnt%=4;
        }
    }

    return 0;
}

POJ1791

题目链接：http://poj.org/problem?id=1791

这题意说的是在一张e * f的大纸上裁剪c * d个a * b大小的名片。

这里c * d个暗示了，这些名片是按照同样的摆放方式，放置了c行，d列，不用考虑，在某个边边角角正好又能裁剪一个等复杂的情况。

所以就枚举名片a，b横着放，竖着放，c，d横着放，竖着放，这一共2 * 2=4种情况即可。

切的一刀需要贯穿整张纸，一旦纸分开，就算两部分，每部分要再分开切。

#include<stdio.h>
#include<algorithm>
using namespace std;

int a,b,c,d,e,f;

const int inf = 1e8;

int ans,_ans,sum_e,sum_f,_a,_b,_c,_d;

int main()
{
    freopen("in.txt","r",stdin);
    scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f);
    while(a!=0)
    {
        ans=inf;
        for(int i=0;i!=4;i++)
        {
            if(i<2){_a=a;_b=b;}
            else {_a=b;_b=a;}
            if(i%2){_c=c;_d=d;}
            else {_c=d;_d=c;}
            sum_e=_a*_c;
            sum_f=_b*_d;

            if(sum_e>e||sum_f>f)continue;
            _ans=0;
            // 计算切除边角料
            if(e>sum_e)_ans++;
            if(f>sum_f)_ans++;
            // 先横着切成多份，每份内再竖着切
            _ans+=((_a-1)+_a*(_b-1));
            ans=min(ans,_ans);
        }
        if(ans==inf)printf("The paper is too small.\n");
        else printf("The minimum number of cuts is %d.\n", ans);

        scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f); 
    }

    return 0;
}

POJ1835

题目链接：http://poj.org/problem?id=1835

这题思路想明白很重要，状态转移的解决方法的设计很重要。

我一开始想成了，一个人，站在一个正方体上，有6个面，然后每个面4个朝向，然后每个状态6种动作，到达一个新的状态，用数组存的话应该是[6][4][6][2],这这这，这样想就太复杂了，太难搞。

但其实只需要记录这个人，的6个方向分别指的哪里，然后这6个方向在通过6种动作后会发生什么样的变化即可。

思路见代码，太简单了。

#include<stdio.h>
#include<algorithm>
using namespace std;

int m,n,x,y,z,l,r,f,b,u,d,t;

char s[10];

void left()
{
    int _t=f;
    f=l;l=b;b=r;r=_t;
}

void right()
{
    int _t=f;
    f=r;r=b;b=l;l=_t;
}

void forword()
{
}

void back()
{
    swap(f,b);
    swap(l,r);
}

void up()
{
    int _t=f;
    f=u;u=b;b=d;d=_t;
}

void down()
{
    int _t=f;
    f=d;d=b;b=u;u=_t;
}

void move()
{
    switch(f)
    {
        case 0:x+=t;break;
        case 1:y+=t;break;
        case 2:z+=t;break;
        case 3:x-=t;break;
        case 4:y-=t;break;
        case 5:z-=t;break;
        default:break;
    }
}

int main()
{
    freopen("in.txt","r",stdin);
    scanf("%d", &m);
    for(int i=0;i!=m;i++)
    {
        x=0;y=0;z=0;
        l=4;r=1;u=2;d=5;f=0;b=3;
        scanf("%d", &n);
        for(int j=0;j!=n;j++)
        {
            scanf("%s %d", s, &t);
            switch(s[0])
            {
                case 'l':left();break;
                case 'r':right();break;
                case 'u':up();break;
                case 'd':down();break;
                case 'f':forword();break;
                case 'b':back();break;
                default:break;
            }
            move();
        }
        printf("%d %d %d %d\n", x, y, z, f);
    }
    return 0;
}

POJ1970

题目链接：http://poj.org/problem?id=1970

枚举每一个可能的位置即可，可能的是以当前i，j的位置为开始，往右有5个，往下有5个，往右下有5个，往右上有5个，这4种情况。

#include<stdio.h>
#include<algorithm>
using namespace std;

int T;

int a[19][19];

bool flag;

bool check(int i, int j)
{
    if(a[i][j]==0)return false;
    // i，j是左上角 
    // 检测横着 
    if((j==0||a[i][j-1]!=a[i][j])&&(j<=14))
    {
        bool flag=true;
        for(int p=1;p!=5;p++)
        {
            if(a[i][p+j]!=a[i][j])
            {
                flag=false;break;
            }
        }
        if(j<14&&a[i][j+5]==a[i][j])flag=false;
        if(flag)return true;
    }
    // 检测竖着
    if((i==0||a[i-1][j]!=a[i][j])&&(i<=14))
    {
        bool flag=true;
        for(int p=1;p!=5;p++)
        {
            if(a[p+i][j]!=a[i][j])
            {
                flag=false;break;
            }
        }
        if(i<14&&a[i+5][j]==a[i][j])flag=false;
        if(flag)return true;
    }
    // 检测左上至右下 
    if(((i==0||j==0)||a[i-1][j-1]!=a[i][j])&&(i<=14&&j<=14))
    {
        bool flag=true;
        for(int p=1;p!=5;p++)
        {
            if(a[i+p][j+p]!=a[i][j])
            {
                flag=false;break;
            }
        }
        if((i<14&&j<14)&&a[i+5][j+5]==a[i][j])flag=false;
        if(flag)return true;
    }
    // 检测左下至右上 
    if(((i==18||j==0)||a[i+1][j-1]!=a[i][j])&&(i>=4&&j<=14))
    {
        bool flag=true;
        for(int p=1;p!=5;p++)
        {
            if(a[i-p][j+p]!=a[i][j])
            {
                flag=false;break;
            }
        }
        if((i>4&&j<14)&&a[i-5][j+5]==a[i][j])flag=false;
        if(flag)return true;
    }
    return false;
}

int main()
{
    freopen("in.txt","r",stdin);
    scanf("%d", &T);
    for(int t=0;t!=T;t++)
    {       
        for(int i=0;i!=19;i++)
        {
            for(int j=0;j!=19;j++)
            {
                scanf("%d", &a[i][j]);
            }
        }

        flag = 0;
        for(int i=0;i!=19;i++)
        {
            if(flag)break;
            for(int j=0;j!=19;j++)
            {
                if(check(i, j))
                {
                    printf("%d\n%d %d\n", a[i][j], i+1, j+1);
                    flag=true;
                    break;
                }
            }
        }
        if(!flag)printf("0\n");
    }
    return 0;
}