CCSP201902纸牌计数——解题报告

2024-04-13 03:08

本文主要是介绍CCSP201902纸牌计数——解题报告,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目如下:

Description
我们有一副纸牌,它由 nn 张牌组成,其中每张牌上标有一个数字(0 到 9)和一个大写字母(A 到 Z),例如 2C、1F。

我们如下定义一个字符串与一张牌之间的匹配关系:

字符串 ?? 与任何一张牌都匹配。
第一位为 ? 而第二位为字母的字符串,与任何一张标有该字母的牌匹配。例如,字符串 ?C 与任何标有 C 的牌匹配。
第一位为数字而第二位为字母的字符串,仅与内容完全一致的牌匹配。例如,字符串 0C 与内容为 0C 的牌匹配。
不会出现第一位为数字而第二位为 ? 的字符串。
我们称 m 个字符串 S 1 , … , S m S_1, \dots, S_m S1,,Sm与 m 张牌 C 1 , … , C m C_1, \dots, C_m C1,,Cm​ 是匹配的,当且仅当:存在集合 { 1 , … , m } \{1, \dots, m\} {1,,m} 上的一一映射 σ \sigma σ,使得对于任意 1 ≤ i ≤ m , S i 与 C σ ( i ) 1 \le i \le m,S_i与 C_{\sigma(i)} 1imSiCσ(i)匹配。

例如,对于 ?? 和 ?C 这两个字符串,可以匹配内容为 1C 和 2C 的牌,因为字符串 ?? 与内容为 2C 的牌匹配且字符串 ?C 与内容为 1C 的牌匹配,而 ?? 和 ?C 这两个字符串不能匹配内容为 1S 和 1P 的牌。

现在,给定 mm 个字符串,你需要求解:如果在 nn 张牌中(无放回地)随机选取 mm 张,有多大概率与这些字符串匹配?

Input
每个输入文件包含多个输入数据。

第一行输入该文件的数据个数 TT。

接下来依次输入每个数据。每个数据包含三行,其中:

第一行输入两个正整数 n 和 m;
第二行输入以空格分隔的 n 个字符串,表示每张纸牌的内容(每个字符串第一位为数字,第二位为大写字母);
第三行输入以空格分隔的 m 个字符串,表示每个需要匹配的字符串(每个字符串第一位为数字,第二位为大写字母;或第一位为 ?,第二位为大写字母;或为 ??)。

Output
对于每个输入数据,输出一行,表示所求的概率。概率需要以最简分数 u/vu/v 的形式输出,其中 0 ≤ u ≤ v 0≤u≤v 0uv 且 u, v 为互质的整数。

特殊地,对于 0 请输出 0/1,对于 1 请输出 1/1。

Sample
Input
15
6 1
0C 0S 0P 1C 1S 1P
1S
6 1
0C 0S 0P 1C 1S 1P
?C
6 2
0C 0S 0P 1C 1S 1P
?C ?C
6 2
0C 0S 0P 1C 1S 1P
?C ?S
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?S ?P
6 4
0C 0S 0P 1C 1S 1P
0C ?C ?S ?P
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?S ??
6 4
0C 0S 0P 1C 1S 1P
?C ?C ?? ??
6 4
0C 0S 0P 1C 1S 1P
?A ?? ?? ??
6 4
0C 0S 0P 1C 1S 1P
0C 0C ?S ?P
30 8
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
0C ?C ?C ?C 1S ?S 2P ?P
40 2
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
?C 1C
40 2
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
?C 1S
40 16
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
0C 0C 1C 2C ?C ?C ?C ?C 3S 4S ?S ?S 5P 6P ?P ?P
60 30
1A 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 1P
1C 1C 1S 1P 2A 0A 1A 9A ?S ?U ?Z ?H ?O ?U ?? ?? ?? ?? ?? ?? ?S ?S ?S ?U ?U ?U ?Z ?Z ?C ?C
Output
1/6
1/3
1/15
4/15
4/15
4/15
1/3
2/5
0/1
0/1
252/216775
37/780
1/39
167384/2417388525
50442363273/29566145391215356
Hint
对于分数 a/ba/b,设 g=\gcd(a,b)g=gcd(a,b),那么其最简分数形式为 (a/g)/(b/g)(a/g)/(b/g)。

