社区讨论

who can tell me how to use_int128

P1037[NOIP 2002 普及组] 产生数参与者 9已保存回复 25

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
21 条
当前快照
1 份
快照标识符
@mlhz5506
此快照首次捕获于
2026/02/11 19:56
上周
此快照最后确认于
2026/02/13 19:25
6 天前
查看原帖
who can tell me how to use_int128
CPP
#include <bits/stdc++.h>
using namespace std;
struct Cnt
{
	int change;
	int cnt;
};
int Search(int x, multimap<int, int> &rules)
{
	int xcnt=0;
	vector<bool> vis(10, false);		//0 1 2 3 ……9 false
	vis[x]=true;
	queue<int> q;
	q.push(x);
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		multimap<int, int>::iterator it=rules.find(x);
		for(; it!=rules.end() && it->first==x; it++)
		{
			int y=it->second;
			if(vis[y]==false && y!=0)
			{
				q.push(y);
				xcnt++;   
				vis[y]=true;
			}	
		}
	}
	return xcnt;
}
void Output(map<int, Cnt> &bin)
{
	//输出检验每个数字的变化个数 和 出现次数
	cout<<"bin contains:"<<endl;
	for(map<int, Cnt>::iterator it=bin.begin(); it!=bin.end(); it++)
		cout<<it->first<<" "<<it->second.change<<" "<<it->second.cnt<<endl;		
}

int main()
{
	string s; cin>>s;  int k; cin>>k;
	map<int, Cnt> bin;  //存每种数字能变成多少个不同的数字 桶
	for(int i=0; i<10; i++)
		bin.insert(pair<int,Cnt>(i, {0, 0}));
	multimap<int, int> rules; //记录一个数变成另一个数的规则
	for(int i=0; i<k; i++)	
	{
		int x, y; cin>>x>>y;
		rules.insert(pair<int,int>(x, y));
	}
	//bfs搜索每个数字可以变成什么   2 -》1-》0-》9-》3-》8
	int x=s[0]-'0'; ///首位数字 
	//------------------------------------------
	//数cnt
	int l=s.length(); 
	for(int i=1; i<l; i++)
	{
		int xx=s[i]-'0';
		map<int, Cnt>::iterator it=bin.find(xx);
		it->second.cnt++;		
	}
	long long xcnt=Search(x, rules); ///首位数字去除0后的变换次数
	//bfs搜索每个数字  i  //2-》3-》4 -》3
	for(int i=0; i<10; i++)
	{
		vector<bool> vis(10, false);		//0 1 2 3 ……9 false
		vis[i]=true;
		queue<int> q;
		q.push(i);
		while(!q.empty())
		{
			int x=q.front(); q.pop();
			multimap<int, int>::iterator it=rules.find(x);
			for(; it!=rules.end() && it->first==x; it++)
			{
				int y=it->second;
				if(vis[y]==false)
				{
					q.push(y);
					bin[i].change++;   //信息桶
					vis[y]=true;
				}	
			}
		}
	}
	//Output(bin);
	//------------------------------------------
	//计算
	int128 summethod=1;
	// x xcnt+1
	//(出现的数字的变换种数+1)^此数字的次数
	summethod*=xcnt+1;
	for(map<int, Cnt>::iterator it=bin.begin(); it!=bin.end(); it++)
	{
		if(it->second.cnt==0)
			continue;
		summethod*=pow(it->second.change+1, it->second.cnt);
	}
	cout<<summethod;			
	return 0;
}

回复

25 条回复,欢迎继续交流。

正在加载回复...