最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

CCSP2019T2_纸牌计数 | 2019苏州CCSP大学生计算机系统与程序设计竞赛

来源：博客园


(资料图)

题目描述

偶然在CSDN看到有人写了CCSP2019T2_纸牌计数的题解，突然想起来是一个不错的计数、dp题。以前的U盘找不到了，记得当时存了一步步偏分到AC代码，可惜。又想起来18年打铁了。。。此人的题解的链接 CCSP201902纸牌计数——解题报告当年一共有5题，取自：https://www.sohu.com/a/347851686_610300T1: 摘水果 fruitT2：纸牌计数 cardT3：系统实现题 SQL 查询T4：系统策略题 调度器 schedulerT5：系统结构体 评测鱼 risc-vT2的题面：

Description我们有一副纸牌，它由 n 张牌组成，其中每张牌上标有一个数字（0 到 9）和一个大写字母（A 到 Z），例如 2C、1F。我们如下定义一个字符串与一张牌之间的匹配关系：字符串 ?? 与任何一张牌都匹配。第一位为 ? 而第二位为字母的字符串，与任何一张标有该字母的牌匹配。例如，字符串 ?C 与任何标有 C 的牌匹配。第一位为数字而第二位为字母的字符串，仅与内容完全一致的牌匹配。例如，字符串 0C 与内容为 0C 的牌匹配。不会出现第一位为数字而第二位为 ? 的字符串。我们称 m 个字符串 S1 ... Sm 与 m 张牌 C1 ... Cm 是匹配的，当且仅当：存在集合 { 1 , … , m } 上的一一映射 σ，使得对于任意 1 ≤ i ≤ m ，Si 与 C_σ(i) 匹配。例如，对于 ?? 和 ?C 这两个字符串，可以匹配内容为 1C 和 2C 的牌，因为字符串 ?? 与内容为 2C 的牌匹配且字符串 ?C 与内容为 1C 的牌匹配，而 ?? 和 ?C 这两个字符串不能匹配内容为 1S 和 1P 的牌。现在，给定 m 个字符串，你需要求解：如果在 n 张牌中（无放回地）随机选取 m 张，有多大概率与这些字符串匹配？Input每个输入文件包含多个输入数据。第一行输入该文件的数据个数 T。接下来依次输入每个数据。每个数据包含三行，其中：第一行输入两个正整数 n 和 m；第二行输入以空格分隔的 n 个字符串，表示每张纸牌的内容（每个字符串第一位为数字，第二位为大写字母）；第三行输入以空格分隔的 m 个字符串，表示每个需要匹配的字符串（每个字符串第一位为数字，第二位为大写字母；或第一位为 ?，第二位为大写字母；或为 ??）。Output对于每个输入数据，输出一行，表示所求的概率。概率需要以最简分数 u/v 的形式输出，其中 0 ≤ u ≤ v 且 u, v 为互质的整数。特殊地，对于 0 请输出 0/1，对于 1 请输出 1/1。Subtasks对于所有的数据，1 <= m <= n <= 60, T <= 1000, $1 \leq m \leq n \leq 60; T \leq 1000$。（11分）m=1；（23分）m=n；（27分）n=30 且所有的牌为 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P；（22分）n=40 且所有的牌为 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P；（17分）没有特殊的限制。

题解

一时间不记得咋写的了，按记忆口胡了一个做法，感觉复杂度有点假，但好像跑不满，以后再看看吧：

  • 求概率/期望的时候，两个独立事件（即正交的情况）可以分开考虑，答案为每个事件概率的乘积。类似于积性函数中的一些理念。
  • n张牌的字母都是固定的，一般m个字符串的字母也是固定的（除非是两个问号??）。
  • 考虑是否可以先分26个字母考虑，再考虑??。
  • rdp[j][k] 表示考虑到数字j用了k个问号的（不）合法情况数（合不合法，即是否存在重复计数的），把单个?的情况用组合数计数分配一下
  • 现在 ?? 还没处理吧，所以??可以在这个层次上再套一层dp
  • val[i][w] 表示考虑到字母i已经用了w个??的合法方案数，最后背包dp一遍求答案
  • （不确定有没有爆 long long，感觉复杂度可以减掉一个60？
