| 记录编号 |
578906 |
评测结果 |
AAAAWWWWWWWWWWWWWWWW |
| 题目名称 |
[NOIP 2015]斗地主 |
最终得分 |
20 |
| 用户昵称 |
 zhengtn03 |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
0.000 s |
| 提交时间 |
2023-05-13 23:40:51 |
内存使用 |
0.00 MiB |
显示代码纯文本
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<iomanip>
#include<stdlib.h>
using namespace std;
struct Noip
{
// 3 4 5 6 7 8 9 10 J Q K A 2 小王 大王
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
char steps[13][13][13][13][2] = { 0 };
long long play[13][13][13][13][2] = { 0 };
struct Info
{
long long play_out;
int min_times;
Info()
{
play_out = 0;
min_times = 10000;
}
};
//火箭
Info rocket(int a[], int count[])
{
Info ans;
//printf("%d\n", ans.min_times);
for (int i = 0; i <= 12; i++)
{
if (a[i] != 0)
{
return ans;
}
}
if (a[13] == 1 && a[14] == 1)
{
ans.play_out = (long long)1 << (13 * 4);
ans.play_out |= (long long)1 << (14 * 4);
ans.min_times = 1;
return ans;
}
if (a[13] == 0 && a[14] == 0)
{
ans.min_times = 0;
return ans;
}
return ans;
}
//炸弹
Info bomb(int a[], int count[])
{
Info ans, tmp, tmp_ans;
if (steps[count[4]][count[3]][count[2]][count[1]][count[5]] != 0)
{
ans.min_times = steps[count[4]][count[3]][count[2]][count[1]][count[5]];
ans.play_out = play[count[4]][count[3]][count[2]][count[1]][count[5]];
return ans;
}
for (int i = 0; i <= 12; i++)
{
tmp.play_out = 0;
if (a[i] >= 4)
{
tmp.play_out |= (long long)1 << (i * 4);
tmp.play_out |= (long long)1 << (i * 4 + 1);
tmp.play_out |= (long long)1 << (i * 4 + 2);
tmp.play_out |= (long long)1 << (i * 4 + 3);
count[4]--;
a[i] -= 4;
tmp_ans = bomb(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
a[i] += 4;
count[4]++;
tmp.play_out ^= (long long)1 << (i * 4);
tmp.play_out ^= (long long)1 << (i * 4 + 1);
tmp.play_out ^= (long long)1 << (i * 4 + 2);
tmp.play_out ^= (long long)1 << (i * 4 + 3);
break;
}
}
tmp = rocket(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
steps[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.min_times;
play[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.play_out;
//printf("%d\n", ans.min_times);
return ans;
}
//单张
Info single(int a[], int count[])
{
//printf("single\n");
Info ans, tmp, tmp_ans;
if (steps[count[4]][count[3]][count[2]][count[1]][count[5]] != 0)
{
ans.min_times = steps[count[4]][count[3]][count[2]][count[1]][count[5]];
ans.play_out = play[count[4]][count[3]][count[2]][count[1]][count[5]];
return ans;
}
/*
for (int i = 0; i <= 14; i++)
{
printf("%d ", a[i]);
}
printf("\n");
*/
set<int> st;
for (int i = 0; i <= 14; i++)
{
tmp.play_out = 0;
if (a[i] >= 1 && st.count(a[i]) == 0)
{
st.insert(a[i]);
tmp.play_out |= (long long)1 << (i * 4);
count[a[i]]--;
count[a[i] - 1]++;
a[i]--;
tmp_ans = single(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
a[i]++;
count[a[i] - 1]--;
count[a[i]]++;
tmp.play_out ^= (long long)1 << (i * 4);
}
}
tmp = bomb(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
steps[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.min_times;
play[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.play_out;
//printf("%d\n", ans.min_times);
return ans;
}
//一对
Info one_pair(int a[], int count[])
{
Info ans, tmp, tmp_ans;
if (steps[count[4]][count[3]][count[2]][count[1]][count[5]] != 0)
{
ans.min_times = steps[count[4]][count[3]][count[2]][count[1]][count[5]];
ans.play_out = play[count[4]][count[3]][count[2]][count[1]][count[5]];
return ans;
}
set<int> st;
for (int i = 0; i <= 12; i++)
{
tmp.play_out = 0;
if (a[i] >= 2 && st.count(a[i]) == 0)
{
st.insert(a[i]);
tmp.play_out |= (long long)1 << (i * 4);
tmp.play_out |= (long long)1 << (i * 4 + 1);
count[a[i]]--;
count[a[i] - 2]++;
a[i] -= 2;
tmp_ans = one_pair(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
a[i] += 2;
count[a[i] - 2]--;
count[a[i]]++;
tmp.play_out ^= (long long)1 << (i * 4);
tmp.play_out ^= (long long)1 << (i * 4 + 1);
}
}
tmp = single(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
steps[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.min_times;
play[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.play_out;
return ans;
}
//三带零
Info tri_zero(int a[], int count[])
{
Info ans, tmp, tmp_ans;
if (steps[count[4]][count[3]][count[2]][count[1]][count[5]] != 0)
{
ans.min_times = steps[count[4]][count[3]][count[2]][count[1]][count[5]];
ans.play_out = play[count[4]][count[3]][count[2]][count[1]][count[5]];
return ans;
}
set<int> st;
for (int i = 0; i <= 12; i++)
{
tmp.play_out = 0;
if (a[i] >= 3 && st.count(a[i]) == 0)
{
st.insert(a[i]);
tmp.play_out |= (long long)1 << (i * 4);
tmp.play_out |= (long long)1 << (i * 4 + 1);
tmp.play_out |= (long long)1 << (i * 4 + 2);
count[a[i]]--;
count[a[i] - 3]++;
a[i] -= 3;
tmp_ans = tri_zero(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
a[i] += 3;
count[a[i] - 3]--;
count[a[i]]++;
tmp.play_out ^= (long long)1 << (i * 4);
tmp.play_out ^= (long long)1 << (i * 4 + 1);
tmp.play_out ^= (long long)1 << (i * 4 + 2);
}
}
tmp = one_pair(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
steps[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.min_times;
play[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.play_out;
return ans;
}
//三带一
Info tri_one(int a[], int count[])
{
Info ans, tmp, tmp_ans;
if (steps[count[4]][count[3]][count[2]][count[1]][count[5]] != 0)
{
ans.min_times = steps[count[4]][count[3]][count[2]][count[1]][count[5]];
ans.play_out = play[count[4]][count[3]][count[2]][count[1]][count[5]];
return ans;
}
set<int> st;
for (int i = 0; i <= 12; i++)
{
tmp.play_out = 0;
if (a[i] >= 3 && st.count(a[i]) == 0)
{
st.insert(a[i]);
tmp.play_out |= (long long)1 << (i * 4);
tmp.play_out |= (long long)1 << (i * 4 + 1);
tmp.play_out |= (long long)1 << (i * 4 + 2);
count[a[i]]--;
count[a[i] - 3]++;
a[i] -= 3;
set<int> st1;
for (int j = 0; j <= 14; j++)
{
if (j == i) continue;
if (a[j] >= 1)
{
if ((j != 13 && j != 14 && st1.count(a[j]) == 0) ||
((j == 13 || j == 14) && st1.count(5) == 0))
{
if (j != 13 && j != 14)
{
st1.insert(a[j]);
}
else
{
st1.insert(5);
}
tmp.play_out |= (long long)1 << (j * 4);
if (j == 13 || j == 14)
{
count[5]--;
}
else
{
count[a[j]]--;
count[a[j] - 1]++;
}
a[j]--;
tmp_ans = tri_one(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
a[j]++;
if (j == 13 || j == 14)
{
count[5]++;
}
else
{
count[a[j] - 1]--;
count[a[j]]++;
}
tmp.play_out ^= (long long)1 << (j * 4);
}
}
}
a[i] += 3;
count[a[i] - 3]--;
count[a[i]]++;
tmp.play_out ^= (long long)1 << (i * 4);
tmp.play_out ^= (long long)1 << (i * 4 + 1);
tmp.play_out ^= (long long)1 << (i * 4 + 2);
}
}
tmp = tri_zero(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
steps[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.min_times;
play[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.play_out;
return ans;
}
//三带一对
Info tri_double(int a[], int count[])
{
Info ans, tmp, tmp_ans;
if (steps[count[4]][count[3]][count[2]][count[1]][count[5]] != 0)
{
ans.min_times = steps[count[4]][count[3]][count[2]][count[1]][count[5]];
ans.play_out = play[count[4]][count[3]][count[2]][count[1]][count[5]];
return ans;
}
set<int> st;
for (int i = 0; i <= 12; i++)
{
tmp.play_out = 0;
if (a[i] >= 3 && st.count(a[i]) == 0)
{
st.insert(a[i]);
tmp.play_out |= (long long)1 << (i * 4);
tmp.play_out |= (long long)1 << (i * 4 + 1);
tmp.play_out |= (long long)1 << (i * 4 + 2);
count[a[i]]--;
count[a[i] - 3]++;
a[i] -= 3;
set<int> st1;
for (int j = 0; j <= 12; j++)
{
if (j == i) continue;
if (a[j] >= 2 && st1.count(a[j]) == 0)
{
st1.insert(a[j]);
tmp.play_out |= (long long)1 << (j * 4);
tmp.play_out |= (long long)1 << (j * 4 + 1);
count[a[j]]--;
count[a[j] - 2]++;
a[j] -= 2;
tmp_ans = tri_double(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
a[j] += 2;
count[a[j] - 2]--;
count[a[j]]++;
tmp.play_out ^= (long long)1 << (j * 4);
tmp.play_out ^= (long long)1 << (j * 4 + 1);
}
}
a[i] += 3;
count[a[i] - 3]--;
count[a[i]]++;
tmp.play_out ^= (long long)1 << (i * 4);
tmp.play_out ^= (long long)1 << (i * 4 + 1);
tmp.play_out ^= (long long)1 << (i * 4 + 2);
}
}
tmp = tri_one(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
steps[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.min_times;
play[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.play_out;
return ans;
}
//四带两对
Info four_double(int a[], int count[])
{
Info ans, tmp, tmp_ans;
if (steps[count[4]][count[3]][count[2]][count[1]][count[5]] != 0)
{
ans.min_times = steps[count[4]][count[3]][count[2]][count[1]][count[5]];
ans.play_out = play[count[4]][count[3]][count[2]][count[1]][count[5]];
return ans;
}
for (int i = 0; i <= 12; i++)
{
tmp.play_out = 0;
if (a[i] == 4)
{
tmp.play_out |= (long long)1 << (i * 4);
tmp.play_out |= (long long)1 << (i * 4 + 1);
tmp.play_out |= (long long)1 << (i * 4 + 2);
tmp.play_out |= (long long)1 << (i * 4 + 3);
count[4]--;
a[i] -= 4;
for (int j = 0; j <= 12; j++)
{
if (j == i) continue;
if (a[j] >= 2)
{
tmp.play_out |= (long long)1 << (j * 4);
tmp.play_out |= (long long)1 << (j * 4 + 1);
count[a[j]]--;
count[a[j] - 2]++;
a[j] -= 2;
for (int k = j + 1; k <= 12; k++)
{
if (k == i || k == j) continue;
if (a[k] >= 2)
{
tmp.play_out |= (long long)1 << (k * 4);
tmp.play_out |= (long long)1 << (k * 4 + 1);
count[a[k]]--;
count[a[k] - 2]++;
a[k] -= 2;
tmp_ans = four_double(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
a[k] += 2;
count[a[k] - 2]--;
count[a[k]]++;
tmp.play_out ^= (long long)1 << (k * 4 + 1);
tmp.play_out ^= (long long)1 << (k * 4);
}
}
a[j] += 2;
count[a[j] - 2]--;
count[a[j]]++;
tmp.play_out ^= (long long)1 << (j * 4);
tmp.play_out ^= (long long)1 << (j * 4 + 1);
}
}
a[i] += 4;
count[4]++;
break;
}
}
tmp = tri_double(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
steps[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.min_times;
play[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.play_out;
return ans;
}
//四带二
Info four_two(int a[], int count[])
{
Info ans, tmp, tmp_ans;
if (steps[count[4]][count[3]][count[2]][count[1]][count[5]] != 0)
{
ans.min_times = steps[count[4]][count[3]][count[2]][count[1]][count[5]];
ans.play_out = play[count[4]][count[3]][count[2]][count[1]][count[5]];
return ans;
}
for (int i = 0; i <= 12; i++)
{
tmp.play_out = 0;
if (a[i] == 4)
{
tmp.play_out |= (long long)1 << (i * 4);
tmp.play_out |= (long long)1 << (i * 4 + 1);
tmp.play_out |= (long long)1 << (i * 4 + 2);
tmp.play_out |= (long long)1 << (i * 4 + 3);
count[4]--;
a[i] -= 4;
for (int j = 0; j <= 14; j++)
{
if (j == i) continue;
if (a[j] >= 1)
{
tmp.play_out |= (long long)1 << (j * 4);
if (j == 13 || j == 14)
{
count[5]--;
}
else
{
count[a[j]]--;
count[a[j] - 1]++;
}
a[j]--;
for (int k = j + 1; k <= 14; k++)
{
if (k == i || k == j) continue;
if (a[k] >= 1)
{
tmp.play_out |= (long long)1 << (k * 4);
if (k == 13 || k == 14)
{
count[5]--;
}
else
{
count[a[k]]--;
count[a[k] - 1]++;
}
a[k]--;
tmp_ans = four_two(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
a[k]++;
if (k == 13 || k == 14)
{
count[5]++;
}
else
{
count[a[k] - 1]--;
count[a[k]]++;
}
tmp.play_out ^= (long long)1 << (k * 4);
}
}
a[j]++;
if (j == 13 || j == 14)
{
count[5]++;
}
else
{
count[a[j] - 1]--;
count[a[j]]++;
}
tmp.play_out ^= (long long)1 << (j * 4);
}
}
a[i] += 4;
count[4]++;
break;
}
}
tmp = four_double(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
steps[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.min_times;
play[count[4]][count[3]][count[2]][count[1]][count[5]] = ans.play_out;
return ans;
}
//三顺
Info tri_straight(int a[], int count[])
{
Info ans, tmp, tmp_ans;
for (int i = 0; i <= 6; i++)
{
int line_count = 0;
for (int j = i; j <= 11; j++)
{
if (a[j] >= 3)
{
line_count++;
}
else break;
}
if (line_count >= 2)
{
tmp.play_out = 0;
for (int j = i; j < i + 2; j++)
{
tmp.play_out |= (long long)1 << (j * 4);
tmp.play_out |= (long long)1 << (j * 4 + 1);
tmp.play_out |= (long long)1 << (j * 4 + 2);
count[a[j]]--;
count[a[j] - 3]++;
a[j] -= 3;
}
tmp_ans = tri_straight(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
for (int j = i + 2; j < i + line_count; j++)
{
tmp.play_out |= (long long)1 << (j * 4);
tmp.play_out |= (long long)1 << (j * 4 + 1);
tmp.play_out |= (long long)1 << (j * 4 + 2);
count[a[j]]--;
count[a[j] - 3]++;
a[j] -= 3;
tmp_ans = tri_straight(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
}
for (int j = i; j < i + line_count; j++)
{
a[j] += 3;
count[a[j] - 3]--;
count[a[j]]++;
}
}
}
tmp = four_two(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
return ans;
}
//双顺
Info double_straight(int a[], int count[])
{
//printf("双顺\n");
Info ans, tmp, tmp_ans;
for (int i = 0; i <= 6; i++)
{
int line_count = 0;
for (int j = i; j <= 11; j++)
{
if (a[j] >= 2)
{
line_count++;
}
else break;
}
if (line_count >= 3)
{
tmp.play_out = 0;
for (int j = i; j < i + 3; j++)
{
tmp.play_out |= (long long)1 << (j * 4);
tmp.play_out |= (long long)1 << (j * 4 + 1);
count[a[j]]--;
count[a[j] - 2]++;
a[j] -= 2;
}
tmp_ans = double_straight(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
for (int j = i + 3; j < i + line_count; j++)
{
tmp.play_out |= (long long)1 << (j * 4);
tmp.play_out |= (long long)1 << (j * 4 + 1);
count[a[j]]--;
count[a[j] - 2]++;
a[j] -= 2;
tmp_ans = double_straight(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
}
for (int j = i; j < i + line_count; j++)
{
a[j] += 2;
count[a[j] - 2]--;
count[a[j]]++;
}
}
}
tmp = tri_straight(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
return ans;
}
//单顺
Info one_straight(int a[], int count[])
{
Info ans, tmp, tmp_ans;
for (int i = 0; i <= 7; i++)
{
int line_count = 0;
for (int j = i; j <= 11; j++)
{
if (a[j] != 0)
{
line_count++;
}
else break;
}
if (line_count >= 5)
{
//printf("zzz\n");
tmp.play_out = 0;
for (int j = i; j < i + 5; j++)
{
tmp.play_out |= (long long)1 << (j * 4);
count[a[j]]--;
count[a[j] - 1]++;
a[j]--;
}
tmp_ans = one_straight(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
for (int j = i + 5; j < i + line_count; j++)
{
tmp.play_out |= (long long)1 << (j * 4);
count[a[j]]--;
count[a[j] - 1]++;
a[j]--;
tmp_ans = one_straight(a, count);
tmp.min_times = tmp_ans.min_times + 1;
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
}
for (int j = i; j < i + line_count; j++)
{
a[j]++;
count[a[j] - 1]--;
count[a[j]]++;
}
}
}
tmp = double_straight(a, count);
if (tmp.min_times < ans.min_times)
{
ans = tmp;
}
return ans;
}
void input()
{
int a[15] = { 0 };
int count[6] = { 0 };
int n, T;
scanf("%d%d", &T, &n);
while (T--)
{
for (int i = 0; i < 15; i++)
{
a[i] = 0;
}
for (int i = 0; i < 6; i++)
{
count[i] = 0;
}
int ai, bi;
for (int i = 0; i < n; i++)
{
scanf("%d%d", &ai, &bi);
if (ai == 1) a[11]++; //A
else if (ai == 0)
{
if (bi == 1) a[13]++;
else if (bi == 2) a[14]++;
}
else if (ai == 2) a[12]++; //2
else
{
ai -= 3;
a[ai]++;
}
}
for (int i = 0; i <= 12; i++)
{
count[a[i]]++;
}
count[5] += a[13];
count[5] += a[14];
/*
for (int i = 0; i <= 14; i++)
{
printf("%d ", a[i]);
}
printf("\n");
*/
/*
for (int i = 0; i <= 5; i++)
{
printf("%d ", count[i]);
}
printf("\n");
*/
Info ans = one_straight(a, count);
printf("%d\n", ans.min_times);
}
}
}noip;
int main()
{
freopen("landlords.in", "r", stdin);
freopen("landlords.out", "w", stdout);
noip.input();
return 0;
}