社区讨论
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 条回复,欢迎继续交流。
正在加载回复...