CCF CSP 202109-4 collect cards

Define the storage structure

Structure ： Card draw status , The layer number （ Extraction times ）, Probability product

Define a queue , Simulate the hierarchical traversal process of the tree

Input

Total number of cards read n And coins k Number of cards changed

Read in the card to get the probability

Use queues to simulate n Hierarchy traversal of fork tree

Every outgoing node

• Judge whether the card drawing is completed
• If it's done , Calculate the probability product , And sum it up
• If not done , Keep drawing , Generate child nodes , Calculate the probability product , And put the child nodes in the queue

The queue is empty （ End of traversal ）, Output results

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
double p[16];// Number of cards n Less than or equal to 16, The corresponding probability number is less than or equal to 16 
int n,k;
struct node{
	int state;// Card draw status [ It's essentially a vector , Someone is 1, Indicates the card drawn to this position ] 
	int level;// The layer number （ Extraction times ） 
	double p;// Probability product  
}; 
int main(){
	scanf("%d%d",&n,&k);// Total number of cards read n And coins k Number of cards changed 
	for(int i=0;i<n;i++) scanf("%lf",p+i);// For the first i The probability of a card is p[i-1]
	double ans = 0;// Record the expected number of cards drawn 
	
	node nodecur,nodechild;
	queue<node> q;// Define a queue , Simulate the hierarchical traversal process of the tree 
	
	// Initial root node  
	nodecur.state = 0;
	nodecur.level = 0;
	nodecur.p = 1;
	// Start n Hierarchy traversal of fork tree  
	q.push(nodecur); 
	while(!q.empty()){
		nodecur = q.front();
		q.pop();
		int cnt = 0;// Record the number of different types of cards drawn 
		for(int i=0;i<n;i++)
			if((nodecur.state>>i)&1) cnt++;
		//nodecur.level-cnt Is the number of coins  
		if(cnt+(nodecur.level-cnt)/k>=n){
			ans = ans += nodecur.p * nodecur.level; // Cumulative probability product * The layer number  
			continue;// here , There is no need to generate child nodes , Just skip , The reason is that the conditions have been met , There is no need to draw  
		}
		for(int i=0;i<n;i++){// Generate child nodes  
			nodechild.p = nodecur.p*p[i];// Calculate the probability product of child nodes  
			nodechild.state = nodecur.state|(1<<(n-i-1));
			nodechild.level = nodecur.level + 1;
			q.push(nodechild);// Queue child nodes  
		}
	}
	printf("%.10lf\n",ans);// Title Example 2 It is reserved to the... After the decimal point 10 position  
	return 0;
}