首页 > 代码库 > Codeforces Round #253 (Div. 2)——Borya and Hanabi
Codeforces Round #253 (Div. 2)——Borya and Hanabi
题目连接
- 题意：
n表示有n个卡片。每一个卡片有一种颜色和一个数字（共五种不同的颜色和五个不同的数字）。事先知道每种卡片有几张。可是不知道详细的位置。
问须要几次提示就能够知道全部卡片的位置都在哪里：每次提示能够选择一个颜色或者一个数字。就能够知道含有所选属性的牌有哪些。
- 分析：
首先明确总情况数不多，仅仅有2^10，所以枚举。
能确定某张牌位置的情况：1）提示了一个属性，而这个属性仅仅有一张牌 2）某个属性有n张牌，知道了n-1张牌的位置
两个提示确定一张牌：必定的，仅仅要存在这张牌。那么两个提示必定能够找到相应的牌的位置
一个提示就能够确定某张牌的情况：此时这张牌的还有一个属性在总的集合中必定仅仅有一个 - 关键：
全部同样的卡片仅仅用保留一个就可以
set<int> st[10];
int all = 1 << 10, ans = INF;
int change(char x)
{
if (x == ‘B‘) return 0;
else if (x == ‘Y‘) return 1;
else if (x == ‘W‘) return 2;
else if (x == ‘G‘) return 3;
else return 4; //R
}
void fun(int num, set<int> st[])
{
int one = 0, t[10] = {0};
for (int j = 1, ct = 0; j < all; j <<= 1, ct++)
if (num & j)
{
one++;
t[ct] = 1;
}
REP(i, 5) FF(j, 5, 10)
if (t[i] && t[j])
{
st[i].erase(j);
st[j].erase(i);
}
REP(i, 10)
if (t[i] && st[i].size() == 1)
{
st[*(st[i].begin())].erase(i);
st[i].clear();
}
int len = 0;
REP(i, 5) len += st[i].size();
if (len <= 1)
ans = min(ans, one);
}
int main()
{
int n;
char x; int y;
cin >> n;
REP(i, n)
{
cin >> x >> y;
st[change(x)].insert(y + 4);
st[y + 4].insert(change(x));
}
FF(i, 0, all)
{
set<int> tt[10];
REP(j, 10) tt[j] = st[j];
fun(i, tt);
}
WI(ans);
return 0;
}Codeforces Round #253 (Div. 2)——Borya and Hanabi
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。