ZOJ 2012.11月赛

    本来上周日(11.25)轮到我做汇报，PPT都写好了，看到ZOJ有月赛，便想练练手。

   当时做比赛的时候已经三点了，看到DFIJ这四题出的比较多，就决定拿下这4道题。

 

    J题(ZOJ3675) Trim the Nails

    题意：指甲宽为m，指甲刀宽为n，单位均为毫米，但指甲刀是不完整的，'*'表示完整，'.'表示不完整。问最少剪几次可以剪完指甲。注意指甲刀可以翻转。比如输入m=7 n=6且指甲刀表示为***..*：

 

fingernail:			-------
nail clipper:			*..***
nail clipper turned over:	***..*
Requires two cuts.

 

    分析：指甲刀最多有2*(m+n)种方式来修剪指甲，且指甲的状态只有2^m个，由于m<=20,n<=10，果断用BFS寻找最优解。最坏情况复杂度为10^6。

 

     I(ZOJ3674) Search in the Wiki

    题意：给出n个单词a和对应的解释单词ai，然后给出m个查询，每个查询包含若干个单词，询问这些单词所共有的解释单词，没有则输出NO。

    分析：可以将每个单词作为键，对应的解释单词作为值，保存在map中；对于m条查询，从map中找到相应单词的项，无非就是统计解释单词出现的次数，最后次数=单词个数的那些解释单词就是答案。可以设一个map统计每个单词出现的次数，最后筛选排序输出。

 

    F(ZOJ3671)  Japanese Mahjong III

    题意：打麻将，给14张牌，看是否是符合规定的两种要求。两种要求为：

    1.七对: 14张牌由7对相同的牌组成，且每一对都不同(花色或序号)；

    2.13单: 有1万9万、1条9条、1坨9坨、东南西北、中发白(13张)，剩余一张是前面13张中的任意一张。

    分析：先按类别排序；对于7对，i为偶数时，必须要求(i,i+1)相同(花色和序号完全一样)，i为奇数时，必须要求(i,i+1)不同(花色或者序号不一样)；对于13单，首先判断当前重复的牌的张数，若!=1显然不是13单，若=1，删掉这张，并看是否与标准13张牌完全相同。

 

    D(ZOJ3669) Japanese Mahjong I

    题意：还是打麻将，胡牌的格式为14张牌，4个3元组，每个3元祖要么3张完全一样，要么是花色相同的顺子，剩余两张牌为花色相同的任意牌(对子)。给出13张牌，问摸到哪些牌可以胡牌。

    分析：麻将总的牌类为3*9+7=34种，枚举添加每一种牌，构成14张，问题变为判断14张牌是否胡牌。枚举对子，问题变为12张牌是否由4个三元组构成。DFS判断一下就OK了。复杂度很小。注意由3个4张完全相同+一个对子不算胡牌，在这里错了几次。

 

附3674和3669代码

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> split(const string& aim, const string& pattern)
{
    string str(aim);
    str += pattern;
    vector<string> result;
    string::size_type pos;
    string::size_type size = str.size();
    for(string::size_type i = 0; i < size; i++)
    {
        if((pos=str.find(pattern, i))==string::npos)
            return result;
        if(pos != i)    ///避免分隔符连续出现导致保存空串
        {
            string s = str.substr(i, pos-i);    ///[i,pos)
            result.push_back(s);
        }
        i = pos + pattern.size() - 1;
    }
    return result;
}

int main()
{
    int n,m;
    map<string, vector<string> > words;
    map<string, vector<string> >::iterator mapIt;
    map<string,int> myMap;
    vector<string> result;
    string wd,str;
    while(cin>>n)
    {
        words.clear();
        getchar();
        while(n--)
        {
            getline(cin,wd);
            getline(cin,str);
            vector<string> iVec = split(str," ");
            words.insert(make_pair(wd, iVec));
        }
        cin>>m;
        getchar();
        while(m--)
        {
            result.clear();
            myMap.clear();
            getline(cin,str);
            vector<string> iVec = split(str," ");
            for(vector<string>::size_type i = 0; i != iVec.size(); i++)
            {
                string s = iVec[i];
                mapIt = words.find(s);
                vector<string> iVec = mapIt->second;
                for(vector<string>::size_type j = 0; j != iVec.size(); j++)
                {
                    string s = iVec[j];
                    //myMap[s]++;
                    //or
                    map<string,int>::iterator mapt = myMap.find(s);
                    if(mapt == myMap.end())
                        myMap.insert(make_pair(s,1));
                    else
                        mapt->second++;
                }
            }
            for(map<string,int>::iterator it = myMap.begin(); it!=myMap.end(); it++)
            {
                if(it->second == iVec.size())
                    result.push_back(it->first);
            }
            if(result.size()==0)
                printf("NO\n");
            else
            {
                sort(result.begin(),result.end());
                for(vector<string>::size_type i = 0; i < result.size(); i++)
                {
                    printf("%s",result[i].c_str());
                    printf("%c",i==result.size()-1 ? '\n' : ' ');
                }
            }
        }
    }
    return 0;
}

 

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int m[10],p[10],s[10],z[8]; ///27+7种牌的数量