gcd ⁡ ( a , b ) \gcd(a,b) gcd(a,b) 可以这样计算:如果 a=0 则答案为 b,否则为 gcd ⁡ ( b m o d a , a ) \gcd(b \bmod a, a) gcd(bmoda,a)(需递归计算)。

Subtasks
对于所有的数据, 1 ≤ m ≤ n ≤ 60 ; T ≤ 1000 1 \leq m \leq n \leq 60;T \leq 1000 1mn60T1000

(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个字符串( m ≤ n m\leq n mn),这里的字符串有三种情况,①双问号??,②问号+字母,如?C,③数字加字母,如1C。(必定不会出现数字+问号的形式)。要求从n张牌里面取出m张牌,求这m张牌与m个字符串能建立一一匹配的概率。这里的字符串都是2个字符组成,且数字为0-9,字母为A-Z。
匹配规则:字符串中数字+字母的必须匹配带有同样的数字+字母的纸牌;问号+字母的匹配任意带有相同字母的纸牌;双问号可以匹配任何纸牌。

第一阶段:(0-34)分
对于m=1的情况,显然把n个字符串都遍历一遍即可。
对于m=n的情况,优先匹配m个字符串中数字明确的,再匹配字母明确的即可。

cnt1 = cnt2 = cnt3 = 0;
for (int i = 1; i <= m; i++) {if (c[i][0] == '?') {if (c[i][1] == '?')ggg[++cnt3] = i;//??else gg[++cnt2] = i;//?C}else g[++cnt1] = i;//NC
}
if (m == 1) {int cnt = 0;for (int i = 1; i <= n; i++)if (isMatch(s[i], c[1]))cnt++;printf("%llu/%llu\n", (ull)cnt / gcd(cnt, n), (ull)n / gcd(cnt, n));
}
else if (m == n) {int tag[100] = { 0 }, judge = 0;for (int i = 1; i <= cnt1; i++) {//优先匹配数字+字母int x = g[i]; judge = 1;for (int j = 1; j <= n; j++) {if (tag[j])continue;if (isMatch(s[j], c[x])) {//匹配成功judge = 0; tag[j] = 1; break;}}//不能匹配if (judge)break;}if (!judge) {for (int i = 1; i <= cnt2; i++) {//匹配问号+字母int x = gg[i]; judge = 1;for (int j = 1; j <= n; j++) {if (tag[j])continue;//没被选入或已经匹配if (isMatch(s[j], c[x])) {//匹配成功judge = 0; tag[j] = 1; break;}}//不能匹配if (judge)break;}}if (!judge)printf("1/1\n");else printf("0/1\n");

第二阶段:(35-61)分
不考虑正解,在前面的基础上再加上只针对n=30的情况。
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。
利用排列组合,所有的情况数目 a l l = C m n all=C_m^n all=Cmn,对于所有能匹配的情况,必定是m个字符串中数字明确的字符串都从n个里面被选中了,设其个数为 f i x e d fixed fixed,剩下还要从30-fixed个里面再拿m-fixed个字符串。
那么可以先计算 C 30 − f i x e d m − f i x e d C_{30-fixed}^{m-fixed} C30fixedmfixed,然后再用它减去不合法的情况即为答案。
不合法的情况可以先考虑单个字母不合条件的情况,比如考虑字母C,设在m个字符串中有tot个是数字+C,有sum个包含C,被选取的fixed已经包含了tot了,那么至少还要选取sum-tot个带C字母的串。那么不合法的情况就是选取带C字母的串的个数小于sum-tot的情况。即 C 10 − t o t i × C 30 − f i x e d + t o t m − f i x e d − i ( i = 0 , 1 , . . . , s u m − t o t − 1 ) C_{10-tot}^i \times C_{30-fixed+tot}^{m-fixed-i}(i=0,1,...,sum-tot-1) C10toti×C30fixed+totmfixedi(i=0,1,...,sumtot1),对于字母S和P同理。
但是当只考虑单字母时,其实里面包含了两个字母同时不合条件的情况,如果有某些情况C和S同时不合条件,则考虑C时候减去一次,考虑S时也减去一次。因此还要把这些次数加回来。计算的方式就是把上面的一维的情况变成二维的,具体可看下述代码。
显然不存在三个字母都不合条件的情况。

if (n == 30 && Cas == 3) {//tot表示C\S\P,明确了数字部分的纸牌分别出现的次数//sum表示C\S\P分别出现的次数(包括问号+字母和数字+字母) //num表示确定某个明确了数字和字母的牌数,必须小于等于1int num[50] = { 0 }, tot[3] = { 0 }, sum[3] = { 0 }, judge = 0;for (int i = 1; i <= m; i++) {int x = -1;if (c[i][1] == 'C') {if (c[i][0] != '?')x = c[i][0] - '0', tot[0]++;sum[0]++;}if (c[i][1] == 'S') {if (c[i][0] != '?')x = c[i][0] - '0' + 10, tot[1]++;sum[1]++;}if (c[i][1] == 'P') {if (c[i][0] != '?')x = c[i][0] - '0' + 20, tot[2]++;sum[2]++;}if (x != -1)num[x]++;if (num[x] > 1) {//必定不匹配judge = 1; break;}}if (judge) {printf("0/1\n"); continue;}int fixed = tot[0] + tot[1] + tot[2];//必须要取的fixed个int lef = m - fixed;//剩余要抽的牌数ull res = Cmn(n - fixed, m - fixed);//对剩下m-fixed个全部取出来的情况数for (int i = 0; i < 3; i++) {//考虑单个字母,即C\S\P其中一个,要减去这个字母不符合条件的所有情况//考虑到每种情况实际上还能划分为1、只有当前字母不符合条件,2、另有一个字母也不符合条件//根据对称性,两个字母同时不符合条件的情况会被多减去一次for (int j = 0; j < sum[i] - tot[i]; j++) {res -= Cmn(10 - tot[i], j) * Cmn(n - fixed - 10 + tot[i], lef - j);}}//在上面减去的情况中,两个字母同时不符合的情况要加回来for (int i = 0; i < 2; i++)for (int j = i + 1; j < 3; j++)for (int x = 0; x < sum[i] - tot[i]; x++)for (int y = 0; y < sum[j] - tot[j]; y++) {res += Cmn(10 - tot[i], x) * Cmn(10 - tot[j], y) * Cmn(n - fixed - 20 + tot[i] + tot[j], lef - x - y);}//显然,不会出现三个字母都不符合的情况ull all = Cmn(n, m);printf("%llu/%llu\n", res / gcd(res, all), all / gcd(res, all));
}

第三阶段:(62-83)分
不考虑正解,在前面的基础上再加上只针对n=40的情况。
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。
该情况与n=30相比就是字母C的字符串多了一倍。这个改变使得如果数字+C恰好出现一次的串可以有两种选择。
简要说下思路:
思路继承于n=30的情况,假设数字+C恰好出现一次的有cnt个,如果从n-fixed个串里面不选和它们相同的串,那么就有 2 c n t 2^{cnt} 2cnt种情况,如果n-fixed个串里面有一个是和它们中的某个串相同,那么有 C c n t 1 × 2 c n t − 1 C_{cnt}^1\times 2^{cnt-1} Ccnt1×2cnt1种情况,以此类推从n-fixed里面有i个是与这些恰好出现一次的字符串的某些串相同,则有 C c n t i × 2 c n t − i C_{cnt}^i\times 2^{cnt-i} Ccnti×2cnti种情况,每一个i对应一个解,其解法和n=30的情况相同。

注意:对于每个求组合数,a中取b时,b一定要是合法的情况,否则跳过。

if (n == 40 && Cas == 4) {int num[50] = { 0 }, tot[3] = { 0 }, sum[3] = { 0 }, judge = 0;for (int i = 1; i <= m; i++) {int x = -1;if (c[i][1] == 'C') {if (c[i][0] != '?')x = c[i][0] - '0', tot[0]++;sum[0]++;}if (c[i][1] == 'S') {if (c[i][0] != '?')x = c[i][0] - '0' + 10, tot[1]++;sum[1]++;}if (c[i][1] == 'P') {if (c[i][0] != '?')x = c[i][0] - '0' + 20, tot[2]++;sum[2]++;}if (x != -1)num[x]++;if (x >= 10 && num[x] > 1) {//必定不匹配judge = 1; break;}if (x >= 0 && x < 10 && num[x]>2) {judge = 1; break;}}if (judge) {printf("0/1\n"); continue;}int cnt = 0;int fixed = tot[0] + tot[1] + tot[2];int lef = m - fixed;//剩余要抽的牌数for (int i = 0; i < 10; i++)if (num[i] == 1) {cnt++;}//将?C出现过的数字设置为不能再选ull res = 0;for (int k = 0; k <= cnt; k++) {//每次增加某个只出现一次的?C,使得两个相同的?C都被选中,即相当于被固定选择的牌多了一张if (m < fixed + k)continue;//注意,可能牌不够抽ull tmp = Cmn(n - cnt - fixed, m - fixed - k);for (int i = 0; i < 2; i++)for (int j = i + 1; j < 3; j++)//对于字母C,被固定的牌有tot[i]+k张for (int x = 0; x < (i == 0 ? sum[i] - tot[i] - k : sum[i] - tot[i]); x++) {for (int y = 0; y < sum[j] - tot[j]; y++) {if (lef - k - x - y < 0)continue;//避免越界的情况tmp += Cmn((i == 0 ? 20 - cnt : 10) - tot[i], x) * Cmn(10 - tot[j], y) * Cmn(n - fixed - (i == 0 ? 30 : 20 + cnt) + tot[i] + tot[j], lef - k - x - y);}}for (int i = 0; i < 3; i++) {for (int j = 0; j < (i == 0 ? sum[i] - tot[i] - k : sum[i] - tot[i]); j++) {if (lef - k - j < 0)continue;//避免越界的情况tmp -= Cmn((i == 0 ? 20 - cnt : 10) - tot[i], j) * Cmn(n - fixed - (i == 0 ? 20 : 10 + cnt) + tot[i], lef - k - j);}}for (int i = 1; i <= cnt - k; i++) tmp <<= 1;res += Cmn(cnt, k) * tmp;}ull all = Cmn(n, m);printf("%llu/%llu\n", res / gcd(res, all), all / gcd(res, all));
}

第四阶段:(84-100)分
直接求正解,和前面的阶段几乎没有什么联系。
std解法,DP求解,解释可看其中的注释。

ull have[30][15] = { 0 }, Cas = 0;
for (int i = 1; i <= n; i++) {have[s[i][1] - 'A' + 1][s[i][0] - '0' + 1]++;
}
ull havex[30] = { 0 }, needx[30] = { 0 }, need[30][15] = { 0 }, cof[30][65] = { 0 };
ull shave[30][20] = { 0 }, sshave[30] = { 0 }, sdp[20][65] = { 0 }, dp[30][65] = { 0 };
for (int i = 1; i <= n; i++) {havex[s[i][1] - 'A' + 1]++;
}
for (int i = 1; i <= m; i++) {if (c[i][1] != '?')needx[c[i][1] - 'A' + 1]++;if (c[i][0] != '?')need[c[i][1] - 'A' + 1][c[i][0] - '0' + 1]++;
}
for (int a = 1; a <= 26; a++)
for (int i = 1; i <= 10; i++) {shave[a][i] = have[a][i] + shave[a][i - 1];//每个字母,数字从0-9的前缀和
}
for (int a = 1; a <= 26; a++)
sshave[a] = shave[a][10] + sshave[a - 1];//字母A-Z的前缀和
//先算数字+字母的部分
for (int a = 1; a <= 26; a++) {//这里的合法情况只考虑明确了数字和字母的牌sdp[0][0] = 1;for (int i = 1; i <= 10; i++) {//sdp[i][k]表示选到数字i为止,一共选取k张牌的所有合法情况for (int j = need[a][i]; j <= have[a][i]; j++) {for (int k = j; k <= shave[a][i]; k++) {sdp[i][k] += sdp[i - 1][k - j] * Cmn(have[a][i], j);}}}for (int k = 0; k < 65; k++)cof[a][k] = sdp[10][k];memset(sdp, 0, sizeof(sdp));
}
dp[0][0] = 1;//这里的合法情况比上面多保证了?+字母的情况
for (int a = 1; a <= 26; a++) {//dp[a][k]表示选到字母a为止,一共选了k张牌的所有合法情况for (int j = needx[a]; j <= havex[a]; j++) {for (int k = j; k <= sshave[a]; k++) {dp[a][k] += dp[a - 1][k - j] * cof[a][j];}}
}
ull all = Cmn(n, m), _g = gcd(dp[26][m], all);
printf("%llu/%llu\n", dp[26][m] / _g, all / _g);

完整代码如下:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
char s[100][5], c[100][5], done[100];
int g[100], gg[100], ggg[100], cnt1, cnt2, cnt3;//cnt1表示明确了数字和字母的数目,对应g数组
int t, n, m;                                    //cnt2表示问号+字母的数目,cnt3表示??的数目,分别对应gg和ggg数组
ull gcd(ull a, ull b) {return b == 0 ? a : gcd(b, a % b);
}
inline bool isMatch(char* ss, char* cc) {if (cc[0] == '?') {if (cc[1] == '?')return true;else if (cc[1] == ss[1])return true;}else if (cc[0] == ss[0] && cc[1] == ss[1])return true;return false;
}
inline ull Cmn(ull m, ull n) {ull res = 1;for (ull i = 0; i < n; i++) {res *= (m - i);res /= (i + 1);}return res;
}
int main(void) {//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);scanf("%d", &t);while (t--) {scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++)scanf("%s", s[i]);for (int i = 1; i <= m; i++)scanf("%s", c[i]);int flag = 0;for (int i = 1; i <= m; i++) {flag = 1;for (int j = 1; j <= n; j++) {if (isMatch(s[j], c[i])) {flag = 0; break;}}if (flag)break;}if (flag) {printf("0/1\n"); continue;}cnt1 = cnt2 = cnt3 = 0;for (int i = 1; i <= m; i++) {if (c[i][0] == '?') {if (c[i][1] == '?')ggg[++cnt3] = i;//??else gg[++cnt2] = i;//?C}else g[++cnt1] = i;//NC}if (m == 1) {int cnt = 0;for (int i = 1; i <= n; i++)if (isMatch(s[i], c[1]))cnt++;printf("%llu/%llu\n", (ull)cnt / gcd(cnt, n), (ull)n / gcd(cnt, n));}else if (m == n) {int tag[100] = { 0 }, judge = 0;for (int i = 1; i <= cnt1; i++) {//优先匹配数字+字母int x = g[i]; judge = 1;for (int j = 1; j <= n; j++) {if (tag[j])continue;if (isMatch(s[j], c[x])) {//匹配成功judge = 0; tag[j] = 1; break;}}//不能匹配if (judge)break;}if (!judge) {for (int i = 1; i <= cnt2; i++) {//匹配问号+字母int x = gg[i]; judge = 1;for (int j = 1; j <= n; j++) {if (tag[j])continue;//没被选入或已经匹配if (isMatch(s[j], c[x])) {//匹配成功judge = 0; tag[j] = 1; break;}}//不能匹配if (judge)break;}}if (!judge)printf("1/1\n");else printf("0/1\n");}else {ull have[30][15] = { 0 }, Cas = 0;for (int i = 1; i <= n; i++) {have[s[i][1] - 'A' + 1][s[i][0] - '0' + 1]++;}Cas = 3;for (int i = 1; i <= 10; i++) {if (have['C' - 'A' + 1][i] != 1) { Cas = 0; break; }if (have['S' - 'A' + 1][i] != 1) { Cas = 0; break; }if (have['P' - 'A' + 1][i] != 1) { Cas = 0; break; }}Cas = 4;for (int i = 1; i <= 10; i++) {if (have['C' - 'A' + 1][i] != 2) { Cas = 0; break; }if (have['S' - 'A' + 1][i] != 1) { Cas = 0; break; }if (have['P' - 'A' + 1][i] != 1) { Cas = 0; break; }}if (n == 30 && Cas == 3) {//tot表示C\S\P,明确了数字部分的纸牌分别出现的次数//sum表示C\S\P分别出现的次数(包括问号+字母和数字+字母) //num表示确定某个明确了数字和字母的牌数,必须小于等于1int num[50] = { 0 }, tot[3] = { 0 }, sum[3] = { 0 }, judge = 0;for (int i = 1; i <= m; i++) {int x = -1;if (c[i][1] == 'C') {if (c[i][0] != '?')x = c[i][0] - '0', tot[0]++;sum[0]++;}if (c[i][1] == 'S') {if (c[i][0] != '?')x = c[i][0] - '0' + 10, tot[1]++;sum[1]++;}if (c[i][1] == 'P') {if (c[i][0] != '?')x = c[i][0] - '0' + 20, tot[2]++;sum[2]++;}if (x != -1)num[x]++;if (num[x] > 1) {//必定不匹配judge = 1; break;}}if (judge) {printf("0/1\n"); continue;}int fixed = tot[0] + tot[1] + tot[2];//必须要取的fixed个int lef = m - fixed;//剩余要抽的牌数ull res = Cmn(n - fixed, m - fixed);//对剩下m-fixed个全部取出来的情况数for (int i = 0; i < 3; i++) {//考虑单个字母,即C\S\P其中一个,要减去这个字母不符合条件的所有情况//考虑到每种情况实际上还能划分为1、只有当前字母不符合条件,2、另有一个字母也不符合条件//根据对称性,两个字母同时不符合条件的情况会被多减去一次for (int j = 0; j < sum[i] - tot[i]; j++) {res -= Cmn(10 - tot[i], j) * Cmn(n - fixed - 10 + tot[i], lef - j);}}//在上面减去的情况中,两个字母同时不符合的情况要加回来for (int i = 0; i < 2; i++)for (int j = i + 1; j < 3; j++)for (int x = 0; x < sum[i] - tot[i]; x++)for (int y = 0; y < sum[j] - tot[j]; y++) {res += Cmn(10 - tot[i], x) * Cmn(10 - tot[j], y) * Cmn(n - fixed - 20 + tot[i] + tot[j], lef - x - y);}//显然,不会出现三个字母都不符合的情况ull all = Cmn(n, m);printf("%llu/%llu\n", res / gcd(res, all), all / gcd(res, all));}else if (n == 40 && Cas == 4) {int num[50] = { 0 }, tot[3] = { 0 }, sum[3] = { 0 }, judge = 0;for (int i = 1; i <= m; i++) {int x = -1;if (c[i][1] == 'C') {if (c[i][0] != '?')x = c[i][0] - '0', tot[0]++;sum[0]++;}if (c[i][1] == 'S') {if (c[i][0] != '?')x = c[i][0] - '0' + 10, tot[1]++;sum[1]++;}if (c[i][1] == 'P') {if (c[i][0] != '?')x = c[i][0] - '0' + 20, tot[2]++;sum[2]++;}if (x != -1)num[x]++;if (x >= 10 && num[x] > 1) {//必定不匹配judge = 1; break;}if (x >= 0 && x < 10 && num[x]>2) {judge = 1; break;}}if (judge) {printf("0/1\n"); continue;}int cnt = 0;int fixed = tot[0] + tot[1] + tot[2];int lef = m - fixed;//剩余要抽的牌数for (int i = 0; i < 10; i++)if (num[i] == 1) {cnt++;}//将?C出现过的数字设置为不能再选ull res = 0;for (int k = 0; k <= cnt; k++) {//每次增加某个只出现一次的?C,使得两个相同的?C都被选中,即相当于被固定选择的牌多了一张if (m < fixed + k)continue;//注意,可能牌不够抽ull tmp = Cmn(n - cnt - fixed, m - fixed - k);for (int i = 0; i < 2; i++)for (int j = i + 1; j < 3; j++)//对于字母C,被固定的牌有tot[i]+k张for (int x = 0; x < (i == 0 ? sum[i] - tot[i] - k : sum[i] - tot[i]); x++) {for (int y = 0; y < sum[j] - tot[j]; y++) {if (lef - k - x - y < 0)continue;//避免越界的情况tmp += Cmn((i == 0 ? 20 - cnt : 10) - tot[i], x) * Cmn(10 - tot[j], y) * Cmn(n - fixed - (i == 0 ? 30 : 20 + cnt) + tot[i] + tot[j], lef - k - x - y);}}for (int i = 0; i < 3; i++) {for (int j = 0; j < (i == 0 ? sum[i] - tot[i] - k : sum[i] - tot[i]); j++) {if (lef - k - j < 0)continue;//避免越界的情况tmp -= Cmn((i == 0 ? 20 - cnt : 10) - tot[i], j) * Cmn(n - fixed - (i == 0 ? 20 : 10 + cnt) + tot[i], lef - k - j);}}for (int i = 1; i <= cnt - k; i++) tmp <<= 1;res += Cmn(cnt, k) * tmp;}ull all = Cmn(n, m);printf("%llu/%llu\n", res / gcd(res, all), all / gcd(res, all));}else {//std部分,注意cof和dp一定要设置好类型,保证不越界,上面的have数组也属于std部分ull havex[30] = { 0 }, needx[30] = { 0 }, need[30][15] = { 0 }, cof[30][65] = { 0 };ull shave[30][20] = { 0 }, sshave[30] = { 0 }, sdp[20][65] = { 0 }, dp[30][65] = { 0 };for (int i = 1; i <= n; i++) {havex[s[i][1] - 'A' + 1]++;}for (int i = 1; i <= m; i++) {if (c[i][1] != '?')needx[c[i][1] - 'A' + 1]++;if (c[i][0] != '?')need[c[i][1] - 'A' + 1][c[i][0] - '0' + 1]++;}for (int a = 1; a <= 26; a++)for (int i = 1; i <= 10; i++) {shave[a][i] = have[a][i] + shave[a][i - 1];//每个字母,数字从0-9的前缀和}for (int a = 1; a <= 26; a++)sshave[a] = shave[a][10] + sshave[a - 1];//字母A-Z的前缀和//先算数字+字母的部分for (int a = 1; a <= 26; a++) {//这里的合法情况只考虑明确了数字和字母的牌sdp[0][0] = 1;for (int i = 1; i <= 10; i++) {//sdp[i][k]表示选到数字i为止,一共选取k张牌的所有合法情况for (int j = need[a][i]; j <= have[a][i]; j++) {for (int k = j; k <= shave[a][i]; k++) {sdp[i][k] += sdp[i - 1][k - j] * Cmn(have[a][i], j);}}}for (int k = 0; k < 65; k++)cof[a][k] = sdp[10][k];memset(sdp, 0, sizeof(sdp));}dp[0][0] = 1;//这里的合法情况比上面多保证了?+字母的情况for (int a = 1; a <= 26; a++) {//dp[a][k]表示选到字母a为止,一共选了k张牌的所有合法情况for (int j = needx[a]; j <= havex[a]; j++) {for (int k = j; k <= sshave[a]; k++) {dp[a][k] += dp[a - 1][k - j] * cof[a][j];}}}ull all = Cmn(n, m), _g = gcd(dp[26][m], all);printf("%llu/%llu\n", dp[26][m] / _g, all / _g);}}}return 0;
}

这篇关于CCSP201902纸牌计数——解题报告的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/898979

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

Python:豆瓣电影商业数据分析-爬取全数据【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】

**爬取豆瓣电影信息,分析近年电影行业的发展情况** 本文是完整的数据分析展现,代码有完整版,包含豆瓣电影爬取的具体方式【附带爬虫豆瓣,数据处理过程,数据分析,可视化,以及完整PPT报告】   最近MBA在学习《商业数据分析》,大实训作业给了数据要进行数据分析,所以先拿豆瓣电影练练手,网络上爬取豆瓣电影TOP250较多,但对于豆瓣电影全数据的爬取教程很少,所以我自己做一版。 目

开题报告中的研究方法设计:AI能帮你做什么?

AIPaperGPT,论文写作神器~ https://www.aipapergpt.com/ 大家都准备开题报告了吗?研究方法部分是不是已经让你头疼到抓狂? 别急,这可是大多数人都会遇到的难题!尤其是研究方法设计这一块,选定性还是定量,怎么搞才能符合老师的要求? 每次到这儿,头脑一片空白。 好消息是,现在AI工具火得一塌糊涂,比如ChatGPT,居然能帮你在研究方法这块儿上出点主意。是不

【干货分享】基于SSM的体育场管理系统的开题报告(附源码下载地址)

中秋送好礼 中秋佳节将至,祝福大家中秋快乐,阖家幸福。本期免费分享毕业设计作品:《基于SSM的体育场管理系统》。 基于SSM的体育场管理系统的开题报告 一、课题背景与意义 随着全民健身理念的深入人心,体育场已成为广大师生和社区居民进行体育锻炼的重要场所。然而,传统的体育场管理方式存在诸多问题,如资源分配不均、预约流程繁琐、数据统计不准确等,严重影响了体育场的使用效率和用户体验。

YOLOv8/v10+DeepSORT多目标车辆跟踪(车辆检测/跟踪/车辆计数/测速/禁停区域/绘制进出线/绘制禁停区域/车道车辆统计)

01:YOLOv8 + DeepSort 车辆跟踪 该项目利用YOLOv8作为目标检测模型,DeepSort用于多目标跟踪。YOLOv8负责从视频帧中检测出车辆的位置,而DeepSort则负责关联这些检测结果,从而实现车辆的持续跟踪。这种组合使得系统能够在视频流中准确地识别并跟随特定车辆。 02:YOLOv8 + DeepSort 车辆跟踪 + 任意绘制进出线 在此基础上增加了用户

nyoj 1038 纸牌游戏

poj 的一道改编题,说是翻译题更恰当,因为只是小幅度改动。 一道模拟题,代码掌控能力比较好,思维逻辑清晰的话就能AC。 代码如下: #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct node{char c[5];int rk;char da[5];int nu

纸牌函数生成器

此模板用来生成纸牌类的测试数据,本人手打,不合理或缀余的地方希望大神指出。 T=10000(测试数据组数), t (两摞相等的牌,每摞牌的数量); 每张牌用A,2~9,T,J,Q,K;表示牌面大小; 用S,H,C,D;表示花色。 共52张牌。 #include<stdio.h>#include<time.h>#include<stdlib.h>#include<string.

归并排序/计数排序

1:归并排序 1.1:代码 void _MergeSort(int* arr, int left, int right, int* tmp){if (left >= right){return;}int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+1, righ

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比