注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 564  

2013-03-02 17:18:19|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
挺水的题目。。。
不过850分的是一道神题——只可惜是道陈题,也就是说,随便到网上搜搜就可以搜到了。
不过我完全没法想到的,因为思路完全被局限于dp了,而没有去想其它的——为何我做TC 1000pt的题目总感觉是新思路呢?虽然题目不会做是好事——但是啥都不会也不是好事吧。

250pt的题目依旧很简单,证明不会,yy即可。
500pt的题目傻叉dp,所以略掉。。。
1000pt的题目是经典题目(默认第三题1000pt):
求给定的数列b的方案数,要求bi<=ai,且异或和为k的方案数?
方法很神奇的,当然有个更加优秀的dp思路——SOLUTION
不过题解的方法似乎更好想与更好些:
首先b的顺序是无所谓的,所以我们可以将它们排个序。
最大的那个数一定有个最大的位,这个位是很特殊的,如果n的最大位数大于它,那么答案肯定无解的。
现在分两种情况:
如果最大的b对应的那个数最大位是0,那么只要前N-1项的数异或起来之后就是n的最大位的值,那么一定可以通过改变bN对应的数使得异或为n,因为bN前N-1项是任意地。
否则,确定了bN对应的那个数最大位为1,我们将n最大位异或1,bN最大位置为0,此时的答案一定与bN最大位为1的答案存在一一对应关系。求解该问题即可。注意这样递归下去,每个数必有一位1变成0,那么总共也就n*32次,每次长度为n的dp。所以时间复杂度n^2*32,毫无压力
代码很好写很好调。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int Mod=1000000007;
const int NUM=100;
const int MAX=31;

int f[NUM][NUM];

struct DefectiveAddition
{
int count(vector <int> cards, int n)
{
int i,j,maxt=-1;
int N=cards.size();
sort(cards.begin(),cards.end());
REP2(i,0,MAX)
if((cards[N-1]>>i)&1)
maxt=i;
if(maxt==-1)
return (n==0);
if(n>=(1<<(maxt+1)))
return 0;
f[0][0]=1;
REP2(i,0,N-1)
REP2(j,0,2)
{
f[i+1][j]=0;
f[i+1][j]=(f[i+1][j]+(LL)f[i][j^0] * min(cards[i]+1,1<<maxt ) )%Mod;
f[i+1][j]=(f[i+1][j]+(LL)f[i][j^1] * max(cards[i]-(1<<maxt)+1 ,0 ) )%Mod;
}
LL ans=0;
ans+=f[N-1][(n>>maxt)&1];
cards[N-1]-=(1<<maxt);
n^=(1<<maxt);
ans=(ans+count(cards,n))%Mod;
return ans;
}
};



  评论这张
 
阅读(242)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017