本来上周日(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;
}
分享到:
相关推荐
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
ZOJ1007 计算形如sigma(1/(k(k+x)),1,+OO)的近似数值。
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
ZOJ3180 ACM题目 算法的实现 浙江大学ZOJ
ZOJ1337 AC代码,附带题目和说明。
zoj吐血制作,希望大家喜欢
zoj1014题Operand, AC通过
Zoj1009题Emigma, AC通过
浙大acm OJ1204,自己做的,已经AC 分享一下,若有更好的算法可以教教我
zju 1992 acm algoruthm 算法题
zoj 3890 Wumpus.md
zoj 1279 Cowculations.md
zoj 1119 SPF.md
zoj 1325 Palindromes.md
zoj 1812 Stamps.md
zoj 3019 Puzzle.md
zoj 3795 Grouping.md