【dfs/bfs+set+快速幂】swjtuOJ 2094

【注：交大的看到这篇文章要学会自己写，不要为了比赛而比赛！~】

题目大意

问题一：主人公去度假，问经过a^b天后是星期几（简单题）问题二：一个天平,n个重物,每个物体的重量wi已知，问能称出的所有重量有多少种?

问题二要注意到天平两侧都可以放重物，每一个重物的权值都可以赋值为w,0,-w，相当于三分，我们知道二分可以用二进制位运算进行枚举，例如：枚举所有子集

int j,k,top=0;int t = 1 << n;for(int i = 0;i < t; ++ i){//位运算枚举子集,O(N*2^N)j = i;k = 0;while(j){if(j&1) printf（”%d “,w[k]）;j >>= 1;++ k;}printf(“\n”);}

这道三分的问题直接搜索了，母函数解决不了(w太大存不下), 搜索dfs和bfs都可以，很裸的搜索了，去重用set神器！O(∩_∩)O~

【注意】求的和是负值也是有效的，abs后扔进set里面~~~

–

说一下思路问题一：整数快速幂，题目1<=a,b<=10有误，a,b范围很大的问题二：和之前说的思路一致，直接搜索，我写了两版，供读者参考，求出来的和扔进set容器里面自动去重了，最后输出set的大小和最后一个数值（自动排序后最后一个数肯定为所有物体重量w之和）

set和map的比较：map最大优点是映射，对于存储数字序列，也有自动去重、自动排序的功能，还可以映射出该数字出现的次数（在值域之中it->second）；set是不可重复的多元集合，最大特点在于去重，而且默认排序。总之，去重神器set Orz~

参考代码一：dfs/*====================================*\|* set去重+三种状态枚举子集：dfs + bfs*||* 两种状态可以用二进制位运算解决 *|\*====================================*/;const int _max = 4e6 + 10;const int mod = 7;int a,b,n,w[20];struct node{ int num; ll sum;};set<ll>s;void dfs(int deep,ll tot){//深度优先搜索 if(deep==n){if(tot) s.insert(abs(tot));return; } dfs(deep+1,tot); dfs(deep+1,tot-w[deep]); dfs(deep+1,tot+w[deep]);}ll quick_mod(ll a,ll b){//矩阵快速幂 ll ans = 1; while(b){if(b&1) ans = (ans*a)% mod;b >>= 1;a = (a * a) % mod; } return ans;}int main(){ #ifndef ONLINE_JUDGE freopen(“input.txt”,”r”,stdin); #endif // ONLINE_JUDGE while(scanf(“%d%d”,&a,&b)==2){ll d = quick_mod((ll)a,(ll)b);if(d%7==0||d%7==6) printf(“800 “);else printf(“1000 “);scanf(“%d”,&n);for(int i = 0; i < n; ++ i){scanf(“%d”,w+i);}s.clear();dfs(0,0);set<ll>::reverse_iterator it = s.rbegin();//反向迭代器printf(“%d %lld\n”,s.size(),*it); } return 0;}参考代码二：bfs/*====================================*\|* set去重+三种状态枚举子集：dfs + bfs*||* 两种状态可以用二进制位运算解决 *|\*====================================*/;const int _max = 4e6 + 10;const int mod = 7;int a,b,n,w[20];struct node{ int num; ll sum;};set<ll>s;queue<node>Q;void bfs(){ //广度优先搜索 node q; q.num = 0; q.sum = 0; Q.push(q); while(!Q.empty()){q = Q.front();Q.pop();if(q.num==n){if(q.sum>0) s.insert(q.sum);continue; //return;最短路是return}node p;p.num = q.num + 1;for(int i = 0; i < 3; ++ i){if(i == 0) {p.sum = q.sum ;}else if(i == 1){p.sum = q.sum + w[q.num];}else p.sum = q.sum – w[q.num];Q.push(p);} }}ll quick_mod(ll a,ll b){//矩阵快速幂 ll ans = 1; while(b){if(b&1) ans = (ans*a)% mod;b >>= 1;a = (a * a) % mod; } return ans;}int main(){ #ifndef ONLINE_JUDGE freopen(“input.txt”,”r”,stdin); #endif // ONLINE_JUDGE while(scanf(“%d%d”,&a,&b)==2){ll d = quick_mod((ll)a,(ll)b);if(d%7==0||d%7==6) printf(“800 “);else printf(“1000 “);scanf(“%d”,&n);for(int i = 0; i < n; ++ i){scanf(“%d”,w+i);}s.clear();while(!Q.empty()) Q.pop();bfs();set<ll>::reverse_iterator it = s.rbegin();//反向迭代器printf(“%d %lld\n”,s.size(),*it); } return 0;}

，当你能梦的时候就不要放弃梦

相关文章：

你感兴趣的文章：

标签云：