#include #define fi first#define se second#define o2(x) (x) * (x)#define mk make_pair#define eb emplace_back#define SZ(x) ((int)(x).size())#define all(x) (x).begin(), (x).end()#define clr(a, b) memset((a), (b), sizeof((a)))#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)#define per(i, s, t) for(register int i = (s), LIM=(t); i > LIM; --i)#define GKD std::ios::sync_with_stdio(false);cin.tie(0)#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())using namespace std;typedef long long LL;typedef long long int64;typedef unsigned long long uint64;typedef pair pii;// mt19937 rng(time(NULL));//std::clock()// mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());// shuffle(arr, arr + n, rng64);inline int64 read() {    int64 x = 0;int las = 0;char ch = getchar();    while (ch < "0" || ch > "9") las |= (ch == "-"), ch = getchar();    while (ch >= "0" && ch <= "9") x = (x << 3) + (x << 1) + ch - "0", ch =    getchar(); return x = las ? -x : x;}inline void write(int64 x, bool las = true) {    if (x == 0) {putchar("0"); if(las)putchar("\n");else putchar(" ");return;}    if (x < 0) {putchar("-");x = -x;}    static char s[23];    int l = 0;    while (x != 0)s[l++] = x % 10 + 48, x /= 10;    while (l)putchar(s[--l]);    if(las)putchar("\n");else putchar(" ");}int lowbit(int x) { return x & (-x); }template T big(const T &a1, const T &a2) {return a1 > a2 ? a1 : a2;}template T sml(const T &a1, const T &a2) {return a1 < a2 ? a1 : a2;}template T big(const T &las, const R &... r) {return big(las, big(r...));}template T sml(const T &las, const R &... r) {return sml(las, sml(r...));}void debug_out() { cout << "\n"; }template void debug_out(const T &las, const R &... r) {    cout << las << " ";    debug_out(r...);}#ifdef LH_LOCAL#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);#else#define debug(...) ;#endif#define debug(...) ;/*================Header Template==============*/const int mod = 998244353;// 998244353int ksm(int a, int64 b, int kmod = mod) {int res = 1;for(;b > 0;b >>= 1, a = (int64)a * a % kmod) if(b &1) res = (int64)res * a % kmod;return res;}const int INF = 0x3f3f3f3f;const int MXN = 2e5 + 5;const int MXM = 5e6 + 7;int n, m;char card[65][3], str[65][3];// 0 <= . <= 9, A <= . <= Z  -> 1 <= . <= 10int cnt[30][15], need[30][15];int sum[2][30];LL fdp[30], rdp[15][65], val[30][65], dp[30][65];LL COMB(int n, int m) {    if(n == m) return 1;    if(n < m) return 0;    LL res = 1;    for(int i = 0; i < m; ++i) {        res *= (n - i);        res /= i + 1;    }    return res;}void work() {    n = read(), m = read();    for(int i = 1; i <= n; ++i) scanf("%s", card[i]);    for(int i = 1; i <= m; ++i) scanf("%s", str[i]);    int flag = 1;    for(int i = 1; i <= n; ++i) {        cnt[card[i][1] - "A"][card[i][0] - "0" + 1] ++;        sum[0][card[i][1] - "A"] ++;    }    LL ww = m;    for(int i = 1; i <= m; ++i) {        if(str[i][1] != "?") {            if(str[i][0] != "?") need[str[i][1] - "A"][str[i][0] - "0" + 1] ++;            else need[str[i][1] - "A"][0] ++;            sum[1][str[i][1] - "A"] ++;            ww --;        }    }    LL res = 1;    for(int i = 0; i < 26; ++i) {        if(sum[0][i] < sum[1][i]) {            flag = 0;            break;        }        for(int w = 0; w <= ww; ++w) {            need[i][0] += w;            fdp[i] = 1;            memset(rdp, 0, sizeof(rdp));            rdp[0][0] = 1;            // rdp[j][k] 表示考虑到数字j用了k个问号的（不）合法情况数（合不合法，即是否存在重复计数的）            // 把单个?的情况用组合数计数分配一下            // ?? 还没处理吧，所以??可以在这个层次上再套一层dp            // val[i][w] 表示考虑到字母i已经用了w个??的合法方案数            for(int j = 1; j <= 10; ++j) {                if(cnt[i][j] < need[i][j]) {                    flag = 0;                    break;                }                fdp[i] = fdp[i] * COMB(cnt[i][j], need[i][j]);                // for(int k = 0; k <= need[i][0]; ++k) rdp[j][k] = rdp[j - 1][k];                if(1 || cnt[i][j] > need[i][j] && need[i][j] > 0) {                    for(int h = 0; h <= cnt[i][j] - need[i][j]; ++h) {                        for(int k = h; k <= need[i][0]; ++k) {                            rdp[j][k] = rdp[j][k] + rdp[j - 1][k - h] * COMB(cnt[i][j], need[i][j] + h);                            // debug(h, j, k, rdp[j][k])                        }                    }                    // if(i == "C" - "A") debug(j)                }else {                    // if(i == "C" - "A") debug(j, rdp[j][1], rdp[j - 1][1])                }            }            // rdp[10][0] = 0;            fdp[i] = fdp[i] * COMB(sum[0][i] - (sum[1][i] - need[i][0]), need[i][0]);            LL ret = rdp[10][need[i][0]];            if(i == "C" - "A") debug(i, w, need[i][0], fdp[i], rdp[10][need[i][0]], fdp[i] - rdp[10][need[i][0]], ret, fdp[i] - ret)            res *= (ret);            need[i][0] -= w;            val[i][w] = ret;            if(i == "C" - "A" && val[i][w] > 1) debug(i, w, val[i][w])        }    }    for(int j = 0; j <= ww; ++j) dp[0][j] = val[0][j];    for(int i = 1; i < 26; ++i) {        for(int j = 0; j <= ww; ++j) {            for(int k = 0; k <= j; ++k) {                dp[i][j] = dp[i][j] + dp[i - 1][j - k] * val[i][k];            }        }    }    res = dp[25][ww];    LL allcase = COMB(n, m);    LL agcd = __gcd(allcase, res);    debug(allcase, res, res / agcd, allcase / agcd)    if(flag == 0) {        printf("0/1\n");    }else {        printf("%lld/%lld\n", res / agcd, allcase / agcd);    }    // 不确定有没有爆 long long    for(int i = 0; i < 26; ++i) {        sum[0][i] = sum[1][i] = 0;        for(int j = 0; j <= 10; ++j) {            cnt[i][j] = need[i][j] = 0;        }        for(int j = 0; j <= ww; ++j) {            val[i][j] = 0;            dp[i][j] = 0;        }    }}int main() {#ifdef LH_LOCAL    freopen("c:/lh/system-lab/acm_code/OJ/in.txt", "r", stdin);    // freopen("c:/lh/system-lab/acm_code/OJ/out.txt", "w", stdout);#endif    for(int cas = 1, tim = (1 ? read(): 1); cas <= tim; ++ cas) {        work();    }    // 56160000    debug(26*60*10*60*60)#ifdef LH_LOCAL    cout << "Debug log: time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl;#endif    return 0;}/*340 20C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P?C 1C40 160C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P0C 0C 1C 2C ?C ?C ?C ?C 3S 4S ?S ?S 5P 6P ?P ?P60 301A 1B 1C 1D 1E 1F 1G 1H 1I 1J 1K 1L 1M 1N 1O 1P 1Q 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 0A 1A 2A 3A 4A 5A 6A 7A 8A 9A 1S 3S 5S 7S 9S 0U 2U 4U 6U 8U 2Z 3Z 5Z 7Z 1C 1C 1C 1C 1C 1C 1C 1C 1S 1P1C 1C 1S 1P 2A 0A 1A 9A ?S ?U ?Z ?H ?O ?U ?? ?? ?? ?? ?? ?? ?S ?S ?S ?U ?U ?U ?Z ?Z ?C ?C37/780167384/2417388525  -> 4351984/x -> 5551 * 28 * 2850442363273/29566145391215356 -> 201769453092/xSampleInput156 10C 0S 0P 1C 1S 1P1S6 10C 0S 0P 1C 1S 1P?C6 20C 0S 0P 1C 1S 1P?C ?C6 20C 0S 0P 1C 1S 1P?C ?S6 40C 0S 0P 1C 1S 1P?C ?C ?S ?P6 40C 0S 0P 1C 1S 1P0C ?C ?S ?P6 40C 0S 0P 1C 1S 1P?C ?C ?S ??6 40C 0S 0P 1C 1S 1P?C ?C ?? ??6 40C 0S 0P 1C 1S 1P?A ?? ?? ??6 40C 0S 0P 1C 1S 1P0C 0C ?S ?P30 80C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P0C ?C ?C ?C 1S ?S 2P ?P40 20C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P?C 1C40 20C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P?C 1S40 160C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0C 1C 2C 3C 4C 5C 6C 7C 8C 9C 0S 1S 2S 3S 4S 5S 6S 7S 8S 9S 0P 1P 2P 3P 4P 5P 6P 7P 8P 9P0C 0C 1C 2C ?C ?C ?C ?C 3S 4S ?S ?S 5P 6P ?P ?P60 301A 1B 1C 1D 1E 1F 1G 1H 1I 1J 1K 1L 1M 1N 1O 1P 1Q 1R 1S 1T 1U 1V 1W 1X 1Y 1Z 0A 1A 2A 3A 4A 5A 6A 7A 8A 9A 1S 3S 5S 7S 9S 0U 2U 4U 6U 8U 2Z 3Z 5Z 7Z 1C 1C 1C 1C 1C 1C 1C 1C 1S 1P1C 1C 1S 1P 2A 0A 1A 9A ?S ?U ?Z ?H ?O ?U ?? ?? ?? ?? ?? ?? ?S ?S ?S ?U ?U ?U ?Z ?Z ?C ?COutput1/61/31/154/154/154/151/32/50/10/1252/21677537/7801/39167384/241738852550442363273/29566145391215356Hint对于分数 a/b，设 g=gcd(a,b)，那么其最简分数形式为 (a/g)/(b/g)。*/

关键词：