void init()
{
    memset(m,0,sizeof(m));
    memset(p,0,sizeof(p));
    memset(s,0,sizeof(s));
    memset(z,0,sizeof(z));
}


///dfs 寻找4个: 3个构成的顺子或3张一样的牌
bool OnPot(int num)
{
    int i;
    if(num==0)
        return true;
    for(i = 1; i <= 9; i++)
    {
        if(m[i]>=3)
        {
            m[i] -= 3;
            if(OnPot(num-1))
                return true;
            m[i] += 3;
        }
        if(p[i]>=3)
        {
            p[i] -= 3;
            if(OnPot(num-1))
                return true;
            p[i] += 3;
        }
        if(s[i]>=3)
        {
            s[i] -= 3;
            if(OnPot(num-1))
                return true;
            s[i] += 3;
        }
        if(i<=7 && z[i]>=3)
        {
            z[i] -= 3;
            if(OnPot(num-1))
                return true;
            z[i] += 3;
        }
    }
    for(i = 1; i <= 7; i++)     ///wind和dragon没有顺子
    {
        if(m[i] && m[i+1] && m[i+2])
        {
            m[i]--,m[i+1]--,m[i+2]--;
            if(OnPot(num-1))
                return true;
            m[i]++,m[i+1]++,m[i+2]++;
        }
        if(p[i] && p[i+1] && p[i+2])
        {
            p[i]--,p[i+1]--,p[i+2]--;
            if(OnPot(num-1))
                return true;
            p[i]++,p[i+1]++,p[i+2]++;
        }
        if(s[i] && s[i+1] && s[i+2])
        {
            s[i]--,s[i+1]--,s[i+2]--;
            if(OnPot(num-1))
                return true;
            s[i]++,s[i+1]++,s[i+2]++;
        }
    }
    return false;
}

///寻找是否存在3个: 每个有4张完全相同的牌构成
bool OnPot_2()
{
    return false;
    int cnt = 0;
    for(int i = 1; i <= 9; i++)
    {
        if(m[i]==4)
            cnt++;
        if(p[i]==4)
            cnt++;
        if(s[i]==4)
            cnt++;
        if(i<=7&&z[i]==4)
            cnt++;
    }
    return cnt==3;
}

///先找出张数>=2的牌作为对子
bool solve()
{
    for(int i = 1; i <= 9; i++)
    {
        if(m[i] >= 2)
        {
            m[i] -= 2;
            if(OnPot_2()) return true;
            if(OnPot(4)) return true;
            m[i] += 2;
        }
        if(p[i] >=2)
        {
            p[i] -= 2;
            if(OnPot_2()) return true;
            if(OnPot(4)) return true;
            p[i] += 2;
        }
        if(s[i]>=2)
        {
            s[i] -= 2;
            if(OnPot_2()) return true;
            if(OnPot(4)) return true;
            s[i] += 2;
        }
        if(i<=7 && z[i]>=2)
        {
            z[i] -= 2;
            if(OnPot_2()) return true;
            if(OnPot(4)) return true;
            z[i] += 2;
        }
    }
    return false;
}

int main()
{
    int i;
    char str[30];
    string result;
    int cnt;
    while(scanf("%s",str) != EOF)
    {
        cnt = 0;
        result.clear();
        init();
        for(i = 0; i < 26; i += 2)
        {
            if(str[i+1]=='m') m[str[i]-'0']++;
            else if(str[i+1]=='p') p[str[i]-'0']++;
            else if(str[i+1]=='s') s[str[i]-'0']++;
            else z[str[i]-'0']++;
        }
        char kind[5] = "mpsz";
        for(i = 1; i <= 27+7; i++)              ///按 m p s z顺序枚举, 共9*3+7种牌
        {
            int ind = (i-1)/9;
            int tm[10],tp[10],ts[10],tz[8];     ///保存原始值
            memcpy(tm,m,sizeof(m));
            memcpy(tp,p,sizeof(p));
            memcpy(ts,s,sizeof(s));
            memcpy(tz,z,sizeof(z));
            int seq = i%9;
            if(seq==0) seq = 9;
            if(ind==0&&m[seq]<4) m[seq]++;
            else if(ind==1&&p[seq]<4) p[seq]++;
            else if(ind==2&&s[seq]<4) s[seq]++;
            else if(ind==3&&z[seq]<4) z[seq]++;
            else continue;
            if(solve())
            {
                cnt++;
                result += seq + '0';
                result += kind[ind];
            }
            memcpy(m,tm,sizeof(tm));
            memcpy(p,tp,sizeof(tp));
            memcpy(s,ts,sizeof(ts));
            memcpy(z,tz,sizeof(tz));
        }
        if(cnt==0)
        {
            printf("0\n");
            continue;
        }
        printf("%d %s\n",cnt,result.c_str());
    }
    return 0;
}