[Niuke2021-8-I] The Grand Tournament [模拟/状压DP/乱搞/组合数学?]
空気浮遊
2021年08月10日
笑话：牛奶饮料倒键盘上了，之后凝结成晶体，按下去又软又脆；队友：变成了奶轴
Problem
https://ac.nowcoder.com/acm/contest/11259/I
Solution
找 45 个点的无向图上 5 个匹配的方案数
看不懂题解（式子很对但算这个式子的复杂度不对啊 kora，而且超难写）
但 THU 和几个过了的代码用的都是某种神秘的 dp
适用于状态数实际上不太多的情况？例如 55 选 5 的状态压缩，不用 55 的二进制数而用 55 个随机数中数个数的异或值作为有没有被选择的状态。
随后就是一堆关于德普的大模拟（我为什么没玩 rdr2 的德普小游戏，我要是玩了会是这个吊样.jpg）
在调试模拟题的途中总是能深刻地认识到自己是个傻逼这件事...
Code
#include<bits/stdc++.h>
using namespace std;
// Head
/// Read
#define ENABLED_FREAD
#ifdef ENABLED_FREAD
namespace Fread
{
#define BUF_SIZE 1<<21
char cb[BUF_SIZE],*cs,*ct;
#define getc (cs==ct&&(ct=(cs=cb)+fread(cb,1,BUF_SIZE,stdin),cs==ct)?0:*cs++)
template<class T>inline void gn(T &num)
{
char ch;int flag=1;
while(!isdigit(ch=getc))if(ch=='-')flag=-flag;
for(num=ch-'0';isdigit(ch=getc);num=num*10+ch-'0');
num*=flag;
}
inline char gc()
{
char ch;
while(!isdigit(ch=getc) && !isalpha(ch));
return ch;
}
#undef getc
}
using namespace Fread;
#else
template<typename T>inline void gn(T &x) {
char ch=getchar(), pl=1; x=0;
while(!isdigit(ch)) pl=(ch=='-'?-1:1), ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
x*=pl;
}
#endif
/// Rand
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l,r)(rng)
#define rreal(l, r) uniform_real_distribution<double>(l,r)(rng)
/// Typedef
typedef long long ll;
typedef pair<int, int> ipair;
// Definition
int Cardtype[500];
int Cardrank[500];
const char types[] = "CDHS";
const char ranks[] = "23456789TJQKA";
struct Card {
int ty, rk, sp;
Card(char a=0, char b=0) {
ty=Cardtype[a];
rk=Cardrank[b];
sp=0;
}
int gid() {
return (ty-1)*13+rk-1;
}
void put() {
putchar(types[ty-1]), putchar(ranks[rk-1]);
}
} ;
void gbinit() {
Cardtype['C']=1;
Cardtype['D']=2;
Cardtype['H']=3;
Cardtype['S']=4;
Cardrank['2']=1;
Cardrank['3']=2;
Cardrank['4']=3;
Cardrank['5']=4;
Cardrank['6']=5;
Cardrank['7']=6;
Cardrank['8']=7;
Cardrank['9']=8;
Cardrank['T']=9;
Cardrank['J']=10;
Cardrank['Q']=11;
Cardrank['K']=12;
Cardrank['A']=13;
}
bool cmp(const Card &a, const Card &b) {
return a.sp==b.sp?a.rk>b.rk:a.sp>b.sp;
}
struct Comb {
vector<Card> cd;
int ty;
Comb(vector<Card> x) {
assert(x.size()==5);
sort(x.begin(), x.end(), cmp);
bool flush=1;
int dif=1;
bool straight = true;
bool spec_str = true;
for(int i=0; i<4; i++) {
if(x[i].rk!=x[i+1].rk+1) straight = 0;
if(i>=1 && x[i].rk!=x[i+1].rk+1) spec_str = 0;
if(x[i].rk==x[i+1].rk) x[i].sp=x[i+1].sp=1;
else dif++;
if(x[i].ty!=x[i+1].ty) flush=0;
}
if(spec_str && x[0].rk==13 && x[4].rk==1) straight=1;
else spec_str=0;
for(int i=0; i<3; i++) {
if(x[i].rk==x[i+1].rk && x[i+1].rk==x[i+2].rk)
x[i].sp=x[i+1].sp=x[i+2].sp=2;
}
for(int i=0; i<2; i++) {
if(x[i].rk==x[i+1].rk && x[i+1].rk==x[i+2].rk && x[i+2].rk==x[i+3].rk)
x[i].sp=x[i+1].sp=x[i+2].sp=x[i+3].sp=3;
}
sort(x.begin(), x.end(), cmp);
// Royal flush
if(straight && x[0].rk==13 && flush && !spec_str)
ty=0;
// Straight flush
else if(straight && flush)
ty=1;
// Four of a Kind
else if(dif==2 && x[0].sp==3)
ty=2;
// Full House
else if(dif==2 && x[0].sp==2)
ty=3;
// Flush
else if(flush)
ty=4;
// Straight
else if(straight)
ty=5;
// Three of a kind
else if(dif==3 && x[0].sp==2)
ty=6;
// Two Pairs
else if(dif==3 && x[0].sp==1)
ty=7;
// One Pair
else if(dif==4)
ty=8;
// High Card
else ty=9;
if(spec_str) {
x[0].rk=0;
sort(x.begin(), x.end(), cmp);
}
cd=x;
}
Comb () { ty=114514; }
bool operator > (const Comb &b) {
if(ty<b.ty) return true;
else if(ty==b.ty) {
for(int i=0; i<5; i++)
if(cd[i].rk>b.cd[i].rk) return true;
else if(cd[i].rk<b.cd[i].rk) return false;
}
return false;
}
void put () {
for(int i=0; i<5; i++)
cd[i].put(), putchar(' ');
putchar('\n');
}
} ;
Card rca() {
char a=gc(), b=gc();
Card ret(a, b);
return Card(a, b);
}
const int N=20;
Comb mbig(vector<Card> x) {
assert(x.size()==7);
Comb ret;
for(int i=0; i<7; i++)
for(int j=i+1; j<7; j++) {
vector<Card> nx;
for(int k=0; k<7; k++)
if(k!=i && k!=j) nx.emplace_back(x[k]);
Comb ncx(nx);
if(ncx>ret) ret=ncx;
}
return ret;
}
vector<Card> cmuca;
Card ia, ib;
int E[100][100];
uint64_t hah[100];
unordered_map<uint64_t, ll> dp[100][10];
int occ[100];
ll dfs(int x, int c, uint64_t nha) {
if(c==5) return 1;
if(x==55) return 0;
if(occ[x]) return dfs(x+1, c, nha);
if(dp[x][c].count(nha)) return dp[x][c][nha];
ll sum = dfs(x+1, c, nha^hah[x]);
for(int i=x+1; i<55; i++)
if(!occ[i] && E[x][i]) {
occ[i]=1;
sum+=dfs(x+1, c+1, nha^hah[x]^hah[i]);
occ[i]=0;
}
return dp[x][c][nha]=sum;
}
int main() {
gbinit();
ll TOT=3014726985270ll;
ia=rca(), ib=rca();
Card nc, nd;
occ[ia.gid()]=occ[ib.gid()]=1;
for(int i=0; i<5; i++) {
cmuca.emplace_back(nc=rca());
occ[nc.gid()]=1;
}
vector<Card> nx=cmuca;
nx.emplace_back(ia), nx.emplace_back(ib);
Comb my=mbig(nx);
int nci, ndi;
for(int i=0; i<4; i++)
for(int j=0; j<13; j++)
for(int k=0; k<4; k++)
for(int l=0; l<13; l++) {
nc=Card(types[i], ranks[j]);
nd=Card(types[k], ranks[l]);
nci=nc.gid(), ndi=nd.gid();
if(nci!=ndi && !occ[nci] && !occ[ndi]) {
nx=cmuca;
nx.emplace_back(nc), nx.emplace_back(nd);
if(my>mbig(nx))
E[nci][ndi]=1;
}
}
for(int i=0; i<100; i++) hah[i]=rng();
ll suba=dfs(0, 0, 0);
ll gc=__gcd(suba, TOT);
if(suba==0) puts("0/1");
else
printf("%lld/%lld\n", suba/gc, TOT/gc);
return 0;
}本文链接：https://pst.iorinn.moe/archives/niuke-2021-8-i.html
许可： https://pst.iorinn.moe/license.html若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