[Niuke2021-8-I] The Grand Tournament [模拟/状压DP/乱搞/组合数学?]

Author Avatar
空気浮遊 8月10日
  • 在其它设备中阅读本文章

笑话:牛奶饮料倒键盘上了,之后凝结成晶体,按下去又软又脆;YJ:变成了奶轴

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://acxblog.site/archives/niuke-2021-8-i.html
博客以 CC BY-NC-SA 4.0 协议进行许可